Practice with Iterators

[RastaWolf]

Hey Everyone,

Today it is my goal to practice with iterators and become more comfortable with them. I decided to make a list using iterators as much as possible. I want to be able to add and remove items from the list. The container I used is a vector.

So far its gone pretty smooth but I have run into a snag. The snag is regarding removing items from the list. I'm not sure if there is a way to determine the location of an iterator in a vector, so I decided to use a counter, 'int c'.

Specifically my problem was removing the last item in the vector. My program would crash when I would attempt to remove it, leading me to believe my program is stepping out of bounds somewhere.

To my surprise, when I was attempting to set up a logical test to check for items not in the list, my problem with removing the last item was solved. Unfortunately, it proved to be a bad logical test and I'm not really sure why the previous problem was solved. My hunch is that the loop is breaking before it steps out of bounds somewhere. Is it not the case that v.end() is one location past the last item in the vector? If this is the case, wouldn't it be a good logical test that if an iterator was to equal v.end(), then whatever it was searching for isn't there?

I have commented out the section that solves the "removing last item problem" in the code below. I will also include the rest of the code just in case something is unclear.

  cout << "\nWhich item would you like to delete?: ";
                cin >> rem;
                response = toupper(response);
                int c = 0;
                for (iter = favG.begin(); iter != favG.end(); ++iter)
                {
                    if (*iter == rem)
                    {
                        favG.erase(favG.begin() + c);
                    }
                   /* if (iter == favG.end())
                    {
                        cout << "\nThat item is not in the list:" << endl;
                        break;
                    }*/
                    ++c;
                }

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cctype>


using namespace std;

int main()
{
    vector<string> favG;

    vector<string>::const_iterator iter;

    cout << "***   Welcome to your own list   ***\n";
    cout << "\nPlease add your first item: ";
    char response;
    string rem;
    string item;
    cin >> item;
    favG.push_back(item);

    while (response != 'E')
    {
        cout << "\nYour List:\n";
        for (iter = favG.begin(); iter != favG.end(); ++iter)
        {
            cout << *iter << endl;
        }
        if (favG.empty())
            cout << "Your list is empty!\n";
        cout << "\nType 'A' to add to the list\n";
        cout << "\nType 'D' to remove from the list\n";
        cout << "\nType 'E' to exit the program\n";
        cin >> response;
        response = toupper(response);

        if (response == 'A')
        {
            while (response != 'N')
            {
                cout << "\nEnter an item: ";
                cin >> item;
                favG.push_back(item);

                cout << "\nYour List:\n";
                for (iter = favG.begin(); iter != favG.end(); ++iter)
                {
                    cout << *iter << endl;
                }

                cout << "\nWould you like to add another item? (y,n): ";
                cin >> response;
                response = toupper(response);
            }
        }
        else if (response == 'D')
        {
            while (response != 'N')
            {
                cout << "\nYour List:\n";
                for (iter = favG.begin(); iter != favG.end(); ++iter)
                {
                    cout << *iter << endl;
                }
                cout << "\nWhich item would you like to delete?: ";
                cin >> rem;
                response = toupper(response);
                int c = 0;
                for (iter = favG.begin(); iter != favG.end(); ++iter)
                {
                    if (*iter == rem)
                    {
                        favG.erase(favG.begin() + c);
                    }
                   /* if (iter == favG.end())
                    {
                        cout << "\nThat item is not in the list:" << endl;
                        break;
                    }*/
                    ++c;
                }
                for (iter = favG.begin(); iter != favG.end(); ++iter)
                {
                    cout << *iter << endl;
                }
                cout << "\nWould you like to delete another item? (y,n): ";
                cin >> response;
                response = toupper(response);
            }
        }
        else
        {
            cout << "\nGoodbye" << endl;
        }
    }

    return 0;
}

[Disch]

As soon as you insert/erase an element in a vector, all iterators to that vector become invalid.

Also, if you already have an iterator 'iter' you don't need to keep track of a counter 'c'.


Anyway... the problem is here:

                for (iter = favG.begin(); iter != favG.end(); ++iter)  // <- A
                {
                    if (*iter == rem)
                    {
                        favG.erase(favG.begin() + c);  // <- B
                    }

Once 'B' happens and you erase the element from the vector, all your existing iterators (read: 'iter') become invalid. Basically like bad pointers. So once the loop continues, and reaches the 'A' line again... checking against favG.end() and/or incrementing iter is meaningless because iter is invalid at this point.

erase() returns an iterator for this very reason. The returned iterator is the position after the one you just erased (or end() if there were no more elements after it). You can use this to revalidate your iterator.

Note that this kind of loop typically is better as a while() loop because the erasing makes the incrementing conditional.

auto iter = favG.begin();
while(iter != favG.end())
{
    if( /* we want to erase this element */ )
    {
        iter = favG.erase( iter );
    }
    else
    {
        ++iter;
    }
}

[RastaWolf]

Thanks for your help Disch. I learned a lot from your explanation.

If I can ask a quick follow-up question.

If you didn't use 'auto' as the data type for 'iter', what would be the appropriate label?

I'm not experienced enough so I feel if I only want to use auto when I'm very sure of the original form.

Also I added an int i and set it equal to 1 if something gets erased. Is this a standard way of checking to see if an item is there are not?

so if i = 0, the item you're trying to delete is not in the list.

Thanks again!

auto iter = favG.begin();
int i = 0;
while(iter != favG.end())
{
    if( /* we want to erase this element */ )
    {
        iter = favG.erase( iter );
        i = 1;
    }
    else
    {
        ++iter;
    }
}

[Disch]

If you didn't use 'auto' as the data type for 'iter', what would be the appropriate label?

Same as you had it in your original code. std::vector<whatevertypeisinyourvector>::iterator for a normal non-const iterator. Or ...::const_iterator for a const iterator.

Since you have a vector of strings:

std::vector<std::string>::const_iterator iter = favG.begin();

Of course that is really long to type out, so auto is much easier. Also, it doesn't scale well, because if you decide to change your vector to a list or something in the future, then you have to change the 'iter' type as well, whereas if you use auto the iterator will change to the appropriate type automatically.

Also I added an int i and set it equal to 1 if something gets erased.

Avoid generic one-letter names unless what you're representing is clearly obvious. In the case of an iterator or loop counter, a variable name like 'i' is fine. But for anything else you want to be descriptive.

Something like 'entryErased' would be much more clear and would go a long way in telling other people (or yourself in 2 months) what your code is doing.

To take that clarity step a bit further, if the 'entryErased' variable only has 2 states, you might want to make it a bool, and use true and false rather than 0 and 1.

Is this a standard way of checking to see if an item is there are not?

For small scale projects it's a fine approach. However it does have one problem: erase is somewhat of an expensive operation in a vector, because erasing an element means you have to shift over elements after it.

This is no big deal if the vector is small, but if you have a vector of 10,000+ elements and you are erasing 50 of them... it can get expensive.

One way around this is to use the remove function in the algorithm header. The name is somewhat misleading because it doesn't modify the size of the vector. The reference page might explain it better:

http://www.cplusplus.com/reference/algorithm/remove/

But basically, remove will return an iterator that will be the new end of the vector. Then we can do a single erase() to erase all of them at once:

auto newEnd = std::remove( favG.begin(), favG.end(), "The thing to erase" );
if( newEnd == favG.end() )
{
    // elements not found in vector
}
else
{
    // elements found in vector
    entryErased = true;
    favG.erase( newEnd, favG.end() );  // erase all elements from newEnd and onward
}

[vlad from moscow]

There is no need to check whether the returned iterator is equal to the end iterator

auto newEnd = std::remove( favG.begin(), favG.end(), "The thing to erase" );
if( newEnd == favG.end() )
{
    // elements not found in vector
}
else
{
    // elements found in vector
    entryErased = true;
    favG.erase( newEnd, favG.end() );  // erase all elements from newEnd and onward
}

It may be written simpler

favG.erase( std::remove( favG.begin(), favG.end(), "The thing to erase" ), favG.end() );

This statement is valid even for empty vectors.

[Disch]

True, but then he gets no notification that any elements were removed.

[RastaWolf]

Thank you both Disch and Vlad for your thorough responses. It's a great help to a guy like me. Explanations from books are great, but explanations about specific questions from experienced programmers is an amazing resource that shouldn't be taken for granted.

I see what you mean about how taxing erase could be if its a larger vector, so I will become proficient at using remove.

Also, thanks for the tip about avoiding generic names for variables. I try to comment my code as much a possible but having more goal-specific names for variables would really improve the clarity of my code.

Using a bool would certainly make sense. Don't know why I'm so quick to try to solve things with 1's and 0's. True and false should be more intuitive.

again, thanks guys!