Hi all,
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.Code:vector<vector<int> > f;
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!
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.
Originally Posted by brewbuck:
Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.
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.Originally Posted by Mario F.
Hope that made sense :S
QuantumPete
"No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
"Have you tried turning it off and on again?" - The IT Crowd
yes. I've done it this way:
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.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];
Have you considered std::map ??? It's a random access container that stores elements efficiently in a Red-Black tree.
QuantumPete
"No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
"Have you tried turning it off and on again?" - The IT Crowd
a multimap would do it, but does it preserve the element order between insert and lookup?
for example if I insert:
isCode:multimap<int, int> mm; mm.insert(make_pair<int, int>(1, 12)); mm.insert(make_pair<int, int>(1, 8));
guaranteed to put outCode: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 << " "; }
?Code:12 8
Last edited by pheres; 09-04-2007 at 06:25 AM.
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.
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.ok, thank you. I'll try that tomorrow, when my head it clear enough againIf 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.
>> 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.
