Thread: finding element in std::map

  1. #1
    Registered User
    Join Date
    Sep 2009
    Posts
    6

    finding element in std::map

    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) ?

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by tabstop View Post
    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

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.)

  5. #5
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by tabstop View Post
    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.)
    Wow, there's a lower_bound/upper_bound MEMBER function as well? That's useful.
    I keep learning about the STL a lot, even though I know quite a lot about it.

  6. #6
    Registered User
    Join Date
    Sep 2009
    Posts
    6
    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:
    Code:
    --map.lower_bound(x)
    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.

  7. #7
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    You could just check the return value against end before decrementing.

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.)

  9. #9
    Registered User
    Join Date
    Sep 2009
    Posts
    6
    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
    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;
    }
    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 ?

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  12. #12
    Registered User
    Join Date
    Sep 2009
    Posts
    6
    Quote Originally Posted by tabstop View Post
    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.
    I don't understand. This code output (7,1), as expected:
    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;
    }
    Quote Originally Posted by tabstop View Post
    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.
    You're right. But I was talking about the constant factor (searching twice).

    Quote Originally Posted by anon View Post
    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.
    Are you sure decrementing .end() is correct ? What about decrementing .begin(), or incrementing .end() ? --.begin() becomes .end() ?

  13. #13
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    performing --(..) on map.end() is undefinied.
    No, it's not. Where did you get that idea? It's only undefined if the map is empty.
    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

  14. #14
    The larch
    Join Date
    May 2006
    Posts
    3,573
    The standard says this about operator-- of bidirectional iterators.

    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.                 |
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  15. #15
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> What about decrementing .begin(), or incrementing .end() ? --.begin() becomes .end() ?

    These are both undefined.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 06-14-2009, 01:39 PM
  2. Replies: 4
    Last Post: 01-05-2008, 11:30 PM
  3. finding the element number in an array
    By tommy69 in forum C Programming
    Replies: 7
    Last Post: 04-02-2004, 04:26 AM
  4. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 12:04 PM
  5. Finding numbers higher than the first element in array
    By sonict in forum C++ Programming
    Replies: 2
    Last Post: 12-02-2002, 10:00 AM