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 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

Answer 2

I don't know of any prepackaged data structure to do this in standard C++. Seems to me like you'd need two data structures, of the form:

std::map<unsigned long,std::vector<unsigned long> > employee_projects

And one such as:

std::map<unsigned long,std::vector<unsigned long> > project_employees

Where employee_projects is a list of integers (employeeIDs) mapping to a list of projectIDs), and project_employees is the converse. Prepopulate both, and you can quickly reference them throughout your application.

Caveat: Any modifications during runtime will have to be manually applied to each structure.

Answer 3

You can go with two big global-ish multimaps as you suggest, or you could maintain the information locally in the project and employee data structures. Have the Project class contain a vector (or set) of pointers to Employee, and the Employee class contain a vector/set of pointers to Project, plus a function that associates an Employee to a Project by pushing a pointer to each onto the vector of the other. Then given either object, you can get the collection of objects of the other type that are associated with it. Something like:

    (in Employee.h):
class Project;  // Forward declare project

class Employee {
public:
  AddProject(Project *proj);
  vector<Project *> projects();
  size_t num_projects() {return projects_.size();}
  Project *project(size_t i) {return projects_[i];}
private:
  vector<Project *> projects_;
};

and similarly for Project.h.

Either approach can work; the local approach is the way you would typically do it in a language like C where you don't have multimap available. You can also use indices or IDs in place of pointers. One advantage of the local approach is that more of the work you need to do with Projects and Employees can become local behavior of the Project/Employee classes, implemented with methods of those classes, and unit tested separately from the rest of the system. That doesn't work with the multimap approach, since the individual classes know nothing of the multimaps.

The difference isn't so apparent here, where you only have the two classes, but I've seen cases where lots of these kinds of relationships were represented with large global-ish data structures that were part of a huge monster class, and unit testing became almost impossible (since you needed to set up so many data structures in the monster class to get anything done).

Answer 4

Pick the relationship that you think will be the most common and create that map. Then, either write function or derive from a map class and extend with a method for doing the lookup the other direction. That lookup will obviously be much slower (will have to iterate over the values) but it would let you get away with using only one map.

Probably would make the most sense to wrap the whole thing in a class so you can change the map if you realize you need the other look up more or you want to switch to using 2 maps or some other solution.

Answer 5

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