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

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

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 4

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