在编写一些针对 C++17 的代码时，我遇到了一个绊脚石，用于确定合并两个兼容的 std::unordered_maps 的操作的异常安全性。根据当前的工作草案第 26.2.7 节，表 91 部分内容涉及以下条件a.merge( a2 )：
要求：
a.get_allocator() == a2.get_allocator()。尝试使用 的散列函数和键相等谓词提取每个元素
a2并将其插入。在具有唯一键的容器中，如果某个元素的键与来自 的元素的键等效，则不会从 中提取该元素。aaaa2a2后置条件：指向被转移元素的指针和引用
a2指代那些相同的元素，但作为a. 引用被转移元素的迭代器和所有引用的迭代器a都将失效，但剩余元素的迭代器a2将保持有效。抛出：除非散列函数或键相等谓词抛出，否则什么都没有。
值得注意的是，这些条件强烈地让人想起那些在 §26.2.6 表 90 中给出的普通关联容器 (std::map) 的要求a.merge( a2 )：
要求：
a.get_allocator() == a2.get_allocator()。尝试使用 的比较对象提取其中的每个元素
a2并将其插入。在具有唯一键的容器中，如果某个元素的键与来自 的元素的键等效，则不会从 中提取该元素。aaaa2a2后置条件：指向被转移元素的指针和引用
a2指代那些相同的元素，但作为a. 引用被转移元素的迭代器将继续引用它们的元素，但它们现在表现为迭代器 intoa，而不是 intoa2。抛出：除非比较对象抛出，否则什么都没有。
我需要合并两个具有相同数量元素的 std::unordered_maps，我可以确保这在两个容器中都是唯一的，这意味着包含合并结果的地图的元素数量将是以前的两倍，并且容器合并- from 将是空的。多亏了 C++17，这应该是完全安全的，对吧？
就性能而言，这是一个巨大的胜利……除了，我有这个挥之不去的疑问。有趣的是，后置条件语句没有说明合并映射中的前一个最大负载因子是否会得到尊重，虽然这似乎是一个安全的隐含假设，但它似乎与关于 unordered_map 异常安全性的语句发生了天真的冲突。如果您使用哈希表设计，其中存储桶是连续分配的缓冲区，那么保持负载因子似乎意味着重新散列，这似乎意味着重新分配存储桶缓冲区。
这似乎已经是一种极端的凝视练习，并且有充分的理由不理会它：可以想象，可以将更复杂的哈希表制作为完全基于节点的结构，类似于通常支撑 std 的红黑树::map，在这种情况下，规范似乎是合理的，因为重新散列并不意味着分配。
也许对我有利的是，我屈服于怀疑并深入研究了 gcc-7.1 的合并实现。这非常复杂，但总结一下我的发现，我发现存储桶确实是连续分配的缓冲区，并且重新散列确实意味着重新分配。也许，我想，我错过了一些更深层次的魔法（我盯着源代码看了将近一整天，仍然觉得我对它的理解很差）它只是在合并期间禁用了重新散列，这意味着所有指定的条件会得到支持，但在适当大的合并后你可能会得到一个令人讨厌的性能回归，因为你的地图可能会超载。
我进行了反映我的用例的实际评估（如果可能的话，我会提出，对不起），而不是仅仅质疑我对 libstdc++ 的解释：
#include <memory> // for std::shared_ptr<>
#include <new> // for std::bad_alloc
#include <utility> // for std::move(), std::pair<>
#include <type_traits> // for std::true_type
#include <unordered_map> // for std::unordered_map<>
#include <functional> // for std::hash<>, std::equal_to<>
#include <string> // for std::string
#include <iostream> // for std::cout
#include <cstddef> // for std::size_t
template<typename T>
class PrimedFailureAlloc
{
public:
using value_type = T;
using propagate_on_container_copy_assignment = std::true_type;
using propagate_on_container_move_assignment = std::true_type;
using propagate_on_container_swap = std::true_type;
PrimedFailureAlloc() = default;
template<typename U>
PrimedFailureAlloc( const PrimedFailureAlloc<U>& source ) noexcept
: m_triggered{ source.m_triggered }
{ }
template<typename U>
PrimedFailureAlloc( PrimedFailureAlloc<U>&& source ) noexcept
: m_triggered{ std::move( source.m_triggered ) }
{ }
T* allocate( std::size_t n )
{
if ( *m_triggered ) throw std::bad_alloc{};
return static_cast<T*>( ::operator new( sizeof( T ) * n ) );
}
void deallocate( T* ptr, std::size_t n ) noexcept
{
::operator delete( ptr );
}
bool operator==( const PrimedFailureAlloc& rhs ) noexcept
{
return m_triggered == rhs.m_triggered;
}
void trigger() noexcept { *m_triggered = true; }
private:
template<typename U>
friend class PrimedFailureAlloc;
std::shared_ptr<bool> m_triggered{ new bool{ false } };
};
template<typename T>
bool operator!=( const PrimedFailureAlloc<T>& lhs,
const PrimedFailureAlloc<T>& rhs ) noexcept
{
return !(lhs == rhs);
}
template< typename Key
, typename T
, typename Hash = std::hash<Key>
, typename KeyEqual = std::equal_to<Key>
>
using FailingMap = std::unordered_map<
Key,
T,
Hash,
KeyEqual,
PrimedFailureAlloc<std::pair<const Key, T>>
>;
template<typename Key, typename T>
void printMap( const FailingMap<Key, T>& map )
{
std::cout << "{\n";
for ( const auto& [str, index] : map )
std::cout << " { " << str << ", " << index << " }\n";
std::cout << "}\n";
}
int main()
{
PrimedFailureAlloc<std::pair<const std::string, int>> a;
FailingMap<std::string, int> m1{ a };
FailingMap<std::string, int> m2{ a };
m1.insert( { { "Purple", 0 }, { "Green", 3 }, { "Indigo", 16 } } );
m2.insert( { { "Blue", 12 }, { "Red", 2 }, { "Violet", 5 } } );
// m1.reserve( m1.size() + m2.size() );
a.trigger();
m1.merge( m2 );
std::cout << "map :=\n";
printMap( m1 );
return 0;
}
果然，在GCC-7.1下编译这段代码后，我得到：
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
[1] 10944 abort ./a.out
然而，取消注释第 95 行 ( m1.reserve( m1.size() + m2.size() );) 会产生预期的输出：
map :=
{
{ Red, 2 }
{ Violet, 5 }
{ Purple, 0 }
{ Green, 3 }
{ Blue, 12 }
{ Indigo, 16 }
}
了解 C++17 仍然是一个尚未最终确定的标准草案，并且 gcc 的实现是实验性的，我想我的问题是：
- 我是否严重误解了标准中规定的合并操作的安全性？是否有使用
std::unordered_map::merge()我错过的最佳实践？我是否应该暗中负责确保桶的分配？std::unordered_map::reserve()当 clang、MSVC 和 Intel 最终支持 C++17 时，使用实际上是可移植的吗？我的意思是，当无法进行无异常合并时，我的程序中止确实遵循列出的后置条件……</li> - 这实际上是标准中的缺陷吗？如果文本被复制粘贴，无序关联容器和普通关联容器之间措辞的相似性可能会导致意外的保证。
- 这只是一个 gcc 错误吗？
值得注意的是，在撰写本文之前，我确实检查了 gcc 的错误跟踪器，似乎没有发现与我的描述相匹配的开放错误，此外，我检查了 C++ 标准缺陷报告，同样似乎是空的（诚然，做了一个该网站的文本搜索正在加重，我可能不够彻底）。后者并不令人惊讶，因为标准缺陷及其解决方法或后果通常会在 gcc 的源代码中注明，而我在检查期间没有发现这样的符号。我尝试在最近的 clang 签出（超过一周）中编译我的示例代码，但是编译器出现了段错误，所以我没有进一步检查，也没有咨询 libc++。