Serious vector issue

[ganbree]

Okay, I've got a serious problem with std::vector, the code I'm working with is huge and it's got vectors left, right and center. The problem is that one of the vectors is having to reallocate itself elsewhere. This is causing the references to point to random things.
For illustrative purposes:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> Vector1;
	Vector1.push_back(12);
	Vector1.reserve(1);

	std::vector<int>::reference Reference = Vector1[0];

	cout << Vector1.capacity() << " " << Reference << endl;

	vector<int> Vector2;
	Vector2.push_back(11);
	Vector1.reserve(2);

	cout << Vector1.capacity() << " " << Reference << endl;
	return 0;
}

Ive tried using int& , const int& , std::vector<int>::reference and the various iteratorts; none of them seem to be able to remain valid through the relocation. I cant think of any means to get around this, what should I do?

[Salem]

http://www.sgi.com/tech/stl/Vector.html
Read the footnotes.

> I cant think of any means to get around this, what should I do?
- Allocate enough space to begin with.
- Choose a different design which doesn't rely on preserving references for such an extended period of time.

> the code I'm working with is huge and it's got vectors left, right and center
Have you considered other data structures?

[ganbree]

So they're being invalidated.

My first thought was to create a 'smart' iterator that wouldnt be invalidated. But to do this it'd need to traverse the structure back from the stack allocated point; because these are vectors of objects containing vectors etc. that could be hard to write, the structure currently has theoretically unlimited depth, and the iterator would need to know what goes inside what, which I suppose could be done with some nasty RTTI.

I'm currently thinking that the solution is to use pointers, replace the vectors to objects with vectors to pointers to objects. Then instead of taking references I could copy the pointer value. Which wouldnt be moved around by vector. This'll probably lead to memory leaks.

Last option is changing the container type. I think std::list might be good but I need quick access by an index.

[ArkM]

I can't understand what the OP snippet illustrates. By the way, reserve member argument defines new total capacity but not capacity increment. Evidently, all pointers and references to vector elements are valid while v.size() <= v.capacity() . That's because std::vector must have continuous storage for all its elements (by standard requienment). It's impossible to keep previously allocated elements in place when the next size value > current capacity and new memory chunk is allocated.

Vector of pointers partially solves persistent pointers/references problem but creates lots of other problems (for example, catastrophic speed degradation for simple POD elements). Sometimes it's a proper solution but usually it's "a medicine which is worst than disease".

It seems the simplest way to go - see the last Salem's sentence:

Have you considered other data structures?

It's not so hard work to define your own intrusive container-like structure with list of fixed size arrays and fast index-to-array translation. I have used this approach, it works fine.