build a vector of vectors, sizes not known

This is a discussion on build a vector of vectors, sizes not known within the C++ Programming forums, part of the General Programming Boards category; Hi all, Code: vector<vector<int> > f; I want to fill this vector in a nested loop. problem is, that I ...

  1. #1
    Registered User
    Join Date
    Nov 2006
    Posts
    519

    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. #2
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,511
    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.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    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.

  3. #3
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by Mario F. View Post
    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.

    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

  4. #4
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    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. #5
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    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

  6. #6
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    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
    ?
    Last edited by pheres; 09-04-2007 at 06:25 AM.

  7. #7
    Registered User
    Join Date
    Jan 2005
    Posts
    7,340
    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. #8
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    Quote Originally Posted by Daved View Post
    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. #9
    Registered User
    Join Date
    Jan 2005
    Posts
    7,340
    >> 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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. PlaySound
    By cangel in forum C++ Programming
    Replies: 16
    Last Post: 10-08-2009, 05:29 PM
  2. Vectors
    By naseerhaider in forum C++ Programming
    Replies: 11
    Last Post: 05-09-2008, 08:21 AM
  3. How can i made vectors measuring program in DevC++
    By flame82 in forum C Programming
    Replies: 1
    Last Post: 05-07-2008, 02:05 PM
  4. How properly get data out of vectors of templates?
    By 6tr6tr in forum C++ Programming
    Replies: 4
    Last Post: 04-15-2008, 10:35 AM
  5. Boom, Headoshot!!
    By mrafcho001 in forum A Brief History of Cprogramming.com
    Replies: 50
    Last Post: 07-21-2005, 08:28 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21