# std::map and std::set size() cost?

This topic is 4143 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

taking a gander around one can find that for std::list, size() can be either O(1) or O(N) depending on the STL implementation (GNU,SGI and others have O(N) becuase otherwise splice would be O(N) ) however hunting for the cost of size() for std::map and std::set I ahve not seen the cost explictily stated (I figued it should be O(1), but without seeing the docs on that, I am not 100% sure it is)... also does anyone know what happens on hash collision for hash_map and hash_set?

##### Share on other sites
VC2005's implementation of std::map and std::set store the size as a member variable, so size() is O(1). However, that's not guaranteed. There's some STL FAQ somewhere on the Internet that says you should check empty containers with empty(), not size()==0 for this exact reason.

##### Share on other sites
The C++ ISO standard (14882:2003) states that all container's size member function should have a constant time complexity, you can't include (multi)hash_map/set because they are not standardized containers however they should follow suite in general.

##### Share on other sites
All the standard says is that all containers', including list's, size "should have constant complexity." I think the should in this case means implementation-defined, but constant complexity recommended. I'm not sure what complexities current libraries offer, but I believe std::set::size and std::map::size is constant complexity.

Quote:
 also does anyone know what happens on hash collision for hash_map and hash_set?

Which hash_map and hash_set? The ones in SGI's STL? The ones in TR1? I know they have different names, but those are the closest you get to standard hash maps in C++ today.

##### Share on other sites
Quote:
 VC2005's implementation of std::map and std::set store the size as a member variable, so size() is O(1). However, that's not guaranteed. There's some STL FAQ somewhere on the Internet that says you should check empty containers with empty(), not size()==0 for this exact reason.

yes I am well away that using empty() is a much better idea {typically implemented as end()==begin()} but there are number of situations where dependign on the size of ther map or set determines what algorithm to use later... or what to do during... a simple issue can be of one wishes to have a ID number associated to each object in a map (for debugging purposes).. the easiest thing to type is m_id=myMap.size(), but now if elements are continuously added to a map, and if std::map::size is implemented as std::difference(begin(),end()), then that will make this O(N^2) {this is what happens in many abuses of std::list) so then to avoid this, one has to track the size yourself.. but that is kind of stupid if the size is already tracked, or if std::map are specified to be O(1) in .size() .... I am beginning to think that it jsut *depends* on which STL one is using, as "should" does not mean "must" .. the ISO C++ standard also says that std::list::size() should be O(1) and std::list::splice should also be O(1) doing both is not possible! gotta choose... in GNU C++ 4.02, the map keeps track of the size (takes digging to track this down in the headers) but if I want to compile with a different enviroment, knowing that is not good enough (especilaly if the project is open sourced)

oh well... usch a hassle.... ISO C++ standard has so many evolutionary scars on it (i.e. the shoulds)

##### Share on other sites
Quote:
 Original post by kRoguestd::list::splice should also be O(1) doing both is not possible!

That is not true.

Quote:
 void splice(iterator position, list& x);Requires: &x != this.Effects: Inserts the contents of x before position and x becomes empty. Invalidates all iterators and references to the list x.Throws: NothingComplexity: Constant time.void splice(iterator position, list& x, iterator i);Effects: Inserts an element pointed to by i from list x before position and removes the element from x.The result is unchanged if position == i or position == ++i. Invalidates only the iteratorsand references to the spliced element.Throws: NothingRequires: i is a valid dereferenceable iterator of x.Complexity: Constant time.void splice(iterator position, list& x, iterator first,iterator last);Effects: Inserts elements in the range [first, last) before position and removes the elementsfrom x.Requires: [first, last) is a valid range in x. The result is undefined if position is an iterator inthe range [first, last). Invalidates only the iterators and references to the spliced elements.Throws: NothingComplexity: Constant time if &x == this; otherwise, linear time.

So it's linear time when
void splice(iterator position, list<T,Allocator>& x, iterator first, iterator last);
is the overload called and &x != this. All other splice overloads are constant time. And, yes, should doesn't mean must in the standard.

##### Share on other sites
yes, yes it is the last one where O(1) is no possible is size is tracked (adn the most likely case)...

1. 1
2. 2
3. 3
4. 4
Rutin
18
5. 5

• 11
• 21
• 12
• 11
• 11
• ### Forum Statistics

• Total Topics
631405
• Total Posts
2999884
×