CODEWITHSUNDEEP
c++performancevectorset
jntrcs
jntrcs

Reputation: 607

Why is inserting into a set<vector<string>> so slow?

For a class project we are making a simple compiler / Relational Database. Mine produces the correct answers, but too slowly on large queries. I ran visual studio's performance analysis and my program is spending 80% of it's time inserting my tuples (rows in a table) into a set. The function is part of computing a cross product, so the result has lots and lots of rows, but I need suggestions on a faster way to insert my tuples into the set.

for (set<vector<string>>::iterator it = tuples.begin(); it != tuples.end(); ++it)
{
    for (set<vector<string>>::iterator it2 = tuples2.begin(); it2 != tuples2.end(); ++it2)
    {
        vector<string> f(*it);
        f.insert(f.end(), it2->begin(), it2->end());
        newTuples.insert(f); //This is the line that takes all the processing time
    }
}

Upvotes: 0

Views: 176

Answers (3)

Surt
Surt

Reputation: 16089

We might as well go C++11 (totally untested code)

for (const auto& it : tuples) {
    for (const auto& it2 : tuples2) {
        auto where = newTuples.emplace(it); // returns where its placed
        auto& vect = where.first; // makes the next more readable
        vect.insert(vect.end(), it2.begin(), it2.end());
    }
}

Note on collisions some strings disappears from the result, is that really what you want? Your using the vector as key, will that ever be a collision? add

if (!where.second) {
  ; // collision
}

to check.

This should remove all double work of moving (if the compiler doesn't optimize it away anyway).

Upvotes: 0

alain
alain

Reputation: 12047

A set might be the wrong container. A set is ordered, and keeps only unique elements. There might be many string comparisons happening when you insert a new vector.

Use a list or a vector instead (if you can).

...and avoid needless copying, as SergeyA already pointed out in his answer

Upvotes: 1

SergeyA
SergeyA

Reputation: 62563

You are copying big vector by value for no reason. You should move: newTuples.insert(std::move(f));

Upvotes: 4

Related Questions