class raw_hash_set

template <class Policy, class... Params>

class raw_hash_set

Defined at line 1804 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

A SwissTable.

Policy: a policy defines how to perform different operations on

the slots of the hashtable (see hash_policy_traits.h for the full interface

of policy).

Params...: a variadic list of parameters that allows us to omit default

types. This reduces the mangled name of the class and the size of

debug strings like __PRETTY_FUNCTION__. Default types do not give

any new information.

Hash: a (possibly polymorphic) functor that hashes keys of the hashtable. The

functor should accept a key and return size_t as hash. For best performance

it is important that the hash function provides high entropy across all bits

of the hash.

This is the first element in `Params...` if it exists, or Policy::DefaultHash

otherwise.

Eq: a (possibly polymorphic) functor that compares two keys for equality. It

should accept two (of possibly different type) keys and return a bool: true

if they are equal, false if they are not. If two keys compare equal, then

their hash values as defined by Hash MUST be equal.

This is the second element in `Params...` if it exists, or Policy::DefaultEq

otherwise.

Allocator: an Allocator

[https://en.cppreference.com/w/cpp/named_req/Allocator] with which

the storage of the hashtable will be allocated and the elements will be

constructed and destroyed.

This is the third element in `Params...` if it exists, or

Policy::DefaultAlloc otherwise.

Public Methods

void raw_hash_set<Policy, Params...> ()

Note: can't use `= default` due to non-default noexcept (causes

problems for some compilers). NOLINTNEXTLINE

Defined at line 2106 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void raw_hash_set<Policy, Params...> (size_t bucket_count, const hasher & hash, const key_equal & eq, const allocator_type & alloc)

Defined at line 2111 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void raw_hash_set<Policy, Params...> (size_t bucket_count, const hasher & hash, const allocator_type & alloc)

Defined at line 2123 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void raw_hash_set<Policy, Params...> (size_t bucket_count, const allocator_type & alloc)

Defined at line 2127 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void raw_hash_set<Policy, Params...> (const allocator_type & alloc)

Defined at line 2130 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class InputIter>
void raw_hash_set<Policy, Params...> (InputIter first, InputIter last, size_t bucket_count, const hasher & hash, const key_equal & eq, const allocator_type & alloc)

Defined at line 2134 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class InputIter>
void raw_hash_set<Policy, Params...> (InputIter first, InputIter last, size_t bucket_count, const hasher & hash, const allocator_type & alloc)

Defined at line 2143 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class InputIter>
void raw_hash_set<Policy, Params...> (InputIter first, InputIter last, size_t bucket_count, const allocator_type & alloc)

Defined at line 2148 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class InputIter>
void raw_hash_set<Policy, Params...> (InputIter first, InputIter last, const allocator_type & alloc)

Defined at line 2153 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class T, RequiresNotInit<T> = 0, std::enable_if_t<Insertable<T>::value, int> = 0>
void raw_hash_set<Policy, Params...> (std::initializer_list<T> init, size_t bucket_count, const hasher & hash, const key_equal & eq, const allocator_type & alloc)

Instead of accepting std::initializer_list

<value

_type> as the first

argument like std::unordered_set

<value

_type> does, we have two overloads

that accept std::initializer_list

<T

> and std::initializer_list

<init

_type>.

This is advantageous for performance.

// Turns {"abc", "def"} into std::initializer_list

<std

::string>, then

// copies the strings into the set.

std::unordered_set

<std

::string> s = {"abc", "def"};

// Turns {"abc", "def"} into std::initializer_list

<const

char*>, then

// copies the strings into the set.

absl::flat_hash_set

<std

::string> s = {"abc", "def"};

The same trick is used in insert().

The enabler is necessary to prevent this constructor from triggering where

the copy constructor is meant to be called.

absl::flat_hash_set

<int

> a, b{a};

RequiresNotInit

<T

> is a workaround for gcc prior to 7.1.

Defined at line 2179 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void raw_hash_set<Policy, Params...> (std::initializer_list<init_type> init, size_t bucket_count, const hasher & hash, const key_equal & eq, const allocator_type & alloc)

Defined at line 2184 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class T, RequiresNotInit<T> = 0, std::enable_if_t<Insertable<T>::value, int> = 0>
void raw_hash_set<Policy, Params...> (std::initializer_list<T> init, size_t bucket_count, const hasher & hash, const allocator_type & alloc)

Defined at line 2191 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void raw_hash_set<Policy, Params...> (std::initializer_list<init_type> init, size_t bucket_count, const hasher & hash, const allocator_type & alloc)

Defined at line 2195 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class T, RequiresNotInit<T> = 0, std::enable_if_t<Insertable<T>::value, int> = 0>
void raw_hash_set<Policy, Params...> (std::initializer_list<T> init, size_t bucket_count, const allocator_type & alloc)

Defined at line 2201 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void raw_hash_set<Policy, Params...> (std::initializer_list<init_type> init, size_t bucket_count, const allocator_type & alloc)

Defined at line 2205 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class T, RequiresNotInit<T> = 0, std::enable_if_t<Insertable<T>::value, int> = 0>
void raw_hash_set<Policy, Params...> (std::initializer_list<T> init, const allocator_type & alloc)

Defined at line 2211 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void raw_hash_set<Policy, Params...> (std::initializer_list<init_type> init, const allocator_type & alloc)

Defined at line 2214 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void raw_hash_set<Policy, Params...> (const raw_hash_set<Policy, Params...> & that)

Defined at line 2218 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void raw_hash_set<Policy, Params...> (const raw_hash_set<Policy, Params...> & that, const allocator_type & a)

Defined at line 2222 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void raw_hash_set<Policy, Params...> (raw_hash_set<Policy, Params...> && that)

Defined at line 2236 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void raw_hash_set<Policy, Params...> (raw_hash_set<Policy, Params...> && that, const allocator_type & a)

Defined at line 2255 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

raw_hash_set<Policy, Params...> & operator= (const raw_hash_set<Policy, Params...> & that)

Defined at line 2266 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

raw_hash_set<Policy, Params...> & operator= (raw_hash_set<Policy, Params...> && that)

Defined at line 2282 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void ~raw_hash_set<Policy, Params...> ()

Defined at line 2294 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

iterator begin ()

Defined at line 2301 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

iterator end ()

Defined at line 2310 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

const_iterator begin ()

Defined at line 2315 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

const_iterator end ()

Defined at line 2318 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

const_iterator cbegin ()

Defined at line 2321 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

const_iterator cend ()

Defined at line 2324 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

bool empty ()

Defined at line 2326 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

size_t size ()

Defined at line 2327 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

size_t capacity ()

Defined at line 2331 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

size_t max_size ()

Defined at line 2339 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void clear ()

Defined at line 2341 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class T, int = std::enable_if_t<IsDecomposableAndInsertable<T>::value &&
                                                           IsNotBitField<T>::value &&
                                                           !IsLifetimeBoundAssignmentFrom<T>::value,
                                                       int>()>
std::pair<iterator, bool> insert (T && value)

This overload kicks in when the argument is an rvalue of insertable and

decomposable type other than init_type.

flat_hash_map

<std

::string, int> m;

m.insert(std::make_pair("abc", 42));

Defined at line 2380 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class T, int&, std::enable_if_t<IsDecomposableAndInsertable<T>::value &&
                                                     IsNotBitField<T>::value &&
                                                     IsLifetimeBoundAssignmentFrom<T>::value,
                                                 int> = 0>
std::pair<iterator, bool> insert (T && value)

Defined at line 2389 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class T, int = std::enable_if_t<
                                             IsDecomposableAndInsertable<const T&>::value &&
                                                 !IsLifetimeBoundAssignmentFrom<const T&>::value,
                                             int>()>
std::pair<iterator, bool> insert (const T & value)

This overload kicks in when the argument is a bitfield or an lvalue of

insertable and decomposable type.

union { int n : 1; };

flat_hash_set

<int

> s;

s.insert(n);

flat_hash_set

<std

::string> s;

const char* p = "hello";

s.insert(p);

Defined at line 2410 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class T, int&, std::enable_if_t<IsDecomposableAndInsertable<const T&>::value &&
                                                     IsLifetimeBoundAssignmentFrom<const T&>::value,
                                                 int> = 0>
std::pair<iterator, bool> insert (const T & value)

Defined at line 2418 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

std::pair<iterator, bool> insert (init_type && value)

This overload kicks in when the argument is an rvalue of init_type. Its

purpose is to handle brace-init-list arguments.

flat_hash_map

<std

::string, int> s;

s.insert({"abc", 42});

Defined at line 2429 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class T, int = std::enable_if_t<IsDecomposableAndInsertable<T>::value &&
                                                           IsNotBitField<T>::value &&
                                                           !IsLifetimeBoundAssignmentFrom<T>::value,
                                                       int>()>
iterator insert (const_iterator , T && value)

Defined at line 2452 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class T, int&, std::enable_if_t<IsDecomposableAndInsertable<T>::value &&
                                                     IsNotBitField<T>::value &&
                                                     IsLifetimeBoundAssignmentFrom<T>::value,
                                                 int> = 0>
iterator insert (const_iterator hint, T && value)

Defined at line 2460 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class T, std::enable_if_t<
                                             IsDecomposableAndInsertable<const T&>::value, int> = 0>
iterator insert (const_iterator , const T & value)

Defined at line 2468 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

iterator insert (const_iterator , init_type && value)

Defined at line 2473 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class InputIt>
void insert (InputIt first, InputIt last)

Defined at line 2479 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class T, RequiresNotInit<T> = 0, std::enable_if_t<Insertable<const T&>::value, int> = 0>
void insert (std::initializer_list<T> ilist)

Defined at line 2485 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void insert (std::initializer_list<init_type> ilist)

Defined at line 2489 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

insert_return_type insert (node_type && node)

Defined at line 2493 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

iterator insert (const_iterator , node_type && node)

Defined at line 2507 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class... Args, std::enable_if_t<IsDecomposable<Args...>::value, int> = 0>
std::pair<iterator, bool> emplace (Args &&... args)

This overload kicks in if we can deduce the key from args. This enables us

to avoid constructing value_type if an entry with the same key already

exists.

For example:

flat_hash_map

<std

::string, std::string> m = {{"abc", "def"}};

// Creates no std::string copies and makes no heap allocations.

m.emplace("abc", "xyz");

Defined at line 2525 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class... Args, std::enable_if_t<!IsDecomposable<Args...>::value, int> = 0>
std::pair<iterator, bool> emplace (Args &&... args)

This overload kicks in if we cannot deduce the key from args. It constructs

value_type unconditionally and then either moves it into the table or

destroys.

Defined at line 2536 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class... Args>
iterator emplace_hint (const_iterator , Args &&... args)

Defined at line 2547 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class K = key_type, class F>
iterator lazy_emplace (const key_arg<K> & key, F && f)

Defined at line 2599 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class K = key_type>
size_type erase (const key_arg<K> & key)

Extension API: support for heterogeneous keys.

std::unordered_set

<std

::string> s;

// Turns "abc" into std::string.

s.erase("abc");

flat_hash_set

<std

::string> s;

// Uses "abc" directly without copying it into std::string.

s.erase("abc");

Defined at line 2621 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void erase (const_iterator cit)

Erases the element pointed to by `it`. Unlike `std::unordered_set::erase`,

this method returns void to reduce algorithmic complexity to O(1). The

iterator is invalidated so any increment should be done before calling

erase (e.g. `erase(it++)`).

Defined at line 2632 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void erase (iterator it)

This overload is necessary because otherwise erase

<K

>(const K

&

) would be

a better match if non-const iterator is passed as an argument.

Defined at line 2636 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

iterator erase (const_iterator first, const_iterator last)

Defined at line 2644 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <typename... Params2, typename = std::enable_if_t<std::is_same_v<
                              Alloc, typename raw_hash_set<Policy, Params2...>::allocator_type>>>
void merge (raw_hash_set<Policy, Params2...> & src)

Moves elements from `src` into `this`.

If the element already exists in `this`, it is left unmodified in `src`.

Defined at line 2677 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <typename... Params2, typename = std::enable_if_t<std::is_same_v<
                              Alloc, typename raw_hash_set<Policy, Params2...>::allocator_type>>>
void merge (raw_hash_set<Policy, Params2...> && src)

Defined at line 2705 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

node_type extract (const_iterator position)

Defined at line 2709 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class K = key_type, std::enable_if_t<!std::is_same<K, iterator>::value, int> = 0>
node_type extract (const key_arg<K> & key)

Defined at line 2720 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void swap (raw_hash_set<Policy, Params...> & that)

Defined at line 2725 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void rehash (size_t n)

Defined at line 2739 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void reserve (size_t n)

Defined at line 2741 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class K = key_type>
size_t count (const key_arg<K> & key)

Extension API: support for heterogeneous keys.

std::unordered_set

<std

::string> s;

// Turns "abc" into std::string.

s.count("abc");

ch_set

<std

::string> s;

// Uses "abc" directly without copying it into std::string.

s.count("abc");

Defined at line 2757 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class K = key_type>
void prefetch (const key_arg<K> & key)

Issues CPU prefetch instructions for the memory needed to find or insert

a key. Like all lookup functions, this support heterogeneous keys.

NOTE: This is a very low level operation and should not be used without

specific benchmarks indicating its importance.

Defined at line 2767 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class K = key_type>
iterator find (const key_arg<K> & key, size_t )

Defined at line 2780 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class K = key_type>
iterator find (const key_arg<K> & key)

The API of find() has one extension: the type of the key argument doesn't

have to be key_type. This is so called heterogeneous key support.

Defined at line 2788 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class K = key_type>
const_iterator find (const key_arg<K> & key, size_t )

Defined at line 2796 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class K = key_type>
const_iterator find (const key_arg<K> & key)

Defined at line 2802 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class K = key_type>
bool contains (const key_arg<K> & key)

Defined at line 2808 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class K = key_type>
std::pair<iterator, iterator> equal_range (const key_arg<K> & key)

Defined at line 2817 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class K = key_type>
std::pair<const_iterator, const_iterator> equal_range (const key_arg<K> & key)

Defined at line 2824 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

size_t bucket_count ()

Defined at line 2831 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

float load_factor ()

Defined at line 2832 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

float max_load_factor ()

Defined at line 2835 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void max_load_factor (float )

Defined at line 2836 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

hasher hash_function ()

Defined at line 2840 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

key_equal key_eq ()

Defined at line 2841 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

allocator_type get_allocator ()

Defined at line 2842 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

Protected Methods

template <class K>
void AssertOnFind (const K & key)

Asserts for correctness that we run on find/find_or_prepare_insert.

Defined at line 3279 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void AssertNotDebugCapacity ()

Asserts that the capacity is not a sentinel invalid value.

Defined at line 3285 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class K>
void AssertHashEqConsistent (const K & key)

Asserts that hash and equal functors provided by the user are consistent,

meaning that `eq(k1, k2)` implies `hash(k1)==hash(k2)`.

Defined at line 3317 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class K>
std::pair<iterator, bool> find_or_prepare_insert (const K & key)

Attempts to find `key` in the table; if it isn't found, returns an iterator

where the value can be inserted into, with the control byte already set to

`key`'s H2. Returns a bool indicating whether an insertion can take place.

Defined at line 3358 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class... Args>
void emplace_at (iterator iter, Args &&... args)

Constructs the value in the space pointed by the iterator. This only works

after an unsuccessful find_or_prepare_insert() and before any other

modifications happen in the raw_hash_set.

PRECONDITION: iter was returned from find_or_prepare_insert(k), where k is

the key decomposed from `forward

<Args

>(args)...`, and the bool returned by

find_or_prepare_insert(k) was true.

POSTCONDITION: *m.iterator_at(i) == value_type(forward

<Args

>(args)...).

Defined at line 3373 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

iterator iterator_at (size_t i)

Defined at line 3383 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

const_iterator iterator_at (size_t i)

Defined at line 3386 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

iterator iterator_at_ptr (std::pair<ctrl_t *, void *> ptrs)

Defined at line 3389 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

reference unchecked_deref (iterator it)

Defined at line 3394 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

Records

Friends

template <class Policy, class... Params>
class RawHashSetTestOnlyAccess
template <class Policy, class... Params>
class HashtableFreeFunctionsAccess
template <class Container, typename Enabler>
class HashtableDebugAccess
template <class Policy, class... Params>
void raw_hash_set (raw_hash_set<Policy, Params...> & a, raw_hash_set<Policy, Params...> & b)
template <typename H>
typename std::enable_if<H::template is_hashable<value_type>::value, H>::type raw_hash_set (H h, const raw_hash_set<Policy, Params...> & s)
template <class Policy, class... Params>
bool raw_hash_set (const raw_hash_set<Policy, Params...> & a, const raw_hash_set<Policy, Params...> & b)
template <class Policyclass... Params>
bool raw_hash_set (const raw_hash_set<Policy, Params...> & aconst raw_hash_set<Policy, Params...> & b)