Jump to content
  • Advertisement
Sign in to follow this  
kRogue

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

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


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


That is not true.

Quote:
void splice(iterator position, list<T,Allocator>& 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: Nothing
Complexity: Constant time.

void splice(iterator position, list<T,Allocator>& 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 iterators
and references to the spliced element.
Throws: Nothing
Requires: i is a valid dereferenceable iterator of x.
Complexity: Constant time.

void splice(iterator position, list<T,Allocator>& x, iterator first,
iterator last);

Effects: Inserts elements in the range [first, last) before position and removes the elements
from x.
Requires: [first, last) is a valid range in x. The result is undefined if position is an iterator in
the range [first, last). Invalidates only the iterators and references to the spliced elements.
Throws: Nothing
Complexity: 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 this post


Link to post
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)...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!