Hello!
What is the easiest way (shortest code, fastest) to find largest element smaller than x in std::set/std::map (handling all cases - especially when set/map is empty) ?
Hello!
What is the easiest way (shortest code, fastest) to find largest element smaller than x in std::set/std::map (handling all cases - especially when set/map is empty) ?
I wonder why you think a set and a map are the same here. You should look at the member functions of set (for instance here). If you have a map then you have to decide whether you mean the key, or the value; if the key, then the same function works for both.
I personally prefer std::upper_bound...
upper_bound - C++ Reference
upper_bound is one of the member functions listed, yes. (I would think you would want to make sure to use the member function version in this case as opposed to the algorithm version, since the member function will return a bidirectional iterator which is extremely extremely important in this scenario.)
EVOEx, tabstop: thanks for your replays.
EVOEx: you pointed upper_bound, but notice it returns the smallest element that is greater than x, that's a little different of what I want (I want to find _largest_ element _smaller_ than x). I know I can always reverse the order and then use upper_bound, but I want to know how to do it without reversing the order of structure.
tabstop: I wrote set/map because they are both written on red-black trees and hence I guess have the same abilities, to be precise I want to use map.
So, any ideas ? I've tried using:
but someone told me this is not correct and may not work properly since lower_bound may return map.end() and performing --(..) on map.end() is undefinied.Code:--map.lower_bound(x)
You could just check the return value against end before decrementing.
So as mentioned you want to be careful about finding the entry with the largest key smaller than x vs. finding the entry with the largest entry smaller than x. lower_bound looks at keys; if that's what you want, then there you go. (I forget whether .end is decrementable when used as a bidirectional iterator; if not, then presumably you want the answer to be the last element, which is also known as rbegin.)
Ok let's say I want to write a function to return an iterator to the largest element smaller than x (in terms of key). I managed to write sth like that
and it's working, but there'a got to be better way to do it, since it seems this could be pretty slow (even though I know it has complexity O(log n)). Any ideas ?Code:#include <cstdio> #include <map> #include <algorithm> using namespace std; typedef map<int,int>::iterator iter; iter find(map<int,int> &s, int x) { iter it=s.lower_bound(x); if(it==s.end()) return s.find((s.rbegin())->first); else return it==s.begin() ? s.end() : --it; } int main() { map<int,int> t; int x=0; for(int i=4;i<=8;i+=2) t[i]=++x; for(int i=2;i<=9;++i) { iter it=find(t,i); printf("find(%d):", i); if(it==t.end()) printf("NONE\n"); else printf("(%d,%d)\n",it->first,it->second); } return 0; }
1. If the keys in your map are 1, 4, and 7, and you ask for the largest key less than 15, you will print "NONE"; I don't think that's right.
2. If you can figure out a way to search through a sorted list in less than O(lg n) time without using hashes, I'm pretty sure someone will hand you a million dollars.
I think you also should check whether the container is empty, and it == end() is not a special case, since you can decrement end iterator alright. Hence you can just remove the line with an extra call to find.
It will take care of the performance issue (searching twice is indeed suboptimal), it should correct the code with respect to the bug tabstop pointed out, and it should also take care of empty maps (where lower_bound would return end() == begin())!
I might be wrong.
Quoted more than 1000 times (I hope).Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
I don't understand. This code output (7,1), as expected:
You're right. But I was talking about the constant factor (searching twice).Code:#include <cstdio> #include <map> #include <algorithm> using namespace std; typedef map<int,int>::iterator iter; iter find(map<int,int> &s, int x) { iter it=s.lower_bound(x); if(it==s.end()) return s.find((s.rbegin())->first); else return it==s.begin() ? s.end() : --it; } int main() { map<int,int> t; t[1]=1; t[4]=1; t[7]=1; iter it=find(t,15); if(it==t.end()) printf("NONE\n"); else printf("(%d,%d)\n",it->first,it->second); return 0; }
Are you sure decrementing .end() is correct ? What about decrementing .begin(), or incrementing .end() ? --.begin() becomes .end() ?
No, it's not. Where did you get that idea? It's only undefined if the map is empty.performing --(..) on map.end() is undefinied.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
The standard says this about operator-- of bidirectional iterators.
Since in an non-empty container there exists an iterator which when incremented results in the iterator reaching end(), it means it's OK to decrement the end() iterator. Besides, reverse iterators normally seem to use a generic std::reverse_iterator, which under the hood decrement the end() anyway! Reverse iterator returned by rbegin() holds a normal iterator returned by end(), and when dereferenced returns the value of the previous item.Code:+----------------------------------------------------------------------------+ |expression return type operational assertion/note | | semantics pre/post-condition | +----------------------------------------------------------------------------+ |--r X& pre: there exists s such | | that r == ++s. | | post: s is dereferenceable. | | --(++r) == r. | | --r == --s implies r == s. | | &r == &--r. |
I might be wrong.
Quoted more than 1000 times (I hope).Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
>> What about decrementing .begin(), or incrementing .end() ? --.begin() becomes .end() ?
These are both undefined.