Wie können STL-Map-Container mit mehreren Schlüsseln indiziert und abgefragt werden?

Question

stieß ich auf eine Anforderung, wo der Datensatz als

Name : Employee_Id : Address 

wo Name und employee_id sollen gespeichert Schlüssel sein, die eine Suchfunktion ist, sowohl Name und Mitarbeiter-ID zur Verfügung gestellt werden.

kann ich denke, eine Karte mit dieser Struktur

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

aber ich bin nicht ganz sicher zu speichern, wie die Suchfunktion aussehen wird.

Answer 1

Boost.Multiindex

Dies ist ein Boost example

Im obigen Beispiel ein geordneter Index verwendet wird, aber Sie können auch einen Hash-Index verwenden:

#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

Wenn EmployeeID die eindeutige Kennung ist, warum andere Schlüssel benutzen? Ich würde EmployeeID überall als internen Schlüssel verwenden und andere Zuordnungen von externen/von Menschen lesbaren IDs (wie Name) zu ihm haben.

Answer 3

Wenn Sie std :: map verwenden möchten, können Sie zwei separate Container haben, von denen jeder einen anderen Schlüssel (Name, Emp-ID) hat und der Wert sollte ein Zeiger auf die Struktur sein, so dass Sie nicht mehrere Kopien haben der gleichen Daten.

Answer 4

Beispiel mit tew Tasten:

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

Ausgang:

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 :: find nicht-Schlüssel sucht Lösung

Diese Methode spart Sie speichern die Schlüssel zweimal, einmal das indizierte Objekt und zweitens den Schlüssel einer Karte wie unter: https://stackoverflow.com/a/44526820/895245

Dies bietet minimale Beispiele für die zentrale Technik, die leichter sein sollte zuerst verstehen: 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); 
}