RHUnorderedMap.h#
Fully qualified name: carb/container/RHUnorderedMap.h
File members: carb/container/RHUnorderedMap.h
// SPDX-FileCopyrightText: Copyright (c) 2022-2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
// SPDX-License-Identifier: LicenseRef-NvidiaProprietary
//
// NVIDIA CORPORATION, its affiliates and licensors retain all intellectual
// property and proprietary rights in and to this material, related
// documentation and any modifications thereto. Any use, reproduction,
// disclosure or distribution of this material and related documentation
// without an express license agreement from NVIDIA CORPORATION or
// its affiliates is strictly prohibited.
#pragma once
#include "RobinHoodImpl.h"
#include <functional> // for std::hash
#include <stdexcept>
#include <tuple>
#include <type_traits>
#include <utility>
namespace carb::container
{
template <typename Key,
typename Value,
typename Hasher = std::hash<Key>,
typename Equals = std::equal_to<Key>,
size_t LoadFactorMax100 = kDefaultLoadFactor,
typename Allocator = std::allocator<std::pair<const Key, Value>>>
class RHUnorderedMap
: public detail::RobinHood<detail::RobinHoodMapTraits<Key, Value, Hasher, Equals, Allocator, LoadFactorMax100>>
{
using Base = detail::RobinHood<detail::RobinHoodMapTraits<Key, Value, Hasher, Equals, Allocator, LoadFactorMax100>>;
static_assert(std::is_same_v<typename Allocator::value_type, std::pair<const Key, Value>>,
"Allocator::value_type must match std::pair<const Key, Value>");
public:
using key_type = typename Base::key_type;
using mapped_type = Value;
using value_type = typename Base::value_type;
using size_type = typename Base::size_type;
using difference_type = typename Base::difference_type;
using hasher = typename Base::hasher;
using key_equal = typename Base::key_equal;
using reference = typename Base::reference;
using const_reference = typename Base::const_reference;
using pointer = typename Base::pointer;
using const_pointer = typename Base::const_pointer;
using iterator = typename Base::iterator;
using const_iterator = typename Base::const_iterator;
using find_iterator = typename Base::find_iterator;
using const_find_iterator = typename Base::const_find_iterator;
using allocator_type = typename Base::allocator_type;
constexpr static size_t LoadFactor = Base::LoadFactor;
private:
// MSVC has an internal compiler error or other errors if we try using Base::IsTransparent_v or use it directly.
template <typename T>
constexpr static bool IsTransparent_v =
detail::dependent_bool<detail::SupportsTransparent<key_type, hasher, key_equal>, T>::value;
public:
constexpr RHUnorderedMap() noexcept = default;
explicit RHUnorderedMap(size_type reserved,
const hasher& h = hasher(),
const key_equal& ke = key_equal(),
const allocator_type& al = allocator_type())
: Base(reserved, h, ke, al)
{
}
RHUnorderedMap(size_type reserved, const allocator_type& al) : RHUnorderedMap(reserved, hasher(), key_equal(), al)
{
}
RHUnorderedMap(size_type reserved, const hasher& h, const allocator_type& al)
: RHUnorderedMap(reserved, h, key_equal(), al)
{
}
explicit RHUnorderedMap(const allocator_type& al) : Base(al)
{
}
template <class InputIt>
RHUnorderedMap(InputIt first,
InputIt last,
size_type reserved = 0,
const hasher& h = hasher(),
const key_equal& ke = key_equal(),
const allocator_type& al = allocator_type())
: RHUnorderedMap(reserved, h, ke, al)
{
// Since first and last are input iterators, we only get one iteration through the list and cannot measure it.
while (first != last)
insert(*(first++));
}
template <class InputIt>
RHUnorderedMap(InputIt first, InputIt last, size_type reserved, const allocator_type& al)
: RHUnorderedMap(reserved, hasher(), key_equal(), al)
{
// Since first and last are input iterators, we only get one iteration through the list and cannot measure it.
while (first != last)
insert(*(first++));
}
template <class InputIt>
RHUnorderedMap(InputIt first, InputIt last, size_type reserved, const hasher& h, const allocator_type& al)
: RHUnorderedMap(reserved, h, key_equal(), al)
{
// Since first and last are input iterators, we only get one iteration through the list and cannot measure it.
while (first != last)
insert(*(first++));
}
RHUnorderedMap(std::initializer_list<value_type> init,
size_type reserved = 0,
const hasher& h = hasher(),
const key_equal& ke = key_equal(),
const allocator_type& al = allocator_type())
: RHUnorderedMap(reserved ? reserved : init.size(), h, ke, al)
{
for (auto& val : init)
insert(val);
}
RHUnorderedMap(std::initializer_list<value_type> init, size_type reserved, const allocator_type& al)
: RHUnorderedMap(init, reserved, hasher(), key_equal(), al)
{
}
RHUnorderedMap(std::initializer_list<value_type> init, size_type reserved, const hasher& h, const allocator_type& al)
: RHUnorderedMap(init, reserved, h, key_equal(), al)
{
}
RHUnorderedMap(const RHUnorderedMap& other) : Base(other)
{
}
RHUnorderedMap(const RHUnorderedMap& other, const Allocator& alloc) : Base(other, alloc)
{
}
RHUnorderedMap(RHUnorderedMap&& other) : Base(std::move(other))
{
}
RHUnorderedMap(RHUnorderedMap&& other, const Allocator& alloc) : Base(std::move(other), alloc)
{
}
~RHUnorderedMap() = default;
RHUnorderedMap& operator=(const RHUnorderedMap& other)
{
Base::operator=(other);
return *this;
}
RHUnorderedMap& operator=(RHUnorderedMap&& other)
{
Base::operator=(std::move(other));
return *this;
}
std::pair<iterator, bool> insert(const value_type& value)
{
return this->insert_unique(value);
}
std::pair<iterator, bool> insert(value_type&& value)
{
return this->insert_unique(std::move(value));
}
template <typename P>
std::pair<iterator, bool> insert(std::enable_if_t<std::is_constructible<value_type, P&&>::value, P&&> value)
{
return insert(value_type{ std::forward<P>(value) });
}
template <typename... Args>
std::pair<iterator, bool> emplace(Args&&... args)
{
// We need the key, so just construct the item here
return insert(value_type{ std::forward<Args>(args)... });
}
template <typename... Args>
std::pair<iterator, bool> try_emplace(const key_type& key, Args&&... args)
{
auto [pvalue, inserted] = this->internal_insert(key);
if (inserted)
this->construct(pvalue, std::piecewise_construct, std::forward_as_tuple(key),
std::forward_as_tuple(std::forward<Args>(args)...));
return std::make_pair(this->make_iter(pvalue), inserted);
}
template <typename... Args>
std::pair<iterator, bool> try_emplace(key_type&& key, Args&&... args)
{
auto [pvalue, inserted] = this->internal_insert(key);
if (inserted)
this->construct(pvalue, std::piecewise_construct, std::forward_as_tuple(std::move(key)),
std::forward_as_tuple(std::forward<Args>(args)...));
return std::make_pair(this->make_iter(pvalue), inserted);
}
template <typename K, typename... Args, typename = std::enable_if_t<IsTransparent_v<K>>>
std::pair<iterator, bool> try_emplace(K&& key, Args&&... args)
{
const K& kref = key;
auto [pvalue, inserted] = this->internal_insert(kref);
if (inserted)
this->construct(pvalue, std::piecewise_construct, std::forward_as_tuple(std::forward<K>(key)),
std::forward_as_tuple(std::forward<Args>(args)...));
return std::make_pair(this->make_iter(pvalue), inserted);
}
size_type erase(const key_type& key)
{
if (auto vt = this->internal_find(key))
{
this->internal_erase(vt);
return 1;
}
return 0;
}
template <typename K,
typename = std::enable_if_t<IsTransparent_v<K> && !std::is_convertible_v<K, const_iterator> &&
!std::is_convertible_v<K, const_find_iterator>>>
size_type erase(const K& key)
{
size_t count = 0;
while (auto vt = this->internal_find(key))
{
this->internal_erase(vt);
++count;
}
return count;
}
#if CARB_EXCEPTIONS_ENABLED || defined(DOXYGEN_BUILD)
mapped_type& at(const key_type& key)
{
auto vt = this->internal_find(key);
if (vt)
return vt->second;
throw std::out_of_range("key not found");
}
const mapped_type& at(const key_type& key) const
{
auto vt = this->internal_find(key);
if (vt)
return vt->second;
throw std::out_of_range("key not found");
}
template <typename K, typename = std::enable_if_t<IsTransparent_v<K>>>
mapped_type& at(const K& key)
{
if (auto vt = this->internal_find(key))
return vt->second;
throw std::out_of_range("equivalent key not found");
}
template <typename K, typename = std::enable_if_t<IsTransparent_v<K>>>
const mapped_type& at(const K& key) const
{
if (auto vt = this->internal_find(key))
return vt->second;
throw std::out_of_range("equivalent key not found");
}
#endif
mapped_type& operator[](const key_type& key)
{
auto [pvalue, inserted] = this->internal_insert(key);
if (inserted)
this->construct(pvalue, std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::tuple<>());
return pvalue->second;
}
mapped_type& operator[](key_type&& key)
{
auto [pvalue, inserted] = this->internal_insert(key);
if (inserted)
this->construct(pvalue, std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::tuple<>{});
return pvalue->second;
}
template <typename K, typename = std::enable_if_t<IsTransparent_v<K>>>
mapped_type& operator[](K&& key)
{
auto [pvalue, inserted] = this->internal_insert(std::forward<K>(key));
if (inserted)
this->construct(
pvalue, std::piecewise_construct, std::forward_as_tuple(std::forward<K>(key)), std::tuple<>{});
return pvalue->second;
}
size_type count(const key_type& key) const
{
return !!this->internal_find(key);
}
template <typename K, typename = std::enable_if_t<IsTransparent_v<K>>>
size_type count(const K& key) const
{
return this->internal_count_multi(key); // transparent key may match multiple even on unique container
}
#ifndef DOXYGEN_BUILD
using Base::begin;
using Base::cbegin;
using Base::cend;
using Base::end;
using Base::capacity;
using Base::empty;
using Base::max_size;
using Base::size;
using Base::clear;
using Base::erase;
using Base::swap;
using Base::contains;
using Base::equal_range;
using Base::find;
using Base::rehash;
using Base::reserve;
using Base::get_allocator;
using Base::hash_function;
using Base::key_eq;
#endif
};
#ifndef DOXYGEN_BUILD
// Deduction guides
template <typename InputIt,
typename Hash = std::hash<detail::KeyFromIt_t<InputIt>>,
typename Pred = std::equal_to<detail::KeyFromIt_t<InputIt>>,
size_t LoadFactorMax100 = kDefaultLoadFactor,
typename Alloc = detail::AllocFromIt_t<InputIt>>
RHUnorderedMap(InputIt, InputIt, size_t = 0, Hash = Hash(), Pred = Pred(), Alloc = Alloc())
-> RHUnorderedMap<detail::KeyFromIt_t<InputIt>, detail::MappedFromIt_t<InputIt>, Hash, Pred, LoadFactorMax100, Alloc>;
template <typename Key,
typename T,
typename Hash = std::hash<Key>,
typename Pred = std::equal_to<Key>,
size_t LoadFactorMax100 = kDefaultLoadFactor,
typename Alloc = std::allocator<std::pair<const Key, T>>>
RHUnorderedMap(std::initializer_list<std::pair<Key, T>>, size_t = 0, Hash = Hash(), Pred = Pred(), Alloc = Alloc())
-> RHUnorderedMap<Key, T, Hash, Pred, LoadFactorMax100, Alloc>;
template <typename InputIt, typename Alloc>
RHUnorderedMap(InputIt, InputIt, size_t, Alloc) -> RHUnorderedMap<detail::KeyFromIt_t<InputIt>,
detail::MappedFromIt_t<InputIt>,
std::hash<detail::KeyFromIt_t<InputIt>>,
std::equal_to<detail::KeyFromIt_t<InputIt>>,
kDefaultLoadFactor,
Alloc>;
template <typename InputIt, typename Hash, typename Alloc>
RHUnorderedMap(InputIt, InputIt, size_t, Hash, Alloc) -> RHUnorderedMap<detail::KeyFromIt_t<InputIt>,
detail::MappedFromIt_t<InputIt>,
Hash,
std::equal_to<detail::KeyFromIt_t<InputIt>>,
kDefaultLoadFactor,
Alloc>;
template <typename Key, typename T, typename Alloc>
RHUnorderedMap(std::initializer_list<std::pair<Key, T>>, size_t, Alloc)
-> RHUnorderedMap<Key, T, std::hash<Key>, std::equal_to<Key>, kDefaultLoadFactor, Alloc>;
template <typename Key, typename T, typename Hash, typename Alloc>
RHUnorderedMap(std::initializer_list<std::pair<Key, T>>, size_t, Hash, Alloc)
-> RHUnorderedMap<Key, T, Hash, std::equal_to<Key>, kDefaultLoadFactor, Alloc>;
#endif
} // namespace carb::container