Printable View
In the two forms of vector::erase:
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
can the 'iterator' mentioned be a vector::const_iterator, vector::reverse_iterator, or vector::const_reverse_iterator as well as a vector::iterator ?
The reverse iterator might work. I'm betting the const variants don't.
I guess the question is really why the 'erase' functions are specified in terms of only iterator and not in terms of reverse_iterator also. After all a reverse_iterator will position the end-user within the vector just as well as a normal iterator does.Quote:
Originally Posted by Lindley
As for const_iterator, does this specify that one can not change the vector in any way through the const_iterator or does this specify only that one can not change the element to which the const_iterator "points" ? If the latter, then a const_iterator should be just as valid as an iterator for use in the 'erase' method.
Hi
That's very true.Quote:
Originally Posted by eldiener
As you know, the iterator can point to one element past the end in its sequence, the end element for the reverse iterator would mean (-1, N], i.e., the memory space which the allocator can't have the access to in its original sequence. Since vector::erase removes the element in the range of [first, last), this means that calling erase on reverse iterator would mean (first, last] deallocating the end() elements but never the first element in the original sequence where the first causes access violation, and the second fails to do its job fully.
My guess is that it implies the former.Quote:
As for const_iterator, does this specify that one can not change the vector in any way through the const_iterator or does this specify only that one can not change the element to which the const_iterator "points" ? If the latter, then a const_iterator should be just as valid as an iterator for use in the 'erase' method.
I believe you misunderstand the reverse_iterator. This is because the actual elements "pointed to" by the reverse_iterator are just as valid as the elements "pointed to" by the normal "iterator" no matter where the "pointer" of the reverse_iterator "points". I am aware that the reverse_iterator actually points from the regular iterator's end() element to the regular iterator's begin() element. But when you ask the reverse_iterator to access an element, it actually accesses the element that is one before the element to which it "points".Quote:
Originally Posted by potatoCode
So it does not matter how you view the range of the reverse_iterator, but only that the reverse_iterator actually "points" to valid elements to erase.
As for your supposition above the const_iterator I believe you are probably right and access to a vector with its const_iterator does mean that the vector itself can not be changed in any way through the const_iterator.
Still I would suppose that vector::erase should work equally as well wirh reverse_iterator as with iterator, so it is interesting that it should be limited to just iterator if that is what the C++ standard is actually saying. Notice also that for the vector::insert function the first parameter is always specified in terms of iterator and never reverse_iterator also.
I would guess that only a normal iterator works. Here is a subset
of the C++ standard for vector. Only "iterator" is given as
an option for erase.
Code:namespace std
{
template <class T, class Allocator = allocator<T> >
class vector
{
public:
// types:
typedef typename Allocator::reference reference;
typedef typename Allocator::const_reference const_reference;
typedef implementation defined iterator; // See 23.1
typedef implementation defined const_iterator; // See 23.1
typedef implementation defined size_type; // See 23.1
typedef implementation defined difference_type;// See 23.1
typedef T value_type;
typedef Allocator allocator_type;
typedef typename Allocator::pointer pointer;
typedef typename Allocator::const_pointer const_pointer;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
// skipping code
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
// skipping code
};
}
Actually, I have not misunderstood. The reason reverse_iterator returns *(iterator - 1) is to keep the iterator from dereferencing inaccessible area. Note that reverse_iterator uses current iterator with operator++ implmented on --current. you can view the implementations. Note also that reason std::vector doesn't support erase on reverse_iterators is, IMHO, doing so is probablly superflous since 5th iterator tag category is already implemented in vector, thus, overloading vector::erase just to support reverse_iterators is redudant. I suppose this is why reverse_iterator is inherited from iterator, rather than categorized as a iterator_tag.Quote:
Originally Posted by eldiener
You are right about reverse_iterator, but I think you're a bit confused about how vector::erase work. It's the vector::erase's range that would cause access violation, not the reverse_iterators. In addition, as I illustrated before, given that erase(rbegin(), rend()) would erase all but not the first, thus the member function fails to do what it promises.
Thinking about it little more, I think so since any changes made, or any operations that would cause std::allocator to alter its state would mean that the object is not const.Quote:
As for your supposition above the const_iterator I believe you are probably right and access to a vector with its const_iterator does mean that the vector itself can not be changed in any way through the const_iterator.
I have no doubt that it would since *(current - 1) returns an iterator traceable by the iterator_traits. But for the reasons I mentioned, I don't see the must need for it.Quote:
Still I would suppose that vector::erase should work equally as well wirh reverse_iterator as with iterator, so it is interesting that it should be limited to just iterator if that is what the C++ standard is actually saying. Notice also that for the vector::insert function the first parameter is always specified in terms of iterator and never reverse_iterator also.
EDIT:
Just so that we're on the same page here, you know that these iterators are implementation defined, and the meaning of bidirectional encompasses reverse.
EDIT2:
if my words aren't good enough, you can infer from the code below
Code:vector<int> v(5);
vector<int> b(v.rbegin(), v.rend());
To the OP, did you try any of the above by creating a small project to see if it compiles? Take a look at this:
http://cplusplus.com/reference/stl/vector/
Now notice the descriptions for the insert and assign functions which are declared as template functions where erase is not. In cases where the iterator's type is a template any type of iterator could be used. However in a case where the iterator is not a template there must be some constraint in the implementation. If you can find the code for the erase function you may be able to see this for yourself. My guess is that the constraint has to do with the fact that erasing requires elements to be copied so that the container's elements are still contiguous after the erase. If forward iterating the impl must be copying things from the end toward the beginning. If reverse iterating how would the impl know how to properly identify the location such that the elements can be properly copied after the erasure? It could have something to do with that.
I think that it is pretty clear what the limitation is by now. If you really want to know why then you'll probably have to study the implementation (if you can find, read, and understand it). Perhaps you'll have to ask yourself just what is a reverse iterator and how would a generic implementation of erase handle its responsibilties if the iterator type can be reverse or forward?
More effective stl by scott meyers has a chapter about reverse iterators, and more specifically, how to use them when you want to delete or insert.Quote:
Originally Posted by kempofighter
They work just like normal iterators, but you should be careful of what "in front of" means when you insert with a reverse iterator...
So what does Meyers say about using the erase member function(s) of say, std::vector with reverse iterators?Quote:
Originally Posted by monarch_dodra
Quote:
Originally Posted by laserlight
Good question. In fact item 26 specifically acknowledges the signature of erase and highights the iterator type specified by the interface. However the item doesn't really explain the details of why other than to suggest that iterators have special priveleges that no other iterator type has. Item 28 discusses converting a reverse_iterator to an iterator which is rather tricky for erasure. If the OP has the book I recommend reading those items. After reading them i still don't understand "why" particularly well but it certainly agrees with our conclusion that only iterator can be used with erase.
It has been explained to me elsewhere that because one can always get an iterator from a reverse_iterator, using the reverse_iterator::base() member function, there is no need to have erase also take a reverse_iterator. Also I do appreciate that however erase is actually implemented a revers_iterator does not directly "point" to the area of a vector to be erased. But I still think that the latter consideration is not important since an iterator is not really an address anyway.Quote:
Originally Posted by kempofighter