I need help with STL: vector

[Feoggou]

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

if I have this:

struct IT
{
int x, int y;
};

vector<IT*>myVars;

if I have myVars filled with elements and I have:

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.

[Eri523]

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.

[Lindley]

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);

[Feoggou]

thanks a lot for explaining. I didn't know that

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?

[ZuK]

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

[Lindley]

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.

[Eri523]

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.

[Feoggou]

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?

[Lindley]

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.

[Feoggou]

thanks a lot for all your help.

[jwbarton]

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.

[Lindley]

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.

[jwbarton]

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