2 * InspIRCd -- Internet Relay Chat Daemon
4 * Copyright (C) 2019-2020 Sadie Powell <sadie@witchery.services>
5 * Copyright (C) 2014 Attila Molnar <attilamolnar@hush.com>
7 * This file is part of InspIRCd. InspIRCd is free software: you can
8 * redistribute it and/or modify it under the terms of the GNU General Public
9 * License as published by the Free Software Foundation, version 2.
11 * This program is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
16 * You should have received a copy of the GNU General Public License
17 * along with this program. If not, see <http://www.gnu.org/licenses/>.
31 template <typename T, typename Comp>
32 class map_pair_compare : public Comp
35 typedef typename value_type::first_type key_type;
38 bool operator()(const value_type& x, const value_type& y) const
40 return Comp::operator()(x.first, y.first);
43 bool operator()(const value_type& x, const key_type& y) const
45 return Comp::operator()(x.first, y);
48 bool operator()(const key_type& x, const value_type& y) const
50 return Comp::operator()(x, y.first);
54 template <typename Val, typename Comp>
55 class map_value_compare : public std::binary_function<Val, Val, bool>
58 // Constructor should be private
60 bool operator()(const Val& x, const Val& y) const
63 return c(x.first, y.first);
67 template <typename T, typename Comp, typename Key = T, typename ElementComp = Comp>
71 typedef std::vector<T> storage_type;
75 typedef typename storage_type::iterator iterator;
76 typedef typename storage_type::const_iterator const_iterator;
77 typedef typename storage_type::reverse_iterator reverse_iterator;
78 typedef typename storage_type::const_reverse_iterator const_reverse_iterator;
80 typedef typename storage_type::size_type size_type;
81 typedef typename storage_type::difference_type difference_type;
85 typedef Comp key_compare;
86 typedef ElementComp value_compare;
90 flat_map_base(const flat_map_base& other)
95 #if __cplusplus >= 201103L
96 flat_map_base& operator=(const flat_map_base& other) = default;
99 size_type size() const { return vect.size(); }
100 bool empty() const { return vect.empty(); }
101 size_type capacity() const { return vect.capacity(); }
102 size_type max_size() const { return vect.max_size(); }
104 void clear() { vect.clear(); }
105 void reserve(size_type n) { vect.reserve(n); }
107 iterator begin() { return vect.begin(); }
108 iterator end() { return vect.end(); }
109 reverse_iterator rbegin() { return vect.rbegin(); }
110 reverse_iterator rend() { return vect.rend(); }
112 const_iterator begin() const { return vect.begin(); }
113 const_iterator end() const { return vect.end(); }
114 const_reverse_iterator rbegin() const { return vect.rbegin(); }
115 const_reverse_iterator rend() const { return vect.rend(); }
117 key_compare key_comp() const { return Comp(); }
119 iterator erase(iterator it) { return vect.erase(it); }
120 iterator erase(iterator first, iterator last) { return vect.erase(first, last); }
121 size_type erase(const key_type& x)
123 size_type n = vect.size();
124 std::pair<iterator, iterator> itpair = equal_range(x);
125 vect.erase(itpair.first, itpair.second);
126 return n - vect.size();
129 iterator find(const key_type& x)
132 iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
133 if ((it != vect.end()) && (!c(x, *it)))
138 const_iterator find(const key_type& x) const
140 // Same as above but this time we return a const_iterator
142 const_iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
143 if ((it != vect.end()) && (!c(x, *it)))
148 std::pair<iterator, iterator> equal_range(const key_type& x)
150 return std::equal_range(vect.begin(), vect.end(), x, value_compare());
153 std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
155 return std::equal_range(vect.begin(), vect.end(), x, value_compare());
158 iterator lower_bound(const key_type& x)
160 return std::lower_bound(vect.begin(), vect.end(), x, value_compare());
163 const_iterator lower_bound(const key_type& x) const
165 return std::lower_bound(vect.begin(), vect.end(), x, value_compare());
168 iterator upper_bound(const key_type& x)
170 return std::upper_bound(vect.begin(), vect.end(), x, value_compare());
173 const_iterator upper_bound(const key_type& x) const
175 return std::upper_bound(vect.begin(), vect.end(), x, value_compare());
178 size_type count(const key_type& x) const
180 std::pair<const_iterator, const_iterator> itpair = equal_range(x);
181 return std::distance(itpair.first, itpair.second);
185 std::pair<iterator, bool> insert_single(const value_type& x)
187 bool inserted = false;
190 iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
191 if ((it == vect.end()) || (c(x, *it)))
194 it = vect.insert(it, x);
196 return std::make_pair(it, inserted);
199 iterator insert_multi(const value_type& x)
201 iterator it = std::lower_bound(vect.begin(), vect.end(), x, value_compare());
202 return vect.insert(it, x);
206 } // namespace detail
208 template <typename T, typename Comp = std::less<T>, typename ElementComp = Comp>
209 class flat_set : public detail::flat_map_base<T, Comp, T, ElementComp>
211 typedef detail::flat_map_base<T, Comp, T, ElementComp> base_t;
214 typedef typename base_t::iterator iterator;
215 typedef typename base_t::value_type value_type;
219 template <typename InputIterator>
220 flat_set(InputIterator first, InputIterator last)
222 this->insert(first, last);
225 flat_set(const flat_set& other)
230 #if __cplusplus >= 201103L
231 flat_set& operator=(const flat_set& other) = default;
234 std::pair<iterator, bool> insert(const value_type& x)
236 return this->insert_single(x);
239 template <typename InputIterator>
240 void insert(InputIterator first, InputIterator last)
242 for (; first != last; ++first)
243 this->insert_single(*first);
246 void swap(flat_set& other)
248 base_t::vect.swap(other.vect);
252 template <typename T, typename Comp = std::less<T>, typename ElementComp = Comp>
253 class flat_multiset : public detail::flat_map_base<T, Comp, T, ElementComp>
255 typedef detail::flat_map_base<T, Comp, T, ElementComp> base_t;
258 typedef typename base_t::iterator iterator;
259 typedef typename base_t::value_type value_type;
263 template <typename InputIterator>
264 flat_multiset(InputIterator first, InputIterator last)
266 this->insert(first, last);
269 flat_multiset(const flat_multiset& other)
274 #if __cplusplus >= 201103L
275 flat_multiset& operator=(const flat_multiset& other) = default;
278 iterator insert(const value_type& x)
280 return this->insert_multi(x);
283 template <typename InputIterator>
284 void insert(InputIterator first, InputIterator last)
286 for (; first != last; ++first)
287 insert_multi(*first);
290 void swap(flat_multiset& other)
292 base_t::vect.swap(other.vect);
296 template <typename T, typename U, typename Comp = std::less<T>, typename ElementComp = Comp >
297 class flat_map : public detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> >
299 typedef detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> > base_t;
302 typedef typename base_t::iterator iterator;
303 typedef typename base_t::key_type key_type;
304 typedef typename base_t::value_type value_type;
305 typedef U mapped_type;
306 typedef typename base_t::value_compare value_compare;
310 template <typename InputIterator>
311 flat_map(InputIterator first, InputIterator last)
316 flat_map(const flat_map& other)
321 #if __cplusplus >= 201103L
322 flat_map& operator=(const flat_map& other) = default;
325 std::pair<iterator, bool> insert(const value_type& x)
327 return this->insert_single(x);
330 template <typename InputIterator>
331 void insert(InputIterator first, InputIterator last)
333 for (; first != last; ++first)
334 this->insert_single(*first);
337 void swap(flat_map& other)
339 base_t::vect.swap(other.vect);
342 mapped_type& operator[](const key_type& x)
344 return insert(std::make_pair(x, mapped_type())).first->second;
347 value_compare value_comp() const
349 return value_compare();
353 template <typename T, typename U, typename Comp = std::less<T>, typename ElementComp = Comp >
354 class flat_multimap : public detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> >
356 typedef detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> > base_t;
359 typedef typename base_t::iterator iterator;
360 typedef typename base_t::value_type value_type;
361 typedef U mapped_type;
362 typedef typename base_t::value_compare value_compare;
366 template <typename InputIterator>
367 flat_multimap(InputIterator first, InputIterator last)
369 this->insert(first, last);
372 flat_multimap(const flat_multimap& other)
377 #if __cplusplus >= 201103L
378 flat_multimap& operator=(const flat_multimap& other) = default;
381 iterator insert(const value_type& x)
383 return this->insert_multi(x);
386 template <typename InputIterator>
387 void insert(InputIterator first, InputIterator last)
389 for (; first != last; ++first)
390 this->insert_multi(*first);
393 void swap(flat_multimap& other)
395 base_t::vect.swap(other.vect);
398 value_compare value_comp() const
400 return value_compare();