STL set lower_bound

[mattg]

Hi,

Can somebody explain to me why the code

#include<iostream>
#include<set>

using namespace std;

class node {
public : int val;
node(int v){
val = v;
}
};


struct node_comp{
bool operator () (node * n1, node * n2) const {
return n1->val < n2->val;
}
};


set<node*, node_comp> s1;

void test(){
s1.insert((new node(1)));
s1.insert((new node(2)));
s1.insert(new node(8));
s1.insert(new node(9));
s1.insert(new node(12));

}
int main(){
test();
set<node*, node_comp>::iterator iter;

iter = s1.lower_bound(new node(5));
cout << "iter =" << (*iter)->val << endl;
}

outputs

iter = 8

instead of

iter = 2

?

 

[Michael DOUBEZ]

Hi,

Can somebody explain to me why the code [snip]
set<node*, node_comp> s1;

void test(){
s1.insert((new node(1)));
s1.insert((new node(2)));
s1.insert(new node(8));
s1.insert(new node(9));
s1.insert(new node(12));

}
int main(){
test();
set<node*, node_comp>::iterator iter;

iter = s1.lower_bound(new node(5));
cout << "iter =" << (*iter)->val << endl;
}

outputs

iter = 8

instead of

iter = 2

?

Because lower_bound returns an iterator pointing to the first element in
s1 which *does not* compare less than 5.

8 is the first value where (!(8<5)).

 

[mattg]

mattg <[email protected]> kirjutas:
[...]

void test(){
     s1.insert((new node(1)));
     s1.insert((new node(2)));
     s1.insert(new node(8));
     s1.insert(new node(9));
     s1.insert(new node(12)); [...]

     iter = s1.lower_bound(new node(5));

outputs

iter = 8

instead of

iter = 2

?

Because that's how lower_bound is defined:

"Returns an iterator to the first element in a set with a key that is equal
to or greater than a specified key"

If you want the previous element, you can check the result against s1.begin
() and decrement the iterator.

hth
Paavo

so something like:

if(iter != s1.begin())
{
node* lessthan = *(--iter); //this is the node less than the query
}

 

[mattg]

mattg <[email protected]> kirjutas:

mattg <[email protected]> kirjutas:
[...]
void test(){
     s1.insert((new node(1)));
     s1.insert((new node(2)));
     s1.insert(new node(8));
     s1.insert(new node(9));
     s1.insert(new node(12));
[...]
     iter = s1.lower_bound(new node(5));
outputs
iter = 8
instead of
iter = 2
?
Because that's how lower_bound is defined:
"Returns an iterator to the first element in a set with a key that is
equ al
to or greater than a specified key"
If you want the previous element, you can check the result against
s1.beg in
() and decrement the iterator.
hth
Paavo

so something like:

if(iter != s1.begin())
{
   node* lessthan = *(--iter); //this is the node less than the query
}

Yes, something like that. And I hope you are realizing you are leaking
memory all over the place, and the design would become much simpler by
using std::set<node>.

BEst regards
Paavo

yes I realize I am leaking memory everywhere, this was simply a test,
in my actual application I clean up. My original attempt at this was
using node as a struct instead of a class but I couldn't figure out
how to write the line

iter = s1.lower_bound(new node(5));

 

[mattg]

I would write this example as:

#include<iostream>
#include<set>

using namespace std;

class node {
private:
        int val;
public:
        node(int v){
                val = v;
        }
        int GetVal() const {
                return val;
        }
        bool operator<(const node& b) const {
                return val<b.val;
        }

};

set<node> s1;

void test(){
        s1.insert(1);
        s1.insert(2);
        s1.insert(8);
        s1.insert(9);
        s1.insert(12);

}

int main(){
        test();
        set<node>::iterator iter;

        iter = s1.lower_bound(5);
        cout << "iter =" << iter->GetVal() << endl;

}

Ahh ok, thats much cleaner, but I have 2 questions:

1) does this design not cause any memory leaks
2) if I add to the node

class node {
private:
int val;
int val2;
public:
node(int v){
val = v;
val2 = 0;
}
int GetVal() const {
return val;
}
int Do() {
val2++;
}
bool operator<(const node& b) const {
return val<b.val;
}

};

and I try calling iter->Do() I get error

test.cpp:80: error: passing 'const node' as 'this' argument of 'void
node:o()' discards qualifiers

How would I work around this?

 

[mattg]

Alright yea, thanks thats probably the reason why I opted with the
messy pointer storage initially. Well, to close this topic up I'd
just like to say its really counter-intuitive to design a method
called lower_bound(x) that finds the y such that x<=y. Coming from a
math background we are very strict on our usage of these technical
terms, and this could probably win an award somewhere for abuse of
notation. As you all probably know a lower bound of a number x in the
reals should be a number y in the reals such that y<=x. Guess the guys
designing STL containers slept through these classes.

On Sun, 29 Mar 2009 16:07:22 -0700, mattg wrote:

[snip]

class node {
private:
        int val;
        int val2;
public:
        node(int v){
                val = v;
                val2 = 0;
        }
        int GetVal() const {
                return val;
        }
        int Do() {
                val2++;
        }
        bool operator<(const node& b) const {
                return val<b.val;
        }

and I try calling iter->Do() I get error

test.cpp:80: error: passing 'const node' as 'this' argument of 'void
node:o()' discards qualifiers

How would I work around this?

Using 'new' and store pointers.

 

[James Kanze]

mattg <[email protected]> kirjutas:

Math and programming are two different things. For starters,
there is no datatype actually corresponding to real numbers.

I believe STL designers worked their design out very
carefully. If lower_bound were to return the "previous"
element, then what to return if there is none? There is no
concept of an iterator "before begin()". I guess they had a
choice of introducing yet another pseudovalue in addition to
end () iterator, or demanding all algorithm users to deal with
the special case when there is no "previous element". I guess
they preferred to return the "next" iterator and avoid the
problem entirely, so that only those users who actually need
the previous one are having to consider the special case.

The documentation at SGI site says that lower_bound "returns
the first position where value could be inserted without
violating the ordering". So it appers this is not lower bound
of existing elements, but lower bound of insertion places for
the new element.

It treats the argument as the "lower bound", and and returns the
first element in the set corresponding to that lower bound.
(Of course, then we have problems with upper_bound.)

Seriously, IIUC, the idea is that by iterating between
lower_bound(a) and upper_bound(b), you visit all elements >= a
and < b. In other words, you've defined a (possibly empty)
sequence in the usual iterator conventions. And that possibly
empty is important; it means that if a is not a member of the
set, lower_bound(a) must equal upper_bound(a).

 

[Juha Nieminen]

Because lower_bound returns an iterator pointing to the first element in
s1 which *does not* compare less than 5.

8 is the first value where (!(8<5)).

Another way of thinking about it: If you insert the searched value at
the position returned by lower_bound, the data container will still be
ordered after the insertion.

 

[Michael DOUBEZ]

Another way of thinking about it: If you insert the searched value at
the position returned by lower_bound, the data container will still be
ordered after the insertion.

It is true but IMHO it is more a property than a definition.

 

[Dennis]

Ahh ok, thats much cleaner, but I have 2 questions:

1) does this design not cause any memory leaks
2) if I add to the node

class node {
private:
int val;
int val2;
public:

int Do() {
val2++;
}

};

and I try calling iter->Do() I get error

test.cpp:80: error: passing 'const node' as 'this' argument of 'void
node:o()' discards qualifiers

How would I work around this?

use a map.
std::map<int, int> IntMap;
std::map<int, Node> NodeMap;

With either set or map, the key can't be changed, which is what the Do
method tries to do, evne though internally
the set's key is not being modified.

Dennis