Skip to main content
GameDev.net gamedev.net
🔒 Locked

How to delete a row in a vectorvectorstring ?

Started by draconar Dec 1, 2010 at 5:39 PM 10 replies 1.8k views
Original Post
draconar
draconar
Hi, I don't have the access to the code right now, but it is easy to visualize it.

I have a vector > filled correctly with all my data. I'm iterating over it using a vector >::iterator. Whenever I find a row containing certain data, the row is 'useless' and should be deleted completely from the vector.

After 3hs of trying to combine every single combination of STD's erase, clear and remove without success (I was getting memory access errors), I gave up and created a temp vector instead. This tempVector was filled with the rows I needed and then I assigned it to the original vector< vector<> >, which worked correctly.

how could I achieve it using iterators? Would it be faster than the 'push_back()' + assignment to the tempVector?

thanks!
rip-off
rip-off
Like this:
typedef std::vector<std::string> Row;for(std::vector<Row>::iterator it = vector.begin() ; it != vector.end() ; /* handled in loop body */){   if(shouldRemove(*it))   {      it = vector.erase(it);   }   else   {      ++it;   }}

That or use the swap and pop trick, if the order is irrelevant, or the remove/erase idiom.
blog | twitter
draconar
draconar
cool!
I try it later.

So basically I can tell vector.erase() to get the address of the row and it will deal with it. Then there is no need to remove the elements that each Row holds. Maybe that was my problem.

thanks!
rip-off
rip-off
If your rows are large, you really don't want to erase() them one by one. Erasing a vector element causes all elements from there on to be moved down one index in memory, which for vector<> is expensive as all these vectors will be copied.

Using something like remove_if() isn't too much more complex and is much more efficient:
// In some utility includetemplate<typename Container, typename Functor>void remove_and_erase_if(Container &container, const Functor &functor){    typename Container::iterator end = container.end();    typename Container::iterator it = std::remove_if(container.begin(), end, functor);    container.erase(it, end);}// Near to usestruct ShouldRemove{   bool operator()(const Row &row) const   {        // whatever condition        return row.size() > 3;   }};// Elsewhereremove_and_erase_if(vector, ShouldRemove());


This test demonstrates the amount of work remove_if avoids (this is only with small vectors, for larger vectors it gets worse!):
#include <string>#include <vector>#include <iostream>#include <algorithm>// In some utility includetemplate<typename Container, typename Functor>void remove_and_erase_if(Container &container, const Functor &functor){    typename Container::iterator end = container.end();    typename Container::iterator it = std::remove_if(container.begin(), end, functor);    container.erase(it, end);}static int alloc, copies, assign, destruct;void printInfo(){   std::cout << "\tAlloc   : " << alloc << '\n';   std::cout << "\tCopy    : " << copies << '\n';   std::cout << "\tAssign  : " << assign << '\n';   std::cout << "\tDestruct: " << destruct << '\n';}void resetInfo(){   alloc = 0;   copies = 0;   assign = 0;   destruct = 0;}struct Foo {    Foo() { ++alloc; }    ~Foo() { ++destruct; }    Foo(const Foo &) { ++copies; }    Foo &operator=(const Foo &) { ++assign; return *this; }};typedef std::vector<Foo> Row;// Near to usestruct ShouldRemove{   bool operator()(const Row &row) const   {        // whatever condition        return (row.size() % 2) == 0;   }};typedef std::vector<Row> Container;void naive(Container &vector){   ShouldRemove predicate;   for(Container::iterator it = vector.begin() ; it != vector.end() ; /* handled in loop body */)   {      if(predicate(*it))      {         it = vector.erase(it);      }      else      {         ++it;      }   }}void removeIf(Container &vector){   remove_and_erase_if(vector, ShouldRemove());}template<typename Function>void test(const Function &function){   resetInfo();   Container vector;   for(int i = 0 ; i < 10 ; ++i)   {       vector.push_back(Row(i));   }   std::cout << "Before: " << vector.size() << '\n';   printInfo();   function(vector);      std::cout << "After: " << vector.size() << '\n';   printInfo();}int main(){   std::cout << "Naive:\n";   test(&naive);   std::cout << "\n\nremove_if:\n";   test(&removeIf);}


Sample output:
Quote:

Naive:Before: 10	Alloc   : 10	Copy    : 125	Assign  : 0	Destruct: 90After: 5	Alloc   : 10	Copy    : 280	Assign  : 0	Destruct: 265remove_if:Before: 10	Alloc   : 10	Copy    : 125	Assign  : 0	Destruct: 90After: 5	Alloc   : 10	Copy    : 150	Assign  : 0	Destruct: 135


If the number of Rows is increased to 1000 (note the length increases per-row):
Quote:

Naive:Before: 1000	Alloc   : 1000	Copy    : 1173251	Assign  : 0	Destruct: 674751After: 500	Alloc   : 1000	Copy    : 167715001	Assign  : 0	Destruct: 167466001remove_if:Before: 1000	Alloc   : 1000	Copy    : 1173251	Assign  : 0	Destruct: 674751After: 500	Alloc   : 1000	Copy    : 1423251	Assign  : 0	Destruct: 1174251


Wow, two magnitudes of a difference! Gotta love algorithmic efficiency =]
blog | twitter
belfegor
belfegor
Quote:

rip-off...

I don't know what compiler you are using but i have tested this on mvc++ 2010 express and got this results (inserted 1000 elements):
Naive:Before: 1000        Alloc   : 499500        Copy    : 499500        Assign  : 0        Destruct: 499500After: 500        Alloc   : 499500        Copy    : 499500        Assign  : 0        Destruct: 749000remove_if:Before: 1000        Alloc   : 499500        Copy    : 499500        Assign  : 0        Destruct: 499500After: 500        Alloc   : 499500        Copy    : 499500        Assign  : 0        Destruct: 749000

got "naive" & "remove_if" same results???
Just copy/pasted your code and instead 10 put 1000.
rip-off
rip-off
MSVC 2010 supports "rvalue references", which completely changes how expensive it is to move std::vector objects. The performance analysis given is in the context of pre C++0x compilers. I haven't used C++0x nearly enough to comment on what is going on.
blog | twitter
draconar
draconar
man, what a thoroughly reply. Thank you very much.

Know what? I was always afraid of functors, but I gave it a try and worked flawlessly (and fast).
rip-off
rip-off
Functors look kind of funky but they are very easy to use. It is just some boilerplate, but if done right allows the compiler to inline the algorithm you're calling if it can - functors are often faster than function pointers for this reason.
blog | twitter
belfegor
belfegor
Sorry for intrusion (again), but i have question about this function:
//template<typename Container, typename Functor>template<class Container, class Functor>void remove_and_erase_if(Container &container, const Functor &functor){    //typename Container::iterator end = container.end();    //typename Container::iterator it = std::remove_if(container.begin(), end, functor);	Container::iterator end = container.end();    Container::iterator it = std::remove_if(container.begin(), end, functor);    container.erase(it, end);}

1. For the template arguments, is there difference using typename rather
then class? Both versions work for me.
2. Why do you/we need to put typename infront iterators? Again, this also
works for me without it.
draconar
draconar
Hi, Belphegor.

1.
for template declarations, typename & class are equivalent. Just a matter of personal taste. I prefer typename, since it sounds more "mathematically" correct to me.

2. think the item was a typo.. since the typename will be available as the "Container" variable.
rip-off
rip-off
The typename keyword was introduced because the compiler doesn't know whether identifiers inside a template type are types or objects until the template is instantiated. The template code is checked for syntax errors at the point it is encountered, at this stage the exact value of the template type parameters aren't known.

So for #2, the keyword is necessary, nested types like iterators are so called "dependent types". Some compilers support omitting the typename keyword as a language extension. If you are using MSVC, there is an option in your project settings to "Disable Language Extensions". If you do this, the code will not compile without typename.

Once typename was introduced, it was allowed in place of class in template argument lists. The use of class is discouraged, as templates are not restricted to user defined types (as class suggests) but can be used by primitive types also. This should answer #1, though it isn't really important.
blog | twitter
belfegor
belfegor
Thanks both for explanation.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.