Sign in to follow this  

How to delete a row in a vectorvectorstring ?

This topic is 2572 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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 include
template<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 use
struct ShouldRemove
{
bool operator()(const Row &row) const
{
// whatever condition
return row.size() > 3;
}
};


// Elsewhere
remove_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 include
template<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 use
struct 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: 90
After: 5
Alloc : 10
Copy : 280
Assign : 0
Destruct: 265


remove_if:
Before: 10
Alloc : 10
Copy : 125
Assign : 0
Destruct: 90
After: 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: 674751
After: 500
Alloc : 1000
Copy : 167715001
Assign : 0
Destruct: 167466001


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


Wow, two magnitudes of a difference! Gotta love algorithmic efficiency =]

Share this post


Link to post
Share on other sites
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: 499500
After: 500
Alloc : 499500
Copy : 499500
Assign : 0
Destruct: 749000


remove_if:
Before: 1000
Alloc : 499500
Copy : 499500
Assign : 0
Destruct: 499500
After: 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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

This topic is 2572 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this