C++ Maps cho Nhiều-to-Nhiều

Question

tôi cần một cấu trúc dữ liệu để lưu trữ thông tin này để: (Tôi có NHIỀU -to- NHIỀU)

1 .given một nhân viên tôi có thể tìm hiểu các dự án 2. cho các dự án tôi có thể tìm thấy nhân viên

Nếu tôi sử dụng nhiều bản đồ thì tôi sẽ cần duy trì 2 bản đồ, Có cấu trúc dữ liệu nào khác mà tôi có thể sử dụng ở đây không?

Answer 1

Bạn có thể sử dụng hai bản đồ hoặc bạn có thể sử dụng Boost.Bimap.

Answer 2

Tôi không biết bất kỳ cấu trúc dữ liệu đóng gói sẵn nào để thực hiện điều này trong C++ chuẩn. Dường như với tôi như bạn cần hai cấu trúc dữ liệu, có dạng:

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

Và một ví dụ như:

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

đâu employee_projects là một danh sách các số nguyên (employeeIDs) ánh xạ tới một danh sách các projectID) và project_employees là trò chuyện. Prepopulate cả hai, và bạn có thể nhanh chóng tham khảo chúng trong suốt ứng dụng của bạn.

Lưu ý: Mọi sửa đổi trong thời gian chạy sẽ phải được áp dụng theo cách thủ công cho mỗi cấu trúc.

Answer 3

Chọn mối quan hệ mà bạn nghĩ sẽ là mối quan hệ phổ biến nhất và tạo bản đồ đó. Sau đó, hoặc viết hàm hoặc lấy được từ một lớp bản đồ và mở rộng với một phương thức để thực hiện tìm kiếm hướng khác. Việc tra cứu đó rõ ràng sẽ chậm hơn nhiều (sẽ phải lặp lại các giá trị) nhưng nó sẽ cho phép bạn thoát khỏi việc sử dụng chỉ một bản đồ.

Có lẽ sẽ có ý nghĩa nhất khi quấn toàn bộ đồ vật trong lớp để bạn có thể thay đổi bản đồ nếu bạn nhận ra mình cần cái nhìn khác hoặc muốn chuyển sang sử dụng 2 bản đồ hoặc một số giải pháp khác.

Answer 4

Bạn có thể sử dụng hai hình đa giác lớn trên toàn cầu như bạn đề xuất hoặc bạn có thể duy trì thông tin cục bộ trong cấu trúc dữ liệu của dự án và nhân viên. Có lớp Project chứa một vector (hoặc set) của con trỏ tới Employee, và lớp Employee chứa một vector/tập hợp con trỏ trỏ tới Project, cộng với một hàm kết hợp Employee với Project bằng cách đẩy một con trỏ tới mỗi vector cai khac. Sau đó, cho một trong hai đối tượng, bạn có thể nhận được bộ sưu tập các đối tượng của loại khác được liên kết với nó. Một cái gì đó như:

(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_; 
}; 

và tương tự cho Project.h.

Hoặc cách tiếp cận có thể hoạt động; cách tiếp cận địa phương là cách bạn thường làm điều đó bằng một ngôn ngữ như C, nơi bạn không có multimap. Bạn cũng có thể sử dụng chỉ mục hoặc ID thay cho con trỏ. Một ưu điểm của phương pháp cục bộ là nhiều công việc bạn cần làm với các dự án và nhân viên có thể trở thành hành vi cục bộ của các lớp Project/Employee, được thực hiện với các phương thức của các lớp đó và đơn vị được kiểm tra riêng biệt với phần còn lại của hệ thống. Điều đó không làm việc với phương pháp tiếp cận multimap, vì các lớp riêng lẻ không biết gì về các multimaps.

Sự khác biệt không rõ ràng ở đây, nơi bạn chỉ có hai lớp, nhưng tôi đã thấy các trường hợp có rất nhiều loại mối quan hệ này được biểu diễn với cấu trúc dữ liệu toàn cầu lớn. lớp và thử nghiệm đơn vị trở nên gần như không thể (vì bạn cần thiết lập rất nhiều cấu trúc dữ liệu trong lớp quái vật để hoàn thành mọi thứ).

Answer 5

Bạn có thể sử dụng Boost.MultiIndex.

Bạn có thể xác định container như sau:

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; 

Đây là một mẫu Runnable:

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

kết quả:

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