CODEWITHSUNDEEP
c++iterator
There is nothing we can do
There is nothing we can do

Reputation: 24695

Strange iterator behaviour

#include "stdafx.h"

int _tmain(int argc, _TCHAR* argv[])
{
    string s = "Haven't got an idea why.";
    auto beg =  s.begin();
    auto end = s.end();
    while (beg < end)
    {
        cout << *beg << '\n';
        if (*beg == 'a')
        {//whithout if construct it works perfectly
            beg = s.erase(beg);
        }
        ++beg;
    }
    return 0;
}

Why if I erase one or more chars from this string this code breaks? I suppose it has something to do with returned iterator after erase operation being created at higher address than end iterator but I'm not sure and it surely isn't right behaviour. Or is it?

Upvotes: 0

Views: 195

Answers (6)

JSawyer
JSawyer

Reputation: 87

You have to iterate from .end()-1 to .begin(). At the same time, it is not safe to use comparison operators other than == and !=.

Here's my code:

    vector<long long> myVector (my, my+myCount);
    //sort and iterate through top correlation data counts
    sort (myVector.begin(), myVector.end());
    cout << endl;
    int TopCorrelationDataCount = 0;
    bool myVectorIterator_lastItem = false;
    vector<long long>::iterator myVectorIterator=myVector.end()-1;
    while (true) {                      
        long long storedData = *myVectorIterator;
        cout << TopCorrelationDataCount << " " << storedData << endl;                       

        //prepare for next item
        TopCorrelationDataCount++;
        //if (TopCorrelationDataCount >= this->TopCorrelationDataSize) break;
        if (myVectorIterator_lastItem) break;
        myVectorIterator--;
        if (myVectorIterator==myVector.begin())
        {
            myVectorIterator_lastItem = true;
        }
    }

Note: It can't be done using an ordinary for, because you have to find out if ==.begin(). If it is, this will be your last iteration. You can't check if ==.begin()-1, as it will result in run time error.

If you only want to use to X items in a vector, use TopCorrelationDataCount.

Upvotes: 0

Marcelo Cantos
Marcelo Cantos

Reputation: 186078

There are several problems with this code.

  1. Don't cache the value of s.end(); it changes as you delete elements.
  2. Don't use beg < end. The idiomatic approach is to write beg != end. If you try to iterate past end, the result is undefined, and a debug version of the string library may deliberately crash your process, so it is meaningless to use <.
  3. The iterator returned from s.erase(beg) might be s.end(), in which case ++beg takes you past the end.

Here's a (I think) correct version:

int _tmain(int argc, _TCHAR* argv[])
{
    string s = "Haven't got an idea why.";
    for (auto beg = s.begin(); beg != s.end();)
    {
        cout << *beg << '\n';
        if (*beg == 'a')
        {//whithout if construct it works perfectly
            beg = s.erase(beg);
        }
        else
        {
            ++beg;
        }
    }
}

EDIT: I suggest accepting FredOverflow's answer. It is simpler and faster than the above.

Upvotes: 8

Pardeep
Pardeep

Reputation: 949

On calling erase operation, stored end iterator pointer becomes invalid. So, use s.end() function in while loop condition

Upvotes: 1

fredoverflow
fredoverflow

Reputation: 263350

Erasing elements one by one from vectors or strings has quadratic complexity. There are better solutions with linear complexity:

#include <string>
#include <algorithm>

int main()
{
    std::string s = "Haven't got an idea why.";
    s.erase(std::remove(s.begin(), s.end(), 'a'), s.end());
    std::cout << s << std::endl;
}

Upvotes: 6

Loki Astari
Loki Astari

Reputation: 264669

Note the semantics of a basic_string and it's iterators.

From www.ski.com/tech/stl

Note also that, according to the C++ standard, basic_string has very unusual iterator invalidation semantics. Iterators may be invalidated by swap, reserve, insert, and erase (and by functions that are equivalent to insert and/or erase, such as clear, resize, append, and replace). Additionally, however, the first call to any non-const member function, including the non-const version of begin() or operator[], may invalidate iterators. (The intent of these iterator invalidation rules is to give implementors greater freedom in implementation techniques.)

Also what happens if 

 beg = s.erase(beg);

Returns an iterator equivalent to end()

Upvotes: 1

Daniel Daranas
Daniel Daranas

Reputation: 22644

The previous s.end() value stored in end is invalid after s.erase(). Hence, do not use it.

Upvotes: 4

Related Questions