Re: How are objects inserted into a set?
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<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;
--
Alan Johnson