I need help with STL: vector
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 13 of 13

Thread: I need help with STL: vector

  1. #1
    Join Date
    Aug 2006
    Location
    Timisoara, Romania
    Posts
    433

    I need help with STL: vector

    please help me. I can't find how it's done.

    if I have this:

    Code:
    struct IT
    {
    int x, int y;
    };
    
    vector<IT*>myVars;
    if I have myVars filled with elements and I have:
    Code:
    vector<IT*>::iterator i;
    //somewhere here i gets to be one of the elements
    how can I delete the element i?
    erase() doesn't work well because it is a pointer to IT.
    "delete i;" doesn't work.

    please tell me how I can delete an element, if it is a pointer, and I only have an iterator to it.

  2. #2
    Join Date
    Jun 2010
    Location
    Germany
    Posts
    2,583

    Re: I need help with STL: vector

    If the pointer to the struct stored in the vector is the only pointer to that object (and that object has actually been dynamically allocated using new) you would need to both delete *i; and myVars.erase(i);. But in this case it wouldn't have made sense to store an IT* instead of the IT object itself in the vector in the first place.
    I was thrown out of college for cheating on the metaphysics exam; I looked into the soul of the boy sitting next to me.

    This is a snakeskin jacket! And for me it's a symbol of my individuality, and my belief... in personal freedom.

  3. #3
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,888

    Re: I need help with STL: vector

    Part of the problem is that you aren't specific enough about what exactly you're trying to do. Deleting what the pointer is directed at is a different operation than removing the pointer from the container.

    In fact, it's generally a good idea *not* to make a vector of raw pointers. You should either use a vector<IT> if possible, or if you really do need pointer semantics, then consider a vector<shared_ptr<IT>> or a vector<unique_ptr<IT>>. Leveraging smart pointers will make your life much easier.

    In order to delete the object specified by the pointer in the container, presuming the object was previously created using "new", you can do:
    delete *i; (dereferencing the iterator gives you the pointer)
    To remove the pointer from the container, you can do:
    myVars.erase(i);

  4. #4
    Join Date
    Aug 2006
    Location
    Timisoara, Romania
    Posts
    433

    Re: I need help with STL: vector

    thanks a lot for explaining. I didn't know that
    Code:
    delete *i;
    is a valid thing. but now I also understand why.

    it seems that though I was not specific enough, you explained what troubled me. thanks.

    one more question I have though:
    when should I use the deque and when should I use the vector? It seems I've always had a preference for deque. are there circumstances where a vector is better to use?

  5. #5
    Join Date
    Oct 2002
    Location
    Austria
    Posts
    1,284

    Re: I need help with STL: vector

    Access to the elements ( via operator [] ) is generally cheaper for a vector. A deque is the better choice if you have to add and remove elements on both ends of the container.
    Kurt

  6. #6
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,888

    Re: I need help with STL: vector

    Quote Originally Posted by Feoggou View Post
    when should I use the deque and when should I use the vector? It seems I've always had a preference for deque. are there circumstances where a vector is better to use?
    The primary difference is that a vector is guaranteed to store elements contiguously, while a deque will not. This means that if you need to pass a pointer to an array to some function, and you'd like to use an STL container to hold that array's memory, you need to use a vector and pass &v[0] as the pointer. (Note, don't do this if the vector is empty!)

    Another advantage of the vector is that it's slightly faster in general provided you can preallocate the maximum size using reserve() or you aren't doing much resizing.

    A deque may be faster (a) if you need to do insertions/removals at places other than the back (although, for insertions/removals in the middle, a list is faster still), or (b) you can't predict the maximum size well and it is potentially very large.

    A deque also has the nice property that references to its elements remain valid as long as they are in the deque (although iterators do not), which is something a vector can't claim----any insert() or erase() on a vector will invalidate all references to elements *and* all iterators.

    As always, relative speeds are only estimates. You'll need to profile both options with full optimization to determine which container is faster in your particular case.

    One additional case: a vector<bool> will use a special compression scheme to store each bool in a single bit, while a deque<bool> will not. One or the other may be more appropriate in particular cases.
    Last edited by Lindley; February 8th, 2011 at 02:57 PM.

  7. #7
    Join Date
    Jun 2010
    Location
    Germany
    Posts
    2,583

    Re: I need help with STL: vector

    I, personally, would always prefer the vector, for its simpler internal implementation that probably leads to more efficiency and the fact that the elements are stored contiguously, unless I need the deque's push_front() and/or pop_front() features.

    As I interpret the cplusplus.com documentation on std::deque, its different internal implementation may lead to a more efficient insert()/erase(), but if I really want that I would likely prefer the std::list which guarantees that, but then this container doesn't provide random access.

    The perfect choice of container very much depends on the specifics of the situation you need it in, therefore I find it hard to give general recommendations about that without being somehow vague.
    I was thrown out of college for cheating on the metaphysics exam; I looked into the soul of the boy sitting next to me.

    This is a snakeskin jacket! And for me it's a symbol of my individuality, and my belief... in personal freedom.

  8. #8
    Join Date
    Aug 2006
    Location
    Timisoara, Romania
    Posts
    433

    Re: I need help with STL: vector

    do you have an idea or a link to describe how they are implemented like?
    I mean, if deque is actually a double-ended queue (which should be a double ended list), isn't the vector also a double ended list?
    if not, what is it? is it a normal vector which, at insertions/deletions to be destroyed and then reconstructed with the specified size?
    Last edited by Feoggou; February 8th, 2011 at 04:24 PM.

  9. #9
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,888

    Re: I need help with STL: vector

    A vector is essentially a dynamic array, using the optimal "reallocate with double the size whenever you run out of space" algorithm.

    A list is a standard doubly-linked list.

    A deque is kind of like a linked list of small arrays. Because more than one element is allocated in each list node, it doesn't require nearly as many allocations as a list; and it can do bookkeeping to allow constant-time random access. But insertions at the front or back don't need to move existing elements at all, which is its big win.

  10. #10
    Join Date
    Aug 2006
    Location
    Timisoara, Romania
    Posts
    433

    Re: I need help with STL: vector

    thanks a lot for all your help.

  11. #11
    Join Date
    Jan 2001
    Posts
    251

    Re: I need help with STL: vector

    Quote Originally Posted by Lindley View Post
    any insert() or erase() on a vector will invalidate all references to elements *and* all iterators.
    An erase() on a vector will only invalidate elements after the erase location - iterators to elements before the erase location remain valid.

    An insert() on a vector will only invalidate elements after the insert location unless a reallocation occurs. If no reallocation occurs, iterators to elements before the insert location remain valid. If a reallocation occurs, all iterators are invalidated.

  12. #12
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,888

    Re: I need help with STL: vector

    Quote Originally Posted by jwbarton View Post
    An erase() on a vector will only invalidate elements after the erase location - iterators to elements before the erase location remain valid.
    That's true, but rarely a useful distinction. The only time I could imagine it being interesting is for erasing a number of elements back-to-front, and for that the erase/remove_if idiom is better anyway.

    An insert() on a vector will only invalidate elements after the insert location unless a reallocation occurs. If no reallocation occurs, iterators to elements before the insert location remain valid. If a reallocation occurs, all iterators are invalidated.
    Also true, but relying on this creates "precarious" code which could be easily broken by a later (seemingly unrelated) change. I wouldn't recommend it.

  13. #13
    Join Date
    Jan 2001
    Posts
    251

    Re: I need help with STL: vector

    I too wouldn't recommend using this, but anyone using STL should still be aware of how it works.

    There are guarantees provided by the standard for each container which specify exactly how and when iterators become invalidated.

    I think anyone using a container benefits from knowing exactly how it allocates memory, and how this affects the iterators to the container.

    Best regards,
    John

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center