473,548 Members | 2,721 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Erasing in a vector while iterating through it

I have some code where there's this vector of pointers to objects and
I need to delete and erase some of them, the problem is that to know
which I need to iterate through the vector and I'm trying to do this
as efficient as possible. The code is something like this:

struct Thing {
int value;
Thing* ptr;
Thing() : ptr(0) { }
};

// .....

std::vector<Thi ng*vec;

So the vector contains pointers to Thing-objects, and for some of
those objects ptr might be set, in which case it will point to one of
the Things pointed to by the pointers in the vector. What I need to do
is to go through the vector and for each Thing where value has a
specific value I need to delete the Thing pointed to by ptr and erase
it from the vector. One way I could do that is to go through the
vector in one pass and collect all those pointers to some other
container and then make another pass and erase them but I'd prefer to
do it in one pass and was wondering if that is legal (something like
this):

std::sort(vec.b egin(), vec.end()); // Sort one the address of the
Things

for (size_t i = 0; i < vec.size(); ++i) {
if (vec[i]->value == SOME_VALUE) {
std::vector<Thi ng*>::iterator it =
std::::lower_bo und(cells.begin (), cells.end(), vec[i]->ptr);
vec[i]->value = 0;
vec[i]->ptr = 0;
delete *it;
--i; // Decrement if the Thing removed is before i in vec
vec.erase(it);
}
}

Since vector::erase will invalidate all references and iterators to
elements after the one removed there are two scenarios that I can
think of. The first is that the element is located after the i'th
element in which case I'll have to do some extra work (since I did --
i), or the element is before the i'th element (it can't be the i'th
element) in which case the i'th element (after the --i) should be the
same. Is this true?

--
Erik Wikström

Jun 11 '07 #1
3 6179
Erik Wikström wrote:
I have some code where there's this vector of pointers to objects and
I need to delete and erase some of them, the problem is that to know
which I need to iterate through the vector and I'm trying to do this
as efficient as possible.
The best way I know would be to iterate, set those you delete to null,
and then, after all the deletion, remove_if all of them at once.
The code is something like this:

struct Thing {
int value;
Thing* ptr;
Thing() : ptr(0) { }
};

// .....

std::vector<Thi ng*vec;

So the vector contains pointers to Thing-objects, and for some of
those objects ptr might be set, in which case it will point to one of
the Things pointed to by the pointers in the vector. What I need to do
is to go through the vector and for each Thing where value has a
specific value I need to delete the Thing pointed to by ptr and erase
it from the vector. One way I could do that is to go through the
vector in one pass and collect all those pointers to some other
container and then make another pass and erase them but I'd prefer to
do it in one pass and was wondering if that is legal (something like
this):

std::sort(vec.b egin(), vec.end()); // Sort one the address of the
Things

for (size_t i = 0; i < vec.size(); ++i) {
if (vec[i]->value == SOME_VALUE) {
std::vector<Thi ng*>::iterator it =
std::::lower_bo und(cells.begin (), cells.end(), vec[i]->ptr);
vec[i]->value = 0;
vec[i]->ptr = 0;
delete *it;
--i; // Decrement if the Thing removed is before i in vec
vec.erase(it);
}
}

Since vector::erase will invalidate all references and iterators to
elements after the one removed
...and the one removed,...
there are two scenarios that I can
think of. The first is that the element is located after the i'th
element in which case I'll have to do some extra work (since I did --
i), or the element is before the i'th element (it can't be the i'th
element) in which case the i'th element (after the --i) should be the
same. Is this true?
You need to check the return value of 'erase'. RTFM.

But before you decide to fix your code for erasing each in the middle,
consider remove_if all of them at once after doing all deletions.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Jun 11 '07 #2
On Jun 11, 7:41 am, Erik Wikström <eri...@student .chalmers.sewro te:
I have some code where there's this vector of pointers to objects and
I need to delete and erase some of them, the problem is that to know
which I need to iterate through the vector and I'm trying to do this
as efficient as possible. The code is something like this:

struct Thing {
int value;
Thing* ptr;
Thing() : ptr(0) { }

};

// .....

std::vector<Thi ng*vec;

So the vector contains pointers to Thing-objects, and for some of
those objects ptr might be set, in which case it will point to one of
the Things pointed to by the pointers in the vector. What I need to do
is to go through the vector and for each Thing where value has a
specific value I need to delete the Thing pointed to by ptr and erase
it from the vector. One way I could do that is to go through the
vector in one pass and collect all those pointers to some other
container and then make another pass and erase them but I'd prefer to
do it in one pass and was wondering if that is legal (something like
this):

std::sort(vec.b egin(), vec.end()); // Sort one the address of the
Things

for (size_t i = 0; i < vec.size(); ++i) {
if (vec[i]->value == SOME_VALUE) {
std::vector<Thi ng*>::iterator it =
std::::lower_bo und(cells.begin (), cells.end(), vec[i]->ptr);
vec[i]->value = 0;
vec[i]->ptr = 0;
delete *it;
--i; // Decrement if the Thing removed is before i in vec
vec.erase(it);
}

}
The usual solution is to combine std::remove() with an erase
operation:

vec.erase( std::remove( vec.begin(), vec.end(), value_to_erase) ,
vec.end());

Unfortunately, this line of code does not manually delete the items
before erasing them from the vector.

Therefore I would suggest eliminating the error-prone and laborious
manual deletion requirement and declare a
std::vector<sha red_ptr<Thing instead of a std::vector<Thi ng *>.
With this one change, the one line of code illustrated above would
work as it should.

Greg

Jun 11 '07 #3
"Greg Herlihy" <gr****@pacbell .netwrote in message
news:11******** *************@i 13g2000prf.goog legroups.com...
On Jun 11, 7:41 am, Erik Wikström <eri...@student .chalmers.sewro te:
>I have some code where there's this vector of pointers to objects and
I need to delete and erase some of them, the problem is that to know
which I need to iterate through the vector and I'm trying to do this
as efficient as possible. The code is something like this:
The usual solution is to combine std::remove() with an erase
operation:
That's almost certainly best. But in those cases where you do need to
walk through the vector (something more complicated than simple
removal) read Item 9 in Scott Meyers' Effective STL - which discusses
the issue for all the standard containers (which don't all have the same
solution).

While Items 1-8 and 10-50 are also very good, I think this one Item
made this book invaluable - it told me this just before I was about to
get it wrong. It also starts with the std::remove solution.
Jun 11 '07 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

15
9673
by: David Jones | last post by:
Hi I have a list of values stored in a vector e.g. std::vector<int> x; x = 1; x = 4; x = 2; x = 4;
8
2191
by: Generic Usenet Account | last post by:
To settle the dispute regarding what happens when an "erase" method is invoked on an STL container (i.e. whether the element is merely removed from the container or whether it also gets deleted in the process), I looked up the STL code. Erase certainly does not delete the memory associated with the element. However, it appears that the...
14
5008
by: Jim West | last post by:
I'm curious why I might be getting such a large performance difference between using a map iterator and a vector iterator. This is a computational electromagnetics code where I have to separate points in space that arrive randomly into groupings based on (x, y, z) dimensions, so I use std::map to do that. Once the sorting is done I need to...
11
4334
by: eeykay | last post by:
Hello, I am facing a starnge problem while erasing the last member in a vector. I am using VC++ .NET 2002 complier. I have vector of CComPtr<..> (irrelevant here), and then I iterate over the vector. If it is the iterator, then I remove the element from the vector using vecObjects.erase(it). It works fine till the last element. While...
5
12030
by: ma740988 | last post by:
For starters, Happy New Year to all!! I created a vector of pairs where pair first is a primitive and pair second is a vector of ints. So now: # include <iostream> # include <vector>
8
2131
by: Jim Langston | last post by:
There's the thing about iterating though a map or vector when you may delete one of the elements, where you simply assign the iterator to the map.erase() statement or increment it if you don't. Well, I have this issue where I may delete the map element in 3 different places: for ( map_key_pcmissile::iterator mit = World.Missiles.begin();...
5
12078
by: Alan | last post by:
I was wondering whether it is good programming practice or asking for trouble to modify a vector while iterating through it. That is, I want to do something like the following pseudocode in C++: for each element of the vector for each subsequent element of the vector if the belong together <some code to compare them> then merge the...
1
1741
by: wolverine | last post by:
Hi, I have read that to erase an element from a vector with reverse_iterator we have to use -- vector.erase( (++reverseItr).base()) -- But assuming i have to delete the first element of the vector ( zeroth index), would this result in undefined behavior. My thinking is like, since the reverseItr is already pointing to the first element of...
2
9794
by: Christopher | last post by:
Seems odd, but I was wondering if I am in the middle of iterating through a vector, is there a way to calc which index I am currently on? something like: it - vec.begin()? I don't want to change the loop to iterate through using indexes instead of iterators, I just need the index for a little debug output, the rest of the code in the loop...
0
7518
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
7444
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
7711
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
1
7467
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
7805
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
6039
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5367
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
3497
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
1
1932
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.