2 * Copyright 2015 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
16 // Copyright 2013-present Facebook. All Rights Reserved.
17 // @author: Pavlo Kushnir (pavlo)
19 #ifndef FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDSET_H_
20 #define FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDSET_H_
22 #include <initializer_list>
24 #include <unordered_set>
25 #include <folly/Range.h>
26 #include <folly/experimental/StringKeyedCommon.h>
31 * Wrapper class for unordered_set<string> that can
32 * perform lookup operations with StringPiece, not only string.
34 * It uses kind of hack: string pointed by StringPiece is copied when
35 * StringPiece is inserted into set
37 template <class Hasher = StringPieceHash,
38 class Eq = std::equal_to<StringPiece>,
39 class Alloc = std::allocator<folly::StringPiece>>
40 class BasicStringKeyedUnorderedSet
41 : private std::unordered_set<StringPiece, Hasher, Eq, Alloc> {
42 using Base = std::unordered_set<StringPiece, Hasher, Eq, Alloc>;
45 typedef typename Base::key_type key_type;
46 typedef typename Base::value_type value_type;
47 typedef typename Base::hasher hasher;
48 typedef typename Base::key_equal key_equal;
49 typedef typename Base::allocator_type allocator_type;
50 typedef typename Base::reference reference;
51 typedef typename Base::const_reference const_reference;
52 typedef typename Base::pointer pointer;
53 typedef typename Base::const_pointer const_pointer;
54 typedef typename Base::iterator iterator;
55 typedef typename Base::const_iterator const_iterator;
56 typedef typename Base::size_type size_type;
57 typedef typename Base::difference_type difference_type;
59 // Constructors in the same order as in
60 // http://cplusplus.com/reference/unordered_set/unordered_set/unordered_set/
61 explicit BasicStringKeyedUnorderedSet() {
64 explicit BasicStringKeyedUnorderedSet(
66 const hasher& hf = hasher(),
67 const key_equal& eql = key_equal(),
68 const allocator_type& alloc = allocator_type())
69 : Base(n, hf, eql, alloc) {
72 explicit BasicStringKeyedUnorderedSet(const allocator_type& alloc)
76 template <class InputIterator>
77 BasicStringKeyedUnorderedSet(InputIterator b, InputIterator e) {
83 template <class InputIterator>
84 BasicStringKeyedUnorderedSet(
85 InputIterator b, InputIterator e,
87 const hasher& hf = hasher(),
88 const key_equal& eql = key_equal(),
89 const allocator_type& alloc = allocator_type())
90 : Base(n, hf, eql, alloc) {
96 BasicStringKeyedUnorderedSet(const BasicStringKeyedUnorderedSet& rhs)
97 : BasicStringKeyedUnorderedSet(rhs, rhs.get_allocator()) {
100 BasicStringKeyedUnorderedSet(const BasicStringKeyedUnorderedSet& rhs,
101 const allocator_type& a)
102 : BasicStringKeyedUnorderedSet(rhs.begin(),
110 BasicStringKeyedUnorderedSet(BasicStringKeyedUnorderedSet&& rhs) noexcept
111 : Base(std::move(rhs)) {
115 BasicStringKeyedUnorderedSet(BasicStringKeyedUnorderedSet&& rhs,
116 const allocator_type& /* a */) noexcept
117 : Base(std::move(rhs) /* , a */ /* not supported by gcc */) {
121 BasicStringKeyedUnorderedSet(std::initializer_list<value_type> il)
122 : BasicStringKeyedUnorderedSet(il.begin(), il.end()) {
125 BasicStringKeyedUnorderedSet(
126 std::initializer_list<value_type> il,
128 const hasher& hf = hasher(),
129 const key_equal& eql = key_equal(),
130 const allocator_type& alloc = allocator_type())
131 : BasicStringKeyedUnorderedSet(il.begin(), il.end(), n, hf, eql, alloc) {
134 BasicStringKeyedUnorderedSet&
135 operator=(const BasicStringKeyedUnorderedSet& rhs) & {
139 // Cost is as bad as a full copy, so to it via copy + move
140 return *this = BasicStringKeyedUnorderedSet(rhs);
143 BasicStringKeyedUnorderedSet&
144 operator=(BasicStringKeyedUnorderedSet&& rhs) & noexcept {
145 assert(this != &rhs);
147 Base::operator=(std::move(rhs));
153 using Base::max_size;
160 bool operator==(const BasicStringKeyedUnorderedSet& rhs) const {
161 const Base& lhs = *this;
165 template <class... Args>
166 std::pair<iterator, bool> emplace(Args&&... args) {
167 auto key = StringPiece(std::forward<Args>(args)...);
170 ? std::make_pair(it, false)
171 : Base::emplace(stringPieceDup(key, get_allocator()));
174 std::pair<iterator, bool> insert(value_type val) {
177 ? std::make_pair(it, false)
178 : Base::insert(stringPieceDup(val, get_allocator()));
181 iterator erase(const_iterator position) {
182 auto key = *position;
183 auto result = Base::erase(position);
184 stringPieceDel(key, get_allocator());
188 size_type erase(folly::StringPiece key) {
197 void clear() noexcept {
198 for (auto& it : *this) {
199 stringPieceDel(it, get_allocator());
205 using Base::hash_function;
207 using Base::get_allocator;
208 using Base::bucket_count;
209 using Base::max_bucket_count;
210 using Base::bucket_size;
213 ~BasicStringKeyedUnorderedSet() {
214 // Here we assume that unordered_set doesn't use keys in destructor
215 for (auto& it : *this) {
216 stringPieceDel(it, get_allocator());
221 typedef BasicStringKeyedUnorderedSet<> StringKeyedUnorderedSet;
225 #endif /* FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDSET_H_ */