STL set lower_bound
mattg
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
?
Paavo Helde
[...]
> 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
Michael DOUBEZ
> Hi,
>
> Can somebody explain to me why the code
> 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)).
--
Michael
mattg
> mattg <gara.m...@gmail.com> kirjutas:
so something like:
if(iter != s1.begin())
{
node* lessthan = *(--iter); //this is the node less than the query
}
Paavo Helde
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
mattg
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));
Paavo Helde
> 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));
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;
}
mattg
> mattg <gara.m...@gmail.com> kirjutas:
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::Do()' discards qualifiers
How would I work around this?
Obnoxious User
[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::Do()' discards qualifiers
>
> How would I work around this?
Using 'new' and store pointers.
--
OU
Remember 18th of June 2008, Democracy died that afternoon.
http://frapedia.se/wiki/Information_in_English
mattg
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.
Paavo Helde
No 'new', nothing to leak.
> 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::Do()' discards qualifiers
The things in std::set are considered immutable so by default they act as
const. If changing val2 is to be considered not to change the object
state logically (the set order is not affected, for example - this is the
case here), then you should be able to get this working as:
class node {
...
mutable int val2;
...
int Do() const { // note 'const' here
val2++;
}
};
Another way could be to use std::map<int,node> or something, instead of
std::set, depending on your goals.
Paavo
Paavo Helde
...
> 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.
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.
Regards
Paavo
James Kanze
> mattg <gara.m...@gmail.com> kirjutas:
> ...
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).
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
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
It is true but IMHO it is more a property than a definition.
--
Michael
Dennis
"mattg" <gara...@gmail.com> wrote in message
news:4dae89bf-0d4c-4749...@p42g2000prp.googlegroups.com...
<snip>
>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:
<snip>
> int Do() {
> val2++;
> }
<sniip>
>};
>
>and I try calling iter->Do() I get error
>test.cpp:80: error: passing 'const node' as 'this' argument of 'void
>node::Do()' 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