Hi, I don't have the access to the code right now, but it is easy to visualize it.
I have a vector<vector<string> > filled correctly with all my data. I'm iterating over it using a vector<vector<string> >::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!
How to delete a row in a vectorvectorstring ?
Like this:
That or use the swap and pop trick, if the order is irrelevant, or the remove/erase idiom.
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.
Author
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!
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!
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:
This test demonstrates the amount of work remove_if avoids (this is only with small vectors, for larger vectors it gets worse!):
Sample output:
If the number of Rows is increased to 1000 (note the length increases per-row):
Wow, two magnitudes of a difference! Gotta love algorithmic efficiency =]
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 =]
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: 749000got "naive" & "remove_if" same results???
Just copy/pasted your code and instead 10 put 1000.
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.
Author
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).
Know what? I was always afraid of functors, but I gave it a try and worked flawlessly (and fast).
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.
Sorry for intrusion (again), but i have question about this function:
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.
//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.
Author
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
