Find all matching elements in std::list

Question

I was wondering if there's any built-in or well-established way (i.e. via lambda) to go through the elements of an std::list and find all the ones that match a given value? I know I can iterate through all of them, but I thought I'd ask if there's a way to get an iterator that iterates through just the elements that match a given criteria? My sample below only gives me the iterator to the first matching element.

#include <list>
#include <algorithm>
#include <stdio.h>

int main()
{
    std::list<int> List;
    List.push_back(100);
    List.push_back(200);
    List.push_back(300);
    List.push_back(100);
    int findValue = 100;

    auto it = std::find_if(List.begin(), List.end(), [findValue](const int value)
    {
        return (value == findValue);
    });

    if (it != List.end())
    {
        for (; it != List.end(); ++it)
        {
            printf("%d\n", * it);
        }
    }
    return 0;
}

Thanks for any feedback.

Answer 1

std::find_if is a generalisation of std::find for when you need a function to check for the elements you want, rather than a simple test for equality. If you just want to do a simple test for equality then there's no need for the generalised form, and the lambda just adds complexity and verbosity. Just use std::find(begin, end, findValue) instead:

std::vector<std::list<int>::const_iterator> matches;
auto i = list.begin(), end = list.end();
while (i != end)
{
  i = std::find(i, end, findValue);
  if (i != end)
    matches.push_back(i++);
}

But rather than calling find in a loop I'd just write the loop manually:

std::vector<std::list<int>::const_iterator> matches;
for (auto i = list.begin(), toofar = list.end(); i != toofar; ++i)
  if (*i == findValue)
    matches.push_back(i);

Answer 2

Updated answer

With the advent of C++20 just around the corner, the standard library has now introduced the concept of ranges which comes with view adapters and are simply lazy views over collections and their transformations.

This means you can now have an "iterator" which can be used to obtain a filtered and transformed view of an underlying container/collection, without having to create several iterators or even allocate memory.

Having said that, this is a way to create a view over just the filtered elements of your list:

// List is your std::list
auto matching_100 = List | std::views::filter([](auto &v) {
  return v == 100;
});

How sweet is that? All you need to use all that?

#include <ranges>

Try it out

---

Previous answer

Using copy_if and iterators:

#include <list>
#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
    std::list<int> List;
    List.push_back(100);
    List.push_back(200);
    List.push_back(300);
    List.push_back(100);
    int findValue = 100;

    std::copy_if(List.begin(), List.end(), std::ostream_iterator<int>(std::cout, "\n"), [&](int v) {
        return v == findValue;
    });
    return 0;
}

If you don't want to directly output the results and want to fill another container with the matches:

std::vector<int> matches;
std::copy_if(List.begin(), List.end(), std::back_inserter(matches), [&](int v) {
    return v == findValue;
});

Answer 3

boost::filter_iterator allows you to work with only the elements of a iterable that satisfy a predicate. Given a predicate Pred and a container Cont,

auto begin_iter = boost::make_filter_iterator(Pred, std::begin(Cont), std::end(Cont));
auto end_iter = boost::make_filter_iterator(Pred, std::end(Cont), std::end(Cont));

You can now use begin_iter and end_iter as if they were the begin and end iterators of a container containing only those elements of Cont that satisfied Pred. Another added advantage is that you can wrap the iterators in a boost::iterator_range and use it in places which expect a iterable object, like a range-based for loop like this:

auto range = boost::make_iterator_range(begin_iter, end_iter);
for(auto x : range) do_something(x);

In particular, setting Pred to a functor(could be a lambda) that checks for equality with your fixed value will give you the iterators you need.

Answer 4

std::partition lets you simply move all elements matching the predicate to the front of the container (first partition). The return value is an iterator pointing to the first element of the second partition (containing the non matching elements). That's pretty much all you need to "filter" a container.