5

Good afternoon, I am wondering what the time complexity of std::multimap::equal_range is? Is it Big-O(n) or BIG-0(log n). I remember reading that the time complexity of std::multimap::erase "is logarithmic plus linear time for the length of the sequence being removed." <http://frank.mtsu.edu/~csjudy/STL/Multimap.html>

ypnos
  • 50,202
  • 14
  • 95
  • 141
Frank
  • 1,406
  • 2
  • 16
  • 42

3 Answers3

4

C++03 standard, Table 69 ("Associative container requirements") in 23.1.2 says that equal_range has logarithmic complexity.

Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
  • Steve Jessop, Thank you for answer. I just accepted your answer, We are using a multimap container which has char * pointer as the key, We found that equal_range correctly as long as the char * pointers are not bad pointers(Windows term). In Linux, they refer to bad pointer as "Address out of range". Is our observation about equal_range's requirement for good char * pointers correct. We chose not not to std::string as a multimap key because the strcmp was so expensive compared to the good pointer comparer functor bool(char *left, char *right). Thank you. – Frank May 13 '11 at 01:37
  • As far as the standard is concerned yes, keys in a map have to remain valid values, and any use of a pointer to freed data, or a bad address, even just comparing it as a pointer value without dereferencing it, is technically invalid. In practice I'm a bit surprised that it actually failed - are you sure your code never dereferenced the pointers? – Steve Jessop May 13 '11 at 02:02
  • Steve Jessop, Thank you for your reply, If our code had actually deferenced a bad pointer, would it be correct to say that an access violation(Windows) or a bus error/segmentation fault would have happened on(Linux)? Here is a code excerpt: 1.UnmapViewOfFile(PrevMapPtr); 2. TmpPrevMapPtr = PrevMapPtr; 3. typedef std::multimap::const_iterator I; std::pair b = mmultimap.equal_range(TmpPrevMapPtr); 4. for (I i=b.first; i != b.second; ++i){ ranges_type.erase(i->second); } Thank you for your help. – Frank May 13 '11 at 06:29
  • Steve Jessop, Thank you for your reply, If our code had actually deferenced a bad pointer, would it be correct to say that an access violation(Windows) or a bus error/segmentation fault would have happened on(Linux)? Here is a code excerpt: 1.UnmapViewOfFile(PrevMapPtr); 2. TmpPrevMapPtr = PrevMapPtr; 3. typedef std::multimap::const_iterator I; 4. std::pair b = mmultimap.equal_range(TmpPrevMapPtr); 5. for (I i=b.first; i != b.second; ++i){ ranges_type.erase(i->second); } 6. erasecount = mmultimap.erase(TmpPrevMapPtr); Thank you for your help. – Frank May 13 '11 at 06:36
  • Steve Jessop, I apologize for posting 2 versions of my comment. If you have the time, please look at the comment just preceding this one. Thank you for your help. – Frank May 13 '11 at 06:56
  • @Frank: that code doesn't look to me as if it dereferences the pointers used as keys, but I don't see where the map is defined. Maybe you gave it a comparator that does dereference the pointers. And yes, access violation/segv errors indicate dereferencing a bad address of some kind or another. – Steve Jessop May 13 '11 at 08:56
  • @Steve Jessop, Thank you for your reply. Yesterday, in another thread on this same topic, you stated" unfortunately you would need to remove that key[char * pointer] from the multimap before you unmap your file. Or you could make a copy of the string from the mapped file, to insert into the map, but if you're going to do that you might as well use std::string. So I followed your recommendation and so far the code excerpt seems to be functioning.The multimap is defined as std::multimap where Range is a class. Thank you. – Frank May 13 '11 at 12:50
  • @Steve Jessop, Here is the class Range. Thank you. class Range { public: Range(int low, int high, char* ptr = 0,char* mapptr = 0, int stamp = 0){ // [low,high] mLow = low; mHigh = high; mPtr = ptr; mMapPtr = mapptr; mStamp = stamp } bool operator<(const Range& rhs) const{ return mHigh < rhs.mHigh; } ) const { return mCaseNumber; } private: int mLow; int mHigh; char* mPtr; char* mMapPtr; int mStamp; }; // class Range – Frank May 13 '11 at 12:53
2

equal_range is an O(log n) operation returning the pair of lower_bound and upper_bound.

This means it will return an iterator range starting with the first key that is greater-than or equal-to the search key and ending with the first key that is greater than the search key.

Cory Nelson
  • 29,236
  • 5
  • 72
  • 110
  • @Cory Nelson, Thank you for answer. I just accepted your answer. Will std::multimap::equal_range work with search keys that are char* pointers? Do I have to find a good function for hashing pointer values? Thank you. – Frank May 12 '11 at 18:46
  • `equal_range` will work with any type. It uses the comparer you give in the `multimap` constructor -- if the default one (`less`) for `char*` doesn't do what you want, you'll need to define your own. Either way, it doesn't need to do any hashing. – Cory Nelson May 12 '11 at 18:56
  • @Cory Nelson, I stepped through the multimap::equal_range function using a debugger and I found the default one less for char* compares pointer addresses , Left_ < Right_. Is there a better comparer for char * pointer? Is so , what might it look like? If I understand your comment, I don't have to hash the char* pointer keys? Thank you for your help. – Frank May 12 '11 at 19:01
  • The comparer is a function type with signature `bool(T a, T b)`, returning `true` if `a` comes before `b`. It can be a function pointer or a functor. – Cory Nelson May 12 '11 at 19:07
  • @Frank, I provided an appropriate compare function in answer to [your other question](http://stackoverflow.com/questions/5982760/is-it-possible-for-stdmultimapequal-range-to-return-incorrect-results/5983011#5983011). – Robᵩ May 12 '11 at 19:11
  • If you want to treat your char* as strings and order them that way (instead of memory addresses) you can supply a functor that uses strcmp (or use strcmp directly?). Or you can just use std::string instead of char*, whose std::less works the right way. – Christian Rau May 12 '11 at 19:14
  • @Christian Rau, Thank you for your reply. The problem is we that we invalidate the char * pointer key using UnMapViewOfFile(TmpPrevMapPtr). Therefore the string is now a bad ptr so we can't use strcmp? What should we do? Thank you. – Frank May 12 '11 at 19:31
  • @Frank: unfortunately you would need to remove that key from the multimap before you unmap your file. Or you could make a *copy* of the string from the mapped file, to insert into the map, but if you're going to do that you might as well use `std::string`. – Steve Jessop May 13 '11 at 02:08
  • @Steve Jessop, Thank you for your help. If we use std::string, would the functor compare the std::string's? How expensive would the std::string conversion and comparsion be? – Frank May 13 '11 at 06:51
  • @Frank: I don't know the cost, measure it. – Steve Jessop May 13 '11 at 08:57
1

I've never really found a better source for this sort of information than the SGI STL Programmer's Guide. In this case the page you're interested in is the Sorted Associative Container concept page which states under the Complexity Guarantees section:

Lower bound, upper bound, and equal range are logarithmic. [1]

...

[1] This is a much stronger guarantee than the one provided by Associative Container. The guarantees in Associative Container only apply to average complexity; worst case complexity is allowed to be greater. Sorted Associative Container, however, provides an upper limit on worst case complexity.

Oliver Seiler
  • 116
  • 3
  • @olivier Seiler, Thank you for your answer. I just accepted your answer. Thank you. – Frank May 12 '11 at 19:08
  • 1
    Well, the standard is more authoritative, but the SGI docs are more convenient. Occasionally you'll be caught out by something that was changed between there and the C++ standard. – Steve Jessop May 12 '11 at 22:25
  • @Steve Jessop, if you're aware of any specific changes between SGI and the standard, could you answer http://stackoverflow.com/questions/5266386/what-are-the-specific-differences-between-the-original-stl-and-those-parts-of-it ? Thanks. – Mark Ransom May 12 '11 at 22:28
  • @Mark: I've starred it and I'll try to remember, but to be honest since I've installed Foxit, that can search PDFs in less than the geological time taken by Adobe Reader, I don't use the SGI docs very often any more :-) – Steve Jessop May 12 '11 at 22:30