CODEWITHSUNDEEP
c++
user11145590
user11145590

Reputation: 59

C++ Set of Set’s iterator defaults to const preventing insertion

I was implementing primms algorithm for a class and decided to keep a set class with other sub sets to look through. This would enable me to look in main set for one of the two vertices and if not found check all the other sets. If I found two vertices in different sets I would union the sets and get a bigger tree until the tree matched vertice’s number thus garunteeing a MST. However, the iterator defaults to const so insertion is a forbidden action which means this implementation is just out of reach. Any help? Compiler 2011, stl set data structure.

Edit:

Here's some example code, and the error message.

#include <cstdio>
#include <vector>
#include <set>

using namespace std;

int main()
{

//A set and a temp set to load a simple
//set into the structure.
set<int> first;
set<set<int> > s;

//insert two arbitrary numbers
first.insert(1);
first.insert(2);

//insert the arbitrary set.
s.insert(first);

//Create a non const iterator, and iterate through the set of sets {1,2}
//Try to find a three inside of what the set iterator points to. if not insert
//the three. 
for (set<set<int> >::iterator sit = s.begin(); sit != s.end(); ++sit)
{
    if ((*sit).find(3) == (*sit).end())
    {
        (*sit).insert(3);
    }
}

return 0;

}

test.cpp:21:19: error: passing ‘const std::set<int>’ as ‘this’ argument of ‘std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename _Alloc::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename _Alloc::rebind<_Key>::other>::const_iterator = std::_Rb_tree_const_iterator<int>; std::set<_Key, _Compare, _Alloc>::value_type = int]’ discards qualifiers [-fpermissive]
(*sit).insert(3);

Upvotes: 0

Views: 106

Answers (2)

user11145590
user11145590

Reputation: 59

I swapped the implementation to a vector of sets (lookup a deque/list if you want constant pop_front/deletion from your data structure). Then I simply needed to index on the regular number iterator. Here's a working example that printouts the union. Thanks everyone, didn't know if I could modify it or not. 

#include <cstdio>
#include <vector>
#include <set>

using namespace std;

int main()
{
set<int> first;
vector<set<int> > s;

first.insert(1);
first.insert(2);

s.push_back(first);

for (size_t i = 0; i < s.size(); ++i)
{
    if (s[i].find(3) == s[i].end())
    {
        s[i].insert(3);
    }
}
for (size_t i = 0; i < s.size(); ++i)
{
    for (set<int>::const_iterator j = s[i].begin(); j != s[i].end(); ++j)
    {
        printf("%d ", *j);
    }
    printf("\n");
}

return 0; 
}

Upvotes: 0

pasbi
pasbi

Reputation: 2179

You cannot modify items of a std::set via its iterator. That is, iterators to sets are always const. And that's completely sensible once you think about how the set is implemented.

The problem can be solved in different ways. Without knowing more about the context, I'd recommend to use std::list or std::vector instead of std::set.

Upvotes: 1

Related Questions