使用按插入方式排序的参数创建哈希映射

Question

我想更改 std::map （它是哈希函数），以便在迭代时以插入的方式返回对。我尝试过使用无序地图，但没有成功。所以我想我必须创建一个哈希函数，该函数每次都会递增并返回更大的值。我怎样才能做到这一点？我不使用大数据，所以性能不是问题。

Answer 1

听起来你想要一个有序的映射，一个允许 O(1) 查找但记住插入顺序（迭代顺序）的哈希映射。幸运的是，C++ 中存在一个有效的实现：https : //github.com/Tessil/ordered-map

README 中的一个示例是：

#include <iostream>
#include <tsl/ordered_map.h>

int main() 
{
    tsl::ordered_map<char, int> map = {{'d', 1}, {'a', 2}, {'g', 3}};
    map.insert({'b', 4});
    map['h'] = 5;
    map['e'] = 6;

    map.erase('a');


    // {d, 1} {g, 3} {b, 4} {h, 5} {e, 6}
    for(const auto& key_value : map) {
        std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
    }

    return 0;
}

您也可以像 Python 的有序映射一样实现它，它使用链表来跟踪插入顺序。一个优点是更有效的删除（Tessil 的有序映射有O(n)删除，而链表/映射将是平均的O(1)）。假设映射通常存储 type 的键/值类型Key, T，您将存储T在链表中，并将迭代器存储为内部 unordered_map 的值类型。然后，您将包装类和任何迭代器，以确保它从外部像普通哈希图一样起作用。

基本大纲如下所示（如果O(n)删除不可接受，其余部分由您实施）。使用列表是因为它们不会在删除元素时使迭代器失效，并且映射用于通过键查找正确的列表迭代器以进行删除。满足所有大 O 问题，尽管有一些开销。

#include <list>
#include <unordered_map>

template <
    typename Key,
    typename T,
    typename Hash = std::hash<Key>,
    typename KeyEqual = std::equal_to<Key>,
    typename Allocator = allocator<std::pair<Key, T>>
>
class ordered_map
{
public:
    using key_type = Key;
    using mapped_type = T;
    // ....

private:
    using list_type = list<T, typename std::allocator_traits<Allocator>::template rebind_alloc<T>>;
    using list_iterator = typename list_type::iterator;
    using map_type = std::unordered_map<
        Key, list_iterator, Hasah, KeyEqual, 
        typename std::allocator_traits<Allocator>::template rebind_alloc<std::pair<Key, list_iterator>>
    >;

    list_type list_;
    map_type map_;
};