folly-clib-20260203.1245: folly/folly/container/F14Set.h
/*
* Copyright (c) Meta Platforms, Inc. and affiliates.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
//
// Docs: https://fburl.com/fbcref_f14nodeset
//
#pragma once
/**
* F14NodeSet, F14ValueSet, and F14VectorSet
*
* F14FastSet conditionally works like F14ValueSet or F14VectorSet
*
* See F14.md
*/
#include <cstddef>
#include <initializer_list>
#include <tuple>
#include <folly/Portability.h>
#include <folly/container/View.h>
#include <folly/lang/SafeAssert.h>
#include <folly/container/F14Set-fwd.h>
#include <folly/container/Iterator.h>
#include <folly/container/detail/F14Policy.h>
#include <folly/container/detail/F14SetFallback.h>
#include <folly/container/detail/F14Table.h>
#include <folly/container/detail/Util.h>
namespace folly {
#if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
//////// Common case for supported platforms
namespace f14 {
namespace detail {
template <typename Policy>
class F14BasicSet {
template <typename K, typename T>
using EnableHeterogeneousFind = std::enable_if_t<
::folly::detail::EligibleForHeterogeneousFind<
typename Policy::Value,
typename Policy::Hasher,
typename Policy::KeyEqual,
K>::value,
T>;
template <typename K, typename T>
using EnableHeterogeneousInsert = std::enable_if_t<
::folly::detail::EligibleForHeterogeneousInsert<
typename Policy::Value,
typename Policy::Hasher,
typename Policy::KeyEqual,
K>::value,
T>;
template <typename K>
using IsIter = std::is_same<typename Policy::Iter, remove_cvref_t<K>>;
template <typename K, typename T>
using EnableHeterogeneousErase = std::enable_if_t<
::folly::detail::EligibleForHeterogeneousFind<
typename Policy::Value,
typename Policy::Hasher,
typename Policy::KeyEqual,
std::conditional_t<IsIter<K>::value, typename Policy::Value, K>>::
value &&
!IsIter<K>::value,
T>;
public:
//// PUBLIC - Member types
using key_type = typename Policy::Value;
using value_type = key_type;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using hash_token_type = F14HashToken;
using hasher = typename Policy::Hasher;
using key_equal = typename Policy::KeyEqual;
using hashed_key_type = F14HashedKey<key_type, hasher, key_equal>;
using allocator_type = typename Policy::Alloc;
using reference = value_type&;
using const_reference = value_type const&;
using pointer = typename Policy::AllocTraits::pointer;
using const_pointer = typename Policy::AllocTraits::const_pointer;
using iterator = typename Policy::Iter;
using const_iterator = iterator;
private:
using ItemIter = typename Policy::ItemIter;
public:
//// PUBLIC - Member functions
F14BasicSet() noexcept(Policy::kDefaultConstructIsNoexcept) : table_{} {}
explicit F14BasicSet(
std::size_t initialCapacity,
hasher const& hash = hasher{},
key_equal const& eq = key_equal{},
allocator_type const& alloc = allocator_type{})
: table_{initialCapacity, hash, eq, alloc} {}
explicit F14BasicSet(std::size_t initialCapacity, allocator_type const& alloc)
: F14BasicSet(initialCapacity, hasher{}, key_equal{}, alloc) {}
explicit F14BasicSet(
std::size_t initialCapacity,
hasher const& hash,
allocator_type const& alloc)
: F14BasicSet(initialCapacity, hash, key_equal{}, alloc) {}
explicit F14BasicSet(allocator_type const& alloc)
: F14BasicSet(0, hasher{}, key_equal{}, alloc) {}
template <typename InputIt>
F14BasicSet(
InputIt first,
InputIt last,
std::size_t initialCapacity = 0,
hasher const& hash = hasher{},
key_equal const& eq = key_equal{},
allocator_type const& alloc = allocator_type{})
: table_{initialCapacity, hash, eq, alloc} {
initialInsert(first, last, initialCapacity);
}
template <typename InputIt>
F14BasicSet(
InputIt first,
InputIt last,
std::size_t initialCapacity,
allocator_type const& alloc)
: table_{initialCapacity, hasher{}, key_equal{}, alloc} {
initialInsert(first, last, initialCapacity);
}
template <typename InputIt>
F14BasicSet(
InputIt first,
InputIt last,
std::size_t initialCapacity,
hasher const& hash,
allocator_type const& alloc)
: table_{initialCapacity, hash, key_equal{}, alloc} {
initialInsert(first, last, initialCapacity);
}
F14BasicSet(F14BasicSet const& rhs) = default;
F14BasicSet(F14BasicSet const& rhs, allocator_type const& alloc)
: table_(rhs.table_, alloc) {}
F14BasicSet(F14BasicSet&& rhs) = default;
F14BasicSet(F14BasicSet&& rhs, allocator_type const& alloc) noexcept(
Policy::kAllocIsAlwaysEqual)
: table_{std::move(rhs.table_), alloc} {}
/* implicit */ F14BasicSet(
std::initializer_list<value_type> init,
std::size_t initialCapacity = 0,
hasher const& hash = hasher{},
key_equal const& eq = key_equal{},
allocator_type const& alloc = allocator_type{})
: table_{initialCapacity, hash, eq, alloc} {
initialInsert(init.begin(), init.end(), initialCapacity);
}
F14BasicSet(
std::initializer_list<value_type> init,
std::size_t initialCapacity,
allocator_type const& alloc)
: table_{initialCapacity, hasher{}, key_equal{}, alloc} {
initialInsert(init.begin(), init.end(), initialCapacity);
}
F14BasicSet(
std::initializer_list<value_type> init,
std::size_t initialCapacity,
hasher const& hash,
allocator_type const& alloc)
: table_{initialCapacity, hash, key_equal{}, alloc} {
initialInsert(init.begin(), init.end(), initialCapacity);
}
F14BasicSet& operator=(F14BasicSet const&) = default;
F14BasicSet& operator=(F14BasicSet&&) = default;
F14BasicSet& operator=(std::initializer_list<value_type> ilist) {
clear();
bulkInsert(ilist.begin(), ilist.end(), true);
return *this;
}
/// Get the allocator for this container.
allocator_type get_allocator() const noexcept { return table_.alloc(); }
//// PUBLIC - Iterators
/// @methodset Iterators
iterator begin() noexcept { return cbegin(); }
const_iterator begin() const noexcept { return cbegin(); }
/// @methodset Iterators
const_iterator cbegin() const noexcept {
return table_.makeIter(table_.begin());
}
/// @methodset Iterators
iterator end() noexcept { return cend(); }
const_iterator end() const noexcept { return cend(); }
/// @methodset Iterators
const_iterator cend() const noexcept { return table_.makeIter(table_.end()); }
//// PUBLIC - Capacity
/**
* Check if this container has any elements.
* @methodset Capacity
*/
bool empty() const noexcept { return table_.empty(); }
/**
* Number of elements in this container.
* @methodset Capacity
*/
std::size_t size() const noexcept { return table_.size(); }
/**
* The maximum size of this container.
* @methodset Capacity
*/
std::size_t max_size() const noexcept { return table_.max_size(); }
//// PUBLIC - Modifiers
/**
* Remove all elements.
*
* Frees heap-allocated memory; bucket_count is returned to 0.
*
* @methodset Modifiers
*/
void clear() noexcept { table_.clear(); }
/**
* Add a single element.
*
* @overloadbrief Add elements.
* @methodset Modifiers
*/
std::pair<iterator, bool> insert(value_type const& value) {
return emplace(value);
}
/// Add a single element.
std::pair<iterator, bool> insert(value_type&& value) {
return emplace(std::move(value));
}
/**
* Add a single element, with a locational hint.
*
* std::unordered_set's hinted insertion API is misleading. No implementation
* I've seen actually uses the hint. Code restructuring by the caller to use
* the hinted API is at best unnecessary, and at worst a pessimization. It is
* used, however, so we provide it.
*/
iterator insert(const_iterator /*hint*/, value_type const& value) {
return insert(value).first;
}
/// Add a single element, with a locational hint.
iterator insert(const_iterator /*hint*/, value_type&& value) {
return insert(std::move(value)).first;
}
/// Add a single element, of a heterognous type.
template <typename K>
EnableHeterogeneousInsert<K, std::pair<iterator, bool>> insert(K&& value) {
return emplace(std::forward<K>(value));
}
private:
template <class InputIt>
FOLLY_ALWAYS_INLINE void bulkInsert(
InputIt first, InputIt last, bool autoReserve) {
if (autoReserve) {
auto n = std::distance(first, last);
if (n == 0) {
return;
}
table_.reserveForInsert(n);
}
while (first != last) {
insert(*first);
++first;
}
}
template <class InputIt>
void initialInsert(InputIt first, InputIt last, std::size_t initialCapacity) {
FOLLY_SAFE_DCHECK(empty() && bucket_count() >= initialCapacity, "");
// It's possible that there are a lot of duplicates in first..last and
// so we will oversize ourself. The common case, however, is that
// we can avoid a lot of rehashing if we pre-expand. The behavior
// is easy to disable at a particular call site by asking for an
// initialCapacity of 1.
bool autoReserve =
std::is_base_of<
std::random_access_iterator_tag,
typename std::iterator_traits<InputIt>::iterator_category>::value &&
initialCapacity == 0;
bulkInsert(first, last, autoReserve);
}
public:
/// Add a range of elements.
template <class InputIt>
void insert(InputIt first, InputIt last) {
// Bulk reserve is a heuristic choice, so it can backfire. We restrict
// ourself to situations that mimic bulk construction without an
// explicit initialCapacity.
bool autoReserve =
std::is_base_of<
std::random_access_iterator_tag,
typename std::iterator_traits<InputIt>::iterator_category>::value &&
bucket_count() == 0;
bulkInsert(first, last, autoReserve);
}
/// Add elements from an initializer list.
void insert(std::initializer_list<value_type> ilist) {
insert(ilist.begin(), ilist.end());
}
private:
template <typename Arg>
using UsableAsKey = ::folly::detail::
EligibleForHeterogeneousFind<key_type, hasher, key_equal, Arg>;
public:
/**
* Add an element by constructing it in-place.
*
* @overloadbrief Add elements in-place.
* @methodset Modifiers
*/
template <class... Args>
std::pair<iterator, bool> emplace(Args&&... args) {
auto rv = folly::detail::callWithConstructedKey<key_type, UsableAsKey>(
table_.alloc(),
[&](auto&&... inner) {
return table_.tryEmplaceValue(
std::forward<decltype(inner)>(inner)...);
},
std::forward<Args>(args)...);
return std::make_pair(table_.makeIter(rv.first), rv.second);
}
// Emplace with prehash token
template <class... Args>
std::pair<iterator, bool> emplace_token(
F14HashToken const& token, Args&&... args) {
auto rv = folly::detail::callWithConstructedKey<key_type, UsableAsKey>(
table_.alloc(),
[&](auto&&... inner) {
return table_.tryEmplaceValueWithToken(
token, std::forward<decltype(inner)>(inner)...);
},
std::forward<Args>(args)...);
return std::make_pair(table_.makeIter(rv.first), rv.second);
}
/// Emplace with hint.
template <class... Args>
iterator emplace_hint(const_iterator /*hint*/, Args&&... args) {
return emplace(std::forward<Args>(args)...).first;
}
/**
* Remove element at a specific position (iterator).
* @overloadbrief Remove elements.
* @methodset Modifiers
*/
FOLLY_ALWAYS_INLINE iterator erase(const_iterator pos) {
return eraseInto(pos, variadic_noop);
}
/// Remove a range of elements.
iterator erase(const_iterator first, const_iterator last) {
return eraseInto(first, last, variadic_noop);
}
/// Remove a specific key.
size_type erase(key_type const& key) { return eraseInto(key, variadic_noop); }
/// Remove a key, using a heterogeneous representation.
template <typename K>
EnableHeterogeneousErase<K, size_type> erase(K const& key) {
return eraseInto(key, variadic_noop);
}
/**
* Callback-erase a single iterator.
*
* Like erase, but with an additional callback argument which is called with
* an rvalue reference to the item directly before it is destroyed. This can
* be used to extract an item out of a F14Set while avoiding a copy.
*
* @overloadbrief Erase with pre-destruction callback.
* @methodset Modifiers
*/
template <typename BeforeDestroy>
FOLLY_ALWAYS_INLINE iterator
eraseInto(const_iterator pos, BeforeDestroy&& beforeDestroy) {
auto itemPos = table_.unwrapIter(pos);
table_.eraseIterInto(itemPos, beforeDestroy);
// If we are inlined then gcc and clang can optimize away all of the
// work of ++pos if the caller discards it.
itemPos.advanceLikelyDead();
return table_.makeIter(itemPos);
}
/// Callback-erase a range of values.
template <typename BeforeDestroy>
iterator eraseInto(
const_iterator first,
const_iterator last,
BeforeDestroy&& beforeDestroy) {
while (first != last) {
first = eraseInto(first, beforeDestroy);
}
return first;
}
/// Callback-erase a specific key.
template <typename BeforeDestroy>
size_type eraseInto(key_type const& key, BeforeDestroy&& beforeDestroy) {
return table_.eraseKeyInto(key, beforeDestroy);
}
/// Callback-erase a specific key, using a heterogeneous representation.
template <typename K, typename BeforeDestroy>
EnableHeterogeneousErase<K, size_type> eraseInto(
K const& key, BeforeDestroy&& beforeDestroy) {
return table_.eraseKeyInto(key, beforeDestroy);
}
//// PUBLIC - Lookup
/**
* Number of elements matching the given key.
* @methodset Lookup
*/
FOLLY_ALWAYS_INLINE size_type count(key_type const& key) const {
return contains(key) ? 1 : 0;
}
template <typename K>
FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, size_type> count(
K const& key) const {
return contains(key) ? 1 : 0;
}
/**
* @overloadbrief Prehash a key.
* @methodset Lookup
*
* prehash(key) does the work of evaluating hash_function()(key)
* (including additional bit-mixing for non-avalanching hash functions),
* and wraps the result of that work in a token for later reuse.
*
* The returned token may be used at any time, may be used more than
* once, and may be used in other F14 sets and maps. Tokens are
* transferrable between any F14 containers (maps and sets) with the
* same key_type and equal hash_function()s.
*
* Hash tokens are not hints -- it is a bug to call any method on this
* class with a token t and key k where t isn't the result of a call
* to prehash(k2) with k2 == k.
*/
F14HashToken prehash(key_type const& key) const {
return table_.prehash(key);
}
/// @copydoc prehash
F14HashToken prehash(key_type const& key, std::size_t hash) const {
return table_.prehash(key, hash);
}
/// @copydoc prehash
template <typename K>
EnableHeterogeneousFind<K, F14HashToken> prehash(K const& key) const {
return table_.prehash(key);
}
/// @copydoc prehash
template <typename K>
EnableHeterogeneousFind<K, F14HashToken> prehash(
K const& key, std::size_t hash) const {
return table_.prehash(key, hash);
}
/**
* @overloadbrief Prefetch cachelines associated with a key.
* @methodset Lookup
*
* prefetch(token) begins prefetching the first steps of looking for key into
* the local CPU cache.
*
* Example Scenario: Loading 2 values from a cold map.
* You have a map that is cold, meaning it is out of the local CPU cache,
* and you want to load two values from the map. This can be extended to
* load N values, but we're loading 2 for simplicity.
*
* When the map is cold the dominating factor in the latency is loading the
* cache line of the entry into the local CPU cache. Using prehash() will
* issue these cache line fetches in parallel. That means that by the time we
* finish map.find(token1, key1) the cache lines needed by map.find(token2,
* key2) may already be in the local CPU cache. In the best case this will
* half the latency.
*
* It is always okay to call prefetch() before a find() or other lookup
* operation, as it only prefetches cache lines that are guaranteed to be
* needed by the lookup.
*
* std::pair<iterator, iterator> find2(
* auto& set, key_type const& key1, key_type const& key2) {
* auto const token1 = set.prehash(key1);
* set.prefetch(token1);
* auto const token2 = set.prehash(key2);
* set.prefetch(token2);
* return std::make_pair(set.find(token1, key1), set.find(token2, key2));
* }
*/
void prefetch(F14HashToken const& token) const { table_.prefetch(token); }
/**
* @overloadbrief Get the iterator for a key.
* @methodset Lookup
*/
FOLLY_ALWAYS_INLINE iterator find(key_type const& key) {
return const_cast<F14BasicSet const*>(this)->find(key);
}
FOLLY_ALWAYS_INLINE const_iterator find(key_type const& key) const {
return table_.makeIter(table_.find(key));
}
FOLLY_ALWAYS_INLINE iterator
find(F14HashToken const& token, key_type const& key) {
return const_cast<F14BasicSet const*>(this)->find(token, key);
}
FOLLY_ALWAYS_INLINE const_iterator
find(F14HashToken const& token, key_type const& key) const {
return table_.makeIter(table_.find(token, key));
}
template <typename K>
FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, iterator> find(K const& key) {
return const_cast<F14BasicSet const*>(this)->find(key);
}
template <typename K>
FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, const_iterator> find(
K const& key) const {
return table_.makeIter(table_.find(key));
}
template <typename K>
FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, iterator> find(
F14HashToken const& token, K const& key) {
return const_cast<F14BasicSet const*>(this)->find(token, key);
}
template <typename K>
FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, const_iterator> find(
F14HashToken const& token, K const& key) const {
return table_.makeIter(table_.find(token, key));
}
/**
* @overloadbrief Checks if the container contains an element with the
* specific key.
* @methodset Lookup
*/
FOLLY_ALWAYS_INLINE bool contains(key_type const& key) const {
return !table_.find(key).atEnd();
}
template <typename K>
FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, bool> contains(
K const& key) const {
return !table_.find(key).atEnd();
}
FOLLY_ALWAYS_INLINE bool contains(
F14HashToken const& token, key_type const& key) const {
return !table_.find(token, key).atEnd();
}
template <typename K>
FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, bool> contains(
F14HashToken const& token, K const& key) const {
return !table_.find(token, key).atEnd();
}
/**
* @overloadbrief Returns the range of elements matching a specific key.
* @methodset Lookup
*/
std::pair<iterator, iterator> equal_range(key_type const& key) {
return equal_range(*this, key);
}
std::pair<const_iterator, const_iterator> equal_range(
key_type const& key) const {
return equal_range(*this, key);
}
template <typename K>
EnableHeterogeneousFind<K, std::pair<iterator, iterator>> equal_range(
K const& key) {
return equal_range(*this, key);
}
template <typename K>
EnableHeterogeneousFind<K, std::pair<const_iterator, const_iterator>>
equal_range(K const& key) const {
return equal_range(*this, key);
}
//// PUBLIC - Bucket interface
/**
* The number of buckets in this container.
* @methodset Bucket interface
*/
std::size_t bucket_count() const noexcept { return table_.bucket_count(); }
/**
* The maximum number of buckets for this container.
* @methodset Bucket interface
*/
std::size_t max_bucket_count() const noexcept {
return table_.max_bucket_count();
}
//// PUBLIC - Hash policy
/**
* Load factor of the underlying hashtable.
* @methodset Hash policy
*/
float load_factor() const noexcept { return table_.load_factor(); }
/**
* @overloadbrief Load factor control.
* Get the maximum load factor for this container.
* @methodset Hash policy
*/
float max_load_factor() const noexcept { return table_.max_load_factor(); }
/**
* Set the maximum load factor for this container.
* @methodset Hash policy
*/
void max_load_factor(float v) { table_.max_load_factor(v); }
/**
* Rehash this container.
*
* This function is provided for compliance with C++'s requirements for
* hashtables, but is no better than a simple `reserve` call for F14.
*
* @param bucketCapacity The desired capacity across all buckets.
*
* @methodset Hash policy
*/
void rehash(std::size_t bucketCapacity) {
// The standard's rehash() requires understanding the max load factor,
// which is easy to get wrong. Since we don't actually allow adjustment
// of max_load_factor there is no difference.
reserve(bucketCapacity);
}
/**
* Pre-allocate space for at least this many elements.
*
* @param capacity The number of elements to pre-allocate space for.
*
* @methodset Capacity
*/
void reserve(std::size_t capacity) { table_.reserve(capacity); }
//// PUBLIC - Observers
/**
* Get the hasher.
* @methodset Observers
*/
hasher hash_function() const { return table_.hasher(); }
/**
* Get the key_equal.
* @methodset Observers
*/
key_equal key_eq() const { return table_.keyEqual(); }
//// PUBLIC - F14 Extensions
/**
* Checks for a value using operator==
*
* returns true iff there is an element in the set
* that compares equal to key using operator==. It is undefined
* behavior to call this function if operator== on key_type can ever
* return true when the same keys passed to key_eq() would return false
* (the opposite is allowed). When using the default key_eq this function
* is equivalent to contains().
*
* @methodset Lookup
*/
bool containsEqualValue(value_type const& value) const {
return !table_.findMatching(value, [&](auto& k) { return value == k; })
.atEnd();
}
/**
* Get memory footprint, not including sizeof(*this).
* @methodset Capacity
*/
std::size_t getAllocatedMemorySize() const {
return table_.getAllocatedMemorySize();
}
/**
* In-depth memory analysis.
*
* Enumerates classes of allocated memory blocks currently owned
* by this table, calling visitor(allocationSize, allocationCount).
* This can be used to get a more accurate indication of memory footprint
* than getAllocatedMemorySize() if you have some way of computing the
* internal fragmentation of the allocator, such as JEMalloc's nallocx.
* The visitor might be called twice with the same allocationSize. The
* visitor's computation should produce the same result for visitor(8,
* 2) as for two calls to visitor(8, 1), for example. The visitor may
* be called with a zero allocationCount.
*
* @methodset Capacity
*/
template <typename V>
void visitAllocationClasses(V&& visitor) const {
return table_.visitAllocationClasses(visitor);
}
/**
* Visit contiguous ranges of elements.
*
* Calls visitor with two value_type const*, b and e, such that every
* entry in the table is included in exactly one of the ranges [b,e).
* This can be used to efficiently iterate elements in bulk when crossing
* an API boundary that supports contiguous blocks of items.
*
* @methodset Iterators
*/
template <typename V>
void visitContiguousRanges(V&& visitor) const;
/**
* Get stats.
* @methodset Hash policy
*/
F14TableStats computeStats() const noexcept { return table_.computeStats(); }
private:
template <typename Self, typename K>
static auto equal_range(Self& self, K const& key) {
auto first = self.find(key);
auto last = first;
if (last != self.end()) {
++last;
}
return std::make_pair(first, last);
}
protected:
F14Table<Policy> table_;
};
} // namespace detail
} // namespace f14
template <typename Key, typename Hasher, typename KeyEqual, typename Alloc>
class F14ValueSet
: public f14::detail::F14BasicSet<f14::detail::SetPolicyWithDefaults<
f14::detail::ValueContainerPolicy,
Key,
Hasher,
KeyEqual,
Alloc>> {
protected:
friend struct F14ValueSetTester;
using Policy = f14::detail::SetPolicyWithDefaults<
f14::detail::ValueContainerPolicy,
Key,
Hasher,
KeyEqual,
Alloc>;
private:
using Super = f14::detail::F14BasicSet<Policy>;
public:
using typename Super::value_type;
F14ValueSet() = default;
using Super::Super;
F14ValueSet& operator=(std::initializer_list<value_type> ilist) {
Super::operator=(ilist);
return *this;
}
void swap(F14ValueSet& rhs) noexcept(Policy::kSwapIsNoexcept) {
this->table_.swap(rhs.table_);
}
template <typename V>
void visitContiguousRanges(V&& visitor) const {
this->table_.visitContiguousItemRanges(std::forward<V>(visitor));
}
};
#endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
template <
typename InputIt,
typename Hasher = f14::DefaultHasher<iterator_value_type_t<InputIt>>,
typename KeyEqual = f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>,
typename Alloc = f14::DefaultAlloc<iterator_value_type_t<InputIt>>,
typename = detail::RequireInputIterator<InputIt>,
typename = detail::RequireNotAllocator<Hasher>,
typename = detail::RequireNotAllocator<KeyEqual>,
typename = detail::RequireAllocator<Alloc>>
F14ValueSet(
InputIt, InputIt, std::size_t = {}, Hasher = {}, KeyEqual = {}, Alloc = {})
-> F14ValueSet<iterator_value_type_t<InputIt>, Hasher, KeyEqual, Alloc>;
template <
typename InputIt,
typename Alloc,
typename = detail::RequireInputIterator<InputIt>,
typename = detail::RequireAllocator<Alloc>>
F14ValueSet(InputIt, InputIt, std::size_t, Alloc) -> F14ValueSet<
iterator_value_type_t<InputIt>,
f14::DefaultHasher<iterator_value_type_t<InputIt>>,
f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>,
Alloc>;
template <
typename InputIt,
typename Hasher,
typename Alloc,
typename = detail::RequireInputIterator<InputIt>,
typename = detail::RequireNotAllocator<Hasher>,
typename = detail::RequireAllocator<Alloc>>
F14ValueSet(InputIt, InputIt, std::size_t, Hasher, Alloc) -> F14ValueSet<
iterator_value_type_t<InputIt>,
Hasher,
f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>,
Alloc>;
template <
typename Key,
typename Hasher = f14::DefaultHasher<Key>,
typename KeyEqual = f14::DefaultKeyEqual<Key>,
typename Alloc = f14::DefaultAlloc<Key>,
typename = detail::RequireNotAllocator<Hasher>,
typename = detail::RequireNotAllocator<KeyEqual>,
typename = detail::RequireAllocator<Alloc>>
F14ValueSet(
std::initializer_list<Key>,
std::size_t = {},
Hasher = {},
KeyEqual = {},
Alloc = {}) -> F14ValueSet<Key, Hasher, KeyEqual, Alloc>;
template <
typename Key,
typename Alloc,
typename = detail::RequireAllocator<Alloc>>
F14ValueSet(std::initializer_list<Key>, std::size_t, Alloc) -> F14ValueSet<
Key,
f14::DefaultHasher<Key>,
f14::DefaultKeyEqual<Key>,
Alloc>;
template <
typename Key,
typename Hasher,
typename Alloc,
typename = detail::RequireAllocator<Alloc>>
F14ValueSet(std::initializer_list<Key>, std::size_t, Hasher, Alloc)
-> F14ValueSet<Key, Hasher, f14::DefaultKeyEqual<Key>, Alloc>;
#if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
template <typename Key, typename Hasher, typename KeyEqual, typename Alloc>
class F14NodeSet
: public f14::detail::F14BasicSet<f14::detail::SetPolicyWithDefaults<
f14::detail::NodeContainerPolicy,
Key,
Hasher,
KeyEqual,
Alloc>> {
protected:
using Policy = f14::detail::SetPolicyWithDefaults<
f14::detail::NodeContainerPolicy,
Key,
Hasher,
KeyEqual,
Alloc>;
private:
using Super = f14::detail::F14BasicSet<Policy>;
public:
using typename Super::value_type;
F14NodeSet() = default;
using Super::Super;
F14NodeSet& operator=(std::initializer_list<value_type> ilist) {
Super::operator=(ilist);
return *this;
}
void swap(F14NodeSet& rhs) noexcept(Policy::kSwapIsNoexcept) {
this->table_.swap(rhs.table_);
}
template <typename V>
void visitContiguousRanges(V&& visitor) const {
this->table_.visitItems([&](typename Policy::Item ptr) {
value_type const* b = std::addressof(*ptr);
visitor(b, b + 1);
});
}
};
#endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
template <
typename InputIt,
typename Hasher = f14::DefaultHasher<iterator_value_type_t<InputIt>>,
typename KeyEqual = f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>,
typename Alloc = f14::DefaultAlloc<iterator_value_type_t<InputIt>>,
typename = detail::RequireInputIterator<InputIt>,
typename = detail::RequireNotAllocator<Hasher>,
typename = detail::RequireNotAllocator<KeyEqual>,
typename = detail::RequireAllocator<Alloc>>
F14NodeSet(
InputIt, InputIt, std::size_t = {}, Hasher = {}, KeyEqual = {}, Alloc = {})
-> F14NodeSet<iterator_value_type_t<InputIt>, Hasher, KeyEqual, Alloc>;
template <
typename InputIt,
typename Alloc,
typename = detail::RequireInputIterator<InputIt>,
typename = detail::RequireAllocator<Alloc>>
F14NodeSet(InputIt, InputIt, std::size_t, Alloc) -> F14NodeSet<
iterator_value_type_t<InputIt>,
f14::DefaultHasher<iterator_value_type_t<InputIt>>,
f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>,
Alloc>;
template <
typename InputIt,
typename Hasher,
typename Alloc,
typename = detail::RequireInputIterator<InputIt>,
typename = detail::RequireNotAllocator<Hasher>,
typename = detail::RequireAllocator<Alloc>>
F14NodeSet(InputIt, InputIt, std::size_t, Hasher, Alloc) -> F14NodeSet<
iterator_value_type_t<InputIt>,
Hasher,
f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>,
Alloc>;
template <
typename Key,
typename Hasher = f14::DefaultHasher<Key>,
typename KeyEqual = f14::DefaultKeyEqual<Key>,
typename Alloc = f14::DefaultAlloc<Key>,
typename = detail::RequireNotAllocator<Hasher>,
typename = detail::RequireNotAllocator<KeyEqual>,
typename = detail::RequireAllocator<Alloc>>
F14NodeSet(
std::initializer_list<Key>,
std::size_t = {},
Hasher = {},
KeyEqual = {},
Alloc = {}) -> F14NodeSet<Key, Hasher, KeyEqual, Alloc>;
template <
typename Key,
typename Alloc,
typename = detail::RequireAllocator<Alloc>>
F14NodeSet(std::initializer_list<Key>, std::size_t, Alloc) -> F14NodeSet<
Key,
f14::DefaultHasher<Key>,
f14::DefaultKeyEqual<Key>,
Alloc>;
template <
typename Key,
typename Hasher,
typename Alloc,
typename = detail::RequireAllocator<Alloc>>
F14NodeSet(std::initializer_list<Key>, std::size_t, Hasher, Alloc)
-> F14NodeSet<Key, Hasher, f14::DefaultKeyEqual<Key>, Alloc>;
#if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
namespace f14 {
namespace detail {
template <
typename Key,
typename Hasher,
typename KeyEqual,
typename Alloc,
typename EligibleForPerturbedInsertionOrder>
class F14VectorSetImpl
: public F14BasicSet<SetPolicyWithDefaults<
VectorContainerPolicy,
Key,
Hasher,
KeyEqual,
Alloc,
EligibleForPerturbedInsertionOrder>> {
protected:
using Policy = SetPolicyWithDefaults<
VectorContainerPolicy,
Key,
Hasher,
KeyEqual,
Alloc,
EligibleForPerturbedInsertionOrder>;
private:
using Super = F14BasicSet<Policy>;
template <typename K>
using IsIter = Disjunction<
std::is_same<typename Policy::Iter, remove_cvref_t<K>>,
std::is_same<typename Policy::ReverseIter, remove_cvref_t<K>>>;
template <typename K, typename T>
using EnableHeterogeneousVectorErase = std::enable_if_t<
::folly::detail::EligibleForHeterogeneousFind<
typename Policy::Value,
typename Policy::Hasher,
typename Policy::KeyEqual,
std::conditional_t<IsIter<K>::value, typename Policy::Value, K>>::
value &&
!IsIter<K>::value,
T>;
public:
using typename Super::const_iterator;
using typename Super::iterator;
using typename Super::key_type;
using typename Super::value_type;
F14VectorSetImpl() = default;
using Super::Super;
F14VectorSetImpl& operator=(std::initializer_list<value_type> ilist) {
Super::operator=(ilist);
return *this;
}
iterator begin() { return cbegin(); }
const_iterator begin() const { return cbegin(); }
const_iterator cbegin() const {
return this->table_.linearBegin(this->size());
}
iterator end() { return cend(); }
const_iterator end() const { return cend(); }
const_iterator cend() const { return this->table_.linearEnd(); }
private:
template <typename BeforeDestroy>
void eraseUnderlying(
typename Policy::ItemIter underlying, BeforeDestroy&& beforeDestroy) {
Alloc& a = this->table_.alloc();
auto values = this->table_.values_;
// destroy the value and remove the ptr from the base table
auto index = underlying.item();
this->table_.eraseIterInto(underlying, beforeDestroy);
Policy::AllocTraits::destroy(a, std::addressof(values[index]));
// move the last element in values_ down and fix up the inbound index
auto tailIndex = this->size();
if (tailIndex != index) {
auto tail = this->table_.find(
VectorContainerIndexSearch{static_cast<uint32_t>(tailIndex)});
tail.item() = index;
auto p = std::addressof(values[index]);
assume(p != nullptr);
this->table_.transfer(a, std::addressof(values[tailIndex]), p, 1);
}
}
template <typename K, typename BeforeDestroy>
std::size_t eraseUnderlyingKey(K const& key, BeforeDestroy&& beforeDestroy) {
auto underlying = this->table_.find(key);
if (underlying.atEnd()) {
return 0;
} else {
eraseUnderlying(underlying, beforeDestroy);
return 1;
}
}
public:
FOLLY_ALWAYS_INLINE iterator erase(const_iterator pos) {
return eraseInto(pos, variadic_noop);
}
iterator erase(const_iterator first, const_iterator last) {
return eraseInto(first, last, variadic_noop);
}
std::size_t erase(key_type const& key) {
return eraseInto(key, variadic_noop);
}
template <typename K>
EnableHeterogeneousVectorErase<K, std::size_t> erase(K const& key) {
return eraseInto(key, variadic_noop);
}
template <typename BeforeDestroy>
FOLLY_ALWAYS_INLINE iterator
eraseInto(const_iterator pos, BeforeDestroy&& beforeDestroy) {
auto underlying = this->table_.find(
VectorContainerIndexSearch{this->table_.iterToIndex(pos)});
eraseUnderlying(underlying, beforeDestroy);
return ++pos;
}
template <typename BeforeDestroy>
iterator eraseInto(
const_iterator first,
const_iterator last,
BeforeDestroy&& beforeDestroy) {
while (first != last) {
first = eraseInto(first, beforeDestroy);
}
return first;
}
template <typename BeforeDestroy>
std::size_t eraseInto(key_type const& key, BeforeDestroy&& beforeDestroy) {
return eraseUnderlyingKey(key, beforeDestroy);
}
template <typename K, typename BeforeDestroy>
EnableHeterogeneousVectorErase<K, std::size_t> eraseInto(
K const& key, BeforeDestroy&& beforeDestroy) {
return eraseUnderlyingKey(key, beforeDestroy);
}
template <typename V>
void visitContiguousRanges(V&& visitor) const {
auto n = this->table_.size();
if (n > 0) {
value_type const* b = std::addressof(this->table_.values_[0]);
visitor(b, b + n);
}
}
};
} // namespace detail
} // namespace f14
template <typename Key, typename Hasher, typename KeyEqual, typename Alloc>
class F14VectorSet
: public f14::detail::
F14VectorSetImpl<Key, Hasher, KeyEqual, Alloc, std::false_type> {
using Super = f14::detail::
F14VectorSetImpl<Key, Hasher, KeyEqual, Alloc, std::false_type>;
public:
using typename Super::const_iterator;
using typename Super::iterator;
using typename Super::value_type;
using reverse_iterator = typename Super::Policy::ReverseIter;
using const_reverse_iterator = reverse_iterator;
F14VectorSet() = default;
using Super::Super;
F14VectorSet& operator=(std::initializer_list<value_type> ilist) {
Super::operator=(ilist);
return *this;
}
void swap(F14VectorSet& rhs) noexcept(Super::Policy::kSwapIsNoexcept) {
this->table_.swap(rhs.table_);
}
// ITERATION ORDER
//
// Deterministic iteration order for insert-only workloads is part of
// F14VectorSet's supported API: iterator is LIFO and reverse_iterator
// is FIFO.
//
// If there have been no calls to erase() then iterator and
// const_iterator enumerate entries in the opposite of insertion order.
// begin()->first is the key most recently inserted. reverse_iterator
// and reverse_const_iterator, therefore, enumerate in LIFO (insertion)
// order for insert-only workloads. Deterministic iteration order is
// only guaranteed if no keys were removed since the last time the
// set was empty. Iteration order is preserved across rehashes and
// F14VectorSet copies and moves.
//
// iterator uses LIFO order so that erasing while iterating with begin()
// and end() is safe using the erase(it++) idiom, which is supported
// by std::set and std::unordered_set. erase(iter) invalidates iter
// and all iterators before iter in the non-reverse iteration order.
// Every successful erase invalidates all reverse iterators.
//
// No erase is provided for reverse_iterator (AKA const_reverse_iterator)
// to make it harder to shoot yourself in the foot by erasing while
// reverse-iterating. You can write that as set.erase(set.iter(riter))
// if you need it.
reverse_iterator rbegin() { return this->table_.values_; }
const_reverse_iterator rbegin() const { return crbegin(); }
const_reverse_iterator crbegin() const { return this->table_.values_; }
reverse_iterator rend() { return this->table_.values_ + this->table_.size(); }
const_reverse_iterator rend() const { return crend(); }
const_reverse_iterator crend() const {
return this->table_.values_ + this->table_.size();
}
// explicit conversions between iterator and reverse_iterator
iterator iter(reverse_iterator riter) { return this->table_.iter(riter); }
const_iterator iter(const_reverse_iterator riter) const {
return this->table_.iter(riter);
}
reverse_iterator riter(iterator it) { return this->table_.riter(it); }
const_reverse_iterator riter(const_iterator it) const {
return this->table_.riter(it);
}
friend Range<const_reverse_iterator> tag_invoke(
order_preserving_reinsertion_view_fn, F14VectorSet const& c) noexcept {
return {c.rbegin(), c.rend()};
}
};
#endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
template <
typename InputIt,
typename Hasher = f14::DefaultHasher<iterator_value_type_t<InputIt>>,
typename KeyEqual = f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>,
typename Alloc = f14::DefaultAlloc<iterator_value_type_t<InputIt>>,
typename = detail::RequireInputIterator<InputIt>,
typename = detail::RequireNotAllocator<Hasher>,
typename = detail::RequireNotAllocator<KeyEqual>,
typename = detail::RequireAllocator<Alloc>>
F14VectorSet(
InputIt, InputIt, std::size_t = {}, Hasher = {}, KeyEqual = {}, Alloc = {})
-> F14VectorSet<iterator_value_type_t<InputIt>, Hasher, KeyEqual, Alloc>;
template <
typename InputIt,
typename Alloc,
typename = detail::RequireInputIterator<InputIt>,
typename = detail::RequireAllocator<Alloc>>
F14VectorSet(InputIt, InputIt, std::size_t, Alloc) -> F14VectorSet<
iterator_value_type_t<InputIt>,
f14::DefaultHasher<iterator_value_type_t<InputIt>>,
f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>,
Alloc>;
template <
typename InputIt,
typename Hasher,
typename Alloc,
typename = detail::RequireInputIterator<InputIt>,
typename = detail::RequireNotAllocator<Hasher>,
typename = detail::RequireAllocator<Alloc>>
F14VectorSet(InputIt, InputIt, std::size_t, Hasher, Alloc) -> F14VectorSet<
iterator_value_type_t<InputIt>,
Hasher,
f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>,
Alloc>;
template <
typename Key,
typename Hasher = f14::DefaultHasher<Key>,
typename KeyEqual = f14::DefaultKeyEqual<Key>,
typename Alloc = f14::DefaultAlloc<Key>,
typename = detail::RequireNotAllocator<Hasher>,
typename = detail::RequireNotAllocator<KeyEqual>,
typename = detail::RequireAllocator<Alloc>>
F14VectorSet(
std::initializer_list<Key>,
std::size_t = {},
Hasher = {},
KeyEqual = {},
Alloc = {}) -> F14VectorSet<Key, Hasher, KeyEqual, Alloc>;
template <
typename Key,
typename Alloc,
typename = detail::RequireAllocator<Alloc>>
F14VectorSet(std::initializer_list<Key>, std::size_t, Alloc) -> F14VectorSet<
Key,
f14::DefaultHasher<Key>,
f14::DefaultKeyEqual<Key>,
Alloc>;
template <
typename Key,
typename Hasher,
typename Alloc,
typename = detail::RequireAllocator<Alloc>>
F14VectorSet(std::initializer_list<Key>, std::size_t, Hasher, Alloc)
-> F14VectorSet<Key, Hasher, f14::DefaultKeyEqual<Key>, Alloc>;
#if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
template <typename Key, typename Hasher, typename KeyEqual, typename Alloc>
class F14FastSet
: public std::conditional_t<
sizeof(Key) < 24,
F14ValueSet<Key, Hasher, KeyEqual, Alloc>,
f14::detail::
F14VectorSetImpl<Key, Hasher, KeyEqual, Alloc, std::true_type>> {
using Super = std::conditional_t<
sizeof(Key) < 24,
F14ValueSet<Key, Hasher, KeyEqual, Alloc>,
f14::detail::
F14VectorSetImpl<Key, Hasher, KeyEqual, Alloc, std::true_type>>;
public:
using typename Super::value_type;
F14FastSet() = default;
using Super::Super;
F14FastSet& operator=(std::initializer_list<value_type> ilist) {
Super::operator=(ilist);
return *this;
}
void swap(F14FastSet& rhs) noexcept(Super::Policy::kSwapIsNoexcept) {
this->table_.swap(rhs.table_);
}
};
#endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
template <
typename InputIt,
typename Hasher = f14::DefaultHasher<iterator_value_type_t<InputIt>>,
typename KeyEqual = f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>,
typename Alloc = f14::DefaultAlloc<iterator_value_type_t<InputIt>>,
typename = detail::RequireInputIterator<InputIt>,
typename = detail::RequireNotAllocator<Hasher>,
typename = detail::RequireNotAllocator<KeyEqual>,
typename = detail::RequireAllocator<Alloc>>
F14FastSet(
InputIt, InputIt, std::size_t = {}, Hasher = {}, KeyEqual = {}, Alloc = {})
-> F14FastSet<iterator_value_type_t<InputIt>, Hasher, KeyEqual, Alloc>;
template <
typename InputIt,
typename Alloc,
typename = detail::RequireInputIterator<InputIt>,
typename = detail::RequireAllocator<Alloc>>
F14FastSet(InputIt, InputIt, std::size_t, Alloc) -> F14FastSet<
iterator_value_type_t<InputIt>,
f14::DefaultHasher<iterator_value_type_t<InputIt>>,
f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>,
Alloc>;
template <
typename InputIt,
typename Hasher,
typename Alloc,
typename = detail::RequireInputIterator<InputIt>,
typename = detail::RequireNotAllocator<Hasher>,
typename = detail::RequireAllocator<Alloc>>
F14FastSet(InputIt, InputIt, std::size_t, Hasher, Alloc) -> F14FastSet<
iterator_value_type_t<InputIt>,
Hasher,
f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>,
Alloc>;
template <
typename Key,
typename Hasher = f14::DefaultHasher<Key>,
typename KeyEqual = f14::DefaultKeyEqual<Key>,
typename Alloc = f14::DefaultAlloc<Key>,
typename = detail::RequireNotAllocator<Hasher>,
typename = detail::RequireNotAllocator<KeyEqual>,
typename = detail::RequireAllocator<Alloc>>
F14FastSet(
std::initializer_list<Key>,
std::size_t = {},
Hasher = {},
KeyEqual = {},
Alloc = {}) -> F14FastSet<Key, Hasher, KeyEqual, Alloc>;
template <
typename Key,
typename Alloc,
typename = detail::RequireAllocator<Alloc>>
F14FastSet(std::initializer_list<Key>, std::size_t, Alloc) -> F14FastSet<
Key,
f14::DefaultHasher<Key>,
f14::DefaultKeyEqual<Key>,
Alloc>;
template <
typename Key,
typename Hasher,
typename Alloc,
typename = detail::RequireAllocator<Alloc>>
F14FastSet(std::initializer_list<Key>, std::size_t, Hasher, Alloc)
-> F14FastSet<Key, Hasher, f14::DefaultKeyEqual<Key>, Alloc>;
} // namespace folly
namespace folly {
namespace f14 {
namespace detail {
template <typename S>
bool setsEqual(S const& lhs, S const& rhs) {
if (lhs.size() != rhs.size()) {
return false;
}
for (auto& k : lhs) {
if (!rhs.containsEqualValue(k)) {
return false;
}
}
return true;
}
} // namespace detail
} // namespace f14
template <typename K, typename H, typename E, typename A>
bool operator==(
F14ValueSet<K, H, E, A> const& lhs, F14ValueSet<K, H, E, A> const& rhs) {
return setsEqual(lhs, rhs);
}
template <typename K, typename H, typename E, typename A>
bool operator!=(
F14ValueSet<K, H, E, A> const& lhs, F14ValueSet<K, H, E, A> const& rhs) {
return !(lhs == rhs);
}
template <typename K, typename H, typename E, typename A>
bool operator==(
F14NodeSet<K, H, E, A> const& lhs, F14NodeSet<K, H, E, A> const& rhs) {
return setsEqual(lhs, rhs);
}
template <typename K, typename H, typename E, typename A>
bool operator!=(
F14NodeSet<K, H, E, A> const& lhs, F14NodeSet<K, H, E, A> const& rhs) {
return !(lhs == rhs);
}
template <typename K, typename H, typename E, typename A>
bool operator==(
F14VectorSet<K, H, E, A> const& lhs, F14VectorSet<K, H, E, A> const& rhs) {
return setsEqual(lhs, rhs);
}
template <typename K, typename H, typename E, typename A>
bool operator!=(
F14VectorSet<K, H, E, A> const& lhs, F14VectorSet<K, H, E, A> const& rhs) {
return !(lhs == rhs);
}
template <typename K, typename H, typename E, typename A>
bool operator==(
F14FastSet<K, H, E, A> const& lhs, F14FastSet<K, H, E, A> const& rhs) {
return setsEqual(lhs, rhs);
}
template <typename K, typename H, typename E, typename A>
bool operator!=(
F14FastSet<K, H, E, A> const& lhs, F14FastSet<K, H, E, A> const& rhs) {
return !(lhs == rhs);
}
template <typename K, typename H, typename E, typename A>
void swap(F14ValueSet<K, H, E, A>& lhs, F14ValueSet<K, H, E, A>& rhs) noexcept(
noexcept(lhs.swap(rhs))) {
lhs.swap(rhs);
}
template <typename K, typename H, typename E, typename A>
void swap(F14NodeSet<K, H, E, A>& lhs, F14NodeSet<K, H, E, A>& rhs) noexcept(
noexcept(lhs.swap(rhs))) {
lhs.swap(rhs);
}
template <typename K, typename H, typename E, typename A>
void swap(
F14VectorSet<K, H, E, A>& lhs,
F14VectorSet<K, H, E, A>& rhs) noexcept(noexcept(lhs.swap(rhs))) {
lhs.swap(rhs);
}
template <typename K, typename H, typename E, typename A>
void swap(F14FastSet<K, H, E, A>& lhs, F14FastSet<K, H, E, A>& rhs) noexcept(
noexcept(lhs.swap(rhs))) {
lhs.swap(rhs);
}
template <typename K, typename H, typename E, typename A, typename Pred>
std::size_t erase_if(F14ValueSet<K, H, E, A>& c, Pred pred) {
return f14::detail::erase_if_impl(c, pred);
}
template <typename K, typename H, typename E, typename A, typename Pred>
std::size_t erase_if(F14NodeSet<K, H, E, A>& c, Pred pred) {
return f14::detail::erase_if_impl(c, pred);
}
template <typename K, typename H, typename E, typename A, typename Pred>
std::size_t erase_if(F14VectorSet<K, H, E, A>& c, Pred pred) {
return f14::detail::erase_if_impl(c, pred);
}
template <typename K, typename H, typename E, typename A, typename Pred>
std::size_t erase_if(F14FastSet<K, H, E, A>& c, Pred pred) {
return f14::detail::erase_if_impl(c, pred);
}
} // namespace folly