Archived

This topic is now archived and is closed to further replies.

russian-bear

some stl vector problems

Recommended Posts

Hi! I have a litle problem.
std::vector<CObject *> objects;
std::vector<CObject *> free_objects; 
Sometimes i make a call like this:
Object* obj = new Object();
objects.push_back( obj ); 
and some times i wanna make a call like this:
for (std::vector<CObject *>::iterator i = objects.begin(); i != objects.end(); ++i) 
{	
   if ( (*i)->is_free() ) 
   {
       free_object.spush_back( *i );
       objects.erase( i );
   }
} 
When i make objects.erase( i ) call i get a nasty bad memory reference error... What'm i doing wrong i wanna moove a pointer from a vector to another and remove it from the first..... Please help.. [Edit: HTML/legibility fixes.] [edited by - russian-bear on April 28, 2002 9:22:08 PM] [edited by - Oluseyi on April 28, 2002 9:53:01 PM]

Share this post


Link to post
Share on other sites

for (std::vector<CObject *>::iterator i = objects.begin(); i != objects.end(); ++i)
{
if ( (*i)->is_free() )
{
free_object.spush_back( *i );
i = objects.erase( i );
}
}

erase returns an iterator pointed at the next valid element in the controlled sequence. Note that you still have to explicitly delete the objects in free_objects eventually.

[ GDNet Start Here | GDNet Search Tool | GDNet FAQ ]
[ MS RTFM [MSDN] | SGI STL Docs | Boost ]
[ Google! | Asking Smart Questions | Jargon File ]
Thanks to Kylotan for the idea!

Share this post


Link to post
Share on other sites
Shouldn't that be something like...

std::vector::iterator i = objects.begin();
while( i != objects.end()))
{
if ( (*i)->is_free() )
{
free_object.spush_back( *i );
i = objects.erase( i );
}
else
{
++i;
}
}


since you don't want to incrementing because erase already advances the iterator?
[edit]can't code right now =P[/edit]

[edited by - sjelkjd on April 29, 2002 4:09:50 AM]

Share this post


Link to post
Share on other sites
Or you could use <algorithm>


vector<object*>::iterator removed_begin;

remove_copy_if(
objects.begin(),
objects.end(),
back_inserter(free_objects),
not1(mem_fun(object::is_free)));

removed_begin = remove_if(
objects.begin(),
objects.end(),
mem_fun(object::is_free));

objects.erase(
removed_begin,
objects.end());


[edited by - kvh on April 29, 2002 8:29:34 AM]

Share this post


Link to post
Share on other sites

Ok, here we go:


vector<object*>::iterator removed_begin;

// add all freed objects to free_objects
remove_copy_if(
objects.begin(),
objects.end(),
back_inserter(free_objects),
not1(mem_fun(object::is_free)));

// "remove" freed objects
removed_begin = remove_if(
objects.begin(),
objects.end(),
mem_fun(object::is_free));

// erase all "removed" objects
objects.erase(
removed_begin,
objects.end());



remove_copy_if()'s signature:



template<class InputIterator, class OutputIterator, class Predicate>
OutputIterator remove_copy_if(
InputIterator first,
InputIterator last,
OutputIterator result,
Predicate pred);



It copies all elements in the range [first, last) to a range starting at result, but skips elements for which pred(element) returns true.

The first two arguments are easy, just use objects.begin() and objects.end() to iterate over the entire sequence.

The result iterator is a bit harder, we can't use free_objects.end(), because remove_copy_if() only copies elements, it doesn't add new elements. Instead, we can use a back_insert_iterator. When an object is assigned to a back_insert_iterator, it appends that object to the back of a container.

Here's a simple example:


#include <iostream>
#include <vector>
#include <iterator>
using namespace std;

int main()
{
vector<int> v;
back_insert_iterator<vector<int> > it(v);

(*it) = 10; // v.push_back(10)
(*it) = 20; // v.push_back(20)
(*it) = 30; // v.push_back(30)

for(int i=0; i<v.size(); ++i)
cout << v << endl;
}



back_inserter() is a function that returns a back_insert_iterator, it makes the syntax look a bit cleaner since template functions can automatically fill in the template parameters, you don't have to specify the types yourself.

A predicate is a function that returns true or false. For example:



bool is_free(object* obj)
{
return obj->is_free();
}



Instead of a function, it's also possible use a function object:



struct is_free()
{
bool operator()(object* obj)
{
return obj->is_free();
}
};



After you have instantiated a function object like this, you can use it just like you would use a normal function:



object o;
is_free f;
f(&o);



Little function objects that simply pass the call to a member function of operator()'s argument (like the one above) appear fairly often, so the standard library provides a function called mem_fun() that automatically generates such a function object (a mem_fun_t). mem_fun() takes the member function it should call as an argument.

In this case, we don't want to skip the arguments for which is_free() returns true, we want the exact opposite. not1() wraps a predicate and negates it.


Here's remove_if()'s signature:



template<class InputIterator, class Predicate>
OutputIterator remove_if(
InputIterator first,
InputIterator last,
Predicate pred);



This might sound a bit weird. remove_if() removes all elements in the range [first, last) for which pred returns true. However, since remove_if() doesn't know anything about the container on which it operates (only about the iterators), it can't really remove the elements, instead it just rearranges the sequence and moves all "valid" elements to the front. It then returns an iterator to the end of the range of valid elements (== beginning of the invalid/removed elements).

To physically remove the elements from the container we erase the entire "invalid" range at once.


For more detailed info:

http://www.sgi.com/tech/stl/Vector.html
http://www.sgi.com/tech/stl/remove_copy_if.html
http://www.sgi.com/tech/stl/remove.html
http://www.sgi.com/tech/stl/back_insert_iterator.html
http://www.sgi.com/tech/stl/mem_fun_t.html
http://www.sgi.com/tech/stl/unary_negate.html


Hope that helped...

[edited by - kvh on April 29, 2002 1:28:57 PM]

Share this post


Link to post
Share on other sites
Excellent explanation kvh. I do have a question though: isn''t remove_copy_if really copy_if? It doesn''t modify the original sequence, so why "remove_"? I seem to remember some discussion of this in Meyer''s book, but my colleague stole it and is still on his honeymoon, so I can''t get it from his office.

Share this post


Link to post
Share on other sites
remove_copy_if could be better named "copy_if_not".

SGI code for it:

  
template <class _InputIter, class _OutputIter, class _Predicate>
_OutputIter remove_copy_if(_InputIter __first, _InputIter __last,
_OutputIter __result, _Predicate __pred) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
typename iterator_traits<_InputIter>::value_type);
for ( ; __first != __last; ++__first)
if (!__pred(*__first)) {
*__result = *__first;
++__result;
}
return __result;
}


Meyer points out that you cannot implement copy_if by using a negator (e.g. not1()) because the negator makes assumptions on the Predicate''s interface which must be an "adaptable function object", derived from unary_function (IIRC)

[Questions (STFW) | GDNet Start Here | GDNet Search | Forum FAQ | Google | Asking Smart Questions ]
[Docs (RTFM) | MSDN | SGI''s STL | OpenGL | File formats]
[C++ Must Haves (RTFS) | MinGW | Boost | Loki | FLTK | SDL ]

Stolen from Magmai Kai Holmlor, who held it from Oluseyi, who was inspired by Kylotan...

Share this post


Link to post
Share on other sites