2 * Copyright 2016 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_STRINGKEYEDMAP_H_
20 #define FOLLY_EXPERIMENTAL_STRINGKEYEDMAP_H_
22 #include <initializer_list>
25 #include <folly/Range.h>
26 #include <folly/experimental/StringKeyedCommon.h>
31 * Wrapper class for map<string, Value> 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 map
37 template <class Value,
38 class Compare = std::less<StringPiece>,
39 class Alloc = std::allocator<std::pair<const StringPiece, Value>>>
41 : private std::map<StringPiece, Value, Compare, Alloc> {
43 using Base = std::map<StringPiece, Value, Compare, Alloc>;
46 typedef typename Base::key_type key_type;
47 typedef typename Base::mapped_type mapped_type;
48 typedef typename Base::value_type value_type;
49 typedef typename Base::key_compare key_compare;
50 typedef typename Base::allocator_type allocator_type;
51 typedef typename Base::reference reference;
52 typedef typename Base::const_reference const_reference;
53 typedef typename Base::pointer pointer;
54 typedef typename Base::const_pointer const_pointer;
55 typedef typename Base::iterator iterator;
56 typedef typename Base::const_iterator const_iterator;
57 typedef typename Base::reverse_iterator reverse_iterator;
58 typedef typename Base::const_reverse_iterator const_reverse_iterator;
59 typedef typename Base::difference_type difference_type;
60 typedef typename Base::size_type size_type;
62 using Base::get_allocator;
64 // Ctors in the same order as
65 // http://cplusplus.com/reference/map/map/map/
66 explicit StringKeyedMap(
67 const key_compare& comp = key_compare(),
68 const allocator_type& alloc = allocator_type())
72 explicit StringKeyedMap(const allocator_type& alloc)
76 template <class InputIterator>
77 explicit StringKeyedMap(
78 InputIterator b, InputIterator e,
79 const key_compare& comp = key_compare(),
80 const allocator_type& alloc = allocator_type())
83 // emplace() will carry the duplication
84 emplace(b->first, b->second);
88 StringKeyedMap(const StringKeyedMap& rhs)
89 : StringKeyedMap(rhs, rhs.get_allocator()) {
92 StringKeyedMap(const StringKeyedMap& rhs, const allocator_type& a)
93 : StringKeyedMap(rhs.begin(), rhs.end(), rhs.key_comp(), a) {
96 StringKeyedMap(StringKeyedMap&& other) noexcept
97 : Base(std::move(other)) {
100 StringKeyedMap(StringKeyedMap&& other, const allocator_type& /* a */) noexcept
101 : Base(std::move(other) /*, a*/ /* not supported by gcc */) {}
103 StringKeyedMap(std::initializer_list<value_type> il,
104 const key_compare& comp = key_compare(),
105 const allocator_type& alloc = allocator_type())
106 : StringKeyedMap(il.begin(), il.end(), comp, alloc) {
109 StringKeyedMap& operator=(const StringKeyedMap& other) & {
110 if (this == &other) {
113 return *this = StringKeyedMap(other);
116 StringKeyedMap& operator=(StringKeyedMap&& other) & noexcept {
117 assert(this != &other);
119 Base::operator=(std::move(other));
125 using Base::max_size;
135 // no need for copy/move overload as StringPiece is small struct
136 mapped_type& operator[](StringPiece key) {
141 // operator[] will create new (key, value) pair
142 // we need to allocate memory for key
143 return Base::operator[](stringPieceDup(key, get_allocator()));
148 using Base::lower_bound;
149 using Base::upper_bound;
151 template <class... Args>
152 std::pair<iterator, bool> emplace(StringPiece key, Args&&... args) {
157 return Base::emplace(stringPieceDup(key, get_allocator()),
158 std::forward<Args>(args)...);
161 std::pair<iterator, bool> insert(value_type val) {
162 auto it = find(val.first);
167 std::make_pair(stringPieceDup(val.first, get_allocator()),
168 std::move(val.second)));
171 iterator erase(const_iterator position) {
172 auto key = position->first;
173 auto result = Base::erase(position);
174 stringPieceDel(key, get_allocator());
178 size_type erase(StringPiece key) {
187 void clear() noexcept {
188 for (auto& it : *this) {
189 stringPieceDel(it.first, get_allocator());
195 // Here we assume that map doesn't use keys in destructor
196 for (auto& it : *this) {
197 stringPieceDel(it.first, get_allocator());
204 #endif /* FOLLY_EXPERIMENTAL_STRINGKEYEDMAP_H_ */