Using Boost Filter Iterator with non-Primitive Objects

Question

Lets say I have a returned iterator from Boost's Multi-Index, where each record contains an age and a name field.

I get the iterator with

auto& index = get<age>(m_records);
auto ibegin = index.begin();
auto iend = index.end();

How could I use this iterator with Boost's Filter Iterator so that I could return all records that, say have name = "John"?

I set up a struct for the predicate operator, I'm not sure if it's right:

struct name_equal_to {
      std::string struct_sname;
      bool operator()(ServerRecord x) { return x.get_name() == struct_sname; }
      name_equal_to(std::string in) : struct_sname(in){}
   };

Answer 1

@sehe's answer is absolutely correct, but if you care about efficiency then this is not the fastest way to retrieve all Johns sorted by age. Suppose your container has N elements and there are M Johns among them. So:

1. Traversing all elements sorted by age and filtering by "John" takes N steps.
2. Retrieving all Johns and sorting by age (as discussed in your other post) requires (roughly) 2·log(N) steps to retrieve the range of Johns, one allocation of the temporary vector, M steps to fill it, O(M·log(M)) to sort it and M to traverse it.

So, it is O(N) vs. O(log(N)+M·log(M)). I bet #2 is faster than #1 when M << N, which I take it to be the usual situation (of course you should measure your actual program).

Answer 2

I'd use the filtered adaptor, to make things more readable:

for (auto& r : get<age>(m_records) | filtered(name_equal_to("John"))
    std::cout << r << "\n";

I'd stylistically improve the functor (Live On Coliru):

struct name_equal_to {
    bool operator()(ServerRecord const& x) const { 
        return x.get_name() == sname_; 
    }
    name_equal_to(std::string in) : sname_(std::move(in)){}
  private:
    std::string sname_;
};

And to make it really elegant, use Phoenix to define the predicate named_john in-place:

auto named_john = phx::bind(&record::name, arg1) == "John";

See it Live On Coliru, where it prints two records ordered by the age index:

2 John 40
4 John 57

Full sample code

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/range/iterator_range.hpp>
#include <iostream>

using boost::multi_index_container;
using namespace boost::multi_index;

struct record {
    int         id;
    std::string name;
    int         age;

    friend std::ostream& operator<<(std::ostream& os,const record& e) {
        return os << e.id << " " << e.name << " " << e.age;
    }
};

typedef multi_index_container<
  record,
  indexed_by<
    ordered_unique<tag<struct id>      , BOOST_MULTI_INDEX_MEMBER(record, int        , id)>   ,
    ordered_non_unique<tag<struct name>, BOOST_MULTI_INDEX_MEMBER(record, std::string, name)> ,
    ordered_non_unique<tag<struct age> , BOOST_MULTI_INDEX_MEMBER(record, int        , age)> >
> employee_set;


employee_set get_records()
{
    employee_set es;

    es.insert(record{ 0,       "Joe",   31 });
    es.insert(record{ 1,    "Robert",   27 });
    es.insert(record{ 2,      "John",   40 });
    // next insertion will fail, as there is an record with the same ID
    es.insert(record{ 2, "Aristotle", 2387 });
    es.insert(record{ 3,    "Albert",   20 });
    es.insert(record{ 4,      "John",   57 });

    return es;
}

#include <boost/phoenix.hpp>
#include <boost/range/adaptors.hpp>
namespace phx = boost::phoenix;
using namespace phx::arg_names;
using boost::adaptors::filtered;

int main()
{
    auto const m_records = get_records();

    auto named_john = phx::bind(&record::name, arg1) == "John";

    for (auto& r : get<age>(m_records) | filtered(named_john)) {
        std::cout << r << "\n";
    };
}