Thread: Searching a std::vector of strings, counting matching elements and erasing them

Regarding this topic I have read that the Erase-remove idiom is the way to go. I have a rough understanding of how this works but am unsure whether I can implement a match-counter along with it.

For counting alone, I would use something like this:

Code:

std::vector<std::string> v; // contains duplicate strings in different elements
std::string term = "foo"; // search term, changing at runtime as well

unsigned int matches = 0;
for( auto e : v ) {
    if( e == term ) {
        ++matches;
    }
}

The Erase-remove approach is being demonstrated like this:

Code:

bool is_odd( int var ) {
    return ( var % 2 ) != 0;
}

std::vector<int> v;

v.erase( std::remove_if( v.begin(), v.end(), is_odd ), v.end() );

Or using a lambda:

Code:

std::vector<int> v;

v.erase( std::remove_if( v.begin(), v.end(), []( int var ) {
    return( var % 2 ) != 0;
}), v.end() );

I'm not sure how (or if) I can combine the two things. That is, I don't know how to integrate a function comparing two (changing) strings into the remove_if() method. Nor do I know how to increment a counter during iteration.

The vector is extremely large, so speed is paramount. I think there are many other avenues for optimization, but decreasing the vector's size for each consecutive search could deliver a big speed boost for subsequent searches I imagine, as traversing it holds the biggest cost.

I'm not sure how (or if) I can combine the two things. That is, I don't know how to integrate a function comparing two (changing) strings into the remove_if() method.

If you mean that the string will change in the middle of the erasing, that would make things complicated. Otherwise I don't see why it can't work. Consider the following:

Code:

string matchMe = "foo";
vector<string> v;

// later
v.erase( remove_if( v.begin(), v.end(), [&]( string var ) { return var == matchMe; }), v.end());

In general, the thing that you want to compare against needs to be stored in the object that does the comparing. Lambdas are syntactic sugar for function objects, after all.

Separate the remove_if and erase calls.
Save remove_if's return, which is an iterator to the "new end" of the vector.
Then subtract the new end from the old to see how many were removed.
E.g.,

Code:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v;
    v.push_back(1); v.push_back(0); v.push_back(1); v.push_back(1);
    v.push_back(0); v.push_back(0); v.push_back(1); v.push_back(1);

    auto x = std::remove_if(v.begin(), v.end(),
                [] (int n) {return n == 1;});

    size_t numRemoved = v.end() - x;

    v.erase(x, v.end());

    std::cout << numRemoved;
}

Superb, thanks guys!

Originally Posted by whiteflags

If you mean that the string will change in the middle of the erasing, that would make things complicated. Otherwise (...)

I was only trying to imply that the search string would be a variable, not hard-coded (e.g. element == "Flowers") into the comparison-function. I should have been more clear about that.