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]

desktop wrote:

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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[desktop]

Victor Bazarov wrote:

desktop wrote:

>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

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<tes thh;
test t1;
hh.push_back(t1 ); // Works fine
std::set<testmy _set;
const test& tref = t1; // see *
my_set.insert(t ref); // 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]

desktop wrote:

Victor Bazarov wrote:

>desktop wrote:

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

It seems that I don't understand set.

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>'.

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<tes thh;
test t1;
hh.push_back(t1 ); // Works fine
std::set<testmy _set;
const test& tref = t1; // see *
my_set.insert(t ref); // 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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Old Wolf]

On Jun 8, 6:41 am, desktop <[e-mail] ote:

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]

desktop wrote:

Victor Bazarov wrote:

>desktop wrote:

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

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<tes thh;
test t1;
hh.push_back(t1 ); // Works fine
std::set<testmy _set;
const test& tref = t1; // see *
my_set.insert(t ref); // 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_testmy_ set;

--
Alan Johnson

[Johs]

Old Wolf wrote:

On Jun 8, 6:41 am, desktop <[e-mail] ote:

>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.

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]

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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[desktop]

Victor Bazarov wrote:

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.

[Victor Bazarov]

desktop wrote:

Victor Bazarov wrote:

>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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask