How to get the distinct count of first key in boost::multi_index_container with composite key

Question

boost::multi_index_container enables the construction of containers maintaining one or more indices with different sorting and access semantics like relational database. And I use boost::multi_index_container with composite key to handle something like this:

struct Person {
    Person(int id, string name):
        m_id(id),
        m_name(name)
    {
    }

    int m_id;
    string m_name;
};

typedef multi_index_container<
    Person,
    indexed_by<
        ordered_unique<
            member<Person, int, &Person::m_id>
        >,
        ordered_unique<
            composite_key<
                Person,
                member<Person, string, &Person::m_name>,
                member<Person, int, &Person::m_id>
            >
         >
    >
> Roster;

int main()
{
    Roster r;
    r.insert(Person(1, "Tom"));
    r.insert(Person(2, "Jack"));
    r.insert(Person(3, "Tom"));
    r.insert(Person(4, "Leo"));

    /* The distinct count of name must be 3, and how to get it? */
}

Is that any way to get the distinct count of the non-unique index key in boost::multi_index_container like relational database? And how to get the distinct count of first key(Person::name) of Roster composite key(Person::m_name, Person::m_id)? THX!

EDIT: Or is it that a way to just iterate the distinct first key? So that we can get the distinct count of first key.

Answer 1

You can exploit the fact that you know the composite index is order by m_name first.

This means you can run a standard "unique" across it without an additional sort step:

    size_t unique_names = boost::size(r.get<by_name_id>() 
            | transformed([](Person const& p) -> std::string const& { return p.m_name; })
            | uniqued
        );

This could be a good time/storage trade-off here.

Demo

Live On Coliru

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/composite_key.hpp>

struct Person {
    Person(int id, std::string name):
        m_id(id),
        m_name(name)
    {
    }

    int m_id;
    std::string m_name;
};

namespace bmi = boost::multi_index;

typedef boost::multi_index_container<
    Person,
    bmi::indexed_by<
        bmi::ordered_unique<
            bmi::member<Person, int, &Person::m_id>
        >,
        bmi::ordered_unique<
            bmi::tag<struct by_name_id>,
            bmi::composite_key<
                Person,
                bmi::member<Person, std::string, &Person::m_name>,
                bmi::member<Person, int, &Person::m_id>
            >
        >
    >
> Roster;

#include <iostream>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>

using boost::adaptors::transformed;
using boost::adaptors::uniqued;

int main()
{
    Roster r;
    r.insert(Person(1, "Tom"));
    r.insert(Person(2, "Jack"));
    r.insert(Person(3, "Tom"));
    r.insert(Person(4, "Leo"));

    size_t unique_names = boost::size(r.get<by_name_id>() 
            | transformed([](Person const& p) -> std::string const& { return p.m_name; })
            | uniqued
        );

    std::cout << unique_names;
}

Prints

3

Answer 2

Another possibilty, probably faster if there are many elements with the same key, involves hopping through the index using upper_bound:

Live On Coliru

template<typename Index,typename KeyExtractor>
std::size_t distinct(const Index& i,KeyExtractor key)
{
  std::size_t res=0;
  for(auto it=i.begin(),it_end=i.end();it!=it_end;){
    ++res;
    it=i.upper_bound(key(*it));
  }
  return res;
}

int main()
{
    Roster r;
    r.insert(Person(1, "Tom"));
    r.insert(Person(2, "Jack"));
    r.insert(Person(3, "Tom"));
    r.insert(Person(4, "Leo"));

    auto d=distinct(r.get<1>(),[](const Person& p){return std::cref(p.m_name);});
    std::cout<<d<<"\n";
}