65.9K
CodeProject 正在变化。 阅读更多。
Home

Stree - std::map 和 std::set 的快速替代品

cppnow
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.54/5 (22投票s)

2008年7月15日

LGPL3

7分钟阅读

viewsIcon

125520

downloadIcon

1221

一个（几乎）与 std::map 兼容的数据结构实现，提供了更好的性能和内存利用率。

引言

std::map 是标准模板库 (STL) 中最有用的容器之一。它允许实现排序字典。它通常使用红黑树数据结构实现，这保证了良好的 (O(log n)) 性能，是大多数任务的首选容器（除非您使用的是新的标准库实现 - 例如，Visual Studio 2008 附带 Feature Pack 1 或 GCC 4.2 - 在这种情况下，您可以使用新的 TR1 unordered_map 和 unordered_set）。

尽管 std::map 和 std::set 对于大多数任务来说已经足够好，但红黑树的实现并非速度超群。提供的代码实现了 std::map 和 std::set 的“即插即用”替代品（我们没有实现 multi- 变体），基准测试显示其速度快两倍。

请注意，该实现对 map 的 Key 类型施加了限制：需要一个特殊的“无穷大”值。

需要 Boost 和一个现代 C++ 编译器。

Using the Code

smap 和 sset 分别是 std::map 和 std::set 的即插即用替代品。以下是使用 smap 的示例

#include <iostream>
#include "sti/smap"
using namespace sti;
int main()
{
    // Create a map
    typedef smap<char, int> Map;
    Map my_map;
  
    // Insert some values  
    my_map.insert(std::make_pair('a', 1));
    my_map.insert(std::make_pair('A', 1));
    my_map.insert(std::make_pair('b', 2));
    my_map.insert(std::make_pair('B', 2));
    
    // find an item
    Map::const_iterator it = my_map.find('a');
    std::cout << "my_map[" << it->first << "]= " << it->second << std::endl;

    // Use operator []:
    my_map['a'] = 10;

    // Iterate over map:
    for (it = my_map.begin(); it != my_map.end(); ++it)
    {
       std::cout << "my_map[" << it->first << "]= " 
                 << it->second << std::endl; 
    }

    // Erase an item
    my_map.erase('a');

    // or we can use an iterator:
    it = my_map.find('b');
    my_map.erase(it);

    // Find out how many items are left in map:
    std::cout << "Items: " << my_map.size() << std::endl;

    return 0;
}

类似地，对于 sset

#include <iostream>
#include "sti/sset.h"
using namespace sti;

int main()
{
   typedef sset<int> Set;
   Set my_set;
   my_set.insert(1);
   my_set.insert(10);
   if (my_set.find(1) != my_set.end())
      std::cout << "Found 1 in set" << std::endl;
   else
      std::cout << "Couldn't find 1 in set" << std::endl;
   return 0;
}

sset 和 smap 分别定义在 sset.h 和 smap.h 中，定义如下

namespace sti
{
   // from smap.h
   template<
         class Key,
         class Type,
         class Traits = std::less<key>,
         class Allocator = std::allocator<std::pair <const Key, Type> >,
         int BN = 48,
         class key_policy   = default_stree_key_policy<Key>,
         class value_policy = default_smap_value_policy<Key, Type>,
         class gist_traits  = default_gist_traits<Key>
   > class smap;

   // from sset.h:
   template<
         class Key,
         class Traits = std::less<Key>,
         class Allocator = std::allocator<Key>,
         int BN = 48,
         </key>class key_policy   = default_stree_key_policy<Key>,
         class gist_traits  = default_gist_traits<Key>
<key />   > class sset;
}</key>

模板参数

选择 BN

除了最后一个模板参数 (BN) 之外，此定义与 std::map 和 std::set 相同。BN 类似于 B-Tree 的“阶数” - 它定义了单个节点中应保留多少个元素。更改此值可能会对性能产生重大影响。BN 值为 32 到 128 似乎表现良好（有关更多详细信息，请参见下文的实现）。

key_policy

key_policy 控制键如何在内部节点中存储（参见下面的实现）。key_policy 可以是 std::tr1::true_type 或 std::tr1::false_type。如果 key_policy 是 true_type，则键“按原样”存储，并在需要时（拆分/合并时）使用 memmove() 进行复制。否则，节点本身只存储指向键的指针，以及一个从键计算出的“摘要”(size_t) 值（使用 gist_traits）。

默认情况下，对于小型、简单的类型（POD 类型 - int, char 等），key_policy 为 true_type，而对于其他类型，则为 false_type。

我们不希望将更复杂的类型作为节点的一部分存储，因为移动它们（用于拆分/合并操作）将是昂贵的（并且是错误的，因为我们随后必须调用复制构造函数）。

因此，建议使用默认的 key_policy，无论如何，不要对需要非平凡复制构造函数的类型使用 true_type。

gist_traits

gist_traits 参数仅在 key_policy 为 true_type 时有效。

当 key_policy 为 true_type 时，我们只保留指向内部节点中键的指针。比较这些指针会影响性能（见下文 - 内存作为瓶颈）。在节点本身中保留一个“廉价”值，该值可用于快速比较值（比较两个整数值几乎是“免费”的）。

以下代码解释了这个想法

struct KeyWrapper
{
   KeyType* _key;
   size_t   _gist;
};

bool less(KeyWrapper l, KeyWrapper r)
{
   if (l._gist < r._gist)
     return true;
   else if (l._gist > r._gist)
     return false;
   else
       retrurn less(l->_key, r->_key);
}

如果 gist1 是 key1 的摘要，gist2 是 key2 的摘要，那么必须满足以下条件

  • 如果 key1 < key2，则 gist1 <= gist 2
  • 如果 key1 == key2，则 gist1 == gist2
  • 如果 key1 > key2，则 gist1 >= gist2

提供了一个默认的 gist_traits，它只为所有键返回 0。

对于 string，提供了一个特化，实现了以下功能（为简单起见，假设 sizeof(char)==1）

struct string_gist
{
   const static size_t chars_per_size_t = sizeof(size_t);
   size_t operator()(const std::string& s) const
   {
      sz = std::min(sz, chars_per_size_t);
      size_t r = 0;
      for (size_t i = 0; i < sz; ++i)
         r = (r<<8) + (size_t)c[i];
      return r;
   }
};

value_policy

value_policy 参数控制项在 map 中的存储方式。如果 value_policy 为 false_type，则插入 map 的每个项都单独分配，并且保证项的引用有效（当然，除非项被 erase()）。另一方面，如果 value_policy 为 true_type，则项作为 stree 节点的一部分存储 - 因此在这些节点拆分或合并时可能会重新分配。

默认情况下，如果键和值都是简单的小类型，则 value_policy 为 true_type，否则为 false_type。

性能

源代码中提供了一个简单的基准测试。该基准测试创建一个大型容器，然后使用随机值重复调用 erase()、find() 和 insert()。对 std::map<int, int> 和 smap<int, int> 执行相同的基准测试。

以下是使用 Visual Studio 2008 和标准“Release”优化（Core 2 6400、2GB 内存运行于 WinXP）编译的结果

STL map time: 1548678032
smap time:     740111472

因此，与 std::map 相比，smap 显示了 x2.09 的性能提升。

注意事项

为了简化实现，如果容器被修改，所有迭代器都将失效，因此以下代码（在 std::map 下应该可以工作）将抛出异常

smap<int, int> m;
smap<int, int>::iteraor it;

for (it = m.begin(); it != m.end(); ++it)
{
  if (it->second == 1)
    erase(++it); // <-- delete element at iterator
                 //     and advance iterator
}

作为一种解决方法，erase(iterator) 返回指向被删除元素之后下一个元素的 iterator，因此我们可以这样写（这也将适用于 Visual Studio 的 STL 实现，它以相同的方式扩展了 erase()）

smap<int, int> m;
smap<int, int>::iteraor it;

for (it = m.begin(); it != m.end(); ++it)
{
  if (it->second == 1)
    it = erase(it); // <-- delete element at iterator 
                    //  and advance iterator}

此外，Key 类型有一个限制：需要一个特殊的 infinite() 值，该值必须大于任何键.

实现

内存作为瓶颈

stree 的基本思想是，在现代架构中，内存已成为主要的性能瓶颈：访问随机主内存位置需要几十（在某些情况下是几百）个时钟周期。新的内存架构主要改进了传输速率：一旦到达内存位置，读取 1 个或 100 个字节所需的时间大约相同。缓存通过存储常用内存的低延迟副本，减少了内存访问延迟 - 访问随机（或分散）的内存位置会导致缓存未命中。

基于磁盘的数据结构面临着同样的问题 - 例如，缓存；访问第一个位与访问下一个位的成本都很高，等等。解决方案 - 使用“更扁平”的树（B-Trees）并将多个项保存在一起，现在适用于基于内存的数据结构。

关于跳跃表

跳跃表基本上是一个带有“快捷方式”的排序链表，可以实现快速（平均 O(n)）find 操作。

要构造一个跳跃表，请从一个排序链表开始（称之为 0 级列表）。现在，（随机）选择一半的节点，并用另一个链表（1 级列表）将它们连接起来。然后，从 1 级列表中随机选择一半节点，创建一个 2 级列表，依此类推，直到某个级别没有选择任何元素。

要搜索链表，请从最高级别的列表开始，如果前进到下一个节点会将我们越过所需元素，则“降至”下一级别。平均而言，每个级别最多需要检查 3 个元素。

1-2-3 自顶向下跳跃表

Munro、Papadakis 和 Sedgewick 提出了一种确定性的跳跃表替代版本。此外，他们描述了一种更简单的跳跃表实现 - 1-2-3 自顶向下跳跃表。

以下是一个 1-2-3 跳跃表的示例

这种结构类似于二叉树，其中节点叶子以链表形式连接。搜索从左上角的头部节点 (48) 开始，只要搜索的键大于节点的键，就向右移动，在这种情况下，我们下降到下一级别并继续搜索。类似于 B+ 树，项仅存储在叶子中。

与跳跃表不同，这是一个确定性数据结构：两个节点之间的“间隙”始终在 2 到 3 之间。例如，头部节点 (48) 和其右侧节点之间有 3 个节点的间隙。该间隙包括中间级别的节点 13、30 和 48。类似地，中间级别的节点 13 和 30 之间有 2 个节点的间隙，包括底部的节点 9 和 13。每当间隙超出允许范围（2-3）时，通过添加（或删除）节点来修复结构。

stree

1-2-3 跳跃表只允许最多 3 个的间隙。然而，没有什么可以阻止我们允许更大的间隙。这将稍微减少内存需求（更少的内部节点），但会增加搜索时间（每个级别需要检查更多项）。

另一个可能的修改是将单个间隙中的所有节点存储在一个数组中，我们称之为 stree。以下是同一跳跃表的 stree 版本

通过允许更大的间隙（最多 BN）并将间隙中的项链接列表替换为数组，我们得到了一种与 B+ 树非常相似的数据结构。

历史

  • 2008 年 7 月 15 日：发布。
  • 2008 年 7 月 17 日：添加了更多实现细节。memmove() 仅用于简单类型。
  • 2008 年 8 月 6 日：取消了对 infinite() 的需求。支持所有键和数据类型。模板参数控制是否允许“移动”value_type。
© . All rights reserved.