1

I'm using a vector to store pointers to objects. In some cases I destroy one or more of these objects (setting the vector spaces to NULL after each delete call), which are externally selected:

for (int i=0; i<form->SelectListBox->Items->Count; i++) {
    if (form->SelectListBox->Selected[i]) {
        delete items[i];
        items[i]=NULL;
    }
}

After that, I have erase all NULL pointers. This is what I'm doing and it works:

ItemVector::iterator it;
while ((it=std::find(items.begin(), items.end(), (MyObjects*)NULL))!=items.end()) {
    items.erase(it);
}

Is there a more idiomatic way to "sweep" a vector of pointers? [1]


[1] As you may have guessed, I'm using C++Builder (version 6) and its VCL and try to migrate from using TList to using std::vector as to reduce static casts (the class TList provides a Pack method.

  • I think the idiom you're looking for is the "erase-remove idiom", see en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Erase-Remove I would also recommend using the std::nullptr type which was introduced in C++11 in stead of NULL. – user150961 May 13 '15 at 17:57
  • If possible you should avoid raw pointers in favour of smart pointers. For example you could use boost::ptr_vector<T>, which is designed specifically to contain pointers. – user150961 May 13 '15 at 18:04
7

Your algorithm is O(N²) - if you have 1000 elements in your vector and the first 100 are null, it will run the while loop 100 times, each repositioning up to 999 elements.

In implementation, you would use two iterators, one which you read from and one which you write to. If the read element is null, do not write it, otherwise write it back and increment.

The standard algorithm for doing this is called remove_if and there's detail discussion in this stackoverflow question.

  • Great: just what I was looking for. Seems I've to learn more about standard algorithms. Thanks a lot :-) – Wolf May 13 '15 at 10:29
  • @Wolf It's easy to forget that even if you don't see it being done, that doesn't mean that it is an operation that is O(1). – Neil May 13 '15 at 12:57
  • @Neil Yes, remove_if is O(N). I'm now elaborating a pack_vector_of_pointers template function having problems with deducing the predicate parameter type... – Wolf May 13 '15 at 13:12
  • Accepted. The remove_if "idiom" reads a bit strange, but the upvotes speak a clear language: I should switch to it. – Wolf May 14 '15 at 20:50
0

You could avoid the 2nd pass by calling erase as you delete the element. You need to convert the index to an iterator and be sure you account for the fact that erasing items changes subsequent indexes

int deleted = 0;
for (int i=0; i < Count; i++) {
    if (Selected[i]) {
        delete items[i];
        items.erase(items.begin()+i-deleted++);
    }
}
  • sorry, but that calculation looks to be the kind of thing you don't want to maintain. – gbjbaanb May 13 '15 at 14:38
  • @gbjbaanb sure, but isn't it only the -deleted++ part that causes the confusion? I find this a valid argument, because two code loops for one logical iteration are of course somewhat suspicious. – Wolf May 13 '15 at 14:44
  • items.begin()+i-deleted++ is nightmarish. Adding numbers to an iterator is scary at best, not to mention that it is still O(N^2) time. – Neil May 13 '15 at 15:48
  • @Wolf yup, its the nasty calculation: begin iterator + count - deleted + 1... Little brain get confuse. Don't likey. Will break it one Friday afternoon when it gets refactored to be begin()+i-deleted+1 – gbjbaanb May 13 '15 at 16:01
  • The deleted++ can be moved to a separate line to make it clearer. However, the O(N^2) can't be fixed, so I hereby disown this suggestion. – AShelly May 13 '15 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.