Why are appended vectors throwing away data?

Question

I have a number of vectors contained inside one large vector with pointers. Now I'd like to merge vectors in this list based on an arbitrary condition. This involves first appending the two vectors together, then removing one of them from the "large" vector.

When I run the program, I occasionally get a case where a vector of length 6 and 12 are merged together, giving a total length of 12 (thus throwing away 6 elements).

I've tried to recreate the problem in one contained C++ file. I didn't quite manage this (this one throws a non-debuggable index out of bounds error). As far as I can tell I'm messing up a number of things here.

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <fstream>

int main(int argc, char** argv)
{
    std::vector<std::vector<int>*> lists;

    //create lists with variable size
    for(int i = 0; i < 100; i++) {
        std::vector<int> vec;
        for(int j = 0; j < i; j++) {
            vec.push_back(j);
        }
        lists.push_back(&vec);
    }

    //do the merging
    bool changed = true;
    while(changed) {
        changed = false;
        for(int list = 0; list < (int)lists.size(); list++) {
            std::vector<int>* listInstance = lists.at(list);
            for(int otherList = 0; otherList < (int)lists.size(); otherList++) {
                if(list == otherList) {//avoid merging lists with themselves
                    continue;
                }
                std::vector<int>* otherListInstance = lists.at(otherList);

                if(lists.at(otherList)->size() % 4 == 0) { //some arbitrary condition for merging.
                    changed = true;

                    int otherSize = otherListInstance->size();

                    listInstance->insert(listInstance->end(), otherListInstance->begin(), otherListInstance->end());
                    lists.erase(lists.begin() + otherList);

                    if(otherSize != otherListInstance->size()) {
                        std::cout << "Does not match!\n";
                    }

                    otherList--;
                }
            }
        }
    }

    return 0;
}

Answer 1

Pushing pointers to local variables yields undefined behavior if those variables go out-of-scope:

for (int i = 0; i < 100; i++) {
    std::vector<int> vec;
    for (int j = 0; j < i; j++) {
        vec.push_back(j);
    }
    lists.push_back(&vec); // Pointer to an in-scope local variable
}

// Now lists contains pointers to invalid stack areas

Since it seems you're just trying to create a vector of int vectors, you could simply store it without pointers:

std::vector<std::vector<int>> lists;

for (int i = 0; i < 100; i++) {
    std::vector<int> vec;
    for (int j = 0; j < i; j++) {
        vec.push_back(j);
    }
    lists.push_back(vec);
}

with that change (and obviously also changing every dereferencing to a member-access), e.g.

lists.at(otherList)->size() ---> lists.at(otherList).size()

your code will do just fine.

If you really need/want to use pointers, make sure to allocate them on the heap and I'd also suggest using a smart pointer to store it.

Answer 2

You are pushing pointers to local variables. That's undefined behavior.

Change

std::vector<std::vector<int>*> lists;

//create lists with variable size
for(int i = 0; i < 100; i++) {
    std::vector<int> vec;
    for(int j = 0; j < i; j++) {
        vec.push_back(j);
    }
    lists.push_back(&vec);
}

to

std::vector<std::vector<int>> lists;

//create lists with variable size
for(int i = 0; i < 100; i++) {
    std::vector<int> vec;
    for(int j = 0; j < i; j++) {
        vec.push_back(j);
    }
    lists.push_back(vec);
}

Or create a non-local version using new.

std::vector<std::vector<int> *> lists;

//create lists with variable size
for(int i = 0; i < 100; i++) {
    std::vector<int> * vec = new std::vector<int>();
    for(int j = 0; j < i; j++) {
        vec->push_back(j);
    }
    lists.push_back(vec);
}

Of course it is better to use an std::vector<std::shared_ptr<std::vector<int> > > as your type for lists. That way, you do not need to do manual memory management.