C++ Maps for Many-to-Many

Question

i need a data structure to store this info so that: (I have MANY -to- MANY )

1 .given an employee i can find out the projects 2. given the projects i can find the employee

If I use multi map then I will need to maintain 2 maps, Is there any other data structure that I can use here?

Answer 1

You can either use two maps or you can use Boost.Bimap.

Answer 2

You can use Boost.MultiIndex.

You can define the container as followed:

struct Connection
{
   Employee emp;
   Project  prj;
};

typedef multi_index_container
<
    Connection,
    indexed_by
    <
        ordered_unique< identity<Connection> >,
        ordered_non_unique< member<Connection, Employee, &Connection::emp> >,
        ordered_non_unique< member<Connection, Project, &Connection::prj> >
    >
> Relation;

Here is a runnable sample:

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

#include <iostream>
#include <string>
#include <functional>

namespace mi = boost::multi_index;

// these two type should implement std::less or operator<
typedef std::string Employee; // change to your definition
typedef std::string Project;  // change to your definition

struct Connection
{
   Employee emp;
   Project  prj;

   Connection(const Employee& e, const Project& p): emp(e), prj(p) {}
   bool operator <(const Connection& rhs) const
   {
      return std::less<Employee>()(emp, rhs.emp) ||
             ( emp == rhs.emp && std::less<Project>()(prj, rhs.prj) );
   }
};

struct employee {}; // for tag
struct project  {}; // for tag

typedef mi::multi_index_container
<
    Connection,
    mi::indexed_by
    <
        mi::ordered_unique
        <
            mi::identity<Connection>
        >,
        mi::ordered_non_unique
        <
            mi::tag<employee>,
            mi::member<Connection, Employee, &Connection::emp>
        >,
        mi::ordered_non_unique
        <
            mi::tag<project>,
            mi::member<Connection, Project, &Connection::prj>
        >
    >
> Relation;

typedef Relation::index_iterator<employee>::type EmpIter;
typedef Relation::index_iterator<project>::type  PrjIter;

int main()
{
    Relation rel;

    rel.insert(Connection("Tom",   "sleeping"));
    rel.insert(Connection("Jerry", "sleeping"));
    rel.insert(Connection("Spike", "sleeping"));
    rel.insert(Connection("Tom",   "tormenting-partner"));
    rel.insert(Connection("Jerry", "tormenting-partner"));
    rel.insert(Connection("Spike", "playing-with-tyke"));
    rel.insert(Connection("Tom",   "fishing"));
    rel.insert(Connection("Jerry", "playing-with-nibbles"));
    rel.insert(Connection("Jerry", "tormenting-partner")); // duplicated

    std::cout << "total connections: " << rel.size() << std::endl;

    std::cout << "employees connected with sleeping project:" << std::endl;
    std::pair<PrjIter, PrjIter> pit = rel.get<project>().equal_range("sleeping");
    for (PrjIter it = pit.first; it != pit.second; ++it)
        std::cout << '\t' << it->emp << std::endl;

    std::cout << "projects connected with Jerry:" << std::endl;
    std::pair<EmpIter, EmpIter> eit = rel.get<employee>().equal_range("Jerry");
    for (EmpIter it = eit.first; it != eit.second; ++it)
        std::cout << '\t' << it->prj << std::endl;

    return 0;
}

the result：

total connections: 8
employees connected with sleeping project:
        Tom
        Jerry
        Spike
projects connected with Jerry:
        sleeping
        tormenting-partner
        playing-with-nibbles