RHUnorderedSet.h#
Fully qualified name: carb/container/RHUnorderedSet.h
File members: carb/container/RHUnorderedSet.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 Hasher = std::hash<Key>,
typename Equals = std::equal_to<Key>,
size_t LoadFactorMax100 = kDefaultLoadFactor,
typename Allocator = std::allocator<Key>>
class RHUnorderedSet
: public detail::RobinHood<detail::RobinHoodSetTraits<Key, Hasher, Equals, Allocator, LoadFactorMax100>>
{
using Base = detail::RobinHood<detail::RobinHoodSetTraits<Key, Hasher, Equals, Allocator, LoadFactorMax100>>;
static_assert(std::is_same_v<typename Allocator::value_type, Key>, "Allocator::value_type must match Key");
public:
using key_type = typename Base::key_type;
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::const_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 RHUnorderedSet() noexcept = default;
explicit RHUnorderedSet(size_type reserved,
const hasher& h = hasher(),
const key_equal& ke = key_equal(),
const allocator_type& al = allocator_type())
: Base(reserved, h, ke, al)
{
}
RHUnorderedSet(size_type reserved, const allocator_type& al) : RHUnorderedSet(reserved, hasher(), key_equal(), al)
{
}
RHUnorderedSet(size_type reserved, const hasher& h, const allocator_type& al)
: RHUnorderedSet(reserved, h, key_equal(), al)
{
}
explicit RHUnorderedSet(const allocator_type& al) : Base(al)
{
}
template <class InputIt>
RHUnorderedSet(InputIt first,
InputIt last,
size_type reserved = 0,
const hasher& h = hasher(),
const key_equal& ke = key_equal(),
const allocator_type& al = allocator_type())
: RHUnorderedSet(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>
RHUnorderedSet(InputIt first, InputIt last, size_type reserved, const allocator_type& al)
: RHUnorderedSet(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>
RHUnorderedSet(InputIt first, InputIt last, size_type reserved, const hasher& h, const allocator_type& al)
: RHUnorderedSet(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++));
}
RHUnorderedSet(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())
: RHUnorderedSet(reserved ? reserved : init.size(), h, ke, al)
{
for (auto& val : init)
insert(val);
}
RHUnorderedSet(std::initializer_list<value_type> init, size_type reserved, const allocator_type& al)
: RHUnorderedSet(reserved ? reserved : init.size(), hasher(), key_equal(), al)
{
for (auto& val : init)
insert(val);
}
RHUnorderedSet(std::initializer_list<value_type> init, size_type reserved, const hasher& h, const allocator_type& al)
: RHUnorderedSet(reserved ? reserved : init.size(), h, key_equal(), al)
{
for (auto& val : init)
insert(val);
}
RHUnorderedSet(const RHUnorderedSet& other) : Base(other)
{
}
RHUnorderedSet(const RHUnorderedSet& other, const Allocator& alloc) : Base(other, alloc)
{
}
RHUnorderedSet(RHUnorderedSet&& other) : Base(std::move(other))
{
}
RHUnorderedSet(RHUnorderedSet&& other, const Allocator& alloc) : Base(std::move(other), alloc)
{
}
~RHUnorderedSet() = default;
RHUnorderedSet& operator=(const RHUnorderedSet& other)
{
Base::operator=(other);
return *this;
}
RHUnorderedSet& operator=(RHUnorderedSet&& 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 K, typename = std::enable_if_t<IsTransparent_v<K>>>
std::pair<iterator, bool> insert(K&& value)
{
return this->insert_unique(std::forward<K>(value));
}
template <typename... Args>
std::pair<iterator, bool> emplace(Args&&... args)
{
// The value is the key, so just construct the item here
return insert(value_type{ std::forward<Args>(args)... });
}
size_type erase(const key_type& key)
{
auto vt = this->internal_find(key);
if (vt)
{
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(K&& key)
{
size_t count = 0;
while (auto vt = this->internal_find(key))
{
this->internal_erase(vt);
++count;
}
return count;
}
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::ValueFromIt_t<InputIt>>,
typename Pred = std::equal_to<detail::ValueFromIt_t<InputIt>>,
size_t LoadFactorMax100 = kDefaultLoadFactor,
typename Alloc = std::allocator<detail::ValueFromIt_t<InputIt>>>
RHUnorderedSet(InputIt, InputIt, size_t = 0, Hash = Hash(), Pred = Pred(), Alloc = Alloc())
-> RHUnorderedSet<detail::ValueFromIt_t<InputIt>, Hash, Pred, LoadFactorMax100, Alloc>;
template <typename T,
typename Hash = std::hash<T>,
typename Pred = std::equal_to<T>,
size_t LoadFactorMax100 = kDefaultLoadFactor,
typename Alloc = std::allocator<T>>
RHUnorderedSet(std::initializer_list<T>, size_t = 0, Hash = Hash(), Pred = Pred(), Alloc = Alloc())
-> RHUnorderedSet<T, Hash, Pred, LoadFactorMax100, Alloc>;
template <typename InputIt, typename Alloc>
RHUnorderedSet(InputIt, InputIt, size_t, Alloc) -> RHUnorderedSet<detail::ValueFromIt_t<InputIt>,
std::hash<detail::ValueFromIt_t<InputIt>>,
std::equal_to<detail::ValueFromIt_t<InputIt>>,
kDefaultLoadFactor,
Alloc>;
template <typename InputIt, typename Hash, typename Alloc>
RHUnorderedSet(InputIt, InputIt, size_t, Hash, Alloc)
-> RHUnorderedSet<detail::ValueFromIt_t<InputIt>, Hash, std::equal_to<detail::ValueFromIt_t<InputIt>>, kDefaultLoadFactor, Alloc>;
template <typename T, typename Alloc>
RHUnorderedSet(std::initializer_list<T>, size_t, Alloc)
-> RHUnorderedSet<T, std::hash<T>, std::equal_to<T>, kDefaultLoadFactor, Alloc>;
template <typename T, typename Hash, typename Alloc>
RHUnorderedSet(std::initializer_list<T>, size_t, Hash, Alloc)
-> RHUnorderedSet<T, Hash, std::equal_to<T>, kDefaultLoadFactor, Alloc>;
#endif
} // namespace carb::container