Filter out elements from std::vector

Question

I have ended up with the following code in order to filter out some bad elements from a std::vector:

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

typedef struct mystruct {
    int id;
    std::string name;
};

int main()
{        
    std::vector<mystruct> all_items = {{151, "test1"}, {154, "test4"}, {152, "test2"}, {151, "test1"}, {151, "test1"}, {153, "test3"}};
    std::vector<int> bad_ids = {151, 152};
    std::vector<mystruct> filter_items;

    for (const auto& item : all_items) {
        if ( std::find(bad_ids.begin(), bad_ids.end(), item.id) != bad_ids.end() ) {
            std::cout << "id: " << item.id << " is bad" << std::endl;
        } else {
            std::cout << "id: " << item.id << " is good item" << std::endl;
            filter_items.emplace_back(item);
        }
    }

    for (auto f : filter_items) {
        std::cout << "Good item: " << f.id << std::endl;
    }
}

Is there any more efficient way? Can the std::remove_copy_if or Boost be used here and how?

Answer 1

You're essentially copying copy_if with some additional debug messages. One can rewrite your code with

std::copy_if(all_items.begin(), all_items.end(), std::back_inserter(filter_items),
             [&bad_ids](const mystruct& item)
{
     return std::find(bad_ids.begin(), bad_ids.end(), item.id) == bad_ids.end();
});

But that's not necessarily more efficient, because copy_if and remove_copy_if are usually implemented as

for(; first != last; ++first) {
    if(predicate(*first)){     // copy if; remove_copy_if would negate
        *result = *first;
        result++;
    }
}

A more efficient way would be a faster predicate, e.g. instead of find(bad_ids…) you could use

for(const auto & item : all_items) {
    if(item.id < 151 || 152 < item.id) {
        filtered_items.push_back(item);
    }
}

But that's not as flexible anymore. That being said, we're talking about a small code snippet. As always, you should measure the time your code needs. And in this case, the output by cout will most likely take the most time.

For now, use the variant that you understand best. Your code is fine, there's not much one can improve at that point without resorting to personal preference because it's too short.

By the way, I would call filter_items filtered_items instead, since it doesn't actually filter items. It is a std::vector of items that have been filtered.

Answer 2

Pointless typedef

In C, it's fairly common to have a typedef like this:

typedef struct tag {
   // ...
} type_name;

This allows you define a variable with just type_name var_name;. A struct definition like this:

struct tag {
    // ...
};

...requires that to define a variable of this type, you need to type struct tag var_name;. In C++, that's unnecessary though. Using just:

struct type_name {
    // ...
};

... lets you define a variable as type_name var_name; already. In this case, you've left the final type_name off, so your typedef isn't syntactically correct. It's probably open to some question whether your code should compile at all (but either way, it's incorrect).

Container choice

A great deal here depends on the actual data. If the data you've shown is truly representative (there really are only a couple of bad IDs) your current choice of containers is probably quite good.

On the other hand, if this is a reduced sample, and in real use you might have dozens or even hundreds of IDs in your black list, then it's probably worth considering using something like an std::unordered_set.

Algorithm choice

Another obvious possibility (if the number of bad IDs might get large) would be to use a binary search instead of a linear search through the bad IDs. Note that you've shown in the bad IDs in sorted order--if you were to use a binary search, you'd be taking advantage of this, and their being sorted would be required, which it currently isn't.

Item grouping

Unless you're truly required to show the message about an item being good/bad in the order in which they originally appeared, I'd strongly prefer to see output something like this:

Good items:
A
B   
D

Bad items:
C
E  

Avoid std::endl

I'd use '\n' instead of std::endl. Using std::endl not only prints a new-line to the stream, but also flushes the stream. This is rarely desirable or useful, and if you're producing a substantial amount of output, it'll typically cause a substantial slow-down.

Don't repeat yourself

I'd rather have a single function that does the formatting and display of the output, something on this order:

template <class It>
void show(std::string const &caption, It beg, It end) { 
    std::cout << caption << ":\n";
    for (; beg != end; ++beg)
        std::cout << beg->id << "\n";
}

Format data

Instead of putting all the contents of your vector on one long line, consider formatting it with (for example) one item per line:

std::vector<mystruct> all_items = {
    {151, "test1"}, 
    {154, "test4"}, 
    {152, "test2"}, 
    {151, "test1"}, 
    {151, "test1"}, 
    {153, "test3"}
};

Library usage

What you're really doing is starting with a collection of items, and partitioning it into two groups. That being the case, I'd at least consider using std::partition to do the partitioning part:

int main() { 
    std::unordered_set<int> bad_ids { 151, 152 };
    std::vector<mystruct> all_items = {
        {151, "test1"}, 
        {154, "test4"}, 
        {152, "test2"}, 
        {151, "test1"}, 
        {151, "test1"}, 
        {153, "test3"}
    };


    auto part = std::partition(all_items.begin(), all_items.end(),
        [&](mystruct const &s) { return bad_ids.find(s.id) != bad_ids.end();});

    show("bad items", all_items.begin(), part);
    show("Good items", part, all_items.end());
}

Answer 3

Yes there are better ways:

But exactly what will depend on your want. Do you want to maintain the original vector?

Zeta has shown several techniques that maintain the original container (by using copy). Personally I think that is wrong as copy is inherently an expensive operation.

If you want filter out I would say you want to remove bad items (effectively destroying the original). The the standard Erase Remove Idiom is the technique to use.

ids.erase(std::remove_if(std::begin(ids), std::end(ids), isBadId), std::end(ids));

The std::remove*() algorithm "moves" all the bad elements to the end of the container (returning an iterator to the first bad elemenet). Then the erase will "erase" from the container from that point to the end.

Another alternative is to split the container into two. One of bad values and one of good values. A bit more work. But can be made relatively efficient by using std::move(<stcBegin>, <srcEnd>, <dstBegin>)

 // Find all the bad elements and "move" them to the end, by using swap,
 // of your container. Note this is a usually a move (not a copy so cheap).
 auto firstBadValue = std::end(ids);
 for(auto loop = std::begin(ids); loop != firstBadValue; ++loop) {
     if (isBadId(*loop) {
         std::swap_iter(loop, --firstBadValue);
     }
 }

 // Now "move" one set of the elements from the original container
 // to the new container. Remember to reserve enough space to prevent
 // resizing.
 std::size_t            badSize = std::distance(firstBadValue, std::end(ids));
 std::vector<mystruct>  badValues;
 badValues.reserve(badSize);
 std::move(std::make_reverse_iterator(std::end(ids)), std::make_reverse_iterator(firstBadValue), std::back_insert_iterator(badValues));

 // Now that you have moved the elements out.
 // Reset the correct size of your original container.
 ids.resize(ids.size() - badSize);

The other thing I would note about your code is the use of container.begin(). The standard now provides std::begin() and std::end(). By using these functions you make your code easier to re-use with different container types (especially if you want to use C-Arrays).

Note: In the code above I use badIds as a filtering function. Filters are easy to write as lambdas.

 auto isBadId = [&bad_ids](mystruct const& item) {
     return std::find(std::begin(bad_ids), std::end(bad_ids), item.id) != std::end(bad_ids);
 }

But writing your filter like this (or as a separate function) is always a good idea. It makes your code more readable. This is called self documenting code. If we look at your original code and replace the test with a functor it make it more readable:

// Original Code.
for (const auto& item : all_items) {
    if ( std::find(bad_ids.begin(), bad_ids.end(), item.id) != bad_ids.end() ) {
        std::cout << "id: " << item.id << " is bad" << std::endl;
    } else {
        std::cout << "id: " << item.id << " is good item" << std::endl;
        filter_items.emplace_back(item);
    }
}

// Self documenting code:
// Easier to read and deduce things about.
for (auto const& item : all_items) {
    if (isBadId(item)) {
        logItem(asBad,  item);
    } else {
        logItem(asGood, item);
        filter_items.emplace_back(item);
    }
}