Solved

erasing out of an vector...

Posted on 2008-06-12
11
285 Views
Last Modified: 2012-05-05
I want to iterate through a vector, process some logic on the items determining whether they still belong in the vector. But I'm having trouble figuring out how.

While iterating through, if it's decided that vector element should be remove, you can't erase it right there, because then you cannot contiue iterating the rest of the vector. You would need to contruct a new vector and start over. I thought about saving the index of the vector item I want to remove and erasing them afterwards, but that wont work becase the the item indices will change after I remove the first one.

Any thoughts on how I can swiftly accomplish this?
0
Comment
Question by:mattososky
11 Comments
 
LVL 40

Expert Comment

by:evilrix
ID: 21773568
Have you considered using a std::list instead? You can remove items from a list without invalidating the iterators.
0
 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 250 total points
ID: 21773598
>> Have you considered using a std::list instead?
It will also be significantly more efficient to delete from a list as this only involves the unlinking of 2 pointers, when you delete from a vector everything after the position erased has to be shuffled back to fill the gap.
0
 

Author Comment

by:mattososky
ID: 21773600
Something I'll look into later, but at this point I'm commited to using the vector, so i need a solution with it.
0
 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 250 total points
ID: 21773631
Have you tried iterating from the end to the beginning? Only the iterators after the current position are invalidated.

BTW: the interface for list and vector are the same... changing from one to the other is simple.
0
 

Accepted Solution

by:
mdnt15 earned 250 total points
ID: 21773660
Ok, so i suppose you use a vector where the elements are pointers to some objects or something.

What you can do, is to create a new vector for the elements that you wanna keep. So you create this new vector, you iterate the old vector, and when you decide that you want to keep an element, you just add that at the end of the new vector. You set the entry of that element to null in the old vector. If you want to delete an element you just free that element and set the entry to null in the old vector.

At the end, you can erase the old vector and return the new one. Or, if you want to keep the pointer of the old vector, you just copy the pointers values from the new vector to the old one.

Is this what you wanted to know?
0
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 

Author Comment

by:mattososky
ID: 21773684
then would make the itr = vector.end and itr-- until it equals vector.begin?

0
 

Author Comment

by:mattososky
ID: 21773784
this isnt working...

deletes the first pass, fails at the second with 'vector iterators incompatible'
vector<string*> str_vector;

	for(int i = 0;i<5;i++)

	{

		string* s = new string("YOYO");

		str_vector.push_back(s);

	}
 

	vector<string*>::iterator itr = str_vector.end();
 

	while(itr!=str_vector.begin())

	{

		itr--;

		str_vector.erase(itr);

	}

Open in new window

0
 
LVL 40

Expert Comment

by:evilrix
ID: 21773787
>> then would make the itr = vector.end and itr-- until it equals vector.begin?
Traversing in reverse using forward iterators is tricky and you can't use reverse iterators to erase so you'll have to use indexes...
#include <iostream>

#include <vector>

#include <algorithm>
 

int gen()

{

	static int i = -1;

	return ++i;

}
 

typedef std::vector<int> intvec_t;
 

int main()

{

	intvec_t intvec(10);
 

	std::generate(intvec.begin(), intvec.end(), gen);
 

	std::cout << "Display all numbers and remove odd" << std::endl;
 

	intvec_t::size_type st = (intvec.size() - 1);
 

	do

	{

		std::cout << intvec[st] << std::endl;

		if(intvec[st]%2) { intvec.erase(intvec.begin() + st); }

		--st;

	}

	while(st > 0);
 

	std::cout << std::endl << "After all odd items were rmeoved" << std::endl;

	std::copy(intvec.begin(), intvec.end(), std::ostream_iterator<int>(std::cout, "\n"));

}

Open in new window

0
 
LVL 40

Expert Comment

by:evilrix
ID: 21773810
>> string* s = new string("YOYO");
Why push back pointers to string, it can safely be copied into the vector? Putting heap allocated memory into vectors is always problematic... it creates very hard to protect against leakage issues with exceptions.
0
 
LVL 86

Expert Comment

by:jkr
ID: 21773826
>>You would need to contruct a new vector and start over.

You won't need a new vector - and a little trick will help:
#include <vector>

#include <iostream>

using namespace std;
 

void main () {
 

  int tmp[] = { 1,2,3,4,3,2,5,2};

  vector<int> v(&tmp[0],&tmp[7]);
 

  int offs = 0;
 

  vector<int>::iterator i = v.begin();
 

  for (i = v.begin(); i != v.end(); ++i) cout << *i << " ";
 

  i = v.begin();
 

  while(i != v.end()) {
 

    if (*i == 2) { v.erase(i); i = v.begin() + offs; continue;}
 

    ++i;

    ++offs;

  }

  
 

  cout << endl;

  for (i = v.begin(); i != v.end(); ++i) cout << *i << " ";

}

Open in new window

0
 

Author Comment

by:mattososky
ID: 21773837
this was just a test. I needed to replicate what my real application is doing. I in placeing pointers in there because this is not the only reference to these objects..
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now