C ++ maps for many-to-many

Question

I need a data structure to store this information so that: (I have MUCH MANY)

1. Thanks to the employee, I can find out about projects 2. given the projects, I can find an employee

If I use multiple cards, then I will need to support 2 cards, Is there any other data structure that I can use here?

Answer 1

You can use two cards or use Boost.Bimap .

Answer 2

You can go with two large global multisymbols, as you suggest, or you can maintain information locally in the project and employee data structures. Let the Project class contain a vector (or set) of pointers to Employee, and the Employee class contain a vector / set of pointers to Project, as well as a function that associates an employee with a project by clicking on each other vector. Then, by specifying any object, you can get a collection of objects of another 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.

Any approach can work; a local approach is how you usually do it in a language like C, where you don't have access to multimages. You can also use indexes or identifiers instead of pointers. One of the advantages of the local approach is that most of the work you need to do with projects and employees can become the local behavior of the Project / Employee classes implemented using the methods of these classes and a module that will be tested separately from the rest of the system. This does not work with a multi-brand approach, as individual classes do not know anything about multiplayer.

The difference here is not so obvious where you have only two classes, but I have seen cases where many of these types of relationships were represented by large global data structures that were part of a huge class of monsters, and unit testing became almost impossible (since you had to create so many data structures in the monster class to do something).

Answer 3

You can use Boost.MultiIndex .

You can define a container as follows:

 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 an example of execution:

 #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; } 

result:

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

Answer 4

I don't know of any pre-packaged data structure to do this in standard C ++. It seems to me that you need two data structures:

 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) mapped to a list of projectIDs), and project_employees is the other way around. Teach both, and you can quickly refer to them during your application.

Caution: any changes at runtime will need to be applied manually to each structure.

Answer 5

Choose the relationships that you think will be the most common and will create this card. Then, either write a function or deduce from the map class and continue using the method to search in the other direction. Obviously, the search will be much slower (you have to sort through the values), but this will allow you to avoid using only one map.

It would probably be most advisable to wrap it all up in class so that you can change the map if you understand that you need a different look or want to switch to using two cards or another solution.