an STL set of custom objects, each containing an STL set

Question

As is hopefully clear from the code below, I'd like to have a set of objects objectSet, each containing str1 and str2. The set is keyed on str1, and any new objects with an str1 already in the objectSet will not be added, but if this new object has a different str2, I want to keep track of the fact that I saw it in the str2Set

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <set>
#include <map>

using namespace std;

class Object {
public:
  string _str1;
  string _str2;
  set<string> _str2Set;

  bool operator<(const Object& b) const {
    return _str1 < b._str1;
  }
};

int main(int argc, char *argv[]) {
  set<Object> objectSet;

  Object o;
  o._str1 = "str1";
  o._str2 = "str2";

  pair< set<Object>::iterator, bool> o_ret = objectSet.insert(o);
  if (o_ret.second == false) { // key exists
    int temp = (*o_ret.first)._str2Set.size(); // this is apparently fine
    (*o_ret.first)._str2Set.insert(o._str2); // this results in the error
  }

  return 0;
}

Here is the compiler error:

set_test.cpp: In function ‘int main(int, char**)’: set_test.cpp:31: error: passing ‘const std::set, std::allocator >, std::less, std::allocator > >, std::allocator, std::allocator > > >’ as ‘this’ argument of ‘std::pair, _Compare, typename _Alloc::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const _Key&) [with _Key = std::basic_string, std::allocator >, _Compare = std::less, std::allocator > >, _Alloc = std::allocator, std::allocator > >]’ discards qualifiers

I understand this has to do with const but I still can't figure out exactly what the problem is or how to fix it. Just getting rid of the const doesn't help.

As an alternative, I tried storing my Object's in

map<string,Object> objectSet;

And, strangely enough, the following works just fine:

  pair< map<string,Object>::iterator, bool> o_ret = objectSet.insert(pair<string,Object>(o._str1,o));
  if (o_ret.second == false) { // key exists
    o_ret.first->second._str2Set.insert(o._str2);
  }

Of course, that means I have to store str1 twice, which I consider wasteful. Thanks for your input.

Answer 1

The error says that (*o_ret.first)._str2Set is a const object, and that you cannot call the insert method for it as a result.

And it's quite right : since you are not allowed to modify the objects in a std::set (because that would potentially invalidate the container's consistency), you get a const qualified object when dereferencing an iterator into the container (as if it were a const_iterator).

You also noted that it worked for a std::map, but that's because you're modifying the value there, not the key. Remember that in a std::set, the value IS the key, so you can't modify it.

Answer 2

Your design is flawed. You are using Object as a key to a set, but then you are attempting to modify the keys of your set. Of course you are only modifying parts of Object that don't affect it's use as a key, but the compiler doesn't know that. You need to modify your design, your second version is fine to me, I wouldn't worry about storing the string twice (normally, I don't know your specific circumstances). Alternatively you could split your object so the key part and the value part are separated. Finally you could declare _str2set as mutable.

Answer 3

The iterator you get back from a set insert has a const iterator for the first member of the pair - you're not supposed to modify the object you inserted in the set, because bad things will happen if the modification affects the order. So calling size on it is ok, because that's a const method, but insert is out because it modifies the object in the set. The map works because the Object is the value, not the key, so you can modify it without affecting the indexing of the map (the string is copied when you did the map insert).

If you want to use a set to store your Objects and avoid the extra copy of string, the way to update it is to remove the Object from the set (making a copy before you delete it), update the copy, and then reinsert the copy. You can't update it while it's in the set. I'm away from my STL references at the moment so I can't give you code, but that's the general idea to follow.

Answer 4

The other answers already correctly stated the problem with your approach, here's an idea for a solution. Since the first string is your key, change your main data structure to a std::map keyed on the first string and carrying the rest of the data as the payload:

typedef std::pair< std::string, std::set<std::string> > Payload; // or make your own class
typedef std::map<std::string, Payload>                  Collection;
typedef Collection::value_type                          Data; // this is a std::pair<string, Payload>

// A little helper to create new data objects
Data make_data(std::string s1, std::string s2)
{
  return Data(s1, Payload(s2, std::set<std::string>()));
}

Collection m;

Data x = make_data("mystr1", "mystr2");

std::pair<Collection::iterator, bool> res = m.insert(x);
if (res.second == false)
{
  Payload & p = *res.first;
  p.second.insert(x.second.first);
}

In some sense the second string is a bit redundant, and you might be able to redesign this to do away with it entirely: Instead of insert use find, and if the key already exists, you append your second string to the set.

Answer 5

After reading everyone's helpful comments and learning way more than I thought I ever wanted to know about shallow constness and mutable, I realized I can accomplish everything I wanted simply by storing a pointer to the _str2set. I personally think that declaring it mutable as suggested by @john is fine, but maybe some people would find the ptr solution less objectionable.

class Object {
public:
  string _str1;
  string _str2;
  set<string> * _str2Set;

  bool operator<(const Object& b) const {
    return _str1 < b._str1;
  }
};

int main(int argc, char *argv[]) {
  set<Object> objectSet;

  Object o;
  o._str1 = "str1";
  o._str2 = "str2";
  o._str2Set = new (set<string>);

  pair< set<Object>::iterator, bool> o_ret = objectSet.insert(o);
  if (o_ret.second == false) { // key exists
    (*o_ret.first)._str2Set->insert(o._str2); // this results in the error
    cout << (*o_ret.first)._str2Set->size() << endl;
  }
  return 0;
}