При написании кода, ориентированного на С++ 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 с тем же количеством элементов, которые я мог обеспечить, были бы уникальными для обоих контейнеров, что означает, что карта, содержащая объединенный результат, удвоит количество элементов, которые она ранее имела, и контейнер слит - из будет пустым. Это должно быть абсолютно безопасно благодаря С++ 17, правильно?
Это огромная победа в плане производительности... кроме того, у меня было это сомнительное сомнение. Как ни странно, в постусловном заявлении ничего не говорится о том, будет ли соблюден предыдущий максимальный коэффициент загрузки в объединенной карте, и хотя это кажется безопасным подразумеваемым предположением, оно, казалось, наивно противоречило заявлению об исключении-безопасности unordered_map. Если вы используете схему хеш-таблицы, в которой ведра являются смежными выделенными буферами, поддержание вашего коэффициента загрузки, по-видимому, подразумевает перезагрузку, что, по-видимому, подразумевает перераспределение буфера буфера.
Уже это казалось упражнением в экстремальном взгляде на пуповины, и было хорошей причиной, чтобы уйти достаточно хорошо в одиночку: более сложный хеш-стол можно было бы сделать как полностью основанную на node структуру, похожую на красно- черные деревья обычно лежат в основе std:: map, и в таком случае спецификация представляется разумной, так как пересмотр не предполагает выделения.
Возможно, в мою пользу, я поддался сомнению и вникнул в реализацию gcc-7.1 слияния. Это невероятно сложно, но, чтобы обобщить мои выводы, я обнаружил, что ведра, действительно, смежно распределены буферами, и повторное использование подразумевает перераспределение. Может быть, подумал я, была какая-то более глубокая магия, которую мне не хватало (я смотрел на источник почти целый день и все еще чувствовал, что у меня плохое понимание), который просто отключил повторное переключение во время слияния, а это означает, что все указанные условия будет поддерживаться, но вы можете получить неприятную регрессию производительности после достаточно большого слияния, поскольку ваша карта, вероятно, будет перегружена.
Я перешел на практическую оценку, отражающую мой случай использования (который я бы представил, если это было возможно, извините), вместо того, чтобы просто допросить мою интерпретацию libstdС++:
#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
В то время как строка 98 (m1.reserve( m1.size() + m2.size() );) без комментирования приводит к ожидаемому результату:
map :=
{
{ Red, 2 }
{ Violet, 5 }
{ Purple, 0 }
{ Green, 3 }
{ Blue, 12 }
{ Indigo, 16 }
}
Понимая, что С++ 17 по-прежнему является стандартом проекта, который еще не был доработан, и что реализация gcc является экспериментальной, я полагаю, что мой вопрос будет следующим:
- Неужели я серьезно неверно истолковал безопасность операции слияния, как указано в стандарте? Существуют ли лучшие методы использования
std::unordered_map::merge(), которые я пропустил? Должен ли я быть неявным ответственным за обеспечение распределения ведер? Будет ли использованиеstd::unordered_map::reserve()действительно переносимым, когда clang, MSVC и Intel наконец поддерживают С++ 17? Я имею в виду, что моя программа прерывается, когда невозможно исключить объединение без исключения, после некоторого понятия придерживайтесь перечисленных постусловий... - Это на самом деле дефект в стандарте? Сходство формулировки между неупорядоченными ассоциативными контейнерами и обычными ассоциативными контейнерами могло бы позволить непреднамеренным гарантиям ускользнуть, если текст был, скажем, скопирован.
- Это просто ошибка gcc?
Стоит отметить, что я проверял gcc-трекер перед этой записью и, казалось, не обнаружил никаких открытых ошибок, соответствующих моему описанию, и, кроме того, я проверил стандартный отчет о дефектах С++ и, похоже, выглядел пустым (правда, выполнение текстового поиска этого сайта усугубляется, и я, возможно, был менее тщательным). Последнее неудивительно, поскольку стандартные дефекты и их обходные пути или последствия обычно отмечаются в исходном коде gcc, и во время моего изучения я не обнаружил таких обозначений. Я попытался скомпилировать свой пример кода в моей последней проверке clang (старше недели), но компилятор отключился, поэтому я больше не проводил экзамен и не консультировался с libС++.
