Làm cách nào để lập chỉ mục và truy vấn vùng chứa bản đồ STL bằng nhiều khóa?

Question

Tôi đã xem qua một yêu cầu, nơi ghi chép được lưu giữ như

Name : Employee_Id : Address 

nơi Tên và Employees_ID có nghĩa vụ phải được phím đó là một chức năng tìm kiếm là để được cung cấp trên cả Tên và Id nhân viên.

tôi có thể nghĩ của việc sử dụng bản đồ để lưu trữ cấu trúc này

std::map< std:pair<std::string,std::string> , std::string > 
//  <   < Name , Employee-Id> , Address  > 

nhưng tôi không chắc chắn chính xác như thế nào chức năng tìm kiếm sẽ như thế nào.

Answer 1

Boost.Multiindex

Đây là một Boost example

Trong ví dụ trên một chỉ số lệnh được sử dụng nhưng bạn có thể sử dụng cũng là một chỉ số băm:

#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/member.hpp> 
#include <boost/multi_index/ordered_index.hpp> 
#include <boost/multi_index/hashed_index.hpp> 
#include <string> 
#include <iostream> 

struct employee 
{ 
    int   id_; 
    std::string name_; 
    std::string address_; 

    employee(int id,std::string name,std::string address):id_(id),name_(name),address_(address) {} 

}; 

struct id{}; 
struct name{}; 
struct address{}; 
struct id_hash{}; 
struct name_hash{}; 


typedef boost::multi_index_container< 
    employee, 
    boost::multi_index::indexed_by< 
     boost::multi_index::ordered_unique<boost::multi_index::tag<id>, BOOST_MULTI_INDEX_MEMBER(employee,int,id_)>, 
     boost::multi_index::ordered_unique<boost::multi_index::tag<name>,BOOST_MULTI_INDEX_MEMBER(employee,std::string,name_)>, 
     boost::multi_index::ordered_unique<boost::multi_index::tag<address>, BOOST_MULTI_INDEX_MEMBER(employee,std::string,address_)>, 
     boost::multi_index::hashed_unique<boost::multi_index::tag<id_hash>, BOOST_MULTI_INDEX_MEMBER(employee,int,id_)>, 
     boost::multi_index::hashed_unique<boost::multi_index::tag<name_hash>, BOOST_MULTI_INDEX_MEMBER(employee,std::string,name_)> 
    > 
> employee_set; 

typedef boost::multi_index::index<employee_set,id>::type employee_set_ordered_by_id_index_t; 
typedef boost::multi_index::index<employee_set,name>::type employee_set_ordered_by_name_index_t; 
typedef boost::multi_index::index<employee_set,name_hash>::type employee_set_hashed_by_name_index_t; 

typedef boost::multi_index::index<employee_set,id>::type::const_iterator employee_set_ordered_by_id_iterator_t; 
typedef boost::multi_index::index<employee_set,name>::type::const_iterator employee_set_ordered_by_name_iterator_t; 


typedef boost::multi_index::index<employee_set,id_hash>::type::const_iterator employee_set_hashed_by_id_iterator_t; 
typedef boost::multi_index::index<employee_set,name_hash>::type::const_iterator employee_set_hashed_by_name_iterator_t; 


int main() 
{ 
    employee_set employee_set_; 

    employee_set_.insert(employee(1, "Employer1", "Address1")); 
    employee_set_.insert(employee(2, "Employer2", "Address2")); 
    employee_set_.insert(employee(3, "Employer3", "Address3")); 
    employee_set_.insert(employee(4, "Employer4", "Address4")); 

    // search by id using an ordered index 
    { 
     const employee_set_ordered_by_id_index_t& index_id = boost::multi_index::get<id>(employee_set_); 
     employee_set_ordered_by_id_iterator_t id_itr = index_id.find(2); 
     if (id_itr != index_id.end()) { 
      const employee& tmp = *id_itr; 
      std::cout << tmp.id_ << ", " << tmp.name_ << ", " << tmp .address_ << std::endl; 
     } else { 
      std::cout << "No records have been found\n"; 
     } 
    } 

    // search by non existing id using an ordered index 
    { 
     const employee_set_ordered_by_id_index_t& index_id = boost::multi_index::get<id>(employee_set_); 
     employee_set_ordered_by_id_iterator_t id_itr = index_id.find(2234); 
     if (id_itr != index_id.end()) { 
      const employee& tmp = *id_itr; 
      std::cout << tmp.id_ << ", " << tmp.name_ << ", " << tmp .address_ << std::endl; 
     } else { 
      std::cout << "No records have been found\n"; 
     } 
    } 

    // search by name using an ordered index 
    { 
     const employee_set_ordered_by_name_index_t& index_name = boost::multi_index::get<name>(employee_set_); 
     employee_set_ordered_by_name_iterator_t name_itr = index_name.find("Employer3"); 
     if (name_itr != index_name.end()) { 
      const employee& tmp = *name_itr; 
      std::cout << tmp.id_ << ", " << tmp.name_ << ", " << tmp .address_ << std::endl; 
     } else { 
      std::cout << "No records have been found\n"; 
     } 
    } 

    // search by name using an hashed index 
    { 
     employee_set_hashed_by_name_index_t& index_name = boost::multi_index::get<name_hash>(employee_set_); 
     employee_set_hashed_by_name_iterator_t name_itr = index_name.find("Employer4"); 
     if (name_itr != index_name.end()) { 
      const employee& tmp = *name_itr; 
      std::cout << tmp.id_ << ", " << tmp.name_ << ", " << tmp .address_ << std::endl; 
     } else { 
      std::cout << "No records have been found\n"; 
     } 
    } 

    // search by name using an hashed index but the name does not exists in the container 
    { 
     employee_set_hashed_by_name_index_t& index_name = boost::multi_index::get<name_hash>(employee_set_); 
     employee_set_hashed_by_name_iterator_t name_itr = index_name.find("Employer46545"); 
     if (name_itr != index_name.end()) { 
      const employee& tmp = *name_itr; 
      std::cout << tmp.id_ << ", " << tmp.name_ << ", " << tmp .address_ << std::endl; 
     } else { 
      std::cout << "No records have been found\n"; 
     } 
    } 

    return 0; 
} 

Answer 2

Nếu EmployeeID là định danh duy nhất, tại sao sử dụng các phím khác? Tôi sẽ sử dụng EmployeeID làm khóa bên trong ở khắp mọi nơi và có các ánh xạ khác từ các ID có thể đọc được bên ngoài/con người (chẳng hạn như Tên) cho nó.

Answer 3

Nếu bạn muốn sử dụng std :: map, bạn có thể có hai thùng chứa riêng biệt, mỗi cái có khóa khác nhau (tên, id id) và giá trị phải là cấu trúc con trỏ, do đó bạn sẽ không có nhiều bản sao của cùng một dữ liệu.

Answer 4

Ví dụ với các phím TEW:

#include <memory> 
#include <map> 
#include <iostream> 

template <class KEY1,class KEY2, class OTHER > 
class MultiKeyMap { 
    public: 
    struct Entry 
    { 
    KEY1 key1; 
    KEY2 key2; 
    OTHER otherVal; 
    Entry(const KEY1 &_key1, 
      const KEY2 &_key2, 
      const OTHER &_otherVal): 
      key1(_key1),key2(_key2),otherVal(_otherVal) {}; 
    Entry() {}; 
    }; 
    private: 
    struct ExtendedEntry; 
    typedef std::shared_ptr<ExtendedEntry> ExtendedEntrySptr; 
    struct ExtendedEntry { 
    Entry entry; 
    typename std::map<KEY1,ExtendedEntrySptr>::iterator it1; 
    typename std::map<KEY2,ExtendedEntrySptr>::iterator it2; 
    ExtendedEntry() {}; 
    ExtendedEntry(const Entry &e):entry(e) {}; 
    }; 
    std::map<KEY1,ExtendedEntrySptr> byKey1; 
    std::map<KEY2,ExtendedEntrySptr> byKey2; 

    public: 
    void del(ExtendedEntrySptr p) 
    { 
    if (p) 
    { 
     byKey1.erase(p->it1); 
     byKey2.erase(p->it2); 
    } 
    } 

    void insert(const Entry &entry) { 
    auto p=ExtendedEntrySptr(new ExtendedEntry(entry)); 
    p->it1=byKey1.insert(std::make_pair(entry.key1,p)).first; 
    p->it2=byKey2.insert(std::make_pair(entry.key2,p)).first; 
    } 
    std::pair<Entry,bool> getByKey1(const KEY1 &key1) 
    { 
    const auto &ret=byKey1[key1]; 
    if (ret) 
     return std::make_pair(ret->entry,true); 
    return std::make_pair(Entry(),false); 
    } 
    std::pair<Entry,bool> getByKey2(const KEY2 &key2) 
    { 
    const auto &ret=byKey2[key2]; 
    if (ret) 
     return std::make_pair(ret->entry,true); 
    return std::make_pair(Entry(),false); 
    } 
    void deleteByKey1(const KEY1 &key1) 
    { 
    del(byKey1[key1]); 
    } 
    void deleteByKey2(const KEY2 &key2) 
    { 
    del(byKey2[key2]); 
    } 
}; 


int main(int argc, const char *argv[]) 
{ 
    typedef MultiKeyMap<int,std::string,int> M; 
    M map1; 
    map1.insert(M::Entry(1,"aaa",7)); 
    map1.insert(M::Entry(2,"bbb",8)); 
    map1.insert(M::Entry(3,"ccc",9)); 
    map1.insert(M::Entry(7,"eee",9)); 
    map1.insert(M::Entry(4,"ddd",9)); 
    map1.deleteByKey1(7); 
    auto a=map1.getByKey1(2); 
    auto b=map1.getByKey2("ddd"); 
    auto c=map1.getByKey1(7); 
    std::cout << "by key1=2 (should be bbb): "<< (a.second ? a.first.key2:"Null") << std::endl; 
    std::cout << "by key2=ddd (should be ddd): "<< (b.second ? b.first.key2:"Null") << std::endl; 
    std::cout << "by key1=7 (does not exist): "<< (c.second ? c.first.key2:"Null") << std::endl; 
    return 0; 
} 

Output:

by key1=2 (should be bbb): bbb 
by key2=ddd (should be ddd): ddd 
by key1=7 (does not exist): Null 

Answer 5

C++ 14 std :: set :: tìm tìm kiếm phi-key giải pháp

phương pháp này tiết kiệm bạn lưu trữ khóa hai lần, một khi một đối tượng được lập chỉ mục và thứ hai là khóa của bản đồ được thực hiện tại: https://stackoverflow.com/a/44526820/895245

này cung cấp ví dụ tối thiểu về kỹ thuật trung ương cần được dễ dàng hơn để hiểu đầu tiên: How to make a C++ map container where the key is part of the value?

#include <cassert> 
#include <set> 
#include <vector> 

struct Point { 
    int x; 
    int y; 
    int z; 
}; 

class PointIndexXY { 
    public: 
     void insert(Point *point) { 
      sx.insert(point); 
      sy.insert(point); 
     } 
     void erase(Point *point) { 
      sx.insert(point); 
      sy.insert(point); 
     } 
     Point* findX(int x) { 
      return *(this->sx.find(x)); 
     } 
     Point* findY(int y) { 
      return *(this->sy.find(y)); 
     } 
    private: 
     struct PointCmpX { 
      typedef std::true_type is_transparent; 
      bool operator()(const Point* lhs, int rhs) const { return lhs->x < rhs; } 
      bool operator()(int lhs, const Point* rhs) const { return lhs < rhs->x; } 
      bool operator()(const Point* lhs, const Point* rhs) const { return lhs->x < rhs->x; } 
     }; 
     struct PointCmpY { 
      typedef std::true_type is_transparent; 
      bool operator()(const Point* lhs, int rhs) const { return lhs->y < rhs; } 
      bool operator()(int lhs, const Point* rhs) const { return lhs < rhs->y; } 
      bool operator()(const Point* lhs, const Point* rhs) const { return lhs->y < rhs->y; } 
     }; 
     std::set<Point*, PointCmpX> sx; 
     std::set<Point*, PointCmpY> sy; 
}; 

int main() { 
    std::vector<Point> points{ 
     {1, -1, 1}, 
     {2, -2, 4}, 
     {0, 0, 0}, 
     {3, -3, 9}, 
    }; 
    PointIndexXY idx; 
    for (auto& point : points) { 
     idx.insert(&point); 
    } 
    Point *p; 
    p = idx.findX(0); 
    assert(p->y == 0 && p->z == 0); 
    p = idx.findX(1); 
    assert(p->y == -1 && p->z == 1); 
    p = idx.findY(-2); 
    assert(p->x == 2 && p->z == 4); 
}