RHUnorderedMultimap.h#
Fully qualified name: carb/container/RHUnorderedMultimap.h
File members: carb/container/RHUnorderedMultimap.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 <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 RHUnorderedMultimap
: 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 RHUnorderedMultimap() noexcept = default;
explicit RHUnorderedMultimap(size_type reserved,
const hasher& h = hasher(),
const key_equal& ke = key_equal(),
const allocator_type& al = allocator_type())
: Base(reserved, h, ke, al)
{
}
RHUnorderedMultimap(size_type reserved, const allocator_type& al)
: RHUnorderedMultimap(reserved, hasher(), key_equal(), al)
{
}
RHUnorderedMultimap(size_type reserved, const hasher& h, const allocator_type& al)
: RHUnorderedMultimap(reserved, h, key_equal(), al)
{
}
explicit RHUnorderedMultimap(const allocator_type& al) : Base(al)
{
}
template <class InputIt>
RHUnorderedMultimap(InputIt first,
InputIt last,
size_type reserved = 0,
const hasher& h = hasher(),
const key_equal& ke = key_equal(),
const allocator_type& al = allocator_type())
: RHUnorderedMultimap(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>
RHUnorderedMultimap(InputIt first, InputIt last, size_type reserved, const allocator_type& al)
: RHUnorderedMultimap(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>
RHUnorderedMultimap(InputIt first, InputIt last, size_type reserved, const hasher& h, const allocator_type& al)
: RHUnorderedMultimap(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++));
}
RHUnorderedMultimap(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())
: RHUnorderedMultimap(reserved ? reserved : init.size(), h, ke, al)
{
for (auto& val : init)
insert(val);
}
RHUnorderedMultimap(std::initializer_list<value_type> init, size_type reserved, const allocator_type& al)
: RHUnorderedMultimap(init, reserved, hasher(), key_equal(), al)
{
}
RHUnorderedMultimap(std::initializer_list<value_type> init,
size_type reserved,
const hasher& h,
const allocator_type& al)
: RHUnorderedMultimap(init, reserved, h, key_equal(), al)
{
}
RHUnorderedMultimap(const RHUnorderedMultimap& other) : Base(other)
{
}
RHUnorderedMultimap(const RHUnorderedMultimap& other, const Allocator& alloc) : Base(other, alloc)
{
}
RHUnorderedMultimap(RHUnorderedMultimap&& other) : Base(std::move(other))
{
}
RHUnorderedMultimap(RHUnorderedMultimap&& other, const Allocator& alloc) : Base(std::move(other), alloc)
{
}
~RHUnorderedMultimap() = default;
RHUnorderedMultimap& operator=(const RHUnorderedMultimap& other)
{
Base::operator=(other);
return *this;
}
RHUnorderedMultimap& operator=(RHUnorderedMultimap&& other)
{
Base::operator=(std::move(other));
return *this;
}
iterator insert(const value_type& value)
{
return this->insert_multi(value);
}
iterator insert(value_type&& value)
{
return this->insert_multi(std::move(value));
}
template <typename P>
iterator 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>
iterator emplace(Args&&... args)
{
// We need the key, so just construct the item here
return insert(value_type{ std::forward<Args>(args)... });
}
size_type erase(const key_type& key)
{
size_t count = 0;
auto vt = this->internal_find(key);
decltype(vt) next;
for (; vt; vt = next)
{
next = this->_findnext(vt);
this->internal_erase(vt);
++count;
}
return count;
}
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(K&& key)
{
size_t count = 0;
auto vt = this->internal_find(key);
decltype(vt) next;
for (; vt; vt = next)
{
next = this->_findnext(vt, key);
this->internal_erase(vt);
++count;
}
return count;
}
size_type count(const key_type& key) const
{
return this->internal_count_multi(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);
}
#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>>
RHUnorderedMultimap(InputIt, InputIt, size_t = 0, Hash = Hash(), Pred = Pred(), Alloc = Alloc())
-> RHUnorderedMultimap<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>>>
RHUnorderedMultimap(std::initializer_list<std::pair<Key, T>>, size_t = 0, Hash = Hash(), Pred = Pred(), Alloc = Alloc())
-> RHUnorderedMultimap<Key, T, Hash, Pred, LoadFactorMax100, Alloc>;
template <typename InputIt, typename Alloc>
RHUnorderedMultimap(InputIt, InputIt, size_t, Alloc) -> RHUnorderedMultimap<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>
RHUnorderedMultimap(InputIt, InputIt, size_t, Hash, Alloc)
-> RHUnorderedMultimap<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>
RHUnorderedMultimap(std::initializer_list<std::pair<Key, T>>, size_t, Alloc)
-> RHUnorderedMultimap<Key, T, std::hash<Key>, std::equal_to<Key>, kDefaultLoadFactor, Alloc>;
template <typename Key, typename T, typename Hash, typename Alloc>
RHUnorderedMultimap(std::initializer_list<std::pair<Key, T>>, size_t, Hash, Alloc)
-> RHUnorderedMultimap<Key, T, Hash, std::equal_to<Key>, kDefaultLoadFactor, Alloc>;
#endif
} // namespace carb::container