Confused about erasing elements in STL vector

[Minikloon]

Hi.

Let's say we got :
std::vector<Human> humans;
std::vector<Human*> selectedHumans;

You can select humans which are stored in 'humans'. The selection is saved in 'selectedHumans'. I can create new humans by adding them to 'humans'. I know that there won't be two same humans in 'humans', nor the same human selected twice in 'selectedHumans'.

What I want to do is to delete all the currently selected humans from the 'humans' vector.

What I'm doing right now is this :

for(int i = 0; i < selectedHumans.size(); ++i) {
	for(int j = 0; j < humans.size(); ++j) {
		if(&(humans[j]) == selectedHumans[i]) {
			humans.erase(humans.begin() + j);
			break;
		}
	}
} selectedHumans.clear();

But this strangely doesn't delete all of the selected humans in 'humans'.

Thanks.

[cire]

But this strangely doesn't delete all of the selected humans in 'humans'.

That's because when you erase one element, every element to the right of that element is moved to the left one slot. You then increase your index although there is a different object that you haven't processed at the current index.

Pointers to the elements that were moved, of course, aren't changed. They still point to the area in memory where the elements were previously stored.

[htirwin]

The thing you have to watch out for is that when you erase an element in the vector, the addresses of the vectors elements will not be the same anymore. The elements past the removed items will be shifted back in memory.

So the addresses of the selected humans will no longer coincide with the humans they did before the erase.

Also, when you add elements to a vector, it may need to re-size itself to accommodate for it's new size. It's not guaranteed that any of the memory addresses at all will be the same when this happens.

It's guaranteed that the items held by vector will be sequential in memory, but not guaranteed that the starting point will not change, and it likely will unless you reserve ahead of time enough memory to store all of the items you will every store in it.

It's best not to select them by address in this case, but instead select them by some other identifier like a member variables value. One possibility is to do something like this to give each Human a unique id.

class Human {

private:
    int id;
    static int next_id;
  
public:
    Human();
};

int Human::next_id = 0;

Human::Human() {
    id = next_id++;
}

[Minikloon]

I see.

But how would I go about fixing the pointers in selectedHumans?
Would using another container for humans be a good idea? If so, which one?

[Minikloon]

I fixed the problem by adding

for(int k = 0; k < selected.size(); ++k)
    --selected[k];

after erasing.

[htirwin]

If you're going to go that route, make sure you reserve enough memory that they wont need to re-size themselves, before you start populating them, otherwise when they re-size themselves, they may end up occupying a completely different chunk of memory.

selected_humans.reserve(humans.size());

If you don't know ahead of time how many humans you will have in the vector, you should probably use a different solution.

[cire]

If you can glean anything from this mess of code, you might check out the following:

The strategy is to use a container of std::pair<bool, value_type> in the container. value_type is std::string in the link and would be the human type in your code. In this way you don't need to use pointers or a seperate container to keep track of what is selected.

You can ignore the iterator/begin/end junk. It was a half-assed attempt at an iterator proxy so that the range-based for loop would work with the NameCollection (and the user wouldn't need to know we were storing a pair.) The only place in this code that it's relevant is inside the print function.

Without further adieu, you may find the code here: http://ideone.com/DMmKH1

[JLBorges]

> Would using another container for humans be a good idea?

Yes.

> If so, which one?

I know that there won't be two same humans in 'humans', nor the same human selected twice in 'selectedHumans'.

strongly suggests std::set<> or std::unordered_set<>

#include <set>
#include <string>
#include <iostream>

struct human
{
    human( const std::string& name ) : name(name) {}
    // ..
    const std::string name ;
    // ...
    bool operator< ( const human& that ) const { return name < that.name ; }
};

int main()
{
    std::set<human> humans { {"a"}, {"b"}, {"c"}, {"d"}, {"e"}, {"f"}, {"g"}, {"h"}, {"i"} } ;
    std::set< const human* > selected_hunans ;

    // select some humans
    for( const human& h : humans )
    {
        static bool select = false ;
        if( ( select = !select ) ) selected_hunans.insert( std::addressof(h) ) ;
    }

    std::cout << "\nhumans: " ; for( const human& h : humans ) std::cout << h.name ;
    std::cout << "\nselected: " ; for( const human* p : selected_hunans ) std::cout << p->name ;

    // remove all the currently selected humans from the set of humans
    for( const human* p : selected_hunans ) humans.erase(*p) ;
    selected_hunans.clear() ; // these pointers are no longer invalid

    std::cout << "\nremaining humans: " ; for( const human& h : humans ) std::cout << h.name ;
    std::cout << '\n' ;
}

http://ideone.com/husK6o