Pointer To A Vector Elements While Still Adding

Discussion in 'C++' started by Adam Hartshorne, Mar 26, 2005.

  1. Hi All,

    I have the following problem, and I would be extremely grateful if
    somebody would be kind enough to suggest an efficient solution to it.

    I create an instance of a Class A, and "push_back" a copy of this into a
    vector V. This is repeated many times in an iterative process.

    Ok whenever I "push_back" a copy of Class A, I also want to assign a
    pointer contained in an exisiting instance of a Class B to this
    particular newly "pushed_back" to a particular instance of Class A in
    Vector V. When another push_back occurs I want the same to occur, but
    this pointer might be contained in a different instance of Class A.

    I am concerned because of the changing size of the vector due to new
    instances of Class A been added might cause a simple pointer to become
    invalid.

    Adam
     
    Adam Hartshorne, Mar 26, 2005
    #1
    1. Advertisements


  2. vector::reserve().
     
    Ioannis Vranos, Mar 26, 2005
    #2
    1. Advertisements

  3. Hi All,

    I have the following problem, and I would be extremely grateful if
    somebody would be kind enough to suggest an efficient solution to it.

    I create an instance of a Class A, and "push_back" a copy of this into a
    vector V. This is repeated many times in an iterative process.

    Ok whenever I "push_back" a copy of Class A, I also want to assign a
    pointer contained in an exisiting instance of a Class B to this
    particular newly "pushed_back" to a particular instance of Class A in
    Vector V. When another push_back occurs I want the same to occur, but
    this pointer might be contained in a different instance of Class A.

    I am concerned because of the changing size of the vector due to new
    instances of Class A been added might cause a simple pointer to become
    invalid.

    Adam
    i think you have misunderstood my question. From what I understood
    reserve(), reserves space for n elements in a vector.

    I what to have pointers to the elements in the vector, but am concerned
    if this is valid due to changing the size of the vector by adding new
    elements.

    Adam
     
    Adam Hartshorne, Mar 26, 2005
    #3
  4. Is there any reason you have to use a vector ? Your usage model suggests that
    another class would be more appropriate.

    Cheers,
     
    Donovan Rebbechi, Mar 26, 2005
    #4
  5. While I am running this process, I have no idea what the final size of
    Vector V will be, as it dependent on a set of runtime input data.

    I suppose I could use a list, but I would suggest I would have the same
    problem, that I require pointers to elements in the vector/list, and I
    am under the impression that when I add another element during the next
    iteration, the first pointer to Vector V that was set become invalid.

    Adam
     
    Adam Hartshorne, Mar 26, 2005
    #5

  6. If you reserve enough (unallocated) space for vector (while its size
    remains the same), when you push_back things the elements will not be
    moved and you gain in run-time too, because no reallocation takes place.

    However as Donovan said, if you use this vector in this way only
    (push_back), you had better use list (or deque). Check on page 464 of
    TC++PL 3 for the container costs.
     
    Ioannis Vranos, Mar 26, 2005
    #6

  7. No, list does not reallocate objects and also provides more efficient
    back operation than vector. If you want to have operator[] then you may
    use deque.
     
    Ioannis Vranos, Mar 26, 2005
    #7
  8. So are you saying that if I do the following this is valid, but if
    newList was actually std::vector<Class A> it would not be? Also my real
    quesiton all along has been what do I put where all the ???? are so that
    pointerClass has a pointer to the element in the list where
    newClasssA is stored?

    std::vector<Class B> pointerClassVector
    std::list<Class A> newList

    for (.......) {

    list.push_back(newClassA) ;
    pointerClass.addPointer(????) ;

    }

    Adam
     
    Adam Hartshorne, Mar 26, 2005
    #8
  9. You have a couple of choices:

    1. Store A in a container that does not invalidate outstanding
    iterators on push_back. std::list will do. Or if you want to deal
    strictly with pointers (as you seem to), std::deque also qualifies.

    2. Instead of storing pointers or iterators to A in B, instead store
    indices. The index never invalidates unless the position of A in the
    vector changes. And you can always convert an index to a
    vector<A>::iterator or vector<A>::pointer in constant time.

    -Howard
     
    Howard Hinnant, Mar 26, 2005
    #9
  10. Ok so if I use a list things should be fine. The outstanding question
    still holds, how do I point at the new element that has just been added
    to the list using push_back?

    What do I need to put where the ???, given that setClassAPointer sets
    the pointer in the particular ClassB to the element in the list that has
    just been added?

    std::vector<ClassB> classBs
    std::list<ClassA> classAs

    for(.....) {

    classAs.push_back(ClassA(init)) ;
    classBs.setClassAPointer(?????)
     
    Adam Hartshorne, Mar 26, 2005
    #10
  11. So vector is inappropriate.
    No. list iterators (and you really should be using iterators, not pointers,
    as placeholders!) are not invalidated by insertion.
    Well that's a problem for vectors, but not for lists. You need to rearrange
    elements in a vector to reallocate or insert because of the fact that vectors
    occupy contiguous memory. lists do not (each node stores the address of the
    next node), so adding new elements (even inserting into the middle) does not
    require copying/moving any of the old elements.

    Cheers,
     
    Donovan Rebbechi, Mar 27, 2005
    #11

  12. Yes, when you exceeded the reserved space, the implementation would
    reserve additional (of the default amount one), and it would not be
    guaranteed that objects would remain in the same place, but could be
    moved to another location.






    If you can store list<A>::iterators instead of pointers it would be better.


    For list iterators you would do:


    std::vector<Class B> pointerClassVector;


    //Class B accepts list<A>::iterator
    std::list<Class A> newList;

    for (.......) {

    newlist.push_back(newClassA) ;
    pointerClass.addPointer(newlist.end()) ;

    }



    Otherwise in pointer case, for the last added object, you can do:

    pointerClass.addPointer( &newlist.back() );
     
    Ioannis Vranos, Mar 27, 2005
    #12
  13. Adam Hartshorne

    Jerry Coffin Guest

    Adam Hartshorne wrote:

    [ ... ]
    You've gotten some advice on how to make this work (e.g. using
    std::list instead of vector).

    Another possibility would be to simply avoid the problem, instead
    storing a (probably reference counted) smart pointer to A in both B and
    V. This renders reallocation in the vector irrelevant.

    As to choosing between a vector and a list: I haven't seen you say much
    about how your using things that indicates one way or the other, but my
    experience is that good uses for linked lists are actually fairly
    unusual. While they support constant-speed insertion or deletion in the
    middle of the collection, they require linear traversal to find a
    particular spot in the collection to do that, so unless the spot where
    insertion or deletion will take place is known ahead of time, the
    operatin as a whole is still linear. Worse, since each node is
    typically separately allocated, with links between them, they also
    typically have relatively poor locality of reference, so that linear
    traversal is typically relatively slow as well.

    Now, it's true that when traversing a vector of smart pointers you'll
    have to dereference the pointers to find the objects, so you also lose
    locality of reference vs. a vector of objects -- but assuming the
    vector is sorted, you can do a binary search instead of a linear
    search, reducing the number of times this has to be done (and if the
    vector _isn't_ going to be sorted, then you probably don't have a
    reason to insert/delete in the middle, so you weren't gaining anything
    from using a list anyway).

    Don't get me wrong: lists can be useful -- but I don't think avoiding
    reallocation, by itself, constitutes a good reason to choose them.
     
    Jerry Coffin, Mar 27, 2005
    #13


  14. I think this is incorrect: Adam would not want to push end(),
    but (end()-1) - which cannot be written as is because list
    does not provide a random-access iterator.

    The following would compile (for iterators that are not built-in types):
    pointerClass.addPointer( --newlist.end() ) ;


    Yep -- and this is not necessarily an inferior solution...


    Regards,
    Ivan
     
    Ivan Vecerina, Mar 27, 2005
    #14
  15. Adam Hartshorne

    John Carson Guest

    Is that a fact? Run this code:

    double start, finish;
    list<int> l;
    vector<int> v;

    const size_t loopSize = 1000000;

    start = (double)clock();
    for(int i=0; i<loopSize; ++i)
    l.push_back(5);
    finish = (double)clock();
    cout << "List elapsed time is ";
    cout << (finish - start)/CLOCKS_PER_SEC << endl;

    start = (double)clock();
    for(int i=0; i<loopSize; ++i)
    v.push_back(5);
    finish = (double)clock();
    cout << "Vector elapsed time is ";
    cout << (finish - start)/CLOCKS_PER_SEC << endl;

    Vectors have an advantage with large sizes. To even things up a little, lets
    consider 1000 element arrays and add 100 elements to each:

    const size_t arraySize = 10000;
    const size_t pushSize = 100;

    list<int> l_array[arraySize];
    vector<int> v_array[arraySize];

    start = (double)clock();
    for(int i=0; i<arraySize; ++i)
    {
    for(int j=0; j<pushSize; ++j)
    l_array.push_back(5);
    }
    finish = (double)clock();
    cout << "List array elapsed time is ";
    cout << (finish - start)/CLOCKS_PER_SEC << endl;

    start = (double)clock();
    for(int i=0; i<arraySize; ++i)
    {
    for(int j=0; j<pushSize; ++j)
    v_array.push_back(5);
    }
    finish = (double)clock();
    cout << "Vector array elapsed time is ";
    cout << (finish - start)/CLOCKS_PER_SEC << endl;

    On my computer at least, you need to get the number of inserted elements
    down to around 10 before the list can compete with the vector in terms of
    speed.
     
    John Carson, Mar 27, 2005
    #15



  16. You are right.


    It can be written as:

    pointerClass.addIterator(--newlist.end());





    Well if you consider that you can increment the stored iterator to access the next element
    or decrement it to access the previous element, while you can't do that with the pointers,
    I can not see any real benefit of using pointers.



    --
    Ioannis Vranos

    http://www23.brinkster.com/noicys

    [I am using 90 characters word-wrapping - (800/640) *72= 90. If someone finds it
    inconvenient, please let me know].
     
    Ioannis Vranos, Mar 27, 2005
    #16
  17. The above should have been:

    "No, list does not reallocate objects and thus provides more efficient back operation than
    vector, when reallocations take place".




    The above in my system produces:

    C:\c>temp
    List elapsed time is 0
    Vector elapsed time is 0

    C:\c>



    Your code tweaked and improved:

    #include <list>
    #include <vector>
    #include <ctime>
    #include <iostream>
    #include <ostream>
    #include <limits>

    int main()
    {
    using namespace std;

    clock_t start, finish, temp;

    list<int> l;
    vector<int> v;

    const unsigned long loopSize = numeric_limits<unsigned long>::max()/1000;

    // Wait to begin from a clear tick for accurate results
    for(temp=start=clock(); start-temp!=0; start=clock())
    ;

    for(unsigned long i=0; i<loopSize; ++i)
    l.push_back(5);

    finish = clock();

    cout << "List elapsed time is ";
    cout << (finish - start)/CLOCKS_PER_SEC << endl;

    // Wait to begin from a clear tick for accurate results
    for(temp=start=clock(); start-temp!=0; start=clock())
    ;

    for(int i=0; i<loopSize; ++i)
    v.push_back(5);

    finish = clock();

    cout << "Vector elapsed time is ";
    cout << (finish - start)/CLOCKS_PER_SEC << endl;
    }


    C:\c>temp
    List elapsed time is 2
    Vector elapsed time is 0

    C:\c>


    Of course if I had reserved enough space for vector before, they would have the same
    performance.

    Check the table in 17.1.2 on page 464 of TC++PL3.






    Vectors have no additional time-cost advantage than lists for back operations, list has
    O(1) while vector has O(1)+ (the + is when reallocations take place). You have O(1) for
    back operations with vector while its size() is smaller its capacity() (which can be
    adjusted with reserve()).





    I used a larger number than your initial one in my code and got 2 seconds difference.
    Compiler MINGW GCC 3.4.2, PC: 1 GHz/1GB, Windows XP.



    --
    Ioannis Vranos

    http://www23.brinkster.com/noicys

    [I am using 90 characters word-wrapping - (800/640) *72= 90. If someone finds it
    inconvenient, please let me know].
     
    Ioannis Vranos, Mar 27, 2005
    #17
  18. for(unsigned long i=0; i<loopSize; ++i)
    v.push_back(5);

    The results remain the same in my system.


    --
    Ioannis Vranos

    http://www23.brinkster.com/noicys

    [I am using 90 characters word-wrapping - (800/640) *72= 90. If someone finds it
    inconvenient, please let me know].
     
    Ioannis Vranos, Mar 27, 2005
    #18


  19. Why did you 'snip' here these two lines from my previous post?
    : The following would compile (for iterators that are not built-in types):
    : pointerClass.addPointer( --newlist.end() ) ;

    We knew ;)


    If that is the case, the iterator is the obvious choice.
    Using pointers:
    - avoids exposing they type of container used for the storage
    of the elements (encapsulation, fewer dependencies)
    - allows you to use containers other than std::list
    (such as std::deque, which could be preferred)
    I don't think it is a good idea, because quotes of most of your
    lines will get truncated by other NG engines that wrap at
    a shorter line length...

    Cheers,
    Ivan
     
    Ivan Vecerina, Mar 27, 2005
    #19



  20. Well, I just noticed that. It was a mistake (probably I did not read it much, and
    considered it was talking about the pointers version).



    Do you mean, if that is true? If you mean that, yes it is true. But I feel like you meant
    something else(?).


    Well, a typedef can solve these issues.


    Are there Usenet servers that wrap their messages? I am not sure about that. The 72
    characters width is a Usenet netiquette thing, making the messages viewable in various
    resolutions. The 72 characters were suitable for 640x480 resolutions, however I think that
    now this rule needs an upgrade. Consider it as an improved version of the old rule. :)

    90 characters are suitable for 800x600 resolution, plus it provides some more useful space
    to write text and code. :)



    --
    Ioannis Vranos

    http://www23.brinkster.com/noicys

    [I am using 90 characters word-wrapping - (800/640) *72= 90. If someone finds it
    inconvenient, please let me know].
     
    Ioannis Vranos, Mar 27, 2005
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.