Optimising Algorithm

I need to optimise this function, but im stumped on ideas to improve on its speed...

bool generateShortestpathLink (const string& start, const string& finish, const book& db) {
    vector <lib> bks;
    vector <string> authors;
    set <lib> storeBKS;
    set <string> storeAuthor;
    queue <pathLink> q;

    pathLink p(start);
    q.push(p);

    while (!q.empty()) {

        p = q.front();

        if (p.getLength() > 6) return false;
        db.getTitles(p.getLastPlayer(), bks);

        for (int x = 0; x < (int) bks.size(); x++) {

            const film& newBook = bks[x];
            if (storeBKS.find(newBook) != storeBKS.end()) continue; 
            db.getAuthors(newBook, authors);
 开发者_开发技巧           storeBKS.insert(newBook);

            for (int i = 0; i < (int) authors.size(); i++) {

                if (storeAuthor.find(authors[i]) != storeAuthor.end()) continue;  
                pathLink newpathLink(p);
                newpathLink.addConnection(newBook, authors[i]); 
                if (authors[i] == finish) return true;
                storeAuthor.insert(authors[i]);
                q.push(newpathLink);
            }
        }
        q.pop();
    }

    return false;
}

it's suppose to be an algo for BFS, where it creates the path used to connect different titles of books with authors. getTitles() and getAuthors are both binary search functions that cannot be changed. Could anyone help me with this?

The first thing I'm seeing is that you're not pre-allocating any memory. This is the first thing to do when optimizing an algorithm where you can't change the algorithm. You should find out how much memory those structures will need and immediately allocate it all at once to prevent them from having to reallocate repeatedly.

Also, consider using a sorted vector instead of a set. This will improve the look-up times quite considerably- just don't insert too often or you'll hurt.

You have specifically ruled out the biggest optimizations by saying that getTitles() can't be touched. You have a loop inside a loop inside a loop. The middle loop appears to be the culprit. As is, getTitles() mandates a linear search algorithm. You can't optimize something if the source of the problem is elsewhere.