是否有一个扁平的未排序 map/set 实现？

Question

有 boost.container flat_map 和其他人，还有 Loki AssocVector 和许多其他类似的保持元素排序的人。

是否有一个现代的（c++11 支持移动等）实现未排序的矢量作为 map/set？

我们的想法是将它用于非常小的 maps/sets（少于 20 个元素）和简单的键（对于这些键，散列并不总是有意义）

Answer 1

有 std::unordered_set 和 std::unordered_map 但据我所知它们不是使用矢量实现的。

一个可能的选择是编写您自己的散列向量并使用 std::hash<Key> 对密钥进行散列，然后对结果数字以向量长度为模进行索引，但是您必须想出一种方法来手动处理碰撞和所有由此产生的问题。不确定我是否推荐过。

另一种方法是将自定义分配器传递给 std::unordered_set 和 std::unordered_map，它们在向量上执行分配（例如，通过拥有一个内部向量），如 [=15= 所建议的那样].

Answer 2

如果集合肯定很小，那么您可以只使用 std::vector（或 std::deque）并使用线性搜索进行查找。对小向量的 O(n) 线性搜索比对更复杂的结构（例如红黑树）的 O(log(n)) 搜索更快。

因此您可以将元素放入 vector 中而不对它们进行排序。如果删除元素，您仍然需要进行一些改组，但对于平面类矢量结构，无论是否排序，这始终是正确的，除非您只删除后面的元素。为什么平整很重要？

Answer 3

是这样的吗？

template<class Key, class Value, template<class...>class Storage=std::vector>
struct flat_map {
  struct kv {
    Key k;
    Value v;
    template<class K, class V>
    kv( K&& kin, V&& vin ):k(std::forward<K>(kin)), v(std::forward<V>(vin)){}
  };
  using storage_t = Storage<kv>;
  storage_t storage;

  // TODO: adl upgrade
  using iterator=decltype(std::begin(std::declval<storage_t&>()));
  using const_iterator=decltype(std::begin(std::declval<const storage_t&>()));
  // boilerplate:
  iterator begin() {
    using std::begin;
    return begin(storage);
  }
  const_iterator begin() const {
    using std::begin;
    return begin(storage);
  }
  const_iterator cbegin() const {
    using std::begin;
    return begin(storage);
  }
  iterator end() {
    using std::end;
    return end(storage);
  }
  const_iterator end() const {
    using std::end;
    return end(storage);
  }
  const_iterator cend() const {
    using std::end;
    return end(storage);
  }
  size_t size() const {
    return storage.size();
  }
  bool empty() const {
    return storage.empty();
  }
  // these only have to be valid if called:
  void reserve(size_t n) {
    storage.reserve(n);
  }
  size_t capacity() const {
    return storage.capacity();
  }
  // map-like interface:
  // TODO: SFINAE check for type of key
  template<class K>
  Value& operator[](K&& k){
    auto it = find(k);
    if (it != end()) return it->v;
    storage.emplace_back( std::forward<K>(k), Value{} );
    return storage.back().v;
  }
private: // C++14, but you can just inject the lambda at point of use in 11:
  template<class K>
  auto key_match( K& k ) {
    return [&k](kv const& kv){
      return kv.k == k;
    };
  }
public:
  template<class K>
  iterator find(K&& k) {
    return std::find_if( begin(), end(), key_match(k) );
  }
  template<class K>
  const_iterator find(K&& k) const {
    return const_cast<flat_map*>(this)->find(k);
  }
  // iterator-less query functions:
  template<class K>
  Value* get(K&& k) {
    auto it = find(std::forward<K>(k));
    if (it==end()) return nullptr;
    return std::addressof(it->v);
  }
  template<class K>
  Value const* get(K&& k) const {
    return const_cast<flat_map*>(this)->get(std::forward<K>(k));
  }
  // key-based erase: (SFINAE should be is_comparible, but that doesn't exist)
  template<class K, class=std::enable_if_t<std::is_converible<K, Key>{}>>
  bool erase(K&& k) {
    auto it = std::remove(
      storage.begin(), storage.end(), key_match(std::forward<K>(k))
    );
    if (it == storage.end()) return false;
    storage.erase( it, storage.end() );
    return true;
  }
  // classic erase, for iterating:
  iterator erase(const_iterator it) {
    return storage.erase(it);
  }
  template<class K2, class V2,
    class=std::enable_if_t<
      std::is_convertible< K2, Key >{}&&
      std::is_convertible< V2, Value >{}
    >
  >
  void set( K2&& kin, V2&& vin ) {
    auto it = find(kin);
    if (it != end()){
      it->second = std::forward<V2>(vin);
      return;
    } else {
      storage.emplace_back( std::forward<K2>(kin), std::forward<V2>(vin) );
    }
  }
};

我将容器类型保留为模板参数，因此如果您愿意，可以使用类似 SBO 向量的结构。

理论上，我应该公开一个模板参数来替换键上的 equals。然而，我确实让关键搜索功能变得透明。

Answer 4

Evgeny Panasyuk 是正确的，我相信你想要的是一个 Open Address Hash Map.
这完全符合您的要求，只有 1 个平面缓冲区，没有分配节点，没有要遵循的指针，并且未排序。

否则你也有 flat_map/AssocVector但是它们是排序的，不像你的要求。

对于 OAHM，我在这里有一个类似 STL 的通用实现：
https://sourceforge.net/projects/cgenericopenaddresshashmap/

您可能还想看看 flat_map:
的基准页面 boost::flat_map and its performance compared to map and unordered_map
OAHM 在所有测试中的表现都非常接近 flat_map，迭代除外。

Answer 5

请看我最近更新到GitHub的sfl库：https://github.com/slavenf/sfl-library

它是 C++11 header-only 库，提供在内存中连续存储元素的平面有序和无序容器。所有容器都满足 Container, AllocatorAwareContainer and ContiguousContainer 的要求。图书馆在 zlib 许可证下获得许可。

是否有一个扁平的未排序 map/set 实现？

Is there a flat unsorted map/set implementation?

c++

containers

boost

stl

c++11