class raw_hash_set

template <class Policy, class Hash, class Eq, class Alloc>

class raw_hash_set

Defined at line 1958 of file ../../third_party/abseil-cpp/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).

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.

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.

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.

Public Methods

void raw_hash_set<Policy, Hash, Eq, Alloc> ()

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

problems for some compilers). NOLINTNEXTLINE

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

void raw_hash_set<Policy, Hash, Eq, Alloc> (size_t bucket_count, const hasher & hash, const key_equal & eq, const allocator_type & alloc)

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

void raw_hash_set<Policy, Hash, Eq, Alloc> (size_t bucket_count, const hasher & hash, const allocator_type & alloc)

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

void raw_hash_set<Policy, Hash, Eq, Alloc> (size_t bucket_count, const allocator_type & alloc)

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

void raw_hash_set<Policy, Hash, Eq, Alloc> (const allocator_type & alloc)

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

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

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

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

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

template <class InputIter>
void raw_hash_set<Policy, Hash, Eq, Alloc> (InputIter first, InputIter last, size_t bucket_count, const allocator_type & alloc)

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

template <class InputIter>
void raw_hash_set<Policy, Hash, Eq, Alloc> (InputIter first, InputIter last, const allocator_type & alloc)

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

template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
void raw_hash_set<Policy, Hash, Eq, Alloc> (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 2266 of file ../../third_party/abseil-cpp/absl/container/internal/raw_hash_set.h

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

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

template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
void raw_hash_set<Policy, Hash, Eq, Alloc> (std::initializer_list<T> init, size_t bucket_count, const hasher & hash, const allocator_type & alloc)

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

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

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

template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
void raw_hash_set<Policy, Hash, Eq, Alloc> (std::initializer_list<T> init, size_t bucket_count, const allocator_type & alloc)

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

void raw_hash_set<Policy, Hash, Eq, Alloc> (std::initializer_list<init_type> init, size_t bucket_count, const allocator_type & alloc)

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

template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
void raw_hash_set<Policy, Hash, Eq, Alloc> (std::initializer_list<T> init, const allocator_type & alloc)

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

void raw_hash_set<Policy, Hash, Eq, Alloc> (std::initializer_list<init_type> init, const allocator_type & alloc)

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

void raw_hash_set<Policy, Hash, Eq, Alloc> (const raw_hash_set<Policy, Hash, Eq, Alloc> & that)

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

void raw_hash_set<Policy, Hash, Eq, Alloc> (const raw_hash_set<Policy, Hash, Eq, Alloc> & that, const allocator_type & a)

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

void raw_hash_set<Policy, Hash, Eq, Alloc> (raw_hash_set<Policy, Hash, Eq, Alloc> && that)

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

void raw_hash_set<Policy, Hash, Eq, Alloc> (raw_hash_set<Policy, Hash, Eq, Alloc> && that, const allocator_type & a)

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

raw_hash_set<Policy, Hash, Eq, Alloc> & operator= (const raw_hash_set<Policy, Hash, Eq, Alloc> & that)

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

raw_hash_set<Policy, Hash, Eq, Alloc> & operator= (raw_hash_set<Policy, Hash, Eq, Alloc> && that)

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

void ~raw_hash_set<Policy, Hash, Eq, Alloc> ()

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

iterator begin ()

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

iterator end ()

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

const_iterator begin ()

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

const_iterator end ()

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

const_iterator cbegin ()

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

const_iterator cend ()

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

bool empty ()

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

size_t size ()

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

size_t capacity ()

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

size_t max_size ()

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

void clear ()

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

template <class T, RequiresInsertable<T> = 0, class T2 = T, typename std::enable_if<IsDecomposable<T2>::value, int>::type = 0, T* = nullptr>
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));

TODO(cheshire): A type alias T2 is introduced as a workaround for the nvcc

bug.

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

template <class T, RequiresInsertable<const T&> = 0, typename std::enable_if<IsDecomposable<const T&>::value, int>::type = 0>
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 2488 of file ../../third_party/abseil-cpp/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 2498 of file ../../third_party/abseil-cpp/absl/container/internal/raw_hash_set.h

template <class T, RequiresInsertable<T> = 0, class T2 = T, typename std::enable_if<IsDecomposable<T2>::value, int>::type = 0, T* = nullptr>
iterator insert (const_iterator , T && value)

TODO(cheshire): A type alias T2 is introduced as a workaround for the nvcc

bug.

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

template <class T, RequiresInsertable<const T&> = 0, typename std::enable_if<IsDecomposable<const T&>::value, int>::type = 0>
iterator insert (const_iterator , const T & value)

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

iterator insert (const_iterator , init_type && value)

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

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

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

template <class T, RequiresNotInit<T> = 0, RequiresInsertable<const T&> = 0>
void insert (std::initializer_list<T> ilist)

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

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

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

insert_return_type insert (node_type && node)

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

iterator insert (const_iterator , node_type && node)

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

template <class... Args, typename std::enable_if<
                                                   IsDecomposable<Args...>::value, int>::type = 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 2571 of file ../../third_party/abseil-cpp/absl/container/internal/raw_hash_set.h

template <class... Args, typename std::enable_if<
                                                   !IsDecomposable<Args...>::value, int>::type = 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 2582 of file ../../third_party/abseil-cpp/absl/container/internal/raw_hash_set.h

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

Defined at line 2593 of file ../../third_party/abseil-cpp/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 2645 of file ../../third_party/abseil-cpp/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 2666 of file ../../third_party/abseil-cpp/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. In order to erase while iterating across a map, use the following

idiom (which also works for standard containers):

for (auto it = m.begin(), end = m.end(); it != end;) {

// `erase()` will invalidate `it`, so advance `it` first.

auto copy_it = it++;

if (

<pred

>) {

m.erase(copy_it);

}

}

Defined at line 2686 of file ../../third_party/abseil-cpp/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 2690 of file ../../third_party/abseil-cpp/absl/container/internal/raw_hash_set.h

iterator erase (const_iterator first, const_iterator last)

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

template <typename H, typename E>
void merge (raw_hash_set<Policy, H, E, Alloc> & src)

Moves elements from `src` into `this`.

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

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

template <typename H, typename E>
void merge (raw_hash_set<Policy, H, E, Alloc> && src)

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

node_type extract (const_iterator position)

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

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

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

void swap (raw_hash_set<Policy, Hash, Eq, Alloc> & that)

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

void rehash (size_t n)

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

void reserve (size_t n)

Defined at line 2785 of file ../../third_party/abseil-cpp/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 2808 of file ../../third_party/abseil-cpp/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 2818 of file ../../third_party/abseil-cpp/absl/container/internal/raw_hash_set.h

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

The API of find() has two extensions.

1. The hash can be passed by the user. It must be equal to the hash of the

key.

2. The type of the key argument doesn't have to be key_type. This is so

called heterogeneous key support.

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

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

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

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

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

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

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

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

Defined at line 2873 of file ../../third_party/abseil-cpp/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 2882 of file ../../third_party/abseil-cpp/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 2889 of file ../../third_party/abseil-cpp/absl/container/internal/raw_hash_set.h

size_t bucket_count ()

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

float load_factor ()

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

float max_load_factor ()

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

void max_load_factor (float )

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

hasher hash_function ()

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

key_equal key_eq ()

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

allocator_type get_allocator ()

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

Protected Methods

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 3232 of file ../../third_party/abseil-cpp/absl/container/internal/raw_hash_set.h

size_t prepare_insert (size_t hash)

Given the hash of a value not currently in the table, finds the next

viable slot index to insert it at.

REQUIRES: At least one non-full slot available.

Defined at line 3256 of file ../../third_party/abseil-cpp/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 3297 of file ../../third_party/abseil-cpp/absl/container/internal/raw_hash_set.h

iterator iterator_at (size_t i)

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

const_iterator iterator_at (size_t i)

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

reference unchecked_deref (iterator it)

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

Records

Friends

template <class Policy, class Hash, class Eq, class Alloc>
class RawHashSetTestOnlyAccess
template <class Container, typename Enabler>
class HashtableDebugAccess
template <class Policy, class Hash, class Eq, class Alloc>
void raw_hash_set (raw_hash_set<Policy, Hash, Eq, Alloc> & a, raw_hash_set<Policy, Hash, Eq, Alloc> & 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, Hash, Eq, Alloc> & s)
template <class Policy, class Hash, class Eq, class Alloc>
bool raw_hash_set (const raw_hash_set<Policy, Hash, Eq, Alloc> & a, const raw_hash_set<Policy, Hash, Eq, Alloc> & b)
template <class Policyclass Hashclass Eqclass Alloc>
bool raw_hash_set (const raw_hash_set<Policy, Hash, Eq, Alloc> & aconst raw_hash_set<Policy, Hash, Eq, Alloc> & b)