精通
英语
和
开源
，
擅长
开发
与
培训
，
胸怀四海
第一信赖
精通
英语
和
开源
，
擅长
开发
与
培训
，
胸怀四海
第一信赖
锐英源精品原创，禁止转载和任何形式的非法内容使用，违者必究
数据的高性能处理是IT行业一直追求的目标，不管是硬件和软件的发展，都是围绕快速来进行。对于普通的程序员开发常用的软件，也要考虑性能这个问题，普通程序员最常用的思维就是map映射比数组线性查找速度快，能用map的场合就用map，但是map的内部机制可能就懂的不多。
这里介绍一个国外文章，原文链接在https://www.codeproject.com/Articles/27799/Stree-A-fast-std-map-and-std-set-replacement，本文是翻译。锐英源软件以前也翻译过C语言下的映射实现uthash，对于开源项目的翻译，锐英源非常擅长，有兴趣的朋友请关注收藏下，遇到开源细节问题，可以找锐英源。
下面是翻译内容，网友有兴趣多关注带注解的部分：
std::map是标准模板库 (STL) 中最有用的容器之一。它允许实现排序字典。它通常使用保证良好 (O(log n)) 性能的红黑树数据结构实现，并且是大多数任务的首选容器（除非您使用新的标准库实现 - 例如，带有 Feature Pack 1 或 GCC 4.2 的 Visual Studio 2008 - 在这种情况下，您可以使用新的 TR1unordered_map和unordered_set)。
尽管std::map和std::set对于大多数任务来说已经足够好，但红黑树的实现并不是速度最优。本文提供的代码实现了std::map和std::set（我们还没有实现多变体）的“插入式”替换，基准测试显示它快两倍。
请注意，map类型实现施加了Key限制：需要一个特殊的“无穷大”值。
需要 Boost 和现代 C++ 编译器。
smap和分别是和sset的替代品。下面是一个使用示例：std::mapstd::setsmap
C++
#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：
C++
#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中定义，定义如下：
C++
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) 模板参数外，此定义与std::mapand相同std::set。BN类似于 B-Tree 的“顺序”——它定义了单个节点中应该保留多少元素。使用此值会对性能产生重大影响。BN32 到 128 的值似乎表现良好（有关详细信息，请参阅下面的实现）。
key_policy控制密钥如何存储在内部节点中（参见下面的实现）。key_policy可以是std::tr1::true_type或std::tr1::false_type。如果key_policy是true_type，则密钥“按原样”存储，并根据需要（在拆分/合并时）使用memmove(). 否则，只有指向键的指针存储在节点本身中，以及size_t从键（使用）计算的“gist”（）值gist_traits。
默认情况下，对于小型简单类型（POD 类型 - int、char等），key_policy是true_type，而对于其他类型，它是false_type。
我们不想将更复杂的类型存储为节点的一部分，因为移动它们（用于拆分/合并操作）会很昂贵（而且是错误的，因为我们必须调用复制构造函数）。
因此建议使用 default key_policy，并且在任何情况下，不要用于需要true_type非平凡复制构造函数的类型。
该gist_traits参数仅在key_policyis时有效true_type。
key_policy什么时候true_type，我们只保留指向内部节点中键的指针。比较这些指针会降低我们的性能（见下文 - 内存作为瓶颈）。在节点本身中保留一个“便宜”的值，可用于快速比较值（比较两个整数值实际上是“免费的”）。
这是解释这个想法的代码：
C++
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);
}
如果gist<sub>1</sub>是 key<sub>1</sub>的gist，并且gist2是 key<sub>2</sub>的gist，那么以下要求必须满足：
提供了一个默认值gist_traits，它只为所有键返回 0。
对于strings，提供了一个实现以下内容的特殊处理（sizeof(char)==1为简单起见）：
C++
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参数控制项目在map中的存储方式。如果value_policy是false_type，那么插入到映射中的每个项目都是单独分配的，并且对项目的引用保证是有效的（当然，除非项目是erase()过了）。另一方面，如果value_policy是true_type，则项目存储为树节点的一部分-因此可以在拆分或合并这些节点时重新分配。
默认情况下，如果键和值都是简单、小类型，否则value_policy为 是true_type，否则是false_type。
源代码提供了一个简单的基准测试。基准测试创建一个大容器，然后erase(), find(), 并insert()使用随机值重复调用。std::map<int, int>对 a和执行相同的基准测试smap<int, int>。
以下是使用标准“发布”优化（Core 2 6400，在 WinXP 上运行 2GB 内存）使用 Visual Studio 2008 编译时的结果：
C++
STL map time: 1548678032
smap time: 740111472
smap因此速度是std::map的2.9倍.
为了简化实现，如果容器被修改，所有迭代器都将失效，因此（应该）使用的以下代码std::map将引发异常：
C++
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到下一个元素，所以我们可以改写（这也适用erase()于以相同方式扩展的 Visual Studio 的 STL 实现）：
C++
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}
stree基本思想是，在现代架构中，内存已成为主要的性能瓶颈：访问一个随机的主内存位置需要数十个（在某些情况下，数百个）时钟周期。新的内存架构主要提高了传输率：一旦你到达一个内存位置，读取 1 或 100 个字节大约需要相同的时间。缓存通过存储经常使用的内存的低延迟副本来减少内存访问延迟 - 访问随机（或广泛分布的）内存位置将导致缓存未命中。
基于磁盘的数据结构面临同样的问题——例如缓存；访问第一位与访问下一位等的高成本。解决方案 - 使用“扁平”树 ( B-Trees ) 并将多个项目放在一起，现在适用于基于内存的数据结构。
跳过列表基本上是一个带有“快捷方式”的排序链表，它允许快速（平均为 O(n)）find操作。
要构建跳过列表，请从排序链表开始（我们称其为 0 级列表）。现在，（随机）选择一半节点并通过另一个链表（1 级列表）连接它们。现在，随机选择 1 级列表中的一半节点并创建一个 2 级列表，依此类推，直到没有为某个级别选择任何元素。
要搜索链表，首先沿着最高级别的列表前进，“下降”到下一个级别，如果前进到下一个节点将使我们越过所需的元素。平均而言，每个级别需要检查的元素不超过 3 个。
Munro、Papadakis 和 Sedgewick提出了另一种确定性的跳过列表版本。此外，他们描述了一个更简单的跳过列表实现——1-2-3 自上而下的跳过列表。
这种结构类似于二叉树，其节点叶子连接在一个链表中。搜索从左上角的头节点（48）开始，只要搜索到的键大于节点的键，就会向右移动，在这种情况下，我们会下降到下一个级别并继续搜索。与 B+ 树类似，项目仅存储在叶子中。
与跳过列表不同，这是一种确定性数据结构：两个节点之间的“间隙”始终在 2 和 3 之间。例如，头节点 (48) 与其右侧的节点之间存在 3 节点间隙. 该间隙包括中间层的节点 13、30 和 48。类似地，中间层的节点 13 和 30 之间存在 2 个节点间隙，其中包括底部的节点 9 和 13。每当间隙超出允许范围 (2-3) 时，通过添加（或删除）节点来固定结构。
1-2-3 跳过列表只允许大小最多为 3 的间隙。但是，没有什么可以阻止我们允许更大的间隙。这将在一定程度上减少内存需求（更少的内部节点），但会增加搜索时间（每个级别需要检查更多项目）。
另一种可能的修改是将单个间隙的所有节点存储在一个数组中，我们称之为stree. 这是stree同一跳过列表的版本：
通过允许更大的间隙（最多BN）并用数组替换间隙中项目的链接列表，我们得到了一个非常类似于B+ 树的数据结构。
注：跳过列表和间隙比较高端，想深入学可以关注下。