memory out of range Vector

Question

I'm writing this program why it throws an error in toupper('a')?

void test2(void) {
  string n;
  vector<string> v;
  auto it = v.begin();
  do {
    cout << "Enter a name of a fruit: ";
    cin >> n;
    v.push_back(n);
  } while (n != "Quit");
  v.erase(v.end() - 1);
  sort(v.begin(), v.end(), [](string g, string l) { return g < l; });
  dis(v);

  for (auto i : v) {
    if (i.at(0) == toupper('a')) {
      cout << i << endl;
      v.erase(remove(v.begin(), v.end(), i));
    }
  }
  dis(v);
}

Can someone help me to find the error?

BTW why don't you write `A` which is the same as `toupper('a')`?? Are you sure thie condition ist what you want:`(i.at(0) == toupper('a'))` ? Is this what you want: `(toupper(i.at(0)) == 'A')`? — Jabberwocky, Apr 20 '20 at 10:26
https://stackoverflow.com/questions/347441/erasing-elements-from-a-vector — 463035818_is_not_an_ai, Apr 20 '20 at 10:26
Don't modify a vector while you're range-looping over it. It will cause undefined behaviour. — molbdnilo, Apr 20 '20 at 10:28
@Jabberwocky yes, if I remove ```v.erase(remove(v.begin(), v.end(), i));``` it works fine — , Apr 20 '20 at 10:29
@Idriss you should be more specific about how it didn't work for you, so we can help — Aykhan Hagverdili, Apr 20 '20 at 10:38
Are you sure that all the `string`s in your `vector` aren't empty? If you have an empty `string` using `at` will throw an `std::out_of_range` exception. — WBuck, Apr 20 '20 at 10:41
Now it's ok, but it didn't remove all the strings start with 'a' ```for (auto it = v.begin(); it != v.end(); it++) { if(toupper(it->at(0))=='A') v.erase(remove(v.begin(), v.end(), *it)); }``` — , Apr 20 '20 at 10:45
@Idriss Didn't any of the answers you've gotten solve the problem? — Ted Lyngmo, Apr 23 '20 at 14:09

Lukas-T · Answer 1 · 2020-04-20T11:18:30.097

4

Since you already tried to implement the erase-remove-idiom, that's how it can be used in this case:

v.erase(std::remove_if(v.begin(), v.end(), [](const std::string &item) {
        return std::toupper(item.at(0)) == 'A';
}), v.end());

Here I assumed, that i.at(0) == toupper('a') is a typo and should be toupper(i.at(0)) == 'A'.

edited Apr 20 '20 at 11:18

answered Apr 20 '20 at 11:09

Lukas-T

11,133
3
20
30

1

OPs code removes only `A`, yours `a` and `A`. It is likely that this is what OP actually wants, but maybe worth a note – 463035818_is_not_an_ai Apr 20 '20 at 11:13
@idclev463035818 Yes, I assumed it would be a typo on OPs side, since WBucks answer handles it the same way. – Lukas-T Apr 20 '20 at 11:17

WBuck · Answer 2 · 2020-04-20T11:18:35.170

3

Write your deletion loop like this:

for ( auto it = std::begin( v ); it != std::end( v ); )
{ 
    if ( toupper( it->at( 0 ) ) == 'A' )
        it = v.erase( it );
    else 
        ++it;
}

If you do it the way you're doing it you'll invalidate the iterator and then never reassign it a valid iterator which is needed to correctly loop through the vector.

edited Apr 20 '20 at 11:18

answered Apr 20 '20 at 10:50

WBuck

5,162
2
25
36

Thank you, why like this way? why you wrote it=begin(v) and not it=v.begin()? – Apr 20 '20 at 10:54
A non-throwing alternative: `if (not it->empty() && toupper( (*it)[0] ) == 'A' )` – Ted Lyngmo Apr 20 '20 at 10:55
@Idriss Honestly, 6 in one, half dozen in the other. I like using the free functions but thats my personal preference – WBuck Apr 20 '20 at 10:55
@TedLyngmo I considered that, but I think that'll just muddy the waters. – WBuck Apr 20 '20 at 10:55
@WBuck but if the condition is true, 'it' won't increase! it's weird , I can't understand, can you explain a little bit please – Apr 20 '20 at 10:59
@Idriss see https://en.cppreference.com/w/cpp/container/vector/erase `erase` will return an iterator to the element after the one that was removed. – Lukas-T Apr 20 '20 at 11:02
@Idriss When you call `erase` it returns an `iterator following the last removed element`. In other words, it returns an `iterator` pointing to the next element in the `vector`. – WBuck Apr 20 '20 at 11:02
@WBuck :o that's awesome thank you guys – Apr 20 '20 at 11:04
1

sorry for the nitpick, "If you do it the way you're doing it you'll invalidate the iterator." you are also invalidating the iterator `it`, it just doesn't matter because in the same line you again assign a valid iterator to `it`. The iterator is invalidated in any case, the actual problem is using the invalidated iterator – 463035818_is_not_an_ai Apr 20 '20 at 11:11
@idclev463035818 True, regardless the `iterator` is being invalidated. Just it's being immediately reassigned a valid `iterator`. I was just trying to keep it as simple as possible. Thats also why I didn't show the `erase-remove-idiom`, just to keep it simple – WBuck Apr 20 '20 at 11:14
simple is completely ok with me, but your last sentence suggests that in your code no iterator is invalidated, which is not "simple" but wrong ;) – 463035818_is_not_an_ai Apr 20 '20 at 11:15
suggestion: If you do it the way you're doing it the range based loops is working on invalidated iterators – 463035818_is_not_an_ai Apr 20 '20 at 11:17
@idclev463035818 I changed the verbiage of the last line to better explain whats happening. – WBuck Apr 20 '20 at 11:20

score 0 · Answer 3 · answered Apr 20 '20 at 11:33

The problem here :

for (auto i : v) {
  if (i.at(0) == toupper('a')) {
    cout << i << endl;
    v.erase(remove(v.begin(), v.end(), i));
  }
}

is that you are modifying the vector inside the loop with erase() which invalidates the iterators used internally to implement the for range loop.

The loop is a syntactic sugar for something like this :

{

auto&& range = v;
auto&& first = std::begin(v); // obtained once before entering the loop
auto&& last = std::end(v); // obtained once before entering the loop

for (; first != last; ++first)
{
    auto i = *first; // first will be invalid the next time after you call erase()
    if (i.at(0) == toupper('a')) {
        cout << i << endl;
        v.erase(remove(v.begin(), v.end(), i)); // you are invalidating the iterators and then dereferencing `first` iterator at the beginning of the next cycle of the loop
    }
}

}

Why calling erase() invalidates the vector ? This is because a vector is like a dynamic array which stores its capacity (whole array size) and size (current elements count), and iterators are like pointers which point to elements in this array

So when erase() is called it will rearrange the array and decrease its size, so updating the end iterator and your first iterator will not be pointing to the next item in the array as you intended . This illustrates the problem :

std::string* arr = new std::string[4];
std::string* first = arr;
std::string* last = arr + 3;

void erase(std::string* it)
{
    std::destroy_at(it);
}

for (; first != last; ++first)
{
    if (some_condition)
        erase(first); // the last element in the array now is invalid
    // thus the array length is now considered 3 not 4
    // and the last iterator should now be arr + 2
    // so you will be dereferencing a destoryed element since you didn't update your last iterator
}

What to learn from this ? Never do something which invalidates the iterators inside for range loop.

Solution: Update iterators at each cycle so you always have the correct bounds :

auto&& range = v;
auto&& first = std::begin(v); // obtained once before entering the loop
auto&& last = std::end(v); // obtained once before entering the loop

for (; first != last;)
{
    auto i = *first;
    if (i.at(0) == toupper('a'))
    {
        first = v.erase(remove(v.begin(), v.end(), i));
        last = std::end(v);
    }
    else
    {
        ++first;
    }
}

that's great! but what's the meaning of invalidate an iterator? — , Apr 20 '20 at 13:04
To invalidate an iterator is to have it pointing to something that is invalid . For example a pointer pointing to a freed heap object or a pointer that points to an element that is out of the array bounds . generally you can think of iterators as pointers , in fact pointers are already iterators — dev65, Apr 20 '20 at 14:47

memory out of range Vector

3 Answers3