What is an alternative set-like data structure whe

问题:

STL sets are designed so that it is not possible to modify the elements in the set (with good reason, see stackoverflow). Suppose however I have a structure in which only one of the members acts as the key. Is there an alternative data structure to a set. I really want exactly the behavior of sets except this inability to modify a field or member which is non-key.

回答1:

May be it's time to redesign, considering std::map instead of std::set.

instead of

struct A
{
   K key;
   V val;
};

set<A> a;

consider

std::map<K,V> m;

you can then do

m[k] = v;

回答2:

A few possibilities come to mind:

1. Adjust your data structures to use std::map instead
2. Use the std::set, but remove the element you want to change and replace it with the updated value.
3. Design and implement a data structure that satisfies your requirements.

I'd look at the first two options as preferable; the last should be used only if you can't adapt your problem or existing STL containers to meet your needs.

回答3:

Declare the non-key as mutable, then you would be able to modify it.

struct A
{
   KeyType key;
   mutable NonKeyType nonkey;
   //..
};

std::set<A> aset;
//...

const A & a = *aset.begin();
a.nonkey = newValue; //you can modify it even if the object `a` is const.

You've to make sure that nonkey is really a non-key; it must not take part in operator< comparison function.

回答4:

There is no way to enforce that members of the class used in the ordering predicate are not modified. An modification to members used in the ordering predicate may potentially break the set.

The easy way to trick the compiler into letting you use the set with mutable members is marking the members as mutable:

 class Foo
 {
     std::string myVal1;
     mutable std::string myVal2;
 public:
     bool operator<(const Foo& rhs)const {
         return myVal1 < rhs.myVal;
     }
 };

Then, you have to manually ensure that Foo::operator<() never uses myVal2 in the comparison. This is possible, but is is a Bad Idea (tm). You can mark this specific operator with a huge comment, but you can't automatically duplicate this comment into all custom comparison functions (std::set<> accepts this as a second parameter).

The real way to achieve what you want is to use a std::map<>. Put the "key" part in the key and the "value" part in the value.