Inserting primitive type into set of sets

Question

I am looking to find all subsets of some set of size n, e.g. {{}, {1}, {1, 2} etc. } using the method described here.

My issue arises with attempting to build a set of sets with C++11. Namely, I have a set<set<int> > permutations which contains all my subsets. If I attempt to insert some integer element i into each of the subsets contained in permutations, as follows:

for (set<set<int> >::iterator it = permutations.begin(); it != permutations.end(); ++it)
{
    it->insert(i);    //error here
}

I run into a "no instance of overloaded function matches the argument list (the object has type qualifiers that prevent a match" error. My understanding is that iterator it refers to a set<int> object, and so *it has member function insert(). What is causing this particular error to arise?

@Carcigenicate The iterator of a set> should point to 1 set though... no? — Borgleader, Aug 09 '17 at 15:16
You cannot modify data in set, so you either need different container or take internal set, update and reinsert. — Slava, Aug 09 '17 at 15:18
@Carcigenicate the full error is: "no instance of overloaded function "std::set<_Kty, _Pr, _Alloc>::insert [with _Kty=int, _Pr=std::less, _Alloc=std::allocator]" matches the argument list and object (the object has type qualifiers that prevent a match)" — rw435, Aug 09 '17 at 15:19
@Slava could you elaborate what you mean by "take the internal set"? — rw435, Aug 09 '17 at 15:21
Apparently `*it` is a `const std::set` even though you're not using a const iterator. — CompuChip, Aug 09 '17 at 15:21
@DavidWang I mean remove it from outer set, update and reinsert. — Slava, Aug 09 '17 at 15:21

Benjamin Lindley · Accepted Answer · 2017-08-09T15:33:50.660

3

You are not allowed to modify the elements of a set, because this would break the internal ordering mechanism which the set uses. So the type of *it in your loop is const set<int>&. Consequently, you cannot call insert on it.

What you can do is make a copy of the element, insert an element into the copy, remove the original, and replace it with the copy.

for (set<set<int> >::iterator it = permutations.begin(); it != permutations.end(); )
{
    auto copy = *it;
    copy.insert(i);
    it = permutations.erase(it);
    permutations.insert(copy);
}

Note that if inserting an element in one set makes it identical to another, it will not be inserted, and you will end up with one less element set in your set. For example, if your set is {{}, {1}, {1,2}}, and i is 1, then the above loop will look at the empty set, add a 1 to it (resulting in {1}), and then it will fail when it tries to add that set back in, because there is already a set with that value.

edited Aug 09 '17 at 15:33

answered Aug 09 '17 at 15:23

Benjamin Lindley

101,917
9
204
274

What the OP wants is even more likely (I'm just guessing) to prepare a total content of set, and then insert it into meta-set of sets. If he is using single set for permutations, then he should insert into meta-set cloned copy of working set, i.e. the mutations must happen on the working set, which was not inserted into meta. So I don't think he will need remove + change + re-insert pattern, IMO he needs just M times "insert(clone(workingSet))". – Ped7g Aug 09 '17 at 15:32
Ah thank you for elaborating and also providing a solution. And @Ped7g you're right, I have cloned a copy of the working set (at each iteration of `i` up to n). – rw435 Aug 09 '17 at 15:48

Inserting primitive type into set of sets

1 Answers1