How to index and query STL map containers by multiple keys?

Question

I came across one requirement where the record is stored as

Name :  Employee_Id  :  Address

where Name and Employee_Id are supposed to be keys that is, a search function is to be provided on both Name and Employee Id.

I can think of using a map to store this structure

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

but I'm not exactly sure how the search function will look like.

Boost Multi Index Container handles that very well http://www.boost.org/doc/libs/1_41_0/libs/multi_index/doc/index.html — adrianm, Dec 07 '09 at 07:04
You can only give a single ordering criterion for a given map. With plain STL you could use two maps, one ordered by Name and the other by Employee_Id or else use the Boost Multi Index container. — David Rodríguez - dribeas, Dec 07 '09 at 07:17

score 23 · Accepted Answer · 2009-12-08T09:52:32.160

Boost.Multiindex

This is a Boost example

In the above example an ordered index is used but you can use also a hashed index:

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

score 2 · Answer 2 · answered Dec 07 '09 at 09:38

2

If you want to use std::map, you can have two separate containers, each one having adifferent key (name, emp id) and the value should be a pointer the structure, so that you will not have multiple copies of the same data.

answered Dec 07 '09 at 09:38

shyam

21
1

This is a possibility. But a clear problem arise with defining the ownership in such a case. Is it the first container, the second container or does the ownership reside outside of them both. If you are the only one writing and looking at the code this does not have to become an issue. But as soon as someone else start using you containers the confusion is sure to set in. – inquam May 27 '15 at 12:50

score 1 · Answer 3 · answered Jun 13 '17 at 16:20

Example with tew keys:

#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

In c++14 it is also possible to use `set` and not have to store the key twice: https://stackoverflow.com/a/44526820/895245 — Ciro Santilli OurBigBook.com, Feb 09 '18 at 17:20

score 0 · Answer 4 · answered Dec 07 '09 at 07:56

0

If EmployeeID is the unique identifier, why use other keys? I would use EmployeeID as the internal key everywhere, and have other mappings from external/human readable IDs (such as Name) to it.

answered Dec 07 '09 at 07:56

Nikola Gedelovski

1,000
6
12

From a performance perspective that means that to get the item by name you need to do 2 index searches instead of 1. While index searches are naturally fast, there will be a greater performance hit when disk access is involved because you'd be doing another disk read. – Tamir Daniely Jun 30 '15 at 22:09

score 0 · Answer 5 · answered Feb 09 '18 at 17:16

C++14 std::set::find non-key searches solution

This method saves you from storing the keys twice, once one the indexed object and secondly on as the key of a map as done at: https://stackoverflow.com/a/44526820/895245

This provides minimal examples of the central technique that should be easier to understand first: 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);
}

How to index and query STL map containers by multiple keys?

5 Answers5

Linked