std, boost или другая широко распространенная реализация контейнера хеш-таблицы с неявными ключами

Question

Если я правильно понимаю, и std :: map, и std :: unordered_map хранят ключи явно (хранят пары ключей / значений). Существует ли какой-либо другой готовый к использованию контейнер (std, boost или другая широко распространенная реализация), который бы не сохранял ключ, а позволил бы извлечь ключ из сохраненного значения с помощью функции (то есть использовать неявный ключ?).

Answer 1

std::set или std::unordered_set, с подходящими функциями хеширования и / или сравнения для типа сохраненного значения.

Однако поиск будет выполняться по типу сохраненного значения, а не по ключу, поэтому вы 'Также потребуется способ изготовления временного объекта из ключа.

Answer 2

Возможно, вы ищете Boost.Intrusive . Boost Intrusive контейнеры «подключаются» к вашим типам значений, чтобы предоставить характеристики определенного контейнера (например, набора, списка, дерева AVL и т. Д.) Непосредственно из объектов.

См. Различия между навязчивыми и неинтрузивными контейнерами для обзора различий между контейнерами STL и контейнерами Boost Intrusive.

Answer 3

Все заказанные контейнеры в библиотеке C ++, например, std::set допускают меньше сравнения признак шаблона, передают его в качестве второго параметра шаблона (my_less в примере ниже).,Если вы этого не сделаете, operator< будет найден через ADL и использован, если найден (ошибка компиляции, если нет);это должно подходить для множества случаев.

Ваша собственная черта или operator< может использоваться для определения порядка в соответствии с данными, хранящимися в наборе, т.е. без ключа.Для этого сравнения данные не копируются, обратите внимание, что для этого требуются постоянные ссылки.

Если вы не хотите создавать стековый объект и предпочитаете использовать вместо него указатели кучи, вы, очевидно, можете хранить boost::shared_ptr в стандартном упорядоченном контейнере и написать свою черту минус сравнение соответственно.В этом случае вы также можете рассмотреть возможность использования boost ptr-контейнеров

Пример:

#include <boost/shared_ptr.hpp>
#include <set>
#include <iterator>
#include <iostream>

struct order_by_AB { int a; int b; int c; 
  order_by_AB(int a, int b, int c) : a(a), b(b), c(c) {}
};

struct my_less
{
  bool operator()(const boost::shared_ptr<order_by_AB>& lh, const boost::shared_ptr<order_by_AB>& rh)
  {
    if (lh->a == rh->a)
      return lh->b < rh->b;
    return lh->a < rh->a;
  }
};

std::ostream& operator<< (std::ostream& os, const boost::shared_ptr<order_by_AB>& rh)
{
  os << "(" << rh->a << "," << rh->b << "," << rh->c << ")";
  return os;
}

int main()
{
    std::set<boost::shared_ptr<order_by_AB>, my_less> data;
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(0, 1, 2)));
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(2, 3, 2)));
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(0, 3, 2)));
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(2, 1, 2)));
    std::copy(data.begin(), data.end(), std::ostream_iterator<boost::shared_ptr<order_by_AB>>(std::cout, "\n"));
    return 0;
}

Отредактировано , чтобы привести пример пользовательского функтора длясравнение. Отредактировано для добавления boost::shared_ptr в контейнер