2 * Copyright 2017 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)
21 #include <initializer_list>
25 #include <folly/Range.h>
26 #include <folly/experimental/StringKeyedCommon.h>
31 * Wrapper class for 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
38 class Compare = std::less<StringPiece>,
39 class Alloc = std::allocator<StringPiece>>
40 class StringKeyedSetBase
41 : private std::set<StringPiece, Compare, Alloc> {
43 using Base = std::set<StringPiece, Compare, Alloc>;
46 typedef typename Base::key_type key_type;
47 typedef typename Base::value_type value_type;
48 typedef typename Base::key_compare key_compare;
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::reverse_iterator reverse_iterator;
57 typedef typename Base::const_reverse_iterator const_reverse_iterator;
58 typedef typename Base::size_type size_type;
59 typedef typename Base::difference_type difference_type;
61 explicit StringKeyedSetBase(
62 const key_compare& comp = key_compare(),
63 const allocator_type& alloc = allocator_type())
67 explicit StringKeyedSetBase(const allocator_type& alloc)
71 template <class InputIterator>
73 InputIterator b, InputIterator e,
74 const key_compare& comp = key_compare(),
75 const allocator_type& alloc = allocator_type())
82 StringKeyedSetBase(const StringKeyedSetBase& rhs)
83 : StringKeyedSetBase(rhs, rhs.get_allocator()) {
86 StringKeyedSetBase(const StringKeyedSetBase& rhs,
87 const allocator_type& a)
88 : StringKeyedSetBase(rhs.begin(), rhs.end(), rhs.key_comp(), a) {
91 StringKeyedSetBase(StringKeyedSetBase&& other) noexcept
92 : Base(std::move(other)) {
93 assert(other.empty());
96 StringKeyedSetBase(StringKeyedSetBase&& other,
97 const allocator_type& alloc) noexcept
98 : Base(std::move(other), alloc) {
99 assert(other.empty());
103 std::initializer_list<value_type> il,
104 const key_compare& comp = key_compare(),
105 const allocator_type& alloc = allocator_type())
106 : StringKeyedSetBase(il.begin(), il.end(), comp, alloc) {
109 StringKeyedSetBase& operator=(const StringKeyedSetBase& other) {
110 if (this == &other) {
113 return *this = StringKeyedSetBase(other);
116 StringKeyedSetBase& operator=(StringKeyedSetBase&& other) noexcept {
117 assert(this != &other);
119 Base::operator=(std::move(other));
120 assert(other.empty());
126 using Base::max_size;
133 using Base::lower_bound;
134 using Base::upper_bound;
136 bool operator==(StringKeyedSetBase const& other) const {
137 Base const& lhs = *this;
138 Base const& rhs = static_cast<Base const&>(other);
142 template <class... Args>
143 std::pair<iterator, bool> emplace(Args&&... args) {
144 auto key = StringPiece(std::forward<Args>(args)...);
149 return Base::emplace(stringPieceDup(key, get_allocator()));
152 std::pair<iterator, bool> insert(value_type val) {
157 return Base::insert(stringPieceDup(val, get_allocator()));
160 iterator erase(const_iterator position) {
161 auto key = *position;
162 auto result = Base::erase(position);
163 stringPieceDel(key, get_allocator());
167 size_type erase(StringPiece key) {
176 void clear() noexcept {
177 for (auto it : *this) {
178 stringPieceDel(it, get_allocator());
183 using Base::get_allocator;
185 void swap(StringKeyedSetBase& other) & {
186 return Base::swap(other);
189 ~StringKeyedSetBase() {
190 // Here we assume that set doesn't use keys in destructor
191 for (auto it : *this) {
192 stringPieceDel(it, get_allocator());
197 using StringKeyedSet = StringKeyedSetBase<>;