Can someone tell me why the iterators are failing in STL

[k_arjun]

When I try to find all subsets of a set using the following code, the iterator vit in the inner for loop of the getPowerSet function misses out on one element certain times. Can anyone tell me why?

#include<iostream>
#include<vector>
#include<set>

using namespace std;

vector< set<char> > getPowerSet(const set<char> &given);
void printPowerSet(const vector< set<char> > &powerset);
void printSet(const set<char> &input);

int main()
{
    int mychars[] = {'a','b','c','d'};
    set<char> given(mychars, mychars+4);

    vector< set<char> > powerset = getPowerSet(given);
    printPowerSet(powerset);
}

void printSet(const set<char> &input)
{
    set<char>::const_iterator it = input.begin();
    for( ; it!= input.end(); ++it)
        cout << *it << " ";
}

void printPowerSet(const vector< set<char> > &powerset)
{
    vector< set<char> >::const_iterator it = powerset.begin();
    for( ; it!= powerset.end(); ++it)
    {
        set<char>::iterator temp = (*it).begin();
        for(; temp!=(*it).end(); ++temp)
        {
            cout<< *temp << " ";
        }
        cout << endl;
    }
}
vector< set<char> > getPowerSet(const set<char> &given)
{
    vector< set<char> > powerset;
    set<char>::iterator it = given.begin();
    for(; it!=given.end(); ++it)
    {
        set<char> temp;
        temp.insert(*it);
        powerset.push_back(temp);

        vector< set<char> >::iterator vit = powerset.begin();
        vector< set<char> >::iterator evit = powerset.end();

        for( ; vit!=evit; ++vit)
        {
            set<char> temp2 = *vit;
            temp2.insert(*it);
            if(temp2.size() != (*vit).size())
            {
                powerset.push_back(temp2);
            }
        }
    }
    return powerset;
}

I have got the code to work without using iterators in that same loop. Used a variable instead. It works. The logic is the same and if possible I would like someone to tell me what went wrong in the first case.

#include<iostream>
#include<vector>
#include<set>

using namespace std;

vector< set<char> > getPowerSet(const set<char> &given);

int main()
{
    int mychars[] = {'a','b','c','d'};
    set<char> given(mychars, mychars+4);
    /*
    {
        for(set<char>::iterator it=given.begin(); it!=given.end(); ++it)
            cout<< *it << " ";
    }
    */
    vector< set<char> > powerset = getPowerSet(given);
    vector< set<char> >::iterator it = powerset.begin();
    for( ; it!= powerset.end(); ++it)
    {
        set<char>::iterator temp = (*it).begin();
        for(; temp!=(*it).end(); ++temp)
        {
            cout<< *temp << " ";
        }
        cout << endl;
    }
}

vector< set<char> > getPowerSet(const set<char> &given)
{
    vector< set<char> > powerset;
    set<char>::iterator it = given.begin();

    for(; it!=given.end(); ++it)
    {
        set<char> temp;
        temp.insert(*it);
        powerset.push_back(temp);
        int s = powerset.size();
        //vector< set<char> >::iterator vit = powerset.begin();
        //vector< set<char> >::iterator evit = powerset.end();
        for(int i=0; i< s; ++i)// vit!=evit; ++vit)
        {
            set<char> temp2 = powerset[i];
            int orig = temp2.size();
            temp2.insert(*it);
            if(temp2.size() != orig)
            {
                powerset.push_back(temp2);
            }
        }
    }
    return powerset;
}

[ravenous]

You have to be careful when using iterators to vectors.

When you call push_back on line 59, the vector has to grow by one element. If the capacity of the vector isn't sufficient to hold the new element, then the vector will re-allocate memory to accomodate the new element. Since the C++ standard says that a std::vector has to store its element contiguously in memory, then all the existing elements have to be moved to the new location as well. All this moving about means that any iterator that you're holding to the original vector is now not valid (it doesn't necessarily point to anywhaere in the vector any more!).

I don't know if this is your issue for sure, but you should definitely try to avoid it if you can :)

[NathanOliver]

Are you saying that running this code will produce different outputs occasionally?

[k_arjun]

No, running the code is always gives a different output.
Lets say the input set to getPowerSet() is {a,b,c}.
After the second iteration, the powerset becomes {a},{b},{a,b}.
On the third iteration, when the powerset should become {a},{b},{a,b},{c},{a,c},{b,c} and {a,b,c}, BUT i end up without {a,b,c}.

A break down of the algo. in the third iteration:

    add {c} to the powerset. It is now {a},{b},{ab},{c}
    Iterate over the powerset. (This is where the error is coming in.)
        First Iteration: Add c to a = {ac} to the powerset.
        Second Iteration: Add c to b = {bc} to the powerset.
        Third Iteration: Tries to add c to c = {c} to the powerset but does not as it already exists.
        In the THIRD iteration it should try to append c to {ab} and get {abc}, but it skips this step.

This issue is not happening with the second code snippet.