Can I use multiple keys on the "SET" container?

[starquest1000]

1) Can I use a struct/class in a "SET" container? For example, see following structure:

struct myClass
{
int key1;
uint8 key2[6];
int otherfields1;
int otherfields2;
}

std::set<myClass> myClass_set; /* instantiating the object */


2) If so, how do I specify the keys (multiple keys)?

3) If not, what kind of container can I use?

Thanks.

[Zhuge]

Can I ask how having two keys for an object would work? As far as I know, none of the STL containers support having multiple keys for the same object, though I suppose you could have two separate containers each having a pointer to the same object.

[imi]

1) You can use structs/classes as template parameter for set's, as long as they are a) copyable, b) assignable and c) supports comparing with operator<. Your "myClass" fullfills the first two items but not the last, so you will not be able to use it in a set effectively. (You can use it in a vector, which does not require operator<).

If you want to "fix" this, either provide a comparator to your set definition or implement an own operator< for your class:

// either provide an own comparator. As example use key1 member
bool my_is_smaller(const myClass& c1, const myClass& c2) { return c1.key1 < c2.key1; }
// and now use set like this:
set<myClass, my_is_smaller> myClass_set;


// or you can provide an operator< (you can also implement the operator
// as member function of myClass, but this is slightly better in some cases)
bool operator<(const myClass& c1, const myClass& c2) { return c1.key1 < c2.key1; }
// now just use set as in your example
std::set<myClass> myClass_set;

2) std::set has no keys and no multiple entries. It kicks out all entries that are equal (or was it equivalent? don't remember..)

Edit: maybe here is a misunderstanding.. by "keys", do you happen to mean the member variables "key1" and "key2" of your class? If so, then it all depends on your operator<. All that set prohibits is, that you can not store two objects in the same set for which are the following is true: "!operator<(o1,o2) && !operator<(o2,o1)" (which basically means: neither is smaller than the other.)

3) You may look into std::map, which is the classic key/value associative container used in many other languages. Or you may want to use std::multiset, which is a set that can store the same value multiple times. (There is also a multimap ;)

[jsmith]

If you truly want multiple keys -- ie, you want log N lookup on two different fields -- you
can look up boost::multi_index_container, however if you're not comfortable with templates
it might be a steep learning curve.

And this also assumes you have the boost libraries available to you.

[starquest1000]

This is response to "imi":

>> Edit: maybe here is a misunderstanding.. by "keys", do you happen to mean the member variables "key1" and "key2" of your class? If so, then it all depends on your operator<.

I am now defining overloading "operator<". And I am using only the first two elements/keys from my structure.

Now I have other questions:

1) When I "myClass_set.find ()" my element and "iterator" is returned, why I getting "read-only structure" when I assign values to other fields during compiling? Why?

myClass myObj;
std::set<myClass>::iterator it;
it = myClass_set.find (myObj); /* Assuming it is found OK */
it->otherfields1 = 100; <=== Compiling error: error: assignment of data-member 'otherfields1 ' in read-only structure

2) I need to modify "otherfields1" & "otherfields2" based on the found "it". How can I work around this?

Thanks.

[imi]

That's right. Iterators in std::sets are constant (std::set::iterator and std::set::const_iterator are the same type). Hence, you are not allowed to change them directly. It's a bit awkward, but IIRC the standard decided to do this so people don't accidently change values in maps and sets which could disturb the sorting order. (In my own opinion a wrong decission, but that's another topic ;)

There are basically three solutions for this. mutable, const_cast and reinserting the value:

The mutable - approach looks like this:

// for the "mutable" - way, define the otherfield's mutable in your class.
// This way they are always changeable - regardless of const. Beware that this also means,
// they can be changed when you use const in other cases (e.g. to pass values to functions)
struct myClass {
...
    mutable int otherfields1;
    mutable int otherfields2;
};

If you just want to set the value once and don't want to open up the otherfields for all places where you could use myClass in a const-matter, you can use const_cast.

const_cast<myClass&>(*it).otherfields1 = 100; // should work in allmost all environments just fine 

Beware, however that const_cast can fail horribly, if the object you cast is really const (was declared as const). The std::set-implementations I know of don't do this, but if you run into trouble, this is a spot to look at. ;). Just don't use const_cast carelessly.


The last solution is considered by many the "cleanest" way: delete the object from the set, change it and then reinserting it back. It's unfortunately also inefficient. Attention: You HAVE to use this way if you change anything that could affect the sorting order of the set! (in your case: key1 or key2)

...
myClass tmp = *myClass_set.erase(it);
tmp.otherfields1 = 100;
myClass_set.insert(tmp);

Ciao, Imi.

[imi]

reminds me... if you have to care for performance there is another good solution.

If you have to find entries in the set often and read/change these "otherfield" values, but very seldom insert or delete anything from the whole set, don't use std::set at all.

Instead, use std::vector together with std::sort() and binary-search (e.g. std::lower_bound). It's a bit more work and you probably should create some wrapper-class for it, but at the end of the day, you get better performance and less hassle with std::set's constness.

Ciao, Imi.

[starquest1000]

Thanks you very much for your help. "imi"

[kempofighter]

2) std::set has no keys and no multiple entries. It kicks out all entries that are equal (or was it equivalent? don't remember..)

Equivalence is correct. There is no operator== for the struct so there is no way for std::set to determine equality even if it wanted to. Two instances of the struct with an identical key would be equivalent but that does not mean that the struct instances are equal because the other member variables of the struct are not compared. Also the set documentation doesn't indicate that it would ever use operator== even if you defined it for the struct.