# Thread: build a vector of vectors, sizes not known

1. ## build a vector of vectors, sizes not known

Hi all,

Code:
vector<vector<int> > f;
I want to fill this vector in a nested loop. problem is, that I don't want to append the vectors from ground to top. also I do not know the final size of the (sub-)vectors.

so maybe it can happen that I want to set element f[4][6], next f[1][3] and so on.

how would you do that? should I check the size before every insert and increase it if needed? or is there something better for such a data structure type out there?

thank you!

2. I'm unsure as to what you mean.

I believe what you want is to control elements relative position within the vector; Your own personal sort. Is that it?

If you are working in a nested loop you pretty much have there a sequential framework for vector operations. This wouldn't be the right choice if you are instead using random access.

3. Originally Posted by Mario F.
This wouldn't be the right choice if you are instead using random access.
I agree. You'd need to keep a count of the allocated size so far and then re-allocate more elements in the vector before you try to access any elements that are greater than the allocated size.

QuantumPete

4. yes. I've done it this way:

Code:
// want to insert at [x][y]
check size of main vector against x -> resize if necessary;
check size of sub vector against y -> resize if necessary;
insert at [x][y];
My question was about alternative data structures which fit better to such uses in the first place. Sorry for making that not as clear as I should.

5. Have you considered std::map ??? It's a random access container that stores elements efficiently in a Red-Black tree.

QuantumPete

6. a multimap would do it, but does it preserve the element order between insert and lookup?

for example if I insert:

Code:
multimap<int, int> mm;
mm.insert(make_pair<int, int>(1, 12));
mm.insert(make_pair<int, int>(1, 8));
is
Code:
multimap<int, int>::iterator start_iter, end_iter;
start_iter = mm.equal_range(1).first;
end_iter = mm.equal_range(1).second;

for
(
multimap<int, int>::iterator iter = start_iter;
iter != end_iter;
iter++
)
{
cout << iter->second << " ";
}
guaranteed to put out
Code:
12 8
?

7. No, the map (or multimap) doesn't guarantee order preservation.

I think resizing the vector before insert is a fine way to go. I believe if you use a resize with a value smaller than the size it does nothing, so you can just call resize every time.

If you are going to be adding the data all at once (before you need to use it), then you could just use a vector<pair<int, int> >. Use push_back to add each element, then stable_sort to sort them with a special functor for sorting based on the first int. This will keep pairs with the same first int value in the same order you inserted them, but will sort everything by its first int. You can then use binary_search, equal_range, lower_bound and upper_bound to search for items in the vector. This has the added performance benefit over a map of not sorting while you insert, and a memory benefit over the vector of vectors of not wasting unneeded space.

8. Originally Posted by Daved
No, the map (or multimap) doesn't guarantee order preservation.

I think resizing the vector before insert is a fine way to go. I believe if you use a resize with a value smaller than the size it does nothing, so you can just call resize every time.
from http://www.sgi.com/tech/stl/Vector.html
void resize(n, t = T()) Sequence Inserts or erases elements at the end such that the size becomes n.
If you are going to be adding the data all at once (before you need to use it), then you could just use a vector<pair<int, int> >. Use push_back to add each element, then stable_sort to sort them with a special functor for sorting based on the first int. This will keep pairs with the same first int value in the same order you inserted them, but will sort everything by its first int. You can then use binary_search, equal_range, lower_bound and upper_bound to search for items in the vector. This has the added performance benefit over a map of not sorting while you insert, and a memory benefit over the vector of vectors of not wasting unneeded space.
ok, thank you. I'll try that tomorrow, when my head it clear enough again

9. >> void resize(n, t = T()) Sequence Inserts or erases elements at the end such that the size becomes n.
Oops. Thanks for checking the advice before use. I was probably thinking of reserve.