How are objects inserted into a set?

[desktop]

I have implemented a red-black tree which is used for std::set.

In the C++ standard 3 different insert methods are specified for the
associative container. But as i see it insert adds an object to the set
based on a key. But where does the key come from?

If I make my own object I don't specify any unique key that insert uses
to place the object.

Does the insert call generate some unique key that it uses each time an
object is inserted?

 

[Victor Bazarov]

I have implemented a red-black tree which is used for std::set.

In the C++ standard 3 different insert methods are specified for the
associative container. But as i see it insert adds an object to the
set based on a key. But where does the key come from?

It's the same as the value. Doesn't the book you're reading about
'std::set' tell you that?

If I make my own object I don't specify any unique key that insert
uses to place the object.

You do. By supplying an object with a value.

Does the insert call generate some unique key that it uses each time
an object is inserted?

Nope.

V

 

[desktop]

It's the same as the value. Doesn't the book you're reading about
'std::set' tell you that?


You do. By supplying an object with a value.


Nope.

V

It seems that I don't understand set. Inserting into a vector works fine:

class test {
public:
int getpp(){return pp;}
void setpp(int i){pp = i;}
private:
int pp;
};


int main() {
std::vector<test> hh;
test t1;
hh.push_back(t1); // Works fine


std::set<test> my_set;
const test& tref = t1; // see *
my_set.insert(tref); // fails with error: no match for
‘operator<’ in ‘__x < __y’

}


Can I only insert into std::set if my class 'test' define '<' and
properly some of the other operators?

I still don't see how insert gets the key from 'test' so it can put it
the right place in the tree.



* According to http://www.cppreference.com/cppset/insert.html

 

[Victor Bazarov]

It seems that I don't understand set.

Hmm... Yes. Do you understand std::map? std::set is very similar to

Inserting into a vector works
fine:
class test {
public:
int getpp(){return pp;}
void setpp(int i){pp = i;}
private:
int pp;
};


int main() {
std::vector<test> hh;
test t1;
hh.push_back(t1); // Works fine


std::set<test> my_set;
const test& tref = t1; // see *
my_set.insert(tref); // fails with error: no match for
‘operator<’ in ‘__x < __y’

}


Can I only insert into std::set if my class 'test' define '<' and
properly some of the other operators?

"properly"? Yes, to use the default sorting mechanism your class
needs to have operator< defined for it. You can make it a member or
you can make it a stand-alone function.

You don't have to have operator< defined if you use custom sorting
functor in your set.

I still don't see how insert gets the key from 'test' so it can put it
the right place in the tree.

What book are you reading that doesn't explain how sorting of
objects works?

* According to http://www.cppreference.com/cppset/insert.html

V

 

[Old Wolf]

Can I only insert into std::set if my class 'test' define '<' and
properly some of the other operators?

Yes. If you read a reference (or the C++ standard)
you will see exactly what operators must be defined.

 

[Alan Johnson]

It seems that I don't understand set. Inserting into a vector works fine:

class test {
public:
int getpp(){return pp;}
void setpp(int i){pp = i;}
private:
int pp;
};


int main() {
std::vector<test> hh;
test t1;
hh.push_back(t1); // Works fine


std::set<test> my_set;
const test& tref = t1; // see *
my_set.insert(tref); // fails with error: no match for
‘operator<’ in ‘__x < __y’

}


Can I only insert into std::set if my class 'test' define '<' and
properly some of the other operators?

I still don't see how insert gets the key from 'test' so it can put it
the right place in the tree.



* According to http://www.cppreference.com/cppset/insert.html

If you've created a red-black tree implementation, then your
implementation must have some way of deciding what order the objects go
in the tree. This is the same concept required for set. You have to
have some way of deciding what order objects go in. The way std::set
(and all the containers that need an ordering) decide this is by an
expression that can determine whether one object is "less" than another.
What it means for an object to be "less" depends on the type.

For types that implement operator<, std::set can just use that. If you
don't want to (or can't) add operator< to a class, you can create a
separate comparison functor and tell std::set to use that. Example:

struct compare_test
{
// If getpp was const we could pass by const reference.
// But it isn't, so we can't.
bool operator()(test test1, test test2)
{
return test1.getpp() < test2.getpp();
}
};

std::set<test, compare_test> my_set;

 

[Johs]

Yes. If you read a reference (or the C++ standard)
you will see exactly what operators must be defined.

I can see operators that must be defined for std::set in 23.3.3, but I
can't find any requirements for the objects that I would like to insert.
This is my object that I would like to insert into a std::set:


class test {
public:
int getpp(){return pp;}
void setpp(int i){pp = i;}

int operator<(int a) const
{
return 22;
}

private:
int pp;
};


But I still get the error:


error: no match for ‘operator<’ in ‘__x < __y

where can I find an interface for the objects to insert?

 

[Victor Bazarov]

[..]
I can see operators that must be defined for std::set in 23.3.3, but I
can't find any requirements for the objects that I would like to
insert. This is my object that I would like to insert into a std::set:


class test {
public:
int getpp(){return pp;}
void setpp(int i){pp = i;}

int operator<(int a) const
{
return 22;
}

private:
int pp;
};


But I still get the error:


error: no match for ‘operator<’ in ‘__x < __y

where can I find an interface for the objects to insert?

You are supposed to implement a comparison between two objects of the
type you're going to store, not between an object and an int:

...
bool operator <(test const& t) const {
...
}

and the actual implementation is supposed to adhere to "strict weak
ordering" rules: if two objects ('a', 'b') are equivalent (for the
purporses of storing in that set), then 'a < b' and 'b < a' should
both return false.

V

 

[desktop]

[..]
I can see operators that must be defined for std::set in 23.3.3, but I
can't find any requirements for the objects that I would like to
insert. This is my object that I would like to insert into a std::set:


class test {
public:
int getpp(){return pp;}
void setpp(int i){pp = i;}

int operator<(int a) const
{
return 22;
}

private:
int pp;
};


But I still get the error:


error: no match for ‘operator<’ in ‘__x < __y

where can I find an interface for the objects to insert?

You are supposed to implement a comparison between two objects of the
type you're going to store, not between an object and an int:

...
bool operator <(test const& t) const {
...
}

and the actual implementation is supposed to adhere to "strict weak
ordering" rules: if two objects ('a', 'b') are equivalent (for the
purporses of storing in that set), then 'a < b' and 'b < a' should
both return false.

V

Where are such rules defined. Could not find them in the C++ Standard.

 

[Victor Bazarov]

[..]
I can see operators that must be defined for std::set in 23.3.3,
but I can't find any requirements for the objects that I would like
to insert. This is my object that I would like to insert into a
std::set: class test {
public:
int getpp(){return pp;}
void setpp(int i){pp = i;}

int operator<(int a) const
{
return 22;
}

private:
int pp;
};


But I still get the error:


error: no match for ‘operator<’ in ‘__x < __y

where can I find an interface for the objects to insert?

You are supposed to implement a comparison between two objects of the
type you're going to store, not between an object and an int:

...
bool operator <(test const& t) const {
...
}

and the actual implementation is supposed to adhere to "strict weak
ordering" rules: if two objects ('a', 'b') are equivalent (for the
purporses of storing in that set), then 'a < b' and 'b < a' should
both return false.

V

Where are such rules defined. Could not find them in the C++ Standard.

The 'set' and 'map' templates have a template argument: the "Compare"
relation (see 23.1.2), which is by default 'std::less'. Now, look up
'std::less' and keep reading until you don't understand (and cannot
figure it out) by reading it again. Then ask more specific questions.

Again: what book are you reading that doesn't explain those things?

V

 

[desktop]

Johs wrote:
[..]
I can see operators that must be defined for std::set in 23.3.3,
but I can't find any requirements for the objects that I would like
to insert. This is my object that I would like to insert into a
std::set: class test {
public:
int getpp(){return pp;}
void setpp(int i){pp = i;}

int operator<(int a) const
{
return 22;
}

private:
int pp;
};


But I still get the error:


error: no match for ‘operator<’ in ‘__x < __y

where can I find an interface for the objects to insert?
You are supposed to implement a comparison between two objects of the
type you're going to store, not between an object and an int:

...
bool operator <(test const& t) const {
...
}

and the actual implementation is supposed to adhere to "strict weak
ordering" rules: if two objects ('a', 'b') are equivalent (for the
purporses of storing in that set), then 'a < b' and 'b < a' should
both return false.

V

Where are such rules defined. Could not find them in the C++ Standard.

The 'set' and 'map' templates have a template argument: the "Compare"
relation (see 23.1.2), which is by default 'std::less'. Now, look up
'std::less' and keep reading until you don't understand (and cannot
figure it out) by reading it again. Then ask more specific questions.

Again: what book are you reading that doesn't explain those things?

V

I am currently reading Bjarne Stroustrup and Accelerated C++. In Bjarne
I can only find half a page about sets in section 17.4.3 that
corresponds to what is found in the C++ Standard text.

There is no info on what rules applies to objects that are inserted into
the set, only that the set should have defined the less operator.

I have read the complete interface for std::set in the C++ Standard but
again there is no info on how to insert own objects.

 

[Victor Bazarov]

[..]
I am currently reading Bjarne Stroustrup and Accelerated C++. In
Bjarne I can only find half a page about sets in section 17.4.3 that
corresponds to what is found in the C++ Standard text.

Get a hold of a copy of "The C++ Standard Library" by Josuttis.

There is no info on what rules applies to objects that are inserted
into the set, only that the set should have defined the less operator.

"The set should have defined the less operator"? Either you are
misquoting or you've misunderstood. The set does not have to define
the less operator.

I have read the complete interface for std::set in the C++ Standard
but again there is no info on how to insert own objects.

Don't read the interface. Read the implementation. "Use the Source,
Luke!"

V

 

[desktop]

[..]
I am currently reading Bjarne Stroustrup and Accelerated C++. In
Bjarne I can only find half a page about sets in section 17.4.3 that
corresponds to what is found in the C++ Standard text.

Get a hold of a copy of "The C++ Standard Library" by Josuttis.

Have that also found something useful in section 22.4.2, thanks for the
reference!

"The set should have defined the less operator"? Either you are
misquoting or you've misunderstood. The set does not have to define
the less operator.

On page 505 in the C++ Standard the operators for set are declared:

template <class Key, class Compare, class Allocator>
bool operator==(const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);
template <class Key, class Compare, class Allocator>
bool operator< (const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);
template <class Key, class Compare, class Allocator>
bool operator!=(const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);
template <class Key, class Compare, class Allocator>
bool operator> (const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);
template <class Key, class Compare, class Allocator>
bool operator>=(const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);
template <class Key, class Compare, class Allocator>
bool operator<=(const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);


So I guess that the "less operator" should be defined for set. Again
this has nothing to do with object being inserted into a set. But I will
follow your advice an investigate the std::less further and also look
into section 22.4.2 in Josuttis.

Don't read the interface. Read the implementation. "Use the Source,
Luke!"

Thats another think I have some trouble finding, see my post:

"Source files for buildt-in containers in std?"

 

[stan]

I am currently reading Bjarne Stroustrup and Accelerated C++. In Bjarne
I can only find half a page about sets in section 17.4.3 that
corresponds to what is found in the C++ Standard text.

There is no info on what rules applies to objects that are inserted into
the set, only that the set should have defined the less operator.

In Stroustrup try 17.1.4 and 17.1.4.1. I found it was helpful to follow
the links such as 17.4.1.5 given in 17.1.4.1 for example. Basically he
covers a lot of ground for map and refers you back to that material when
he speaks in the section explicitly on sets.

 

[BobR]

desktop wrote in message...

On page 505 in the C++ Standard the operators for set are declared:

template <class Key, class Compare, class Allocator> [snip]

So I guess that the "less operator" should be defined for set.

Can you see the 'class Compare' in the template arg list?

[ From GNU GCC (MinGW) ]
"
// Forward declarations of operators < and ==,
// needed for friend declaration.
template <class _Key, class _Compare = less<_Key>,
class _Alloc = allocator<_Key> > class set;
"

Now look at that template. See the ' = less<_Key>'?

"
template <class _Key, class _Compare, class _Alloc>
inline bool operator<(const set<_Key,_Compare,_Alloc>& __x,
const set<_Key,_Compare,_Alloc>& __y);
"

So now you do:

class MyClass{ /* .... */ };
std::set< MyClass > MySet;

So the above 'operator<' template becomes:

inline bool operator<(
const set< MyClass,
less< MyClass >,
allocator< MyClass > >& __x,
const set<MyClass,
less< MyClass >,
allocator< MyClass > >& __y);

'(std:less<>' needs a way to tell whether one instance of 'MyClass' is
less than another instance of 'MyClass'!! See Alan Johnson's post (in this
thread) for that.

[ hope I got that right. Corrections, as always, are welcome. ]

 

[James Kanze]

desktop wrote:

Hmm... Yes. Do you understand std::map? std::set is very similar to
std::map. Essentially 'std::set<T>' is just like 'std::map<const T,T>'.

"properly"? Yes, to use the default sorting mechanism your class
needs to have operator< defined for it.

Strictly speaking, std::less<T> must be defined. Normally, this
is done by defining operator<, and allowing the generic
implementation std::less to do its job, but technically, you can
explicitly instantiate std::less directly for your type. (Note
that operator< is only defined on pointers if they point into
the same object, but you can have a set of pointers anyway,
because an implementation is required to make std::less work for
pointer types.)

You can make it a member or you can make it a stand-alone
function.

You don't have to have operator< defined if you use custom sorting
functor in your set.

Which is probably the more usual solution, unless the type has a
real unique ordering.

What book are you reading that doesn't explain how sorting of
objects works?

Note that it's very important that the ordering function meet
the specified requirements. In particular, it must be
transitive, and for every a and b, if a<b, then ! b<a, and vice
versa. (Both can, however, be false, in which case the objects
are considered equal.)

This seems trivially obvious, but people are constantly getting
it wrong.

 

[Old Wolf]

I can see operators that must be defined for std::set
in 23.3.3, but I can't find any requirements for the
objects that I would like to insert.

At the start of chapter 23 is a list of common
requirements for all containers. In particular:

23.1/3:
The type of objects stored in these components must
meet the requirements of /CopyConstructible/ types
(20.1.3) and the additional requirements of
/Assignable/ types.

The subsequent table includes some more commentary
on operator< , including that it must be defined for
operands of the object in the container (not for
object and int, as you had in your code).

Next is section 23.1.2, associative containers
(note that the <set> section, 23.3.3/2, refers
back to 23.1.2 as well as 23.1):

I won't bother quoting 23.1.2 but between that and
23.1 you should have all the information you're
looking for.