使用隐式键的哈希表容器的标准实现、boost或其他流行实现

Question

如果我理解正确，std::map和std::unordered_map都会显式存储键（存储键/值对）。是否有其他现成的容器（std、boost或其他广泛实现的容器），它不会存储键，而是允许使用函数从存储的值中派生键（即使用隐式键）？

- Suma

Answer 1

使用适当的哈希和/或比较函数为存储值类型选择std::set或std::unordered_set。

但是，查找将根据存储值类型而不是键执行，因此您还需要一种方法从键中制造临时对象。

- Mike Seymour

---

这些是否允许您仅使用键进行查找，而无需完整对象？ - R. Martinho Fernandes

@R.MartinhoFernandes：我想不是；也许我误解了问题。但只要您可以轻松地从键创建临时对象，这可能是一个明智的方法。 - Mike Seymour

@R.MartinhoFernandes，那将是一个不同的问题/要求（我的理解）。开箱即用，您可以创建一个部分对象，其中包含足够生成密钥所需的信息。然而，在大多数非极端情况下，我仍然会存储密钥（现在内存很便宜）。 - David Rodríguez - dribeas

Answer 2

您可能正在寻找Boost.Intrusive。 Boost Intrusive容器“钩入”您的值类型，以直接从对象中提供某个容器（例如set，list，AVL树等）的特性。

请参阅内部和非内部容器之间的区别，了解STL容器和Boost Intrusive容器之间的区别概述。

- Daniel Trebbien

Answer 3

C++库中的所有有序容器，例如std::set，都允许使用less comparison模板特性，将其作为第二个模板参数传递（在下面的示例中为my_less）。如果不这样做，operator<将通过ADL查找并在找到时使用它（如果未找到，则编译错误）；对于许多情况来说，这应该是合适的。

您自己的特性或operator<可以用于根据存储在集合中的数据定义顺序，即无需键。执行此比较不会复制任何数据，请注意它采用const引用。

如果您不想创建堆栈对象，而更喜欢使用堆指针，则可以在标准有序容器中存储boost::shared_ptr，并相应地编写您的less comparison特性。在这种情况下，您还可以考虑使用boost ptr containers。

示例：

#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

- bronekk

---

正如我在另一个答案中提到的那样，这个问题的困难在于你需要一个完整的对象来进行查找。你不能像使用 map 一样只用一个键进行查找。 - R. Martinho Fernandes

我不理解某些内容。你想从什么中派生密钥，应该由谁进行此派生？上述代码从存储的值中派生密钥。如果需要，可以委托此过程，例如委托给容器中存储的类的成员函数。如果您想在实际访问该值之前派生密钥，那么用于派生密钥值所需的数据将来自哪里？ - bronekk

你能否使用 data[x]，其中 x 不是一个完整的 order_by_AB 对象？因为有时候很难获得一个完整的对象：比如，假设该对象持有某些资源。 - R. Martinho Fernandes

我不确定你所说的“full object”是什么意思，能否请您详细说明一下？ - bronekk

@bronekk 我想从存储的值（或正在插入的值）中派生密钥。 派生应由我可以提供的函数完成（例如，通过特性）。 R.M.F. 的另一个问题被其他人很好地解决了 - 完整对象相当大且构造非常复杂，因此仅按键搜索将非常方便。我们已经在内部实现了这样的容器，但如果可能的话，我希望能够找到一些标准的替代品。 - Suma

您可以通过模板参数提供的函数对象，我已更新示例代码。由于没有进行任何复制，因此我仍然不理解您的其他问题。 - bronekk