Solved

erasing out of an vector...

Posted on 2008-06-12
11
306 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
Optimizing Cloud Backup for Low Bandwidth

With cloud storage prices going down a growing number of SMBs start to use it for backup storage. Unfortunately, business data volume rarely fits the average Internet speed. This article provides an overview of main Internet speed challenges and reveals backup best practices.

 
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
 

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

Master Your Team's Linux and Cloud Stack!

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

772 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