CODEWITHSUNDEEP
c++performancestlcontainersc++03
Fabian
Fabian

Reputation: 4211

Are STL associative containers containing containers a performance issue?

In my scenario, I have a std::map<std::string, std::vector<cCustomClass> >, but the same question applies to std::set. These vectors can become quite large (more than 100000 elements), so I am concerned if vectors are reallocated or copied if I add more elements to the map.

The central question is: Will the map copy the large vectors at some point and if yes, does it have a cost proportional to std::vector::capacity()?

If the answer to both is yes, what are my options? My first solution would be to use a std::map<std::string, std::vector<cCustomClass> * > and (or smart pointers), but I wonder if this is necessary.

I use C++03. If the answer depends on the Standard, I appreciate any remarks about it.

Upvotes: 3

Views: 72

Answers (1)

Useless
Useless

Reputation: 67713

Will the map copy the large vectors at some point

No. map, set and the other associative containers are node-based. Nodes are allocated independently for each entry, connected by pointers, and don't need to be copied or re-allocated when the container grows, shrinks, rebalances itself etc. etc.

Your guarantee of this is the iterator invalidation requirements on various containers. Compare

  • std::map::insert

    No iterators or references are invalidated

    If iterators aren't invalidated, the element they point to must keep its location in memory, so inserting into a map can't requiring copying or moving any existing elements.

  • std::vector::insert

    If the new size() is greater than capacity(), all iterators and references are invalidated. Otherwise, only the iterators and references before the insertion point remain valid. The past-the-end iterator is also invalidated.

    If iterators are invalidated, the element may have moved, copying or moving the value. Specifically for a vector, elements after an insertion must be moved/copied to make space for the new element.

    If the vector needed reallocation to grow, all elements must be moved/copied to the new allocated region.

It's worth noting, although it doesn't really affect you with map, that modern compilers will move elements where possible. Your large vector would be moved, for example, which is much cheaper than copying it - if you can update to C++11 or later, that is.

Upvotes: 3

Related Questions