C++ 实现 .NET 风格的 Dictionary

• Visual Studio 示例 - 12.7 KB
• Linux 示例 - 120.9 KB - 由 VadimIV 提供

开始之前

我最初开始这项工作只是为了练习我的 C++ 技能，因为我有一段时间没有使用它了。然后，我将我的第一个版本与 STL 的 unordered_map 类进行了性能比较，结果令我印象深刻：这个解决方案速度更快，并且占用的内存更少（实际上，.NET 的 Dictionary 即使是托管代码也已经快很多了），所以我决定完成这项工作，并在 C++ 中实现一个功能齐全的 Dictionary。

我知道，我没有使用 C++ 的标准命名约定。我在这里实际上使用的是 .NET 的命名约定。此外，在工作中我使用 Visual Studio 2008，所以我不使用 C++11 的特性。即使我家里有 Visual Studio 2013 可以使用 C++11，我也暂时不打算很快将此代码更新为 C++11 兼容，因为我 Actually 知道很多地方仍然使用旧的 C++ 版本。如果您喜欢这段代码并想使其兼容 C++11，请随时进行。

引言

我经常看到人们断言 C++（原生代码）比 C#/.NET/托管代码快得多，但很多时候当我看到 C++ 应用程序的 .NET 移植版本时，它们比它们的 C++ 版本执行得更快。我将此归因于三个主要因素：

• 内存分配；
• .NET 中更好的关联类；
• 更好的字符串（这在文章末尾解释，并且与前一项有关）。

在许多性能比较中，人们说 C++ 并不比 C# 慢，之所以显得慢，是因为 C++ 正在释放使用的内存，而 .NET 在循环中累积内存，直到稍后才释放。好吧，如果用户看不到“稍后”这个过程，那么 C# 将会更快地给出结果，即使它需要更多时间来释放内存。然而，C++ 的问题通常不是释放内存所花费的时间，而是分配内存所花费的时间。构造函数和析构函数在很多情况下都非常快，以至于察觉不到。这个问题促使我写了 O(1) Object Pool in C++ 这篇文章，试图将性能优势还给 C++。

然后，第二个问题是：“关联数组”用作键的类。在 C++ 中它们被称为 maps，在 .NET 中被称为 dictionaries。.NET 是建立在哈希码（Java 也是如此，但这里不讨论）的理念之上的。所有原始类型、字符串以及预期用作键的最重要的结构都有良好的哈希码生成器，这些生成器应能产生分布均匀的结果并快速返回。不幸的是，C++ 没有内置此支持，长时间以来唯一的解决方案是非哈希的 maps，它们相当慢。现在 STL 有了 unordered_map 类，但一些默认的哈希生成器非常糟糕，并且内存消耗很大（至少在我检查过的 Visual Studio 实现中是这样）。

因此，为了尝试减轻这个问题，我提供了一个 .NET 风格 dictionary 的 C++ 实现。与其提供许多可能很慢的默认哈希生成器，我选择不为那些我不知道如何哈希的类型提供默认生成器。在我看来，被迫实现一个好的哈希生成器总比使用一个糟糕的哈希生成器而损失性能要好。

哈希和桶

Dictionary 和 unordered_map 的整个想法是使用哈希码作为“索引器”来关联值与键。生成的哈希码对于同一个键必须始终相同。预期哈希码分布均匀，因此，如果可能，两个不同的值不应生成相同的哈希码。但是，由于哈希码是单个数值，dictionary/map 必须准备好处理两个或多个生成相同哈希码的不同键。

当使用 32 位值时，哈希码可以有超过 40 亿个不同的值（在 64 位下，将 40 亿乘以 40 亿），所以哈希码不能直接用作数组中的位置来查找项。对哈希码进行一些数学运算，以选择一个“桶”来存储键/值对。这些桶然后可以存储许多对。

我不知道 STL 的 unordered_map 是否是这样实现的，或者它是 Visual C++ 特定的实现，但每个桶都是一个可以独立调整大小的 vector，然后还有一些其他规则来实际增加桶的数量。在 .NET 中，我们有一个桶数组，并且，也许是因为 .NET 不允许引用结构体（这可以通过其他方式解决），这些桶是指向结构体数组（实际数据）的索引。

我的实现类似于 .NET 的实现，但不是有两个数组，桶数组本身就是一个结构体数组。然后，如果同一个桶中有更多项，我从 O(1) Object Pool 分配新的结构体实例，并指向它，因为 C++ 允许我使用结构体指针。调整数组大小的规则与 .NET 相同。当项的数量大于桶的数量时，就会发生一次调整大小。这意味着，如果哈希码分布得非常均匀（如顺序哈希码），我们永远不会有两个项在同一个桶中。

作为 C++ 特定的细节，我不会直接分配一个结构体数组。这将调用默认构造函数，如果 TKey 或 TValue 是一个类（不是指针）并且有一个默认构造函数。相反，我只是分配内存块，并在添加项时使用 placement new 在那里初始化结构体。

使用该类

如果您曾经使用过 .NET 的 dictionaries，您可能会认为这个类非常容易使用。如果您不想更改哈希生成器，可以这样声明一个 dictionary：

Dictionary<int, int> dictionary;

< 和 > 中的参数分别是键的类型和值的类型。

然后，有以下方法：

插入和修改

• Add：将新的键/值对添加到 dictionary。如果已存在具有相同键的对，则会抛出异常；
• Set：将值与键关联，向 dictionary 添加新对或替换已存在对的值；
• TryAdd：尝试将新的键/值关联添加到 dictionary，如果添加成功则返回 true，如果已存在具有给定键的对则返回 false，而不进行任何更改。

读取

• GetCount：返回 dictionary 中存在的对的数量；
• ContainsKey：验证给定键是否存在于 dictionary 中，返回 true 或 false，但不返回关联的值；
• GetValue：返回与给定键关联的值，如果该键不存在于 dictionary 中则抛出异常；
• GetValueOrDefault：获取与给定键关联的值，或者返回默认值。此方法已重载。一个版本返回 TValue 类型的默认值，另一个版本允许您提供自定义的默认值；
• TryGetValue：实际上，ContainsKey、GetValue 和 GetValueOrDefault 方法都调用此方法。它返回与给定键关联的值的指针，如果不存在这样的关联则返回 NULL。因此，考虑到 ContainsKey 和 GetValue 都调用它，首选使用此方法，而不是先执行 ContainsKey 再执行 GetValue。

多操作

• GetOrCreateValue：此方法查找给定键的值。如果找到，则直接返回。如果未找到，则调用 valueCreator 来创建该值，然后将其添加到 dictionary 中再返回。此方法已重载，其中一个重载与 lambda 配合得非常好，而另一个接收函数指针和一个附加的上下文指针，该指针在调用函数指针时传递给它。

  由于我认为此方法最难使用，我将为每个重载提供一个示例。

  使用 lambda

  string foundOrCreatedString = dictionary.GetOrCreateValue(57, [](int key){return to_string(key);});
      

  在这种情况下，GetOrCreateValue 将查找与键 57 绑定的字符串。如果找到，则返回（如果它是手动添加的，可能不是“57”）。如果未找到，则将生成一个（使用 to_string(key)），将其添加到 dictionary 中，最后返回。

  使用函数指针

  // A function must exist so we can get a pointer to it
  string StringFromIntCreator(const int &value, void *ignoredContext)
  {
    return to_string(value);
  }
  
  // Then, we need to call the GetOrCreateValue method giving the function pointer and
  // giving a context. In this case I don't need a context, so I am giving NULL. Yet, if
  // if you want to invoke an instance method, you will need to give that instance as
  // the context.
  string foundOrCreatedString = dictionary.GetOrCreateValue(57, &StringFromIntCreator, (void *)NULL);
      

移除和清空

• Clear：从 dictionary 中移除所有项。此方法不会减小 dictionary 的容量。
• Remove：尝试从 dictionary 中移除一对。搜索仅通过键进行。如果找到并移除了项，则返回 true，如果未找到项，则返回 false。

内存管理

dictionary 由于其索引机制，可以快速插入，并且在许多情况下可以直接将新项放入数组中。但是，它以一个小的数组开始，并且可能需要进行许多“重调大小”，这会消耗时间。因此，如果您知道要向 dictionary 中放入多少项，可以在进行任何工作之前设置其容量（甚至可以在构造函数中设置）。

此外，如果您刚添加完项目，或者清空了 dictionary 并想让它释放其内部数组，您可能需要将其容量设置为更小的尺寸。

所以，这里是相关方法：

• GetCapacity：告知用于存储项的桶数组的大小。当此值大于 count 时，可以添加新项而不会导致 dictionary 调整大小；
• SetCapacity：尝试设置桶数组的大小。参数值可能会更改为大于 31 且不能被 2 到 31 之间的值整除的更大的值。小于 31 的任何值都将更改为 31；
• TrimExcess：尝试将容量更改为与 count 相同。

枚举

以下三个方法可用于枚举添加到 dictionary 的所有项。您负责删除返回的枚举器。

枚举的结果是“按桶排序”的，并且适合相同桶的项可能会在调整大小时被重新排序，所以，除非您正在调试桶之类的东西，否则请认为枚举是无序的。

• CreateEnumerator：创建一个枚举器，该枚举器以 Pair<TKey, TValue> 的形式枚举 dictionary 中的所有项；
• CreateKeysEnumerator：创建一个枚举器，该枚举器枚举 dictionary 的所有键；
• CreateValuesEnumerator：创建一个枚举器，该枚举器枚举 dictionary 的所有值。

与 .NET 的区别

尽管此 dictionary 受 .NET 的启发，但它有许多不同之处：

• 相等比较器是一个传递给类的模板参数，而不是传递给构造函数的普通参数。实际上，我没有发现使用“接口”有任何性能损失，但我认为这使得与接口一起使用变得更加困难。在 .NET 中使用比较器作为模板参数可能不好，但在 C++ 中，它效果很好，并且与 STL 类更兼容（即使这不是我的目的）；
• 我添加了我认为有用的方法，例如 GetValueOrDefault、GetOrCreateValue（非常适合缓存，并且比进行搜索然后添加性能更好）、SetCapacity 和 TrimExcess。.NET dictionary 不提供这些方法，我只能说我认为这很遗憾，因为它们非常有用（并且对于内存方面，.NET 会自动释放内存，容量从未减少并且您无法手动执行此操作，这一点很糟糕）；
• 枚举器是最大的区别。.NET 使用可枚举对象，可以生成许多枚举器。好吧，我认为对于像 EnumerateItems 这样的方法创建 IEnumerable 对象（其唯一目的是创建枚举器）是没用的。该方法本身就可以创建枚举器，如果我们真的想要一个“可枚举”对象，我们可以通过使用 lambda 调用该方法来创建一个。实际上，这解决了一个问题，因为许多 .NET 集合是可枚举的，并且有其他方法可以生成不同的可枚举对象。在我看来，只生成枚举器会更好；
• 继续谈论枚举器，.NET 版本需要两次虚函数调用才能完成一次枚举器步骤。可以使用一个带有 `out` 参数的单个方法，但这并不是它的工作方式。好吧，在 C++ 中返回指针很常见，所以我决定返回指向当前项的指针或 `NULL`。这减少了所需的调用次数，并且在我看来，简化了枚举器的编写；
• size_t 类型用于哈希码、计数和容量。这实际上简化了哈希码的数学运算，因为在 .NET 中，对负值进行模运算会得到负结果（用作桶号），所以 .NET 版本总是会丢失第一个位。由于 size_t 是无符号的，因此不需要移除第一位。使用 size_t 也意味着在 32 位计算机上是 32 位，在 64 位计算机上是 64 位。除了更好的哈希外，这还允许创建使用超过 4 GB 内存的 dictionary（您可以认为这是一种坏习惯，但有些特定的缓存场景可能因此受益）。

与 STL 的 unordered_map 有何不同？

嗯，太多了。即使两者有相同的目的，它们的用法也大相径庭，我真心认为我的实现更容易使用。

我知道的是，对于分布非常均匀的哈希码，此实现速度非常快，并且在我所有的测试中，移除项和销毁 dictionary 本身的速度都更快。它存储项所需的内存也更少，但它在调整大小时需要更多内存，因为一个大的数组必须进行调整，而 STL 的 unordered_map 可能单独调整每个桶的大小。重要的是要注意，我的比较是针对 Visual C++ 自带的 STL 进行的。我不知道 Visual C++ 对 STL 类的优化程度如何，也不确定 Visual C++ 的 STL 库是否是真正的 STL 或 Microsoft 版本。

创建比较器/哈希生成器

要为自己的类型创建比较器/哈希生成器，您必须创建一个类，该类具有两个公共静态方法：

• GetHashCode：此函数应接收一个输入（类型为 dictionary 的 TKey，如果传递引用更快，则可以是引用），并为其生成一个 size_t 哈希码。对于直到 `size_t` 大小的整数类型，直接返回输入值是有效的，但对于更大的值，例如 32 位计算机上的 64 位值，最好将高 32 位与值的低 32 位组合起来；
• Equals：此函数应接收两个输入参数（同样是 dictionary 使用的 TKey），并返回它们是否相等。请注意，不一定是相同的“实例”，只需被视为相等即可。两个相同的字符串可以在内存中有不同的地址，但它们应该被视为相等（并且也应该生成相同的哈希码）。

如果将这样的类创建为 DefaultEqualityComparer 模板类的特化，那么它将作为默认比较器用于不选择不同键比较器的 dictionary。

为了创建默认的哈希生成器（仅存在于小型整数类型和 void*），我使用了这个 `#define`（您也可以使用它）：

#define IMPLEMENT_DEFAULT_EQUALITY_COMPARER_AS_DIRECT_COMPARISON_AND_CAST(T) \
template<> \
class DefaultEqualityComparer<T> \
{ \
public: \
  static size_t GetHashCode(T value) \
  { \
    return (size_t)value; \
  } \
  static bool Equals(T value1, T value2) \
  { \
    return value1 == value2; \
  } \
}

这将简单地返回输入值本身转换为 size_t 作为哈希码，并将使用 `==` 运算符进行比较。

如果我们有一个不同的类型，例如 `string`，我们就需要使用更复杂的逻辑。以下是 `std::string` 的哈希码生成器的示例：

template<>
class DefaultEqualityComparer<std::string>
{
public:
  static bool Equals(const std::string &value1, const std::string &value2)
  {
    return value1 == value2;
  }

  static size_t GetHashCode(const std::string &value)
  {
    size_t length = value.length();
    if (length < sizeof(size_t))
    {
      if (length == 0)
        return 0;

      const char *cString = value.c_str();
      size_t result = 0;
      for(size_t i=0; i<length; i++)
      {
        result <<= 8;
        result |= *cString;
        cString++;
      }

      return result;
    }

    const char *cString = value.c_str();
    size_t *asSizeTPointer = (size_t *)cString;
    size_t result = *asSizeTPointer;

    size_t lastCharactersToUseCount = length - sizeof(size_t);
    if (lastCharactersToUseCount > sizeof(size_t))
      lastCharactersToUseCount = sizeof(size_t);

    if (lastCharactersToUseCount > 0)
    {
      size_t otherResult;
      
      if (lastCharactersToUseCount == sizeof(size_t))
        otherResult = *((size_t *)(cString + length - sizeof(size_t)));
      else
      {
        otherResult = 0;
        cString += length;
        for(size_t i=0; i<lastCharactersToUseCount; i++)
        {
          cString --;
          otherResult <<= 8;
          otherResult |= *cString;
        }
      }

      result ^= otherResult;
      result ^= length;
    }

    return result;
  }
};

需要注意的是，它只考虑字符串的第一个和最后一个字节来计算哈希码。这使得它成为一个近乎恒定时间的哈希码生成器，但肯定不会生成最佳哈希码（因此，哈希码的生成可能非常快，但由于哈希效果差，dictionary 可能会变得相当慢）。如果您的字符串内容不同但以相同的字符开头和结尾，它的表现会非常糟糕。

实际上，字符串是另一个可能使 .NET、Java 和其他一些被认为“慢”的语言受益的点，因为字符串对象是不可变的（或具有非常好的复制逻辑），避免了每次将一个字符串变量赋值给另一个变量时进行内存复制。所有直接写在代码中的字符串都真正地作为字符串对象存储，避免了从 char* 到 string 的转换（这可能在 C++ 中按调用进行），并且可以存储预计算的哈希码。

考虑到 C++ 字符串没有预先计算的哈希码，一些算法需要读取整个字符串内容来生成它，这在字符串很大的时候会很慢。在这种情况下，具有大型字符串键的 dictionary/unordered_map 可能比普通 map 慢得多，因为普通 map 会在第一个差异处停止读取比较字符串的内容，而哈希生成器将被迫在给出结果之前读取整个字符串。

示例

示例应用程序是对 Dictionary 和 map（不是 unordered_map）之间的性能测试。我之所以使用 map，是因为我在 Visual Studio 2008 中编写了此解决方案，而它不附带 unordered_map，但您可以轻松地将所有对 map< 的引用替换为 unordered_map< 并与它进行结果比较。

该示例将添加数百万个项，按键搜索所有项，移除它们，并执行其他一些操作，测量所需时间。它不测量内存消耗，但我在我的计算机上可以告诉您，对于 2000 万个 int/int 对，Dictionary 消耗了 575 MB，而 map 消耗了 670 MB。注意：该示例没有任何异常处理，并且由于它创建了大量项，可能会崩溃。如果发生这种情况，请尝试将项的数量从 2000 万减少到 1000 万（或其他较小的值），或者，如果可能，尝试在 64 位而不是 32 位下编译它。

此外，即使在 Release 模式下编译，代码在 Visual Studio 中运行也较慢。Dictionary 代码只是稍微慢一些，但 map 在插入时执行速度慢了约 10 倍，移除项花费了 21 分钟（在 Visual Studio 外部运行时仅需 5 秒）。因此，为了获得正确的结果，请在 Release 模式下编译并在 Visual Studio 外部运行。如果您不这样做，那么 Dictionary 代码将受益更多。

这是在 Visual Studio 外部运行的结果：

We will first compare the speed difference with sequential values:
Testing Dictionary...
Adding 20000000 items: 1045 milliseconds.
Searching all the items by key: 172 milliseconds.
Removing all items by key: 156 milliseconds.
Re-adding all items: 374 milliseconds.
Time to destroy the entire collection: 78 milliseconds.
Full test finished in 1825 milliseconds.

Testing Map...
Adding 20000000 items: 6302 milliseconds.
Searching all the items by key: 2372 milliseconds.
Removing all items by key: 4836 milliseconds.
Re-adding all items: 6178 milliseconds.
Time to destroy the entire collection: 1170 milliseconds.
Full test finished in 20858 milliseconds.


Now we will compare the speed of random values:
Dictionary
Adding: 7878 milliseconds.
Searching for random values: Found: 77317, Not Found: 19922683, Time: 4446 milliseconds.
Deleting dictionary: 312 milliseconds.

Map
Adding: 30623 milliseconds.
Searching for random values: Found: 77317, Not Found: 19922683, Time: 32574 milliseconds.
Deleting map: 5335 milliseconds.

用户 Arild Fiskum 使用 Visual Studio 2012 进行了测试，将此 dictionary 与 unordered_map 进行了比较，并使用了字符串作为键。我惊讶于 unordered_map 实际上添加项的速度更快，但我的实现总体测试更快，而且在许多情况下，我们只添加一次项，然后多次读取它们，所以我认为我的实现已经足够好了。以下是他的结果：

Larger test set compiled with x64:
 
We will first compare the speed difference with sequential values:
Testing Dictionary...
Adding 20000000 items: 21090 milliseconds.
Searching all the items by key: 5846 milliseconds.
Removing all items by key: 6821 milliseconds.
Re-adding all items: 5742 milliseconds.
Time to destroy the entire collection: 2799 milliseconds.
Full test finished in 42305 milliseconds.
 
Testing Map...
Adding 20000000 items: 16752 milliseconds.
Searching all the items by key: 6070 milliseconds.
Removing all items by key: 7948 milliseconds.
Re-adding all items: 16845 milliseconds.
Time to destroy the entire collection: 4266 milliseconds.
Full test finished in 51886 milliseconds.

Bug？

如果您发现 Bug，请告诉我。我没有时间对代码进行广泛的测试。我单独测试了所有方法，但没有使用许多不同的组合，因此仍有可能我遗漏了什么。我真心希望没有 Bug，但如果您发现一个，请告诉我，我会尽力解决它。