CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 12 of 12
  1. #1
    Join Date
    Dec 2003
    Location
    Atlanta, Georgia
    Posts
    11

    vector:erase iterator requirements

    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 ?
    Edward Diener

  2. #2
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: vector:erase iterator requirements

    The reverse iterator might work. I'm betting the const variants don't.

  3. #3
    Join Date
    Dec 2003
    Location
    Atlanta, Georgia
    Posts
    11

    Re: vector:erase iterator requirements

    Quote Originally Posted by Lindley View Post
    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.

    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.
    Edward Diener

  4. #4
    Join Date
    Jan 2008
    Location
    California, USA
    Posts
    822

    Re: vector:erase iterator requirements

    Hi
    Quote Originally Posted by eldiener View Post
    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.
    That's very true.
    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.
    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.
    My guess is that it implies the former.

  5. #5
    Join Date
    Dec 2003
    Location
    Atlanta, Georgia
    Posts
    11

    Re: vector:erase iterator requirements

    Quote Originally Posted by potatoCode View Post
    Hi

    That's very true.
    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.
    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".

    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.
    Edward Diener

  6. #6
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,721

    Re: vector:erase iterator requirements

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

  7. #7
    Join Date
    Jan 2008
    Location
    California, USA
    Posts
    822

    Re: vector:erase iterator requirements

    Quote Originally Posted by eldiener View Post
    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".
    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.

    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.
    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.
    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.
    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 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.

    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());
    Last edited by potatoCode; February 7th, 2010 at 12:14 PM. Reason: fixed some incomplete comments

  8. #8
    Join Date
    Aug 2005
    Location
    San Diego, CA
    Posts
    1,054

    Lightbulb Re: vector:erase iterator requirements

    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?

  9. #9
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: vector:erase iterator requirements

    Quote Originally Posted by kempofighter View Post
    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.

    They work just like normal iterators, but you should be careful of what "in front of" means when you insert with a reverse iterator...

  10. #10
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: vector:erase iterator requirements

    Quote Originally Posted by monarch_dodra
    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.

    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?
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  11. #11
    Join Date
    Aug 2005
    Location
    San Diego, CA
    Posts
    1,054

    Re: vector:erase iterator requirements

    Quote Originally Posted by laserlight View Post
    So what does Meyers say about using the erase member function(s) of say, std::vector with reverse iterators?

    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.

  12. #12
    Join Date
    Dec 2003
    Location
    Atlanta, Georgia
    Posts
    11

    Re: vector:erase iterator requirements

    Quote Originally Posted by kempofighter View Post
    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.
    Edward Diener

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured