分段映射：介于扁平映射和 std::map 之间的折衷

• SegmentedMapTests.zip

1. 引言

映射是一种键值对的集合，具有以下功能：

• 插入一对键值
• 按键搜索一对（每个键都是唯一的，不能有两个具有相同键的对）
• 按键的顺序遍历所有键值对

在标准 C++ 中，有一个名为 `std::map` 的容器，它提供了所有这些操作。但对于大量元素，它的遍历速度不快。一直以来，人们一直在讨论和提议使用扁平映射，它是一个键值对的向量，按键排序。通过二分查找来检索元素。扁平映射在遍历元素方面比 `std::map` 快，但在插入方面很慢，因为为了插入一个元素，必须移动向量中的其他一些元素。

分段映射在遍历和搜索方面几乎与扁平映射一样快，而在插入方面则接近 `std::map`。

2. 分段映射：实现的简要描述

2.1. 设计概述

分段映射是一个段的向量，其中一个段是键值对的向量。最初，只有一个空段，没有键值对——这是一个空的分段映射。随着元素的插入，段会增长。每个段都有大小限制。当任何段达到其限制时，它会被一分为二。分段映射就像一个多细胞生物，当它的细胞分裂时：它长得越大，创建的段就越多。

问题是：段大小限制应该是什么？在我的测试中，我发现最佳值在 100 到 300 之间。在实现中，我提供了 `MaxSliceSize` 参数，它定义了段的大小限制。

2.2. SegmentedMap 容器

容器的开头如下：

template<class K, class V, std::size_t MaxSliceSize = 256, 
                  class Compare = CompareAscending<K>>
class SegmentedMap
{
public:
    using difference_type = int;   
    Compare comp;

    using value_type = std::pair<K, V>;

private:

    struct Segment
    {
        Segment() {}
        Segment(std::size_t n, const K& first, const K& last) :m_elem(n),
                               m_first(first),m_last(last) {}
        DeVector<value_type> m_elem;
        K m_first;
        K m_last;
    };
...

实现段的 `Segment` 结构有两个关键字段 `m_first` 和 `m_last`，它们允许在不分析 `m_elem` 数组的情况下找到键的范围。

当创建一个新段时，会复制所需的键。在此实现中，我没有使用指向现有键的指针。当我将 `m_first` 和 `m_last` 视为指针时，没有注意到任何显著差异。此外，使用副本的代码稍微简单一些。

`MaxSliceSize` 参数定义了段的大小限制。

我在实现中使用了 `DeVector` [1]，它类似于 `std::vector`，但提供了快速的 `push_front` 和 `push_back`；并且，平均而言，插入元素的速度比 `std::vector` 快一倍。

2.3. 插入算法

首先，必须使用给定的键找到一个段。这是通过在 `m_datax` 数组上使用二分查找来完成的。

一旦找到正确的段，这段代码就会执行插入（`index1` 是段的索引，`index2` 是 `elem`（键值对）将要插入的索引）。

     template<class U>
    value_type& insert(std::size_t index1, std::size_t index2, U&& elem)
    {
        DeVector<value_type>& slice = 
                 m_datax[index1].m_elem;//get the slice from segment[index1]
        auto p = slice.insert(slice.begin() + index2, 
                 std::forward<U>(elem)); // insert the element into position index2
        if (slice.size() >= MaxSliceSize)
        {
            std::size_t halfSlice = MaxSliceSize / 2;

            Segment segment(halfSlice,slice[0].first,
            slice[halfSlice-1].first);//create a new segment with the given size 
            std::move(slice.begin(), slice.begin() + halfSlice, segment.m_elem.begin());
            Segment segment2(slice.size() - halfSlice, slice[halfSlice].first, 
            slice[slice.size() - 1].first);        // create a second segment
            std::move(slice.begin() + halfSlice,slice.end(),
            segment2.m_elem.begin());              // move the rest of the slice 
                                                   // into the second segment
            std::swap(m_datax[index1], segment2);  // swap segment that contains 
                                                   // slice with the second segment
            m_datax.insert(m_datax.begin() + index1, std::move(segment));// insert 
                           // the first segment into the map array before index1

            if (index2 >= halfSlice) // if the new element is in the second segment
            {
                return m_datax[index1 + 1].m_elem[index2 - halfSlice];
            }
            else //if the new element is in the first segment
            {
                return m_datax[index1].m_elem[index2];
            }
        }
        // if a segment is not split, simply update the keys
        m_datax[index1].m_first = m_datax[index1].m_elem[0].first;
        m_datax[index1].m_last = 
                m_datax[index1].m_elem[m_datax[index1].m_elem.size() - 1].first;
        return *p;
    }

这被定义为模板，以允许复制或移动一对，这由 `elem` 参数上的通用引用 [2]（转发引用）提供。

3. 基准测试

3.1. 概述

我使用 Microsoft VC++ 2020 和 GCC 11.2 C++ 编译器，使用各种键测试了 `SegmentedMap` 的行为。在这里，我展示了两种类型的映射键值对：

1. “`int` 键” - “`double` 值”；
2. “`string` 键” - “`string` 值”（字符串长度在 21 到 27 个字符之间）。

3.2. 使用的系统

代码在配备 Intel i7-4790、3.6GHz 处理器、16GB RAM 的 PC 上执行。

当使用 Visual C++ 2022（64 位代码）编译时，使用了以下选项：

在 GCC 中，命令行如下：

g++ -O3 -std=c++17  -m64 SegmentedMapTests.cpp -o SegmentedMapTests.exe

3.3. 插入基准测试

3.3.1. “int-double”对的插入

结果如图 1 所示。

这清楚地表明扁平映射是最慢的。分段映射的速度是 `std::map` 的两倍。分段映射绝对是赢家。构建一个包含 5,000,000 个元素的 `flat map` 大约需要 1.5 小时，而其他映射则在 2.5 到 5 秒之间。

3.3.2. “string-string”对的插入

这些测试中使用的 `string` 长度在 21 到 27 个字符之间。结果如图 2 所示。

分段映射比 `std::map` 稍慢。

3.4. 元素遍历基准测试

在顺序访问方面，没有什么比扁平映射更快了。

3.4.1. “int-double”对的遍历

结果如图 3 所示。

虽然扁平映射是最快的，但分段映射也紧随其后；`std::map` 相当慢。但元素的遍历仍然是一项相当快的操作：我们谈论的是纳秒。即使使用 `std::map` 对象，遍历所有 5000000 个元素也只需要不到一秒钟。

3.5. “string-string”对的遍历

结果如图 4 所示。

出于某种原因，分段映射在 GCC C++ 中的结果比在 VC++ 中要好得多；`std::map` 的速度很慢。

3.5. 随机访问基准测试

关于随机访问，所有映射的行为都很相似，扁平映射通常是最快的。

3.5.1. “int-double”对的随机访问

图 5 显示了结果。

在 VC++ 中，分段映射比扁平映射慢；在 GCC C++ 中，情况并非如此。但总的来说，分段映射比 `std::map` 快。

3.5.2. “string-string”对的随机访问

结果如图 6 所示。

分段映射的速度介于扁平映射和 `std::map` 之间。

4. 结论

基准测试表明，分段映射的表现非常出色。它在遍历元素（顺序访问）方面比 `std::map` 快，在插入方面比扁平映射快。

哪个可以推荐？这取决于数据的大小。如果您处理 1000 个元素并且不经常遍历所有元素，请使用 `std::map`。如果您使用的元素不超过 1000 个，并且顺序访问速度很重要，请使用扁平映射。但是，如果元素数量接近一百万或更多，我建议使用分段映射。使用扁平映射是不切实际的：构建它将花费一个多小时。但是，如果顺序访问不是那么重要，您仍然可能对 `std::map` 感到满意。

参考文献

• [1] 使用 Devector 比 std::deque 更好 - CodeProject
• [2] C++11 中的通用引用 -- Scott Meyers : Standard C++ (isocpp.org)

历史

• 2022 年 9 月 18 日：初始版本