2 * InspIRCd -- Internet Relay Chat Daemon
4 * Copyright (C) 2019 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 size_type size() const { return vect.size(); }
96 bool empty() const { return vect.empty(); }
97 size_type capacity() const { return vect.capacity(); }
98 size_type max_size() const { return vect.max_size(); }
100 void clear() { vect.clear(); }
101 void reserve(size_type n) { vect.reserve(n); }
103 iterator begin() { return vect.begin(); }
104 iterator end() { return vect.end(); }
105 reverse_iterator rbegin() { return vect.rbegin(); }
106 reverse_iterator rend() { return vect.rend(); }
108 const_iterator begin() const { return vect.begin(); }
109 const_iterator end() const { return vect.end(); }
110 const_reverse_iterator rbegin() const { return vect.rbegin(); }
111 const_reverse_iterator rend() const { return vect.rend(); }
113 key_compare key_comp() const { return Comp(); }
115 iterator erase(iterator it) { return vect.erase(it); }
116 iterator erase(iterator first, iterator last) { return vect.erase(first, last); }
117 size_type erase(const key_type& x)
119 size_type n = vect.size();
120 std::pair<iterator, iterator> itpair = equal_range(x);
121 vect.erase(itpair.first, itpair.second);
122 return n - vect.size();
125 iterator find(const key_type& x)
128 iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
129 if ((it != vect.end()) && (!c(x, *it)))
134 const_iterator find(const key_type& x) const
136 // Same as above but this time we return a const_iterator
138 const_iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
139 if ((it != vect.end()) && (!c(x, *it)))
144 std::pair<iterator, iterator> equal_range(const key_type& x)
146 return std::equal_range(vect.begin(), vect.end(), x, value_compare());
149 std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
151 return std::equal_range(vect.begin(), vect.end(), x, value_compare());
154 iterator lower_bound(const key_type& x)
156 return std::lower_bound(vect.begin(), vect.end(), x, value_compare());
159 const_iterator lower_bound(const key_type& x) const
161 return std::lower_bound(vect.begin(), vect.end(), x, value_compare());
164 iterator upper_bound(const key_type& x)
166 return std::upper_bound(vect.begin(), vect.end(), x, value_compare());
169 const_iterator upper_bound(const key_type& x) const
171 return std::upper_bound(vect.begin(), vect.end(), x, value_compare());
174 size_type count(const key_type& x) const
176 std::pair<const_iterator, const_iterator> itpair = equal_range(x);
177 return std::distance(itpair.first, itpair.second);
181 std::pair<iterator, bool> insert_single(const value_type& x)
183 bool inserted = false;
186 iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
187 if ((it == vect.end()) || (c(x, *it)))
190 it = vect.insert(it, x);
192 return std::make_pair(it, inserted);
195 iterator insert_multi(const value_type& x)
197 iterator it = std::lower_bound(vect.begin(), vect.end(), x, value_compare());
198 return vect.insert(it, x);
202 } // namespace detail
204 template <typename T, typename Comp = std::less<T>, typename ElementComp = Comp>
205 class flat_set : public detail::flat_map_base<T, Comp, T, ElementComp>
207 typedef detail::flat_map_base<T, Comp, T, ElementComp> base_t;
210 typedef typename base_t::iterator iterator;
211 typedef typename base_t::value_type value_type;
215 template <typename InputIterator>
216 flat_set(InputIterator first, InputIterator last)
218 this->insert(first, last);
221 flat_set(const flat_set& other)
226 std::pair<iterator, bool> insert(const value_type& x)
228 return this->insert_single(x);
231 template <typename InputIterator>
232 void insert(InputIterator first, InputIterator last)
234 for (; first != last; ++first)
235 this->insert_single(*first);
238 void swap(flat_set& other)
240 base_t::vect.swap(other.vect);
244 template <typename T, typename Comp = std::less<T>, typename ElementComp = Comp>
245 class flat_multiset : public detail::flat_map_base<T, Comp, T, ElementComp>
247 typedef detail::flat_map_base<T, Comp, T, ElementComp> base_t;
250 typedef typename base_t::iterator iterator;
251 typedef typename base_t::value_type value_type;
255 template <typename InputIterator>
256 flat_multiset(InputIterator first, InputIterator last)
258 this->insert(first, last);
261 flat_multiset(const flat_multiset& other)
266 iterator insert(const value_type& x)
268 return this->insert_multi(x);
271 template <typename InputIterator>
272 void insert(InputIterator first, InputIterator last)
274 for (; first != last; ++first)
275 insert_multi(*first);
278 void swap(flat_multiset& other)
280 base_t::vect.swap(other.vect);
284 template <typename T, typename U, typename Comp = std::less<T>, typename ElementComp = Comp >
285 class flat_map : public detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> >
287 typedef detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> > base_t;
290 typedef typename base_t::iterator iterator;
291 typedef typename base_t::key_type key_type;
292 typedef typename base_t::value_type value_type;
293 typedef U mapped_type;
294 typedef typename base_t::value_compare value_compare;
298 template <typename InputIterator>
299 flat_map(InputIterator first, InputIterator last)
304 flat_map(const flat_map& other)
309 std::pair<iterator, bool> insert(const value_type& x)
311 return this->insert_single(x);
314 template <typename InputIterator>
315 void insert(InputIterator first, InputIterator last)
317 for (; first != last; ++first)
318 this->insert_single(*first);
321 void swap(flat_map& other)
323 base_t::vect.swap(other.vect);
326 mapped_type& operator[](const key_type& x)
328 return insert(std::make_pair(x, mapped_type())).first->second;
331 value_compare value_comp() const
333 return value_compare();
337 template <typename T, typename U, typename Comp = std::less<T>, typename ElementComp = Comp >
338 class flat_multimap : public detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> >
340 typedef detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> > base_t;
343 typedef typename base_t::iterator iterator;
344 typedef typename base_t::value_type value_type;
345 typedef U mapped_type;
346 typedef typename base_t::value_compare value_compare;
350 template <typename InputIterator>
351 flat_multimap(InputIterator first, InputIterator last)
353 this->insert(first, last);
356 flat_multimap(const flat_multimap& other)
361 iterator insert(const value_type& x)
363 return this->insert_multi(x);
366 template <typename InputIterator>
367 void insert(InputIterator first, InputIterator last)
369 for (; first != last; ++first)
370 this->insert_multi(*first);
373 void swap(flat_multimap& other)
375 base_t::vect.swap(other.vect);
378 value_compare value_comp() const
380 return value_compare();