std :: unordered_map :: merge()的安全性

Question

在编写一些针对C++ 17的代码时,我遇到了一个障碍,它决定了合并两个兼容的std :: unordered_maps的操作的异常安全性.根据目前的工作草案 §26.2.7,表91部分内容涉及以下条件a.merge( a2 ):

要求: a.get_allocator() == a2.get_allocator().

尝试提取每个元素a2并a使用哈希函数和密钥相等谓词将其插入a.在具有唯一键的容器中,如果键中的元素a与元素的键相等a2,则不会从中提取该元素a2.

后置条件:指针和对转移元素的a2引用引用那些相同的元素但作为成员a.引用传递元素的迭代器和引用的所有迭代器a都将失效,但剩余元素的迭代器a2将保持有效.

抛出:除非散列函数或键等式谓词抛出,否则无效.

值得注意的是,这些条件强烈地让人联想到普通关联容器(std :: map)的要求,如§26.2.6,表90所示a.merge( a2 ):

要求: a.get_allocator() == a2.get_allocator().

尝试提取每个元素a2并a使用比较对象将其插入a.在具有唯一键的容器中,如果键中的元素a与元素的键相等a2,则不会从中提取该元素a2.

后置条件:指针和对转移元素的a2引用引用那些相同的元素但作为成员a.引用传递元素的迭代器将继续引用它们的元素,但它们现在表现为迭代器a,而不是a2.

抛出:除非比较对象抛出,否则无效.

我需要合并两个std :: unordered_maps和相同数量的元素,我可以确保这两个元素在两个容器中都是唯一的,这意味着包含合并结果的地图将使之前拥有的元素数量增加一倍,并且容器合并 - 来自将是空的.感谢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的实现是实验性的,我想我的问题是:

1. 我是否严重误解了标准中规定的合并操作的安全性？是否有使用std::unordered_map::merge()我错过的最佳做法？我是否应该暗中负责确保分配桶？std::unordered_map::reserve()当clang,MSVC和Intel最终支持C++ 17时,实际上是否可以使用？我的意思是,我的程序在一个无异常合并是不可能的时候中止,在一些概念之后,坚持列出的后置条件......
2. 这实际上是标准中的缺陷吗？无序关联容器和普通关联容器之间的措辞的相似性可能允许无意识的保证在文本被复制粘贴时滑入.
3. 这只是一个gcc bug吗？

值得注意的是,在这次写作之前我确实检查了gcc的bug跟踪器,似乎没有发现与我的描述相符的开放错误,而且,我检查了C++标准缺陷报告,同样似乎已经空了(诚然,做了一个该网站的文本搜索正在加剧,我可能不太彻底).后者并不令人惊讶,因为标准缺陷及其变通方法或后果通常在gcc的源代码中注明,我在考试期间没有发现这样的符号.我尝试在最近的clang结账中编译我的示例代码(超过一周),但是编译器发生了分段,所以我没有进一步考试,也没有参考过libc ++.

Answer 1

为了了解标准中的措辞是否正确，您需要研究底层函数。
\n合并本身由两个操作组成。

\n\n

\n
• 设置指向添加元素的指针。由于已经分配了，这里不涉及分配
\n
• 如果达到桶中元素数量的界限，则调用 rehash()。
\n

\n\n

调用 rehash() 是您期望抛出异常的地方。Sol 让我们研究一下它的异常安全性。

\n\n

\n

23.2.5.1 异常安全保证 [unord.req.except]
\n 1 对于无序关联容器，clear() 函数不会抛出异常。擦除（k）不会抛出\n异常，除非该异常是由容器\xe2\x80\x99s Hash或Pred对象（如果有）抛出的。
\n 2 对于无序关联容器，如果在插入单个元素的 insert 或 emplace 函数中除容器\xe2\x80\x99s\n 哈希函数之外的任何操作引发异常，则插入无效\n。
\n 3 对于无序关联容器，没有交换函数会抛出异常，除非该异常是由容器\xe2\x80\x99s Hash 或 Pred 对象（如果有）的交换\n 引发的。
\n 4对于无序关联容器，如果从容器\xe2\x80\x99s 哈希函数或比较函数之外的 rehash() 函数内部抛出异常，则 rehash() 函数不起作用。

\n

\n\n

正如您所看到的，rehash() 函数的定义是，如果除了哈希函数或比较函数之外抛出异常，它不会执行任何操作。在我看来，这完全符合合并的定义：

\n\n

\n

抛出：除非哈希函数或键相等谓词抛出，否则不会发生任何异常。

\n

\n\n

我的理解是，当没有空间为bucket list增加底层数据结构时，那么它就保持原来的形式。这可能会导致对元素的访问效率稍低，因为各个存储桶中的元素可能比定义的要多。插入期间也会发生同样的情况。

\n\n

你的情况问题出在哪里？可能是在 rehash() 函数的实现中，在不应该抛出异常的地方抛出异常。

\n\n

免责声明：我不是该主题的专家。这正是我所发现的。因此，如果我错了，请随时纠正我。

\n