Безопасность std :: unordered_map :: merge ()

При написании некоторого кода, предназначенного для 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?

Стоит отметить, что я проверял систему отслеживания ошибок gcc до написания этой статьи и, похоже, не обнаружил открытых ошибок, соответствующих моему описанию, и, кроме того, я проверил стандартный отчет о дефектах C ++ и, похоже, выглядел пустым (правда, делая текстовый поиск на этом сайте усугубляет, и я, возможно, был менее чем тщательно). Последнее неудивительно, так как стандартные дефекты и их обходные пути или последствия обычно отмечаются в исходном коде gcc, и я не нашел таких обозначений во время моего исследования. Я попытался скомпилировать мой пример кода в моей последней проверке clang (старше недели), но компилятор вышел из строя, поэтому я больше не сдавал экзамен и не консультировался с libc ++.