What is an alternative set-like data structure when modifying elements is necessary?

Question

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.

You could declare the member of your class that isn't part of the key as `mutable`. — Kerrek SB, Sep 23 '11 at 15:50
Or better use a map because this way your separate your key from your values. — Khaled Alshaya, Sep 23 '11 at 15:53
@KerrekSB: Except that if the class's `operator<` uses this member in the comparison, it can break `std::set<>`'s requirements. There's a good reason elements of the set have to be const. There's no way to really validate that the mutable members are not modified by the ordering predicate. — André Caron, Sep 23 '11 at 15:55
Thanks all, especially for the mutable suggestion. I would not have thought of that. But I think rewriting to use a map is probably a better choice for my purpose. — drb, Sep 23 '11 at 18:43

score 2 · Answer 1 · answered Sep 23 '11 at 15:59

2

A few possibilities come to mind:

Adjust your data structures to use std::map instead
Use the std::set, but remove the element you want to change and replace it with the updated value.
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.

answered Sep 23 '11 at 15:59

andand

17,134
11
53
79

I usually lean toward `map` in this case, I don't even change my data structure, just create a new `Key` structure, which is the key subset of attribute, and use it as a key. Encapsulating the map provides the guarantee that Key and Value have common values on their common attributes. – Matthieu M. Sep 23 '11 at 17:36

Nawaz · Answer 2 · 2011-09-23T16:01:28.513

1

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.

edited Sep 23 '11 at 16:01

answered Sep 23 '11 at 15:54

Nawaz

353,942
115
666
851

score 1 · Accepted Answer · answered Sep 23 '11 at 16:06

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;

answered Sep 23 '11 at 16:06

Emilio Garavaglia

20,229
2
46
63

score 0 · Answer 4 · answered Sep 23 '11 at 16:00

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.

What is an alternative set-like data structure when modifying elements is necessary?

4 Answers4

Linked