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>
24 #include <folly/Range.h>
25 #include <folly/experimental/StringKeyedCommon.h>
30 * Wrapper class for set<string> that can
31 * perform lookup operations with StringPiece, not only string.
33 * It uses kind of hack: string pointed by StringPiece is copied when
34 * StringPiece is inserted into set
36 template <class Compare = std::less<StringPiece>,
37 class Alloc = std::allocator<StringPiece>>
38 class StringKeyedSetBase
39 : private std::set<StringPiece, Compare, Alloc> {
41 using Base = std::set<StringPiece, Compare, Alloc>;
44 typedef typename Base::key_type key_type;
45 typedef typename Base::value_type value_type;
46 typedef typename Base::key_compare key_compare;
47 typedef typename Base::allocator_type allocator_type;
48 typedef typename Base::reference reference;
49 typedef typename Base::const_reference const_reference;
50 typedef typename Base::pointer pointer;
51 typedef typename Base::const_pointer const_pointer;
52 typedef typename Base::iterator iterator;
53 typedef typename Base::const_iterator const_iterator;
54 typedef typename Base::reverse_iterator reverse_iterator;
55 typedef typename Base::const_reverse_iterator const_reverse_iterator;
56 typedef typename Base::size_type size_type;
57 typedef typename Base::difference_type difference_type;
59 explicit StringKeyedSetBase(
60 const key_compare& comp = key_compare(),
61 const allocator_type& alloc = allocator_type())
65 explicit StringKeyedSetBase(const allocator_type& alloc)
69 template <class InputIterator>
71 InputIterator b, InputIterator e,
72 const key_compare& comp = key_compare(),
73 const allocator_type& alloc = allocator_type())
80 StringKeyedSetBase(const StringKeyedSetBase& rhs)
81 : StringKeyedSetBase(rhs, rhs.get_allocator()) {
84 StringKeyedSetBase(const StringKeyedSetBase& rhs,
85 const allocator_type& a)
86 : StringKeyedSetBase(rhs.begin(), rhs.end(), rhs.key_comp(), a) {
89 StringKeyedSetBase(StringKeyedSetBase&& other) noexcept
90 : Base(std::move(other)) {
91 assert(other.empty());
94 StringKeyedSetBase(StringKeyedSetBase&& other,
95 const allocator_type& alloc) noexcept
96 : Base(std::move(other), alloc) {
97 assert(other.empty());
101 std::initializer_list<value_type> il,
102 const key_compare& comp = key_compare(),
103 const allocator_type& alloc = allocator_type())
104 : StringKeyedSetBase(il.begin(), il.end(), comp, alloc) {
107 StringKeyedSetBase& operator=(const StringKeyedSetBase& other) {
108 if (this == &other) {
111 return *this = StringKeyedSetBase(other);
114 StringKeyedSetBase& operator=(StringKeyedSetBase&& other) noexcept {
115 assert(this != &other);
117 Base::operator=(std::move(other));
118 assert(other.empty());
124 using Base::max_size;
130 using Base::lower_bound;
131 using Base::upper_bound;
133 template <class... Args>
134 std::pair<iterator, bool> emplace(Args&&... args) {
135 auto key = StringPiece(std::forward<Args>(args)...);
140 return Base::emplace(stringPieceDup(key, get_allocator()));
143 std::pair<iterator, bool> insert(value_type val) {
148 return Base::insert(stringPieceDup(val, get_allocator()));
151 iterator erase(const_iterator position) {
152 auto key = *position;
153 auto result = Base::erase(position);
154 stringPieceDel(key, get_allocator());
158 size_type erase(StringPiece key) {
167 void clear() noexcept {
168 for (auto it : *this) {
169 stringPieceDel(it, get_allocator());
174 using Base::get_allocator;
176 ~StringKeyedSetBase() {
177 // Here we assume that set doesn't use keys in destructor
178 for (auto it : *this) {
179 stringPieceDel(it, get_allocator());
184 using StringKeyedSet = StringKeyedSetBase<>;