Jump to content
  • Advertisement
Sign in to follow this  
SteveHatcher

Inserting element into vector during iteration causes crash

This topic is 664 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi All,

 

I have a situation in my code where by during iteration of my vector of pointers, I am modifying the original container. I have done some research and learned this causes a crash (I Think)... The problem I am facing is illustrated in my test program as follows:

#include <vector>
#include <iostream>
#include <memory>

using namespace std;

struct Test1
{
	void update(){
		cout << "update from Test1" << endl;

	}
};

struct Test
{
	vector<shared_ptr<Test1>> m_test;

	void pushOn(std::shared_ptr<Test1> &test1)
	{
		m_test.push_back(test1);
	}

	void update()
	{
		for (vector<shared_ptr<Test1>>::reverse_iterator i = m_test.rbegin(); i != m_test.rend(); ++i)
		{
			auto newPtr = make_shared<Test1>();
			(*i)->update();
			pushOn(newPtr);
			cout << "if you read this it passed" << endl;
		}
	}

};

int main()
{
	auto TestClass = make_shared<Test>();

	auto aaa = make_shared<Test1>();

	TestClass->pushOn(aaa);

	TestClass->update();

	getchar();
	return 0;
}

If you run the program with pushOn(newPtr); commended out, then it works, otherwise it crashes.

 

I have some questions.

 

1. May I have some advice on how to fix this?

 

2. If I am encountering this, does that mean a fundamentally flawed program design?

 

Thanks

Share this post


Link to post
Share on other sites
Advertisement

When you push something into vector, you may trigger vector's memory reallocation. Any iterators that reference elements in vector (namely, your 'reverse_iterator i' in update loop) will be invalidated.

You can avoid invalidation if you reserve some space in vector upfront. If you know there won't be more than N insertions, you can call reserve() on that vector, and push() won't trigger reallocations until capacity (not size) is big enough to store those items.

If you don't know insertions count upfront, probably you'll have to collect inserted items in separate container, and move them later in one batch.

Additionally, you may change container type from vector to something else that still fits your needs and won't reallocate memory - deque, for example.

Share this post


Link to post
Share on other sites

Hi vstrakh,

 

Thanks for your reply, I am slowly learning c++'s ways....

 

So I added this in my constructor:

	Test(){
		m_test.reserve(10);
		m_test.resize(10);
		cout << "struct Test constructor" << endl;
	}

I am still getting the crash though...

 

Thanks for any help.

Share this post


Link to post
Share on other sites

Your constructor reserves enough space for 10 elements, then actually creates 10 elements. So as soon as you add one more, that is element 11 - and you don't have space for that, so it resizes, and you get exactly the same problem as before.

 

If you know you will never have more than 10 elements, the reserve() call alone should be enough.

If you can't be sure about that, then you need to add elements outside the loop, or consider a different data structure, or restart the loop any time you add something.

Share this post


Link to post
Share on other sites
 

1. May I have some advice on how to fix this?   

 

2. If I am encountering this, does that mean a fundamentally flawed program design? 

 

1.  If you will only add to the vector, use indices instead of iterators:

for (int i = m_test.size()-1; i >= 0; i--)
        {
            auto newPtr = make_shared<Test1>();
            m_test[i]->update();
            pushOn(newPtr);
            cout << "if you read this it passed" << endl;
        }

2. Yes.

Edited by kolrabi

Share this post


Link to post
Share on other sites

Your constructor reserves enough space for 10 elements, then actually creates 10 elements. So as soon as you add one more, that is element 11 - and you don't have space for that, so it resizes, and you get exactly the same problem as before.

 

If you know you will never have more than 10 elements, the reserve() call alone should be enough.

If you can't be sure about that, then you need to add elements outside the loop, or consider a different data structure, or restart the loop any time you add something.

 

Ahh thanks! That is an excellent explanation. I *thought* that reserve sets up the vector such that it is ready to take the 'reserved' number of items before it must resize itself, but it still fills them up from 0, 1, 2 etc...

 

I will have a look at your suggested workarounds, I thought this sort of thing would be quite common in C++ so am surprised at this behavior!

 

Share this post


Link to post
Share on other sites

Your code is a test, you won't often find this situation as much in real code but it does happen. In general just avoid changing the vector while iterating. Store up the things you need to add while iterating (but don't add them) and then after you finish the loop add them all on (as others have suggested). 

 

When removing elements while iterating you have a way to deal with iterators changing so that's not as much of a problem.

 

This has a little section at the bottom that explains a few things:

http://www.cplusplus.com/reference/vector/vector/push_back/

Generally about what becomes invalid and when.

Edited by Nanoha

Share this post


Link to post
Share on other sites

 

1.  If you will only add to the vector, use indices instead of iterators:

for (int i = m_test.size()-1; i >= 0; i--)
        {
            auto newPtr = make_shared<Test1>();
            m_test[i]->update();
            pushOn(newPtr);
            cout << "if you read this it passed" << endl;
        }

2. Yes.

 

 

Ahh okay thanks.

 

Now I am wondering if adding them this way vs. other methods is most recommended.

 

Thanks!

 

Share this post


Link to post
Share on other sites

Your constructor reserves enough space for 10 elements, then actually creates 10 elements. So as soon as you add one more, that is element 11 - and you don't have space for that, so it resizes, and you get exactly the same problem as before.
 
If you know you will never have more than 10 elements, the reserve() call alone should be enough.
If you can't be sure about that, then you need to add elements outside the loop, or consider a different data structure, or restart the loop any time you add something.

 
Ahh thanks! That is an excellent explanation. I *thought* that reserve sets up the vector such that it is ready to take the 'reserved' number of items before it must resize itself, but it still fills them up from 0, 1, 2 etc...


It does do exactly that. But you also call resize(10), which changes the vector to have 10 elements, and since you only had 10 capacity, it's full up again.

I will have a look at your suggested workarounds, I thought this sort of thing would be quite common in C++ so am surprised at this behavior!


C++ isn't designed to make everything possible with every container. A vector is designed for top-speed random access to tightly-packed data. When you add more data, it has to move the contents so that they can stay tightly packed and give you quick random access; but the cost of that is that your previous iterator is now out-of-date.

For what it's worth, exactly the same thing happens in C# Lists.

If you absolutely need to add things to a data structure while you iterate over it, you probably want a different data structure than a std::vector.

Share this post


Link to post
Share on other sites

I thought this sort of thing would be quite common in C++ so am surprised at this behavior!

 
Documentation of std::vector will point out that element insertion invalidates iterators.

 

It looks like this vector is a primary owner for these objects. If you can ensure that the vector outlives anything that may refer to its contents then you could just use std::vector<Test1> and then take references to elements or (preferably) simply refer to them directly as needed. If you're thinking about polymorphism then that won't work though.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!