C++: how to understand iterators and remove elements from a vector

Question

I have two vectors. "Points" is my original array of points. "Chosen" is a collection of points to be deleted from "Points". I would like take unique ids of points from "Chosen", assign them to iterator and just erase such points. But somehow I can't do it.

Secondly, in the examples I studied I can't understand, how an iterator is linked to a definite vector. Hope with your help I'll understand iterators.

#include <StdAfx.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;
struct SPoint
{
    int id;
    int X;
    int Y;
};

vector<SPoint> points;
vector<SPoint> chosen;
vector<SPoint> cleared;

vector<SPoint>::iterator it;

void print_vect(const vector<SPoint> & vect)
{
    for (int i = 0; i < vect.size(); ++i)
    {
        cout << vect[i].id << " (" << vect[i].X << "," << vect[i].Y << ")"<<endl;               
    }           

    cout << endl;   
}
bool compare(double val1, double val2)
{
    return val1 > val2;
}
void sort_points(vector<SPoint> & vect, char command)
{
    bool cmp_result;
    SPoint temp;
    bool sorted=true;
    for (int i = 0; i < vect.size()-1 ; i++)
    {
        sorted=true;
        for (int j = 1; j <= vect.size()-1; j++)
        {
            switch (command) 
            {
                case 'x': 
                    {
                        cmp_result = compare(vect[j-1].X, vect[j].X); 
                        break;
                    }
                case 'y': 
                    {
                        cmp_result = compare(vect[j-1].Y, vect[j].Y); 
                        break;              
                    }               
                case 'i': 
                    {
                        cmp_result = compare(vect[j-1].id, vect[j].id); 
                        break;              
                    }           
            }

            if (cmp_result)
            {
                sorted = false;
                temp = vect[j-1];
                vect[j-1] = vect[j];
                vect[j] = temp;
            }

        }
        if (sorted) 
        {
            cout << "Sorted:" << endl;
            print_vect(vect);           
            break;
        }
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    SPoint temp;
    for (int i = 0; i < 10; i++)
    {
        temp.id = i;
        temp.X = i;
        temp.Y = i;
        points.push_back(temp);
    }

    for (int i = 5; i < 10; i++)
    {
        temp.id = i;
        temp.X = i;
        temp.Y = i;
        chosen.push_back(temp);
    }

    cout << "Points:" << endl;
    print_vect(points);
    cout << endl << endl;

    cout << "Chosen:" << endl;
    print_vect(chosen);

    system("pause");

    vector<SPoint>::iterator it;
    for (int i = 0;i < chosen.size(); i++)
    {       
        //points.erase(it);
    }   

    print_vect(points);
    system("pause");


    print_vect(cleared);
    system("pause");
    return 0;
}

What does _somehow I can't do it_ mean, what is the bug, and where is the _minimal_ code you wrote to reproduce it? — Useless, Jan 07 '13 at 15:09
i dont think that iterator is the right way to do that. iterators are for 'iterating' through the collection and do stuff. i think it will go even faster than moving through your vector using vector[i]. — Zaiborg, Jan 07 '13 at 15:13
well, it is there vector::iterator it; for (int i = 0;i < chosen.size(); i++). Then uncomment points.erase(it). I understand that if I cope to transfer int to the iterator it, that should work. But didn't manage to do it. — Kifsif, Jan 07 '13 at 15:14
// erase the first 3 elements: myvector.erase (myvector.begin(),myvector.begin()+3); so if you want to remove some values in the vector, it would be enough to pass a integer to erase() for specific removal, use something like `for (vector::iterator it = chosen.begin(); it != chosen.end(); ++it)`, compare the value in `*it` and then do stuff — Zaiborg, Jan 07 '13 at 15:18
I love how you use "do stuff" without thinking about possible implications, @Zaiborg — Bartek Banachewicz, Jan 07 '13 at 15:23
I can't transfer an int to erase. This method only works with iterators. vector::iterator it; for (int i = 0;i < chosen.size(); i++) { points.erase(chosen[i].id); }. This will bring error C2664: 'std::_Vector_iterator<_Myvec> std::vector<_Ty>::erase(std::_Vector_const_iterator<_Myvec>)' : cannot convert parameter 1 from 'int' to 'std::_Vector_const_iterator<_Myvec>' — Kifsif, Jan 07 '13 at 15:27

score 0 · Answer 1 · edited May 23 '17 at 12:04

0

In general, modifying the container that's being iterated over is a bad idea. Also note that if Chosen is not sorted, it will work in O(Points.size() * Chosen.size()) (+ reallocations); there's just no way other than comparing every element in Points to every element (until found or end) in Chosen. Thus, it would be a better idea to use set (or, even better, unordered_set) as a container for Chosen. Please also note that if you want to remove elements from the middle of the Points, it will have to do a lot of reallocations, and again, set or list would be a better idea.

You can pass additional predicate to std::sort to sort by a specific field of an object - you don't have to reimplement sort algorithm by yourself.

To check if the vector is sorted, you can use is_sorted method (or, if you are using old compiler, adjacent_find, as in here).

edited May 23 '17 at 12:04

Community

1
1

answered Jan 07 '13 at 15:16

Bartek Banachewicz

38,596
7
91
135

No, the idea is not like that. Look: id is unique. Then we can iterate through "chosen", just take the id and remove the element with the same id from "points". No iteration through a vector that we are modifying. – Kifsif Jan 07 '13 at 15:19
Uhm, how are you going to "remove the element with the same id from points" without iterating over it? – Bartek Banachewicz Jan 07 '13 at 15:21
If you pass an iterator to `points.erase`, *as requested in the question*, you are by definition iterating. That's how one acquires an *iterator*. – ssube Jan 07 '13 at 15:22
Bartek, vector seems to be a linced list. I suppose it is possible to remove an element from such a list. – Kifsif Jan 07 '13 at 15:31
1

@Kifsif what you said is totally untrue. `std::vector` is a contiguos memory array. I'd recommend you pick up a book about C++ standard library first. – Bartek Banachewicz Jan 07 '13 at 15:33
Well, I don't understand iterators. That is why I ask for a piece of advice. You tell me that if I use an iterator, I'm already iterating. And this is a bad idea to modify what is bein iterated through. But if erase works only with iterators, then it inevitably is iterating through the vecotor from which it removes an element. It is just like an infinite loop of what was the first: either an egg or a chicken. – Kifsif Jan 07 '13 at 15:41
@Kifsif You don't understand not only iterators, but `vector` and containers in general. You have to take a step back. – Bartek Banachewicz Jan 07 '13 at 15:43

score 0 · Answer 2 · answered Jan 07 '13 at 15:59

I am going to advise a drasic change: Don't use std::vector here, but use std::map instead, using the point's id as a key and the X/Y coordinates as value:

using namespace std;
struct SPoint
{
    int X;
    int Y;
};

map<int, SPoint> points;
vector<int> chosen; // only keeps chosen id's, not complete points

void print_points(const map<int, SPoint> & points)
{
    for (map<int, SPoint>::const_iterator i = points.begin(); i != points.end(); ++i)
    {
        cout << i->first << " (" << i->second.X << "," << i->second.Y << ")"<<endl;               
    }           

    cout << endl;   
}

int tmain(int argc, char* argv[])
{
    SPoint temp;
    for (int i = 0; i < 10; i++)
    {
        temp.X = i;
        temp.Y = i;
        points[i] = temp;
    }

    for (int i = 5; i < 10; i++)
    {
        chosen.push_back(i);
    }

    cout << "Points:" << endl;
    print_points(points);
    cout << endl << endl;

    system("pause");

    for (vector<int>::iterator it = chosen.begin(); it != chosen.end(); it++)
    {       
        points.erase(*it); // erase all points with id corresponding to the current value of chosen
    }   

    print_points(points);
    system("pause");
    return 0;
}

C++: how to understand iterators and remove elements from a vector

2 Answers2