Compare different vector iterators and erase element from the first vector

Question

I've been struggling with this problem for about a week now. I don't know anymore what the problem is or if I update the iterator at the wrong place.

Let's get to the point. I'm trying to make a drop system where random items are being dropped from the monster after the player kills it. I get the items from the container below. After I receive the items from gear container, I want to delete received items from the gear vector as well. I.e. if "Plate armor" is dropped, I want to delete it from the gear container.

I have a vector of Gears where I register different gears such as weapon, armor or accessories. In our case, I will only focus on Armor.

std::vector<std::unique_ptr<Armor>> gear;

/* This is the simplified version of the vector. 
 I register different elements into my gear vector. Now is only armor focused on.
*/
gear.emplace_back(new Armor("Great pauldron", 25, 100));
gear.emplace_back(new Armor("Holy armor", 3, 18));
gear.emplace_back(new Armor("Dominic's eye", 18, 73));
gear.emplace_back(new Armor("Plate armor", 23, 21));
gear.emplace_back(new Armor("Poor armor", 57, 7));
gear.emplace_back(new Armor("Good shield", 91, 5));
gear.emplace_back(new Armor("Jodin's boots", 18, 66));
gear.emplace_back(new Armor("Ivona's gauntlets", 25, 100));

Next step, I make a class where I receive given the number of items as a vector of a vector iterator. (I use the public function for such operation.)

class Maker {
private:

    template<typename Iter, typename RandomGen>
    Iter randomSelection(Iter begin, Iter end, RandomGen& ran) {
        std::uniform_int_distribution<> dist(0, std::distance(begin, end) - 1);
        std::advance(begin, dist(ran));
        return begin;
    }
public:

    template<typename Iter>
    std::vector<Iter> randomSelection(Iter& begin, Iter& end, int amount) {
        std::vector<Iter> it;
        std::random_device randDev;
        std::mt19937 gen(randDev());
        for (int i = 0; i < amount; i++)
            it.push_back(randomSelection<>(begin, end, gen));
        return it;
    }
};

Next, I make a vector of vector iterator to receive random items from the gear container.

Maker mak;
std::vector<std::vector<std::unique_ptr<Armor>>::iterator>& droppedItems = 
    mak.randomSelection(gear.begin(), gear.end(), 5);

The problem comes where I try to compare armor names from both vectors and if found; delete it from our very first gear vector. I almost always get an access violation error. It sometimes works to delete the items without producing any error. But just once every i.e. 20 tries.

for (auto& i = gear.begin(); i != gear.end();) {
        for (auto& j = droppedItems.begin(); j != droppedItems.end(); j++) {
            /* This if statement is where I get the access violation error; 0x05.*/
            if (i->get()->getName() == (*j)->get()->getName()) {
                std::cout << std::endl << i->get()->getName() << " has been deleted!\n";
                i = gear.erase(i);
            }
            else
                i++;
        }
    }

I assume I increment the iterator(s) at the wrong place. I assume I perform the erase operation finely but I'm literally out of ideas.

std::vector<std::vector<std::unique_ptr<Armor>>::iterator>& droppedItems is a reference to a temporary? Other than that, you're probably invalidating the rest of the iterators you hold when you gear.erase(i). — jotik
– jotik, Commented Sep 11, 2017 at 7:13
I think the crash comes from the fact that i may reach ::end() and you are trying to dereference it in your if statement... One possibilty would be to check (after calling erase) if(i == gear.end()) break; (and stop the loop) — Robert
– Robert, Commented Sep 11, 2017 at 7:29
You are both correct and thank you both for the great feedback. However, the thing I don't yet understand is where exactly shall I revalidate the i iterator after it reaches ::end()? — knoxgon
– knoxgon, Commented Sep 11, 2017 at 7:30
since you erase items from gear, that needs to be the inner loop — sp2danny
– sp2danny, Commented Sep 11, 2017 at 7:32
Since you may have missed my edit: One possibilty would be to check (after calling erase) if(i == gear.end()) break; (and stop the loop) or swap the inner with the outer loop — Robert
– Robert, Commented Sep 11, 2017 at 7:39

jotik · Accepted Answer · 2017-09-11 08:21:43Z

3

std::vector<T>::erase(iter) invalidates the iterators and references at or after iter (including end()), but you still attempt to use these invalidated iterators from the droppedItems container afterwards.

For example, if lets say that droppedItems also contains an iterator pointing to the last element of gears, and also some other iterators. When you erase any other element of gears, it invalidates the iterator to the last element. So when you finally call gears.erase() passing the (invalidated) iterator to the last element, it will cause undefined behavior.

std::vector<int> test{1,2,3,4};
auto firstIter = test.begin();
auto secondIter = firstIter + 1;
auto thirdIter = secondIter + 1;
auto fourthIter = thirdIter + 1;
test.erase(secondIter); // Invalidates secondIter, thirdIter and fourthIter
                        // but not firstIter

You can think of std::vector<T> iterators as pointers to T. If you erase an element, the elements following it will be moved in memory to keep the vector elements as a dynamic array. Hence the iterators "pointing" to those elements will not continue to point at the correct elements.

Before test.erase(secondIter):

address: | 0x0 | 0x1 | 0x2 | 0x3 |
value:   |   1 |   2 |   3 |   4 |

firstIter  = 0x0 // Points to element with value 1
secondIter = 0x1 // Points to element with value 2
thirdIter  = 0x2 // Points to element with value 3
fourthIter = 0x3 // Points to element with value 4

After test.erase(secondIter):

address: | 0x0 | 0x1 | 0x2 |
value:   |   1 |   3 |   4 |

firstIter  = 0x0 // Still points to element with value 1
secondIter = 0x1 // no longer points to element with value 2
thirdIter  = 0x2 // no longer points to element with value 3
fourthIter = 0x3 // out of vector bounds

I suggest to instead set random elements of gears to nullptr and then compact the vector afterwards:

template <typename T>
void freeRandomItems(std::vector<std::unique_ptr<T> > & vec,
                     std::size_t amount)
{
    if (amount == 0u)
        return; // Nothing to do

    // Setup RNG:
    std::random_device randDev;
    std::mt19937 gen(randDev());

    if (amount == 1u) { // Remove only one random element:
        vec.erase(randomSelection(vec.begin(), vec.end(), gen));
        return;
    }

    // Deallocate amount pointed elements in vector, reset pointers:
    do {
        randomSelection<>(vec.begin(), vec.end(), gen)->reset();
    } while (--amount);

    // Remove all nullptr elements from vec:
    vec.erase(
            std::remove_if(
                    vec.begin(),
                    vec.end(),
                    [](std::unique_ptr<T> const & v) noexcept { return !v; }),
            vec.end());
}

edited Sep 11, 2017 at 8:21

answered Sep 11, 2017 at 7:16

jotik

18.1k16 gold badges66 silver badges131 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

knoxgon Over a year ago

Thanks a bunch for the swift reply. Should I perhaps just make a statement to check whether or not the droppedItems iterator j is valid by j != droppedItems.end() instead of having it inside the inner loop? But why will inner loop iterator j get invalidated when I perform the erase operation for outer loop, i? Sorry, I may totally miss your point if that's the case I apologize, I'm just totally burned out.

jotik Over a year ago

You can think of std::vector<T> iterators as pointers to T. If you erase an element, the elements following it will be moved in memory to keep the vector elements as a dynamic array. Hence the iterators "pointing" to those elements will not continue to point at the correct elements.

jotik Over a year ago

@VG Added code for a possible solution to your problem, and now also fixed a problem with it.

Kapil Dhaimade · Accepted Answer · 2017-09-13 10:43:11Z

1

Given your case, doing things in a different way could avoid this re-validation business. You may add elements that don't match in a temporary vector for gear in your nested loop and then move that vector into the original gear vector. Something like this?

UPDATED: There was a minor mistake in the posted code. Fixed the same. This code is now working on my machine and giving correct results.

decltype(gear) newGearTmp;
//Reserve size for remaining elements in newGearTmp vector
newGearTmp.reserve(gear.size() - droppedItems.size());
for (auto& i = gear.begin(); i != gear.end(); i++) {
    bool lbFound = false;
    for (auto& j = droppedItems.begin(); j != droppedItems.end() && !lbFound; j++) {
        if (i->get()->getName() == (*j)->get()->getName()) {
            std::cout << std::endl << i->get()->getName() << " has been deleted!\n";
            //i = gear.erase(i); //No need for this
            lbFound = true;
        }
    }
    !lbFound ? newGearTmp.push_back(std::move(*i)) : 0;
}
gear = std::move(newGearTmp); //gear now has new armor, unwanted elements are deleted

This should not be more performance intensive compared to your current implementation which also involves swapping overhead of elements after erase.

Also, in this part of your code, you should get the vector of dropped items by value and not reference. Like this.

Maker mak;
std::vector<std::vector<std::unique_ptr<Armor>>::iterator> droppedItems = 
    mak.randomSelection(gear.begin(), gear.end(), 5);

Taking by reference will lead to droppedItems pointing to a deleted temporary vector which was alive for the scope of function mak.randomSelection().

One more thing. In your original submitted code, the i++ seems a bit out of place. It could lead to some comparisons being skipped as i is incremented without comparing with all js.

edited Sep 13, 2017 at 10:43

answered Sep 11, 2017 at 8:18

Kapil Dhaimade

3122 silver badges12 bronze badges

10 Comments

jotik Over a year ago

This is also one possible solution, but it might incur some performance overhead in dynamic memory management, because memory for newGearTmp must be allocated (maybe more than once, because newGearTmp.reserve() is not used) and memory for the old elements must be deallocated. Allocating new memory might also throw an exception.

Kapil Dhaimade Over a year ago

Agree with new memory might throw exception part, but this will reduce code complexity of OP's current implementation. I'll edit my post to add newGearTmp.reserve(). I omitted it because I was giving the general way to fix without looking at specific improvements.

Kapil Dhaimade Over a year ago

Also, I think performance overhead of erasing multiple elements from gear would be significantly more than making a new vector and appending elements due to all the swapping involved. Profiling may help.

knoxgon Over a year ago

@KapilDhaimade Thanks for posting a possible solution. Yet my program still gives the same error when I tried the exact code above. The same read access violation as I got for the first time from the if statement.

Kapil Dhaimade Over a year ago

@VG, Please check now. There were some errors in my posted code. Have fixed my answer and posted the correct code. It's working on my machine. Sorry, hadn't got time to debug it earlier.

|

Collectives™ on Stack Overflow

Compare different vector iterators and erase element from the first vector

2 Answers 2

3 Comments

10 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

10 Comments

Your Answer

Sign up or log in

Post as a guest

Related