rachitiitr's blog

lower_bound in set<node>
By rachitiitr, history, 9 years ago, In English

struct node{
int i, j, val;
};

set<node> A;
I insert many nodes in A. Now I want to get the lower_bound for some val = k. How do I use A.lower_bound() in this case?

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rachitiitr (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

You can define a custom comparator and then make queries like A.lower_bound({0,0,k}) for example.

Check this example for more clarification: http://ideone.com/xbUGBr

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You have to define the comparison operator (<) if you want to be able to do lower_bound. I've always liked the friend feature of C++.

struct node
{
    int i,j,val;
    friend bool operator < (node n1, node n2)
    {
        // Define your own ordering criteria here
    }
};
→ Reply
»
9 years ago, # |
← Rev. 5   Vote: I like it +12 Vote: I do not like it

when you use A.lower_bound(dummy) it will return iterator to the first node not less than dummy

so your struct should be something like this

struct node{
  int i, j, val;
  bool operator<(node &tmp)const{
    if(val!=tmp.val)return val<tmp.val;
    if(i!=tmp.i)return i<tmp.i;
    return j<tmp.j;
  }
  // of course the logic of the comparator is just example,
  //you should change it as needed in your problem
};

be careful, the std::set does not has == operator, and it uses the < operator to achieve the uniqueness. in other words, if you insert node a and the set wants to check a against node b to check if they are equal or not, it will do the following,

if ( a < b ) => false then if ( b < a ) => false, then it assume that they are equal.

so if your operator does not consider some element in the struct in the < operator it might be the case that the set assume 2 elements are equal while they are not "that's why i used the 3 variables in my example for the < operator".

→ Reply