]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | ////////////////////////////////////////////////////////////////////////////// |
2 | // | |
3 | // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost | |
4 | // Software License, Version 1.0. (See accompanying file | |
5 | // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
6 | // | |
7 | // See http://www.boost.org/libs/container for documentation. | |
8 | // | |
9 | ////////////////////////////////////////////////////////////////////////////// | |
10 | #ifndef BOOST_CONTAINER_FLAT_MAP_HPP | |
11 | #define BOOST_CONTAINER_FLAT_MAP_HPP | |
12 | ||
13 | #ifndef BOOST_CONFIG_HPP | |
14 | # include <boost/config.hpp> | |
15 | #endif | |
16 | ||
17 | #if defined(BOOST_HAS_PRAGMA_ONCE) | |
18 | # pragma once | |
19 | #endif | |
20 | ||
21 | #include <boost/container/detail/config_begin.hpp> | |
22 | #include <boost/container/detail/workaround.hpp> | |
23 | // container | |
24 | #include <boost/container/allocator_traits.hpp> | |
25 | #include <boost/container/container_fwd.hpp> | |
26 | #include <boost/container/new_allocator.hpp> //new_allocator | |
27 | #include <boost/container/throw_exception.hpp> | |
28 | // container/detail | |
29 | #include <boost/container/detail/flat_tree.hpp> | |
30 | #include <boost/container/detail/type_traits.hpp> | |
31 | #include <boost/container/detail/mpl.hpp> | |
32 | #include <boost/container/detail/algorithm.hpp> //equal() | |
33 | // move | |
34 | #include <boost/move/utility_core.hpp> | |
35 | #include <boost/move/traits.hpp> | |
36 | // move/detail | |
37 | #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
38 | #include <boost/move/detail/fwd_macros.hpp> | |
39 | #endif | |
40 | #include <boost/move/detail/move_helpers.hpp> | |
41 | // intrusive | |
42 | #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair | |
43 | #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal | |
44 | //others | |
45 | #include <boost/core/no_exceptions_support.hpp> | |
46 | ||
47 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
48 | #include <initializer_list> | |
49 | #endif | |
50 | ||
51 | namespace boost { | |
52 | namespace container { | |
53 | ||
54 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
55 | ||
56 | template <class Key, class T, class Compare, class Allocator> | |
57 | class flat_multimap; | |
58 | ||
59 | namespace container_detail{ | |
60 | ||
61 | template<class D, class S> | |
62 | BOOST_CONTAINER_FORCEINLINE static D &force(const S &s) | |
63 | { return *const_cast<D*>((reinterpret_cast<const D*>(&s))); } | |
64 | ||
65 | template<class D, class S> | |
66 | BOOST_CONTAINER_FORCEINLINE static D force_copy(S s) | |
67 | { | |
68 | D *vp = reinterpret_cast<D *>(&s); | |
69 | return D(*vp); | |
70 | } | |
71 | ||
72 | } //namespace container_detail{ | |
73 | ||
74 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
75 | ||
76 | //! A flat_map is a kind of associative container that supports unique keys (contains at | |
77 | //! most one of each key value) and provides for fast retrieval of values of another | |
78 | //! type T based on the keys. The flat_map class supports random-access iterators. | |
79 | //! | |
80 | //! A flat_map satisfies all of the requirements of a container and of a reversible | |
81 | //! container and of an associative container. A flat_map also provides | |
82 | //! most operations described for unique keys. For a | |
83 | //! flat_map<Key,T> the key_type is Key and the value_type is std::pair<Key,T> | |
84 | //! (unlike std::map<Key, T> which value_type is std::pair<<b>const</b> Key, T>). | |
85 | //! | |
86 | //! Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). | |
87 | //! | |
88 | //! Allocator is the allocator to allocate the value_types | |
89 | //! (e.g. <i>allocator< std::pair<Key, T> ></i>). | |
90 | //! | |
91 | //! flat_map is similar to std::map but it's implemented like an ordered vector. | |
92 | //! This means that inserting a new element into a flat_map invalidates | |
93 | //! previous iterators and references | |
94 | //! | |
95 | //! Erasing an element invalidates iterators and references | |
96 | //! pointing to elements that come after (their keys are bigger) the erased element. | |
97 | //! | |
98 | //! This container provides random-access iterators. | |
99 | //! | |
100 | //! \tparam Key is the key_type of the map | |
101 | //! \tparam Value is the <code>mapped_type</code> | |
102 | //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). | |
103 | //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s | |
104 | //! (e.g. <i>allocator< std::pair<Key, T> > </i>). | |
105 | #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED | |
106 | template <class Key, class T, class Compare = std::less<Key>, class Allocator = new_allocator< std::pair< Key, T> > > | |
107 | #else | |
108 | template <class Key, class T, class Compare, class Allocator> | |
109 | #endif | |
110 | class flat_map | |
111 | { | |
112 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
113 | private: | |
114 | BOOST_COPYABLE_AND_MOVABLE(flat_map) | |
115 | //This is the tree that we should store if pair was movable | |
116 | typedef container_detail::flat_tree< | |
117 | std::pair<Key, T>, | |
118 | container_detail::select1st<Key>, | |
119 | Compare, | |
120 | Allocator> tree_t; | |
121 | ||
122 | //This is the real tree stored here. It's based on a movable pair | |
123 | typedef container_detail::flat_tree< | |
124 | container_detail::pair<Key, T>, | |
125 | container_detail::select1st<Key>, | |
126 | Compare, | |
127 | typename allocator_traits<Allocator>::template portable_rebind_alloc | |
128 | <container_detail::pair<Key, T> >::type> impl_tree_t; | |
129 | impl_tree_t m_flat_tree; // flat tree representing flat_map | |
130 | ||
131 | typedef typename impl_tree_t::value_type impl_value_type; | |
132 | typedef typename impl_tree_t::const_iterator impl_const_iterator; | |
133 | typedef typename impl_tree_t::iterator impl_iterator; | |
134 | typedef typename impl_tree_t::allocator_type impl_allocator_type; | |
135 | typedef container_detail::flat_tree_value_compare | |
136 | < Compare | |
137 | , container_detail::select1st<Key> | |
138 | , std::pair<Key, T> > value_compare_impl; | |
139 | typedef typename container_detail::get_flat_tree_iterators | |
140 | <typename allocator_traits<Allocator>::pointer>::iterator iterator_impl; | |
141 | typedef typename container_detail::get_flat_tree_iterators | |
142 | <typename allocator_traits<Allocator>::pointer>::const_iterator const_iterator_impl; | |
143 | typedef typename container_detail::get_flat_tree_iterators | |
144 | <typename allocator_traits<Allocator>::pointer>::reverse_iterator reverse_iterator_impl; | |
145 | typedef typename container_detail::get_flat_tree_iterators | |
146 | <typename allocator_traits<Allocator>::pointer>::const_reverse_iterator const_reverse_iterator_impl; | |
147 | public: | |
148 | typedef typename impl_tree_t::stored_allocator_type impl_stored_allocator_type; | |
149 | ||
150 | impl_tree_t &tree() | |
151 | { return m_flat_tree; } | |
152 | ||
153 | const impl_tree_t &tree() const | |
154 | { return m_flat_tree; } | |
155 | ||
156 | private: | |
157 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
158 | ||
159 | public: | |
160 | ||
161 | ////////////////////////////////////////////// | |
162 | // | |
163 | // types | |
164 | // | |
165 | ////////////////////////////////////////////// | |
166 | typedef Key key_type; | |
167 | typedef T mapped_type; | |
168 | typedef std::pair<Key, T> value_type; | |
169 | typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type; | |
170 | typedef typename boost::container::allocator_traits<Allocator>::pointer pointer; | |
171 | typedef typename boost::container::allocator_traits<Allocator>::const_pointer const_pointer; | |
172 | typedef typename boost::container::allocator_traits<Allocator>::reference reference; | |
173 | typedef typename boost::container::allocator_traits<Allocator>::const_reference const_reference; | |
174 | typedef typename boost::container::allocator_traits<Allocator>::size_type size_type; | |
175 | typedef typename boost::container::allocator_traits<Allocator>::difference_type difference_type; | |
176 | typedef Allocator allocator_type; | |
177 | typedef BOOST_CONTAINER_IMPDEF(Allocator) stored_allocator_type; | |
178 | typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare; | |
179 | typedef Compare key_compare; | |
180 | typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator; | |
181 | typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator; | |
182 | typedef BOOST_CONTAINER_IMPDEF(reverse_iterator_impl) reverse_iterator; | |
183 | typedef BOOST_CONTAINER_IMPDEF(const_reverse_iterator_impl) const_reverse_iterator; | |
184 | typedef BOOST_CONTAINER_IMPDEF(impl_value_type) movable_value_type; | |
185 | ||
186 | public: | |
187 | ////////////////////////////////////////////// | |
188 | // | |
189 | // construct/copy/destroy | |
190 | // | |
191 | ////////////////////////////////////////////// | |
192 | ||
193 | //! <b>Effects</b>: Default constructs an empty flat_map. | |
194 | //! | |
195 | //! <b>Complexity</b>: Constant. | |
196 | flat_map() BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value && | |
197 | container_detail::is_nothrow_default_constructible<Compare>::value) | |
198 | : m_flat_tree() | |
199 | { | |
200 | //value_type must be std::pair<Key, T> | |
201 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
202 | } | |
203 | ||
204 | //! <b>Effects</b>: Constructs an empty flat_map using the specified | |
205 | //! comparison object and allocator. | |
206 | //! | |
207 | //! <b>Complexity</b>: Constant. | |
208 | explicit flat_map(const Compare& comp, const allocator_type& a = allocator_type()) | |
209 | : m_flat_tree(comp, container_detail::force<impl_allocator_type>(a)) | |
210 | { | |
211 | //value_type must be std::pair<Key, T> | |
212 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
213 | } | |
214 | ||
215 | //! <b>Effects</b>: Constructs an empty flat_map using the specified allocator. | |
216 | //! | |
217 | //! <b>Complexity</b>: Constant. | |
218 | explicit flat_map(const allocator_type& a) | |
219 | : m_flat_tree(container_detail::force<impl_allocator_type>(a)) | |
220 | { | |
221 | //value_type must be std::pair<Key, T> | |
222 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
223 | } | |
224 | ||
225 | //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and | |
226 | //! allocator, and inserts elements from the range [first ,last ). | |
227 | //! | |
228 | //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using | |
229 | //! comp and otherwise N logN, where N is last - first. | |
230 | template <class InputIterator> | |
231 | flat_map(InputIterator first, InputIterator last, const Compare& comp = Compare(), | |
232 | const allocator_type& a = allocator_type()) | |
233 | : m_flat_tree(true, first, last, comp, container_detail::force<impl_allocator_type>(a)) | |
234 | { | |
235 | //value_type must be std::pair<Key, T> | |
236 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
237 | } | |
238 | ||
239 | //! <b>Effects</b>: Constructs an empty flat_map using the specified | |
240 | //! allocator, and inserts elements from the range [first ,last ). | |
241 | //! | |
242 | //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using | |
243 | //! comp and otherwise N logN, where N is last - first. | |
244 | template <class InputIterator> | |
245 | flat_map(InputIterator first, InputIterator last, const allocator_type& a) | |
246 | : m_flat_tree(true, first, last, Compare(), container_detail::force<impl_allocator_type>(a)) | |
247 | { | |
248 | //value_type must be std::pair<Key, T> | |
249 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
250 | } | |
251 | ||
252 | //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and | |
253 | //! allocator, and inserts elements from the ordered unique range [first ,last). This function | |
254 | //! is more efficient than the normal range creation for ordered ranges. | |
255 | //! | |
256 | //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be | |
257 | //! unique values. | |
258 | //! | |
259 | //! <b>Complexity</b>: Linear in N. | |
260 | //! | |
261 | //! <b>Note</b>: Non-standard extension. | |
262 | template <class InputIterator> | |
263 | flat_map( ordered_unique_range_t, InputIterator first, InputIterator last | |
264 | , const Compare& comp = Compare(), const allocator_type& a = allocator_type()) | |
265 | : m_flat_tree(ordered_unique_range, first, last, comp, a) | |
266 | { | |
267 | //value_type must be std::pair<Key, T> | |
268 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
269 | } | |
270 | ||
271 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
272 | //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and | |
273 | //! allocator, and inserts elements from the range [il.begin() ,il.end()). | |
274 | //! | |
275 | //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using | |
276 | //! comp and otherwise N logN, where N is last - first. | |
277 | flat_map(std::initializer_list<value_type> il, const Compare& comp = Compare(), | |
278 | const allocator_type& a = allocator_type()) | |
279 | : m_flat_tree(true, il.begin(), il.end(), comp, container_detail::force<impl_allocator_type>(a)) | |
280 | { | |
281 | //value_type must be std::pair<Key, T> | |
282 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
283 | } | |
284 | ||
285 | //! <b>Effects</b>: Constructs an empty flat_map using the specified | |
286 | //! allocator, and inserts elements from the range [il.begin() ,il.end()). | |
287 | //! | |
288 | //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using | |
289 | //! comp and otherwise N logN, where N is last - first. | |
290 | flat_map(std::initializer_list<value_type> il, const allocator_type& a) | |
291 | : m_flat_tree(true, il.begin(), il.end(), Compare(), container_detail::force<impl_allocator_type>(a)) | |
292 | { | |
293 | //value_type must be std::pair<Key, T> | |
294 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
295 | } | |
296 | ||
297 | //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and | |
298 | //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function | |
299 | //! is more efficient than the normal range creation for ordered ranges. | |
300 | //! | |
301 | //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be | |
302 | //! unique values. | |
303 | //! | |
304 | //! <b>Complexity</b>: Linear in N. | |
305 | //! | |
306 | //! <b>Note</b>: Non-standard extension. | |
307 | flat_map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(), | |
308 | const allocator_type& a = allocator_type()) | |
309 | : m_flat_tree(ordered_unique_range, il.begin(), il.end(), comp, a) | |
310 | { | |
311 | //value_type must be std::pair<Key, T> | |
312 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
313 | } | |
314 | #endif | |
315 | ||
316 | //! <b>Effects</b>: Copy constructs a flat_map. | |
317 | //! | |
318 | //! <b>Complexity</b>: Linear in x.size(). | |
319 | flat_map(const flat_map& x) | |
320 | : m_flat_tree(x.m_flat_tree) | |
321 | { | |
322 | //value_type must be std::pair<Key, T> | |
323 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
324 | } | |
325 | ||
326 | //! <b>Effects</b>: Move constructs a flat_map. | |
327 | //! Constructs *this using x's resources. | |
328 | //! | |
329 | //! <b>Complexity</b>: Constant. | |
330 | //! | |
331 | //! <b>Postcondition</b>: x is emptied. | |
332 | flat_map(BOOST_RV_REF(flat_map) x) | |
333 | BOOST_NOEXCEPT_IF(boost::container::container_detail::is_nothrow_move_constructible<Compare>::value) | |
334 | : m_flat_tree(boost::move(x.m_flat_tree)) | |
335 | { | |
336 | //value_type must be std::pair<Key, T> | |
337 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
338 | } | |
339 | ||
340 | //! <b>Effects</b>: Copy constructs a flat_map using the specified allocator. | |
341 | //! | |
342 | //! <b>Complexity</b>: Linear in x.size(). | |
343 | flat_map(const flat_map& x, const allocator_type &a) | |
344 | : m_flat_tree(x.m_flat_tree, a) | |
345 | { | |
346 | //value_type must be std::pair<Key, T> | |
347 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
348 | } | |
349 | ||
350 | //! <b>Effects</b>: Move constructs a flat_map using the specified allocator. | |
351 | //! Constructs *this using x's resources. | |
352 | //! | |
353 | //! <b>Complexity</b>: Constant if x.get_allocator() == a, linear otherwise. | |
354 | flat_map(BOOST_RV_REF(flat_map) x, const allocator_type &a) | |
355 | : m_flat_tree(boost::move(x.m_flat_tree), a) | |
356 | { | |
357 | //value_type must be std::pair<Key, T> | |
358 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
359 | } | |
360 | ||
361 | //! <b>Effects</b>: Makes *this a copy of x. | |
362 | //! | |
363 | //! <b>Complexity</b>: Linear in x.size(). | |
364 | flat_map& operator=(BOOST_COPY_ASSIGN_REF(flat_map) x) | |
365 | { m_flat_tree = x.m_flat_tree; return *this; } | |
366 | ||
367 | //! <b>Effects</b>: Move constructs a flat_map. | |
368 | //! Constructs *this using x's resources. | |
369 | //! | |
370 | //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment | |
371 | //! is false and (allocation throws or value_type's move constructor throws) | |
372 | //! | |
373 | //! <b>Complexity</b>: Constant if allocator_traits_type:: | |
374 | //! propagate_on_container_move_assignment is true or | |
375 | //! this->get>allocator() == x.get_allocator(). Linear otherwise. | |
376 | flat_map& operator=(BOOST_RV_REF(flat_map) x) | |
377 | BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value || | |
378 | allocator_traits_type::is_always_equal::value) && | |
379 | boost::container::container_detail::is_nothrow_move_assignable<Compare>::value) | |
380 | { m_flat_tree = boost::move(x.m_flat_tree); return *this; } | |
381 | ||
382 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
383 | //! <b>Effects</b>: Assign elements from il to *this | |
384 | flat_map& operator=(std::initializer_list<value_type> il) | |
385 | { | |
386 | this->clear(); | |
387 | this->insert(il.begin(), il.end()); | |
388 | return *this; | |
389 | } | |
390 | #endif | |
391 | ||
392 | //! <b>Effects</b>: Returns a copy of the allocator that | |
393 | //! was passed to the object's constructor. | |
394 | //! | |
395 | //! <b>Complexity</b>: Constant. | |
396 | allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW | |
397 | { return container_detail::force_copy<allocator_type>(m_flat_tree.get_allocator()); } | |
398 | ||
399 | //! <b>Effects</b>: Returns a reference to the internal allocator. | |
400 | //! | |
401 | //! <b>Throws</b>: Nothing | |
402 | //! | |
403 | //! <b>Complexity</b>: Constant. | |
404 | //! | |
405 | //! <b>Note</b>: Non-standard extension. | |
406 | stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW | |
407 | { return container_detail::force<stored_allocator_type>(m_flat_tree.get_stored_allocator()); } | |
408 | ||
409 | //! <b>Effects</b>: Returns a reference to the internal allocator. | |
410 | //! | |
411 | //! <b>Throws</b>: Nothing | |
412 | //! | |
413 | //! <b>Complexity</b>: Constant. | |
414 | //! | |
415 | //! <b>Note</b>: Non-standard extension. | |
416 | const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW | |
417 | { return container_detail::force<stored_allocator_type>(m_flat_tree.get_stored_allocator()); } | |
418 | ||
419 | ////////////////////////////////////////////// | |
420 | // | |
421 | // iterators | |
422 | // | |
423 | ////////////////////////////////////////////// | |
424 | ||
425 | //! <b>Effects</b>: Returns an iterator to the first element contained in the container. | |
426 | //! | |
427 | //! <b>Throws</b>: Nothing. | |
428 | //! | |
429 | //! <b>Complexity</b>: Constant. | |
430 | iterator begin() BOOST_NOEXCEPT_OR_NOTHROW | |
431 | { return container_detail::force_copy<iterator>(m_flat_tree.begin()); } | |
432 | ||
433 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. | |
434 | //! | |
435 | //! <b>Throws</b>: Nothing. | |
436 | //! | |
437 | //! <b>Complexity</b>: Constant. | |
438 | const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW | |
439 | { return container_detail::force_copy<const_iterator>(m_flat_tree.begin()); } | |
440 | ||
441 | //! <b>Effects</b>: Returns an iterator to the end of the container. | |
442 | //! | |
443 | //! <b>Throws</b>: Nothing. | |
444 | //! | |
445 | //! <b>Complexity</b>: Constant. | |
446 | iterator end() BOOST_NOEXCEPT_OR_NOTHROW | |
447 | { return container_detail::force_copy<iterator>(m_flat_tree.end()); } | |
448 | ||
449 | //! <b>Effects</b>: Returns a const_iterator to the end of the container. | |
450 | //! | |
451 | //! <b>Throws</b>: Nothing. | |
452 | //! | |
453 | //! <b>Complexity</b>: Constant. | |
454 | const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW | |
455 | { return container_detail::force_copy<const_iterator>(m_flat_tree.end()); } | |
456 | ||
457 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning | |
458 | //! of the reversed container. | |
459 | //! | |
460 | //! <b>Throws</b>: Nothing. | |
461 | //! | |
462 | //! <b>Complexity</b>: Constant. | |
463 | reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW | |
464 | { return container_detail::force_copy<reverse_iterator>(m_flat_tree.rbegin()); } | |
465 | ||
466 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning | |
467 | //! of the reversed container. | |
468 | //! | |
469 | //! <b>Throws</b>: Nothing. | |
470 | //! | |
471 | //! <b>Complexity</b>: Constant. | |
472 | const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW | |
473 | { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.rbegin()); } | |
474 | ||
475 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the end | |
476 | //! of the reversed container. | |
477 | //! | |
478 | //! <b>Throws</b>: Nothing. | |
479 | //! | |
480 | //! <b>Complexity</b>: Constant. | |
481 | reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW | |
482 | { return container_detail::force_copy<reverse_iterator>(m_flat_tree.rend()); } | |
483 | ||
484 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end | |
485 | //! of the reversed container. | |
486 | //! | |
487 | //! <b>Throws</b>: Nothing. | |
488 | //! | |
489 | //! <b>Complexity</b>: Constant. | |
490 | const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW | |
491 | { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.rend()); } | |
492 | ||
493 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. | |
494 | //! | |
495 | //! <b>Throws</b>: Nothing. | |
496 | //! | |
497 | //! <b>Complexity</b>: Constant. | |
498 | const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW | |
499 | { return container_detail::force_copy<const_iterator>(m_flat_tree.cbegin()); } | |
500 | ||
501 | //! <b>Effects</b>: Returns a const_iterator to the end of the container. | |
502 | //! | |
503 | //! <b>Throws</b>: Nothing. | |
504 | //! | |
505 | //! <b>Complexity</b>: Constant. | |
506 | const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW | |
507 | { return container_detail::force_copy<const_iterator>(m_flat_tree.cend()); } | |
508 | ||
509 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning | |
510 | //! of the reversed container. | |
511 | //! | |
512 | //! <b>Throws</b>: Nothing. | |
513 | //! | |
514 | //! <b>Complexity</b>: Constant. | |
515 | const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW | |
516 | { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.crbegin()); } | |
517 | ||
518 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end | |
519 | //! of the reversed container. | |
520 | //! | |
521 | //! <b>Throws</b>: Nothing. | |
522 | //! | |
523 | //! <b>Complexity</b>: Constant. | |
524 | const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW | |
525 | { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.crend()); } | |
526 | ||
527 | ////////////////////////////////////////////// | |
528 | // | |
529 | // capacity | |
530 | // | |
531 | ////////////////////////////////////////////// | |
532 | ||
533 | //! <b>Effects</b>: Returns true if the container contains no elements. | |
534 | //! | |
535 | //! <b>Throws</b>: Nothing. | |
536 | //! | |
537 | //! <b>Complexity</b>: Constant. | |
538 | bool empty() const BOOST_NOEXCEPT_OR_NOTHROW | |
539 | { return m_flat_tree.empty(); } | |
540 | ||
541 | //! <b>Effects</b>: Returns the number of the elements contained in the container. | |
542 | //! | |
543 | //! <b>Throws</b>: Nothing. | |
544 | //! | |
545 | //! <b>Complexity</b>: Constant. | |
546 | size_type size() const BOOST_NOEXCEPT_OR_NOTHROW | |
547 | { return m_flat_tree.size(); } | |
548 | ||
549 | //! <b>Effects</b>: Returns the largest possible size of the container. | |
550 | //! | |
551 | //! <b>Throws</b>: Nothing. | |
552 | //! | |
553 | //! <b>Complexity</b>: Constant. | |
554 | size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW | |
555 | { return m_flat_tree.max_size(); } | |
556 | ||
557 | //! <b>Effects</b>: Number of elements for which memory has been allocated. | |
558 | //! capacity() is always greater than or equal to size(). | |
559 | //! | |
560 | //! <b>Throws</b>: Nothing. | |
561 | //! | |
562 | //! <b>Complexity</b>: Constant. | |
563 | size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW | |
564 | { return m_flat_tree.capacity(); } | |
565 | ||
566 | //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no | |
567 | //! effect. Otherwise, it is a request for allocation of additional memory. | |
568 | //! If the request is successful, then capacity() is greater than or equal to | |
569 | //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged. | |
570 | //! | |
571 | //! <b>Throws</b>: If memory allocation allocation throws or T's copy constructor throws. | |
572 | //! | |
573 | //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to | |
574 | //! to values might be invalidated. | |
575 | void reserve(size_type cnt) | |
576 | { m_flat_tree.reserve(cnt); } | |
577 | ||
578 | //! <b>Effects</b>: Tries to deallocate the excess of memory created | |
579 | // with previous allocations. The size of the vector is unchanged | |
580 | //! | |
581 | //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. | |
582 | //! | |
583 | //! <b>Complexity</b>: Linear to size(). | |
584 | void shrink_to_fit() | |
585 | { m_flat_tree.shrink_to_fit(); } | |
586 | ||
587 | ////////////////////////////////////////////// | |
588 | // | |
589 | // element access | |
590 | // | |
591 | ////////////////////////////////////////////// | |
592 | ||
593 | #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
594 | //! Effects: If there is no key equivalent to x in the flat_map, inserts | |
595 | //! value_type(x, T()) into the flat_map. | |
596 | //! | |
597 | //! Returns: A reference to the mapped_type corresponding to x in *this. | |
598 | //! | |
599 | //! Complexity: Logarithmic. | |
600 | mapped_type &operator[](const key_type& k); | |
601 | ||
602 | //! Effects: If there is no key equivalent to x in the flat_map, inserts | |
603 | //! value_type(move(x), T()) into the flat_map (the key is move-constructed) | |
604 | //! | |
605 | //! Returns: A reference to the mapped_type corresponding to x in *this. | |
606 | //! | |
607 | //! Complexity: Logarithmic. | |
608 | mapped_type &operator[](key_type &&k) ; | |
609 | #elif defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN) | |
610 | //in compilers like GCC 3.4, we can't catch temporaries | |
611 | mapped_type& operator[](const key_type &k) { return this->priv_subscript(k); } | |
612 | mapped_type& operator[](BOOST_RV_REF(key_type) k) { return this->priv_subscript(::boost::move(k)); } | |
613 | #else | |
614 | BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript) | |
615 | #endif | |
616 | ||
617 | //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj) | |
618 | //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value | |
619 | //! as if by insert, constructing it from value_type(k, forward<M>(obj)). | |
620 | //! | |
621 | //! No iterators or references are invalidated. If the insertion is successful, pointers and references | |
622 | //! to the element obtained while it is held in the node handle are invalidated, and pointers and | |
623 | //! references obtained to that element before it was extracted become valid. | |
624 | //! | |
625 | //! Returns: The bool component is true if the insertion took place and false if the assignment | |
626 | //! took place. The iterator component is pointing at the element that was inserted or updated. | |
627 | //! | |
628 | //! Complexity: Logarithmic in the size of the container. | |
629 | template <class M> | |
630 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(const key_type& k, BOOST_FWD_REF(M) obj) | |
631 | { | |
632 | return container_detail::force_copy< std::pair<iterator, bool> > | |
633 | (this->m_flat_tree.insert_or_assign | |
634 | ( impl_const_iterator(), k, ::boost::forward<M>(obj)) | |
635 | ); | |
636 | } | |
637 | ||
638 | //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj) | |
639 | //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value | |
640 | //! as if by insert, constructing it from value_type(k, move(obj)). | |
641 | //! | |
642 | //! No iterators or references are invalidated. If the insertion is successful, pointers and references | |
643 | //! to the element obtained while it is held in the node handle are invalidated, and pointers and | |
644 | //! references obtained to that element before it was extracted become valid. | |
645 | //! | |
646 | //! Returns: The bool component is true if the insertion took place and false if the assignment | |
647 | //! took place. The iterator component is pointing at the element that was inserted or updated. | |
648 | //! | |
649 | //! Complexity: Logarithmic in the size of the container. | |
650 | template <class M> | |
651 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj) | |
652 | { | |
653 | return container_detail::force_copy< std::pair<iterator, bool> > | |
654 | (this->m_flat_tree.insert_or_assign | |
655 | ( impl_const_iterator(), ::boost::move(k), ::boost::forward<M>(obj)) | |
656 | ); | |
657 | } | |
658 | ||
659 | //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj) | |
660 | //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value | |
661 | //! as if by insert, constructing it from value_type(k, forward<M>(obj)) and the new element | |
662 | //! to the container as close as possible to the position just before hint. | |
663 | //! | |
664 | //! No iterators or references are invalidated. If the insertion is successful, pointers and references | |
665 | //! to the element obtained while it is held in the node handle are invalidated, and pointers and | |
666 | //! references obtained to that element before it was extracted become valid. | |
667 | //! | |
668 | //! Returns: The bool component is true if the insertion took place and false if the assignment | |
669 | //! took place. The iterator component is pointing at the element that was inserted or updated. | |
670 | //! | |
671 | //! Complexity: Logarithmic in the size of the container in general, but amortized constant if | |
672 | //! the new element is inserted just before hint. | |
673 | template <class M> | |
674 | BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, const key_type& k, BOOST_FWD_REF(M) obj) | |
675 | { | |
676 | return container_detail::force_copy< std::pair<iterator, bool> > | |
677 | (this->m_flat_tree.insert_or_assign | |
678 | ( container_detail::force_copy<impl_const_iterator>(hint) | |
679 | , k, ::boost::forward<M>(obj)) | |
680 | ); | |
681 | } | |
682 | ||
683 | //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj) | |
684 | //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value | |
685 | //! as if by insert, constructing it from value_type(k, move(obj)) and the new element | |
686 | //! to the container as close as possible to the position just before hint. | |
687 | //! | |
688 | //! No iterators or references are invalidated. If the insertion is successful, pointers and references | |
689 | //! to the element obtained while it is held in the node handle are invalidated, and pointers and | |
690 | //! references obtained to that element before it was extracted become valid. | |
691 | //! | |
692 | //! Returns: The bool component is true if the insertion took place and false if the assignment | |
693 | //! took place. The iterator component is pointing at the element that was inserted or updated. | |
694 | //! | |
695 | //! Complexity: Logarithmic in the size of the container in general, but amortized constant if | |
696 | //! the new element is inserted just before hint. | |
697 | template <class M> | |
698 | BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj) | |
699 | { | |
700 | return container_detail::force_copy< std::pair<iterator, bool> > | |
701 | (this->m_flat_tree.insert_or_assign | |
702 | ( container_detail::force_copy<impl_const_iterator>(hint) | |
703 | , ::boost::move(k), ::boost::forward<M>(obj)) | |
704 | ); | |
705 | } | |
706 | ||
707 | //! @copydoc ::boost::container::flat_set::nth(size_type) | |
708 | iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW | |
709 | { return container_detail::force_copy<iterator>(m_flat_tree.nth(n)); } | |
710 | ||
711 | //! @copydoc ::boost::container::flat_set::nth(size_type) const | |
712 | const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW | |
713 | { return container_detail::force_copy<iterator>(m_flat_tree.nth(n)); } | |
714 | ||
715 | //! @copydoc ::boost::container::flat_set::index_of(iterator) | |
716 | size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW | |
717 | { return m_flat_tree.index_of(container_detail::force_copy<impl_iterator>(p)); } | |
718 | ||
719 | //! @copydoc ::boost::container::flat_set::index_of(const_iterator) const | |
720 | size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW | |
721 | { return m_flat_tree.index_of(container_detail::force_copy<impl_const_iterator>(p)); } | |
722 | ||
723 | //! Returns: A reference to the element whose key is equivalent to x. | |
724 | //! | |
725 | //! Throws: An exception object of type out_of_range if no such element is present. | |
726 | //! | |
727 | //! Complexity: logarithmic. | |
728 | T& at(const key_type& k) | |
729 | { | |
730 | iterator i = this->find(k); | |
731 | if(i == this->end()){ | |
732 | throw_out_of_range("flat_map::at key not found"); | |
733 | } | |
734 | return i->second; | |
735 | } | |
736 | ||
737 | //! Returns: A reference to the element whose key is equivalent to x. | |
738 | //! | |
739 | //! Throws: An exception object of type out_of_range if no such element is present. | |
740 | //! | |
741 | //! Complexity: logarithmic. | |
742 | const T& at(const key_type& k) const | |
743 | { | |
744 | const_iterator i = this->find(k); | |
745 | if(i == this->end()){ | |
746 | throw_out_of_range("flat_map::at key not found"); | |
747 | } | |
748 | return i->second; | |
749 | } | |
750 | ||
751 | ////////////////////////////////////////////// | |
752 | // | |
753 | // modifiers | |
754 | // | |
755 | ////////////////////////////////////////////// | |
756 | ||
757 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
758 | ||
759 | //! <b>Effects</b>: Inserts an object x of type T constructed with | |
760 | //! std::forward<Args>(args)... if and only if there is no element in the container | |
761 | //! with key equivalent to the key of x. | |
762 | //! | |
763 | //! <b>Returns</b>: The bool component of the returned pair is true if and only | |
764 | //! if the insertion takes place, and the iterator component of the pair | |
765 | //! points to the element with key equivalent to the key of x. | |
766 | //! | |
767 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
768 | //! to the elements with bigger keys than x. | |
769 | //! | |
770 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
771 | template <class... Args> | |
772 | std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args) | |
773 | { return container_detail::force_copy< std::pair<iterator, bool> >(m_flat_tree.emplace_unique(boost::forward<Args>(args)...)); } | |
774 | ||
775 | //! <b>Effects</b>: Inserts an object of type T constructed with | |
776 | //! std::forward<Args>(args)... in the container if and only if there is | |
777 | //! no element in the container with key equivalent to the key of x. | |
778 | //! p is a hint pointing to where the insert should start to search. | |
779 | //! | |
780 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent | |
781 | //! to the key of x. | |
782 | //! | |
783 | //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted | |
784 | //! right before p) plus insertion linear to the elements with bigger keys than x. | |
785 | //! | |
786 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
787 | template <class... Args> | |
788 | iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args) | |
789 | { | |
790 | return container_detail::force_copy<iterator> | |
791 | (m_flat_tree.emplace_hint_unique( container_detail::force_copy<impl_const_iterator>(hint) | |
792 | , boost::forward<Args>(args)...)); | |
793 | } | |
794 | ||
795 | //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, | |
796 | //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...). | |
797 | //! | |
798 | //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise | |
799 | //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k), | |
800 | //! forward_as_tuple(forward<Args>(args)...). | |
801 | //! | |
802 | //! <b>Returns</b>: The bool component of the returned pair is true if and only if the | |
803 | //! insertion took place. The returned iterator points to the map element whose key is equivalent to k. | |
804 | //! | |
805 | //! <b>Complexity</b>: Logarithmic. | |
806 | template <class... Args> | |
807 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k, BOOST_FWD_REF(Args)... args) | |
808 | { | |
809 | return container_detail::force_copy< std::pair<iterator, bool> >( | |
810 | m_flat_tree.try_emplace(impl_const_iterator(), k, boost::forward<Args>(args)...)); | |
811 | } | |
812 | ||
813 | //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, | |
814 | //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...). | |
815 | //! | |
816 | //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise | |
817 | //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k), | |
818 | //! forward_as_tuple(forward<Args>(args)...). | |
819 | //! | |
820 | //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k. | |
821 | //! | |
822 | //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value | |
823 | //! is inserted right before p. | |
824 | template <class... Args> | |
825 | BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k, BOOST_FWD_REF(Args)... args) | |
826 | { | |
827 | return container_detail::force_copy<iterator>(m_flat_tree.try_emplace | |
828 | (container_detail::force_copy<impl_const_iterator>(hint), k, boost::forward<Args>(args)...).first); | |
829 | } | |
830 | ||
831 | //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, | |
832 | //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...). | |
833 | //! | |
834 | //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise | |
835 | //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)), | |
836 | //! forward_as_tuple(forward<Args>(args)...). | |
837 | //! | |
838 | //! <b>Returns</b>: The bool component of the returned pair is true if and only if the | |
839 | //! insertion took place. The returned iterator points to the map element whose key is equivalent to k. | |
840 | //! | |
841 | //! <b>Complexity</b>: Logarithmic. | |
842 | template <class... Args> | |
843 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args) | |
844 | { | |
845 | return container_detail::force_copy< std::pair<iterator, bool> > | |
846 | (m_flat_tree.try_emplace(impl_const_iterator(), boost::move(k), boost::forward<Args>(args)...)); | |
847 | } | |
848 | ||
849 | //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, | |
850 | //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...). | |
851 | //! | |
852 | //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise | |
853 | //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)), | |
854 | //! forward_as_tuple(forward<Args>(args)...). | |
855 | //! | |
856 | //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k. | |
857 | //! | |
858 | //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value | |
859 | //! is inserted right before p. | |
860 | template <class... Args> | |
861 | BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args) | |
862 | { | |
863 | return container_detail::force_copy<iterator> | |
864 | (m_flat_tree.try_emplace(container_detail::force_copy | |
865 | <impl_const_iterator>(hint), boost::move(k), boost::forward<Args>(args)...).first); | |
866 | } | |
867 | ||
868 | #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
869 | ||
870 | #define BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE(N) \ | |
871 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
872 | std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\ | |
873 | {\ | |
874 | return container_detail::force_copy< std::pair<iterator, bool> >\ | |
875 | (m_flat_tree.emplace_unique(BOOST_MOVE_FWD##N));\ | |
876 | }\ | |
877 | \ | |
878 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
879 | iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
880 | {\ | |
881 | return container_detail::force_copy<iterator>(m_flat_tree.emplace_hint_unique\ | |
882 | (container_detail::force_copy<impl_const_iterator>(hint) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\ | |
883 | }\ | |
884 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
885 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
886 | {\ | |
887 | return container_detail::force_copy< std::pair<iterator, bool> >\ | |
888 | (m_flat_tree.try_emplace(impl_const_iterator(), k BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\ | |
889 | }\ | |
890 | \ | |
891 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
892 | BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
893 | { return container_detail::force_copy<iterator>(m_flat_tree.try_emplace\ | |
894 | (container_detail::force_copy<impl_const_iterator>(hint), k BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first); }\ | |
895 | \ | |
896 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
897 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
898 | {\ | |
899 | return container_detail::force_copy< std::pair<iterator, bool> >\ | |
900 | (m_flat_tree.try_emplace(impl_const_iterator(), boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\ | |
901 | }\ | |
902 | \ | |
903 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
904 | BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
905 | { return container_detail::force_copy<iterator>(m_flat_tree.try_emplace\ | |
906 | (container_detail::force_copy<impl_const_iterator>(hint), boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first); }\ | |
907 | // | |
908 | BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE) | |
909 | #undef BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE | |
910 | ||
911 | #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
912 | ||
913 | //! <b>Effects</b>: Inserts x if and only if there is no element in the container | |
914 | //! with key equivalent to the key of x. | |
915 | //! | |
916 | //! <b>Returns</b>: The bool component of the returned pair is true if and only | |
917 | //! if the insertion takes place, and the iterator component of the pair | |
918 | //! points to the element with key equivalent to the key of x. | |
919 | //! | |
920 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
921 | //! to the elements with bigger keys than x. | |
922 | //! | |
923 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
924 | std::pair<iterator,bool> insert(const value_type& x) | |
925 | { return container_detail::force_copy<std::pair<iterator,bool> >( | |
926 | m_flat_tree.insert_unique(container_detail::force<impl_value_type>(x))); } | |
927 | ||
928 | //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and | |
929 | //! only if there is no element in the container with key equivalent to the key of x. | |
930 | //! | |
931 | //! <b>Returns</b>: The bool component of the returned pair is true if and only | |
932 | //! if the insertion takes place, and the iterator component of the pair | |
933 | //! points to the element with key equivalent to the key of x. | |
934 | //! | |
935 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
936 | //! to the elements with bigger keys than x. | |
937 | //! | |
938 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
939 | std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x) | |
940 | { return container_detail::force_copy<std::pair<iterator,bool> >( | |
941 | m_flat_tree.insert_unique(boost::move(container_detail::force<impl_value_type>(x)))); } | |
942 | ||
943 | //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and | |
944 | //! only if there is no element in the container with key equivalent to the key of x. | |
945 | //! | |
946 | //! <b>Returns</b>: The bool component of the returned pair is true if and only | |
947 | //! if the insertion takes place, and the iterator component of the pair | |
948 | //! points to the element with key equivalent to the key of x. | |
949 | //! | |
950 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
951 | //! to the elements with bigger keys than x. | |
952 | //! | |
953 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
954 | std::pair<iterator,bool> insert(BOOST_RV_REF(movable_value_type) x) | |
955 | { | |
956 | return container_detail::force_copy<std::pair<iterator,bool> > | |
957 | (m_flat_tree.insert_unique(boost::move(x))); | |
958 | } | |
959 | ||
960 | //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is | |
961 | //! no element in the container with key equivalent to the key of x. | |
962 | //! p is a hint pointing to where the insert should start to search. | |
963 | //! | |
964 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent | |
965 | //! to the key of x. | |
966 | //! | |
967 | //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted | |
968 | //! right before p) plus insertion linear to the elements with bigger keys than x. | |
969 | //! | |
970 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
971 | iterator insert(const_iterator p, const value_type& x) | |
972 | { | |
973 | return container_detail::force_copy<iterator>( | |
974 | m_flat_tree.insert_unique( container_detail::force_copy<impl_const_iterator>(p) | |
975 | , container_detail::force<impl_value_type>(x))); | |
976 | } | |
977 | ||
978 | //! <b>Effects</b>: Inserts an element move constructed from x in the container. | |
979 | //! p is a hint pointing to where the insert should start to search. | |
980 | //! | |
981 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x. | |
982 | //! | |
983 | //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted | |
984 | //! right before p) plus insertion linear to the elements with bigger keys than x. | |
985 | //! | |
986 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
987 | iterator insert(const_iterator p, BOOST_RV_REF(value_type) x) | |
988 | { | |
989 | return container_detail::force_copy<iterator> | |
990 | (m_flat_tree.insert_unique( container_detail::force_copy<impl_const_iterator>(p) | |
991 | , boost::move(container_detail::force<impl_value_type>(x)))); | |
992 | } | |
993 | ||
994 | //! <b>Effects</b>: Inserts an element move constructed from x in the container. | |
995 | //! p is a hint pointing to where the insert should start to search. | |
996 | //! | |
997 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x. | |
998 | //! | |
999 | //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted | |
1000 | //! right before p) plus insertion linear to the elements with bigger keys than x. | |
1001 | //! | |
1002 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1003 | iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x) | |
1004 | { | |
1005 | return container_detail::force_copy<iterator>( | |
1006 | m_flat_tree.insert_unique(container_detail::force_copy<impl_const_iterator>(p), boost::move(x))); | |
1007 | } | |
1008 | ||
1009 | //! <b>Requires</b>: first, last are not iterators into *this. | |
1010 | //! | |
1011 | //! <b>Effects</b>: inserts each element from the range [first,last) if and only | |
1012 | //! if there is no element with key equivalent to the key of that element. | |
1013 | //! | |
1014 | //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) | |
1015 | //! search time plus N*size() insertion time. | |
1016 | //! | |
1017 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1018 | template <class InputIterator> | |
1019 | void insert(InputIterator first, InputIterator last) | |
1020 | { m_flat_tree.insert_unique(first, last); } | |
1021 | ||
1022 | //! <b>Requires</b>: first, last are not iterators into *this. | |
1023 | //! | |
1024 | //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be | |
1025 | //! unique values. | |
1026 | //! | |
1027 | //! <b>Effects</b>: inserts each element from the range [first,last) if and only | |
1028 | //! if there is no element with key equivalent to the key of that element. This | |
1029 | //! function is more efficient than the normal range creation for ordered ranges. | |
1030 | //! | |
1031 | //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) | |
1032 | //! search time plus N*size() insertion time. | |
1033 | //! | |
1034 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1035 | //! | |
1036 | //! <b>Note</b>: Non-standard extension. | |
1037 | template <class InputIterator> | |
1038 | void insert(ordered_unique_range_t, InputIterator first, InputIterator last) | |
1039 | { m_flat_tree.insert_unique(ordered_unique_range, first, last); } | |
1040 | ||
1041 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
1042 | //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only | |
1043 | //! if there is no element with key equivalent to the key of that element. | |
1044 | //! | |
1045 | //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.first() to il.end()) | |
1046 | //! search time plus N*size() insertion time. | |
1047 | //! | |
1048 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1049 | void insert(std::initializer_list<value_type> il) | |
1050 | { m_flat_tree.insert_unique(il.begin(), il.end()); } | |
1051 | ||
1052 | //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be | |
1053 | //! unique values. | |
1054 | //! | |
1055 | //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only | |
1056 | //! if there is no element with key equivalent to the key of that element. This | |
1057 | //! function is more efficient than the normal range creation for ordered ranges. | |
1058 | //! | |
1059 | //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) | |
1060 | //! search time plus N*size() insertion time. | |
1061 | //! | |
1062 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1063 | //! | |
1064 | //! <b>Note</b>: Non-standard extension. | |
1065 | void insert(ordered_unique_range_t, std::initializer_list<value_type> il) | |
1066 | { m_flat_tree.insert_unique(ordered_unique_range, il.begin(), il.end()); } | |
1067 | #endif | |
1068 | ||
1069 | //! <b>Requires</b>: this->get_allocator() == source.get_allocator(). | |
1070 | //! | |
1071 | //! <b>Effects</b>: Attempts to extract each element in source and insert it into a using | |
1072 | //! the comparison object of *this. If there is an element in a with key equivalent to the | |
1073 | //! key of an element from source, then that element is not extracted from source. | |
1074 | //! | |
1075 | //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer | |
1076 | //! to those same elements but as members of *this. Iterators referring to the transferred | |
1077 | //! elements will continue to refer to their elements, but they now behave as iterators into *this, | |
1078 | //! not into source. | |
1079 | //! | |
1080 | //! <b>Throws</b>: Nothing unless the comparison object throws. | |
1081 | //! | |
1082 | //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size()) | |
1083 | template<class C2> | |
1084 | BOOST_CONTAINER_FORCEINLINE void merge(flat_map<Key, T, C2, Allocator>& source) | |
1085 | { m_flat_tree.merge_unique(source.tree()); } | |
1086 | ||
1087 | //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, Allocator>&) | |
1088 | template<class C2> | |
1089 | BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_map<Key, T, C2, Allocator> BOOST_RV_REF_END source) | |
1090 | { return this->merge(static_cast<flat_map<Key, T, C2, Allocator>&>(source)); } | |
1091 | ||
1092 | //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, Allocator>&) | |
1093 | template<class C2> | |
1094 | BOOST_CONTAINER_FORCEINLINE void merge(flat_multimap<Key, T, C2, Allocator>& source) | |
1095 | { m_flat_tree.merge_unique(source.tree()); } | |
1096 | ||
1097 | //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, Allocator>&) | |
1098 | template<class C2> | |
1099 | BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_multimap<Key, T, C2, Allocator> BOOST_RV_REF_END source) | |
1100 | { return this->merge(static_cast<flat_multimap<Key, T, C2, Allocator>&>(source)); } | |
1101 | ||
1102 | //! <b>Effects</b>: Erases the element pointed to by p. | |
1103 | //! | |
1104 | //! <b>Returns</b>: Returns an iterator pointing to the element immediately | |
1105 | //! following q prior to the element being erased. If no such element exists, | |
1106 | //! returns end(). | |
1107 | //! | |
1108 | //! <b>Complexity</b>: Linear to the elements with keys bigger than p | |
1109 | //! | |
1110 | //! <b>Note</b>: Invalidates elements with keys | |
1111 | //! not less than the erased element. | |
1112 | iterator erase(const_iterator p) | |
1113 | { | |
1114 | return container_detail::force_copy<iterator> | |
1115 | (m_flat_tree.erase(container_detail::force_copy<impl_const_iterator>(p))); | |
1116 | } | |
1117 | ||
1118 | //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. | |
1119 | //! | |
1120 | //! <b>Returns</b>: Returns the number of erased elements. | |
1121 | //! | |
1122 | //! <b>Complexity</b>: Logarithmic search time plus erasure time | |
1123 | //! linear to the elements with bigger keys. | |
1124 | size_type erase(const key_type& x) | |
1125 | { return m_flat_tree.erase(x); } | |
1126 | ||
1127 | //! <b>Effects</b>: Erases all the elements in the range [first, last). | |
1128 | //! | |
1129 | //! <b>Returns</b>: Returns last. | |
1130 | //! | |
1131 | //! <b>Complexity</b>: size()*N where N is the distance from first to last. | |
1132 | //! | |
1133 | //! <b>Complexity</b>: Logarithmic search time plus erasure time | |
1134 | //! linear to the elements with bigger keys. | |
1135 | iterator erase(const_iterator first, const_iterator last) | |
1136 | { | |
1137 | return container_detail::force_copy<iterator>( | |
1138 | m_flat_tree.erase( container_detail::force_copy<impl_const_iterator>(first) | |
1139 | , container_detail::force_copy<impl_const_iterator>(last))); | |
1140 | } | |
1141 | ||
1142 | //! <b>Effects</b>: Swaps the contents of *this and x. | |
1143 | //! | |
1144 | //! <b>Throws</b>: Nothing. | |
1145 | //! | |
1146 | //! <b>Complexity</b>: Constant. | |
1147 | void swap(flat_map& x) | |
1148 | BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value | |
1149 | && boost::container::container_detail::is_nothrow_swappable<Compare>::value ) | |
1150 | { m_flat_tree.swap(x.m_flat_tree); } | |
1151 | ||
1152 | //! <b>Effects</b>: erase(a.begin(),a.end()). | |
1153 | //! | |
1154 | //! <b>Postcondition</b>: size() == 0. | |
1155 | //! | |
1156 | //! <b>Complexity</b>: linear in size(). | |
1157 | void clear() BOOST_NOEXCEPT_OR_NOTHROW | |
1158 | { m_flat_tree.clear(); } | |
1159 | ||
1160 | ////////////////////////////////////////////// | |
1161 | // | |
1162 | // observers | |
1163 | // | |
1164 | ////////////////////////////////////////////// | |
1165 | ||
1166 | //! <b>Effects</b>: Returns the comparison object out | |
1167 | //! of which a was constructed. | |
1168 | //! | |
1169 | //! <b>Complexity</b>: Constant. | |
1170 | key_compare key_comp() const | |
1171 | { return container_detail::force_copy<key_compare>(m_flat_tree.key_comp()); } | |
1172 | ||
1173 | //! <b>Effects</b>: Returns an object of value_compare constructed out | |
1174 | //! of the comparison object. | |
1175 | //! | |
1176 | //! <b>Complexity</b>: Constant. | |
1177 | value_compare value_comp() const | |
1178 | { return value_compare(container_detail::force_copy<key_compare>(m_flat_tree.key_comp())); } | |
1179 | ||
1180 | ////////////////////////////////////////////// | |
1181 | // | |
1182 | // map operations | |
1183 | // | |
1184 | ////////////////////////////////////////////// | |
1185 | ||
1186 | //! <b>Returns</b>: An iterator pointing to an element with the key | |
1187 | //! equivalent to x, or end() if such an element is not found. | |
1188 | //! | |
1189 | //! <b>Complexity</b>: Logarithmic. | |
1190 | iterator find(const key_type& x) | |
1191 | { return container_detail::force_copy<iterator>(m_flat_tree.find(x)); } | |
1192 | ||
1193 | //! <b>Returns</b>: A const_iterator pointing to an element with the key | |
1194 | //! equivalent to x, or end() if such an element is not found. | |
1195 | //! | |
1196 | //! <b>Complexity</b>: Logarithmic. | |
1197 | const_iterator find(const key_type& x) const | |
1198 | { return container_detail::force_copy<const_iterator>(m_flat_tree.find(x)); } | |
1199 | ||
1200 | //! <b>Returns</b>: The number of elements with key equivalent to x. | |
1201 | //! | |
1202 | //! <b>Complexity</b>: log(size())+count(k) | |
1203 | size_type count(const key_type& x) const | |
1204 | { return static_cast<size_type>(m_flat_tree.find(x) != m_flat_tree.end()); } | |
1205 | ||
1206 | //! <b>Returns</b>: An iterator pointing to the first element with key not less | |
1207 | //! than k, or a.end() if such an element is not found. | |
1208 | //! | |
1209 | //! <b>Complexity</b>: Logarithmic. | |
1210 | iterator lower_bound(const key_type& x) | |
1211 | { return container_detail::force_copy<iterator>(m_flat_tree.lower_bound(x)); } | |
1212 | ||
1213 | //! <b>Returns</b>: A const iterator pointing to the first element with key not | |
1214 | //! less than k, or a.end() if such an element is not found. | |
1215 | //! | |
1216 | //! <b>Complexity</b>: Logarithmic. | |
1217 | const_iterator lower_bound(const key_type& x) const | |
1218 | { return container_detail::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); } | |
1219 | ||
1220 | //! <b>Returns</b>: An iterator pointing to the first element with key not less | |
1221 | //! than x, or end() if such an element is not found. | |
1222 | //! | |
1223 | //! <b>Complexity</b>: Logarithmic. | |
1224 | iterator upper_bound(const key_type& x) | |
1225 | { return container_detail::force_copy<iterator>(m_flat_tree.upper_bound(x)); } | |
1226 | ||
1227 | //! <b>Returns</b>: A const iterator pointing to the first element with key not | |
1228 | //! less than x, or end() if such an element is not found. | |
1229 | //! | |
1230 | //! <b>Complexity</b>: Logarithmic. | |
1231 | const_iterator upper_bound(const key_type& x) const | |
1232 | { return container_detail::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); } | |
1233 | ||
1234 | //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). | |
1235 | //! | |
1236 | //! <b>Complexity</b>: Logarithmic. | |
1237 | std::pair<iterator,iterator> equal_range(const key_type& x) | |
1238 | { return container_detail::force_copy<std::pair<iterator,iterator> >(m_flat_tree.lower_bound_range(x)); } | |
1239 | ||
1240 | //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). | |
1241 | //! | |
1242 | //! <b>Complexity</b>: Logarithmic. | |
1243 | std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const | |
1244 | { return container_detail::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.lower_bound_range(x)); } | |
1245 | ||
1246 | //! <b>Effects</b>: Returns true if x and y are equal | |
1247 | //! | |
1248 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
1249 | friend bool operator==(const flat_map& x, const flat_map& y) | |
1250 | { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } | |
1251 | ||
1252 | //! <b>Effects</b>: Returns true if x and y are unequal | |
1253 | //! | |
1254 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
1255 | friend bool operator!=(const flat_map& x, const flat_map& y) | |
1256 | { return !(x == y); } | |
1257 | ||
1258 | //! <b>Effects</b>: Returns true if x is less than y | |
1259 | //! | |
1260 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
1261 | friend bool operator<(const flat_map& x, const flat_map& y) | |
1262 | { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } | |
1263 | ||
1264 | //! <b>Effects</b>: Returns true if x is greater than y | |
1265 | //! | |
1266 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
1267 | friend bool operator>(const flat_map& x, const flat_map& y) | |
1268 | { return y < x; } | |
1269 | ||
1270 | //! <b>Effects</b>: Returns true if x is equal or less than y | |
1271 | //! | |
1272 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
1273 | friend bool operator<=(const flat_map& x, const flat_map& y) | |
1274 | { return !(y < x); } | |
1275 | ||
1276 | //! <b>Effects</b>: Returns true if x is equal or greater than y | |
1277 | //! | |
1278 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
1279 | friend bool operator>=(const flat_map& x, const flat_map& y) | |
1280 | { return !(x < y); } | |
1281 | ||
1282 | //! <b>Effects</b>: x.swap(y) | |
1283 | //! | |
1284 | //! <b>Complexity</b>: Constant. | |
1285 | friend void swap(flat_map& x, flat_map& y) | |
1286 | { x.swap(y); } | |
1287 | ||
1288 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
1289 | private: | |
1290 | mapped_type &priv_subscript(const key_type& k) | |
1291 | { | |
1292 | iterator i = lower_bound(k); | |
1293 | // i->first is greater than or equivalent to k. | |
1294 | if (i == end() || key_comp()(k, (*i).first)){ | |
1295 | container_detail::value_init<mapped_type> m; | |
1296 | i = insert(i, impl_value_type(k, ::boost::move(m.m_t))); | |
1297 | } | |
1298 | return (*i).second; | |
1299 | } | |
1300 | mapped_type &priv_subscript(BOOST_RV_REF(key_type) mk) | |
1301 | { | |
1302 | key_type &k = mk; | |
1303 | iterator i = lower_bound(k); | |
1304 | // i->first is greater than or equivalent to k. | |
1305 | if (i == end() || key_comp()(k, (*i).first)){ | |
1306 | container_detail::value_init<mapped_type> m; | |
1307 | i = insert(i, impl_value_type(boost::move(k), ::boost::move(m.m_t))); | |
1308 | } | |
1309 | return (*i).second; | |
1310 | } | |
1311 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
1312 | }; | |
1313 | ||
1314 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
1315 | ||
1316 | } //namespace container { | |
1317 | ||
1318 | //!has_trivial_destructor_after_move<> == true_type | |
1319 | //!specialization for optimizations | |
1320 | template <class Key, class T, class Compare, class Allocator> | |
1321 | struct has_trivial_destructor_after_move<boost::container::flat_map<Key, T, Compare, Allocator> > | |
1322 | { | |
1323 | typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; | |
1324 | static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && | |
1325 | ::boost::has_trivial_destructor_after_move<pointer>::value && | |
1326 | ::boost::has_trivial_destructor_after_move<Compare>::value; | |
1327 | }; | |
1328 | ||
1329 | namespace container { | |
1330 | ||
1331 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
1332 | ||
1333 | //! A flat_multimap is a kind of associative container that supports equivalent keys | |
1334 | //! (possibly containing multiple copies of the same key value) and provides for | |
1335 | //! fast retrieval of values of another type T based on the keys. The flat_multimap | |
1336 | //! class supports random-access iterators. | |
1337 | //! | |
1338 | //! A flat_multimap satisfies all of the requirements of a container and of a reversible | |
1339 | //! container and of an associative container. For a | |
1340 | //! flat_multimap<Key,T> the key_type is Key and the value_type is std::pair<Key,T> | |
1341 | //! (unlike std::multimap<Key, T> which value_type is std::pair<<b>const</b> Key, T>). | |
1342 | //! | |
1343 | //! Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). | |
1344 | //! | |
1345 | //! Allocator is the allocator to allocate the value_types | |
1346 | //! (e.g. <i>allocator< std::pair<Key, T> ></i>). | |
1347 | //! | |
1348 | //! flat_multimap is similar to std::multimap but it's implemented like an ordered vector. | |
1349 | //! This means that inserting a new element into a flat_map invalidates | |
1350 | //! previous iterators and references | |
1351 | //! | |
1352 | //! Erasing an element invalidates iterators and references | |
1353 | //! pointing to elements that come after (their keys are bigger) the erased element. | |
1354 | //! | |
1355 | //! This container provides random-access iterators. | |
1356 | //! | |
1357 | //! \tparam Key is the key_type of the map | |
1358 | //! \tparam Value is the <code>mapped_type</code> | |
1359 | //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). | |
1360 | //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s | |
1361 | //! (e.g. <i>allocator< std::pair<Key, T> > </i>). | |
1362 | #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED | |
1363 | template <class Key, class T, class Compare = std::less<Key>, class Allocator = new_allocator< std::pair< Key, T> > > | |
1364 | #else | |
1365 | template <class Key, class T, class Compare, class Allocator> | |
1366 | #endif | |
1367 | class flat_multimap | |
1368 | { | |
1369 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
1370 | private: | |
1371 | BOOST_COPYABLE_AND_MOVABLE(flat_multimap) | |
1372 | typedef container_detail::flat_tree< | |
1373 | std::pair<Key, T>, | |
1374 | container_detail::select1st<Key>, | |
1375 | Compare, | |
1376 | Allocator> tree_t; | |
1377 | //This is the real tree stored here. It's based on a movable pair | |
1378 | typedef container_detail::flat_tree< | |
1379 | container_detail::pair<Key, T>, | |
1380 | container_detail::select1st<Key>, | |
1381 | Compare, | |
1382 | typename allocator_traits<Allocator>::template portable_rebind_alloc | |
1383 | <container_detail::pair<Key, T> >::type> impl_tree_t; | |
1384 | impl_tree_t m_flat_tree; // flat tree representing flat_map | |
1385 | ||
1386 | typedef typename impl_tree_t::value_type impl_value_type; | |
1387 | typedef typename impl_tree_t::const_iterator impl_const_iterator; | |
1388 | typedef typename impl_tree_t::iterator impl_iterator; | |
1389 | typedef typename impl_tree_t::allocator_type impl_allocator_type; | |
1390 | typedef container_detail::flat_tree_value_compare | |
1391 | < Compare | |
1392 | , container_detail::select1st<Key> | |
1393 | , std::pair<Key, T> > value_compare_impl; | |
1394 | typedef typename container_detail::get_flat_tree_iterators | |
1395 | <typename allocator_traits<Allocator>::pointer>::iterator iterator_impl; | |
1396 | typedef typename container_detail::get_flat_tree_iterators | |
1397 | <typename allocator_traits<Allocator>::pointer>::const_iterator const_iterator_impl; | |
1398 | typedef typename container_detail::get_flat_tree_iterators | |
1399 | <typename allocator_traits<Allocator>::pointer>::reverse_iterator reverse_iterator_impl; | |
1400 | typedef typename container_detail::get_flat_tree_iterators | |
1401 | <typename allocator_traits<Allocator>::pointer>::const_reverse_iterator const_reverse_iterator_impl; | |
1402 | public: | |
1403 | typedef typename impl_tree_t::stored_allocator_type impl_stored_allocator_type; | |
1404 | ||
1405 | impl_tree_t &tree() | |
1406 | { return m_flat_tree; } | |
1407 | ||
1408 | const impl_tree_t &tree() const | |
1409 | { return m_flat_tree; } | |
1410 | ||
1411 | private: | |
1412 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
1413 | ||
1414 | public: | |
1415 | ||
1416 | ////////////////////////////////////////////// | |
1417 | // | |
1418 | // types | |
1419 | // | |
1420 | ////////////////////////////////////////////// | |
1421 | typedef Key key_type; | |
1422 | typedef T mapped_type; | |
1423 | typedef std::pair<Key, T> value_type; | |
1424 | typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type; | |
1425 | typedef typename boost::container::allocator_traits<Allocator>::pointer pointer; | |
1426 | typedef typename boost::container::allocator_traits<Allocator>::const_pointer const_pointer; | |
1427 | typedef typename boost::container::allocator_traits<Allocator>::reference reference; | |
1428 | typedef typename boost::container::allocator_traits<Allocator>::const_reference const_reference; | |
1429 | typedef typename boost::container::allocator_traits<Allocator>::size_type size_type; | |
1430 | typedef typename boost::container::allocator_traits<Allocator>::difference_type difference_type; | |
1431 | typedef Allocator allocator_type; | |
1432 | typedef BOOST_CONTAINER_IMPDEF(Allocator) stored_allocator_type; | |
1433 | typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare; | |
1434 | typedef Compare key_compare; | |
1435 | typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator; | |
1436 | typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator; | |
1437 | typedef BOOST_CONTAINER_IMPDEF(reverse_iterator_impl) reverse_iterator; | |
1438 | typedef BOOST_CONTAINER_IMPDEF(const_reverse_iterator_impl) const_reverse_iterator; | |
1439 | typedef BOOST_CONTAINER_IMPDEF(impl_value_type) movable_value_type; | |
1440 | ||
1441 | ////////////////////////////////////////////// | |
1442 | // | |
1443 | // construct/copy/destroy | |
1444 | // | |
1445 | ////////////////////////////////////////////// | |
1446 | ||
1447 | //! <b>Effects</b>: Default constructs an empty flat_map. | |
1448 | //! | |
1449 | //! <b>Complexity</b>: Constant. | |
1450 | flat_multimap() BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value && | |
1451 | container_detail::is_nothrow_default_constructible<Compare>::value) | |
1452 | : m_flat_tree() | |
1453 | { | |
1454 | //value_type must be std::pair<Key, T> | |
1455 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
1456 | } | |
1457 | ||
1458 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison | |
1459 | //! object and allocator. | |
1460 | //! | |
1461 | //! <b>Complexity</b>: Constant. | |
1462 | explicit flat_multimap(const Compare& comp, | |
1463 | const allocator_type& a = allocator_type()) | |
1464 | : m_flat_tree(comp, container_detail::force<impl_allocator_type>(a)) | |
1465 | { | |
1466 | //value_type must be std::pair<Key, T> | |
1467 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
1468 | } | |
1469 | ||
1470 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified allocator. | |
1471 | //! | |
1472 | //! <b>Complexity</b>: Constant. | |
1473 | explicit flat_multimap(const allocator_type& a) | |
1474 | : m_flat_tree(container_detail::force<impl_allocator_type>(a)) | |
1475 | { | |
1476 | //value_type must be std::pair<Key, T> | |
1477 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
1478 | } | |
1479 | ||
1480 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object | |
1481 | //! and allocator, and inserts elements from the range [first ,last ). | |
1482 | //! | |
1483 | //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using | |
1484 | //! comp and otherwise N logN, where N is last - first. | |
1485 | template <class InputIterator> | |
1486 | flat_multimap(InputIterator first, InputIterator last, | |
1487 | const Compare& comp = Compare(), | |
1488 | const allocator_type& a = allocator_type()) | |
1489 | : m_flat_tree(false, first, last, comp, container_detail::force<impl_allocator_type>(a)) | |
1490 | { | |
1491 | //value_type must be std::pair<Key, T> | |
1492 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
1493 | } | |
1494 | ||
1495 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified | |
1496 | //! allocator, and inserts elements from the range [first ,last ). | |
1497 | //! | |
1498 | //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using | |
1499 | //! comp and otherwise N logN, where N is last - first. | |
1500 | template <class InputIterator> | |
1501 | flat_multimap(InputIterator first, InputIterator last, const allocator_type& a) | |
1502 | : m_flat_tree(false, first, last, Compare(), container_detail::force<impl_allocator_type>(a)) | |
1503 | { | |
1504 | //value_type must be std::pair<Key, T> | |
1505 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
1506 | } | |
1507 | ||
1508 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and | |
1509 | //! allocator, and inserts elements from the ordered range [first ,last). This function | |
1510 | //! is more efficient than the normal range creation for ordered ranges. | |
1511 | //! | |
1512 | //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. | |
1513 | //! | |
1514 | //! <b>Complexity</b>: Linear in N. | |
1515 | //! | |
1516 | //! <b>Note</b>: Non-standard extension. | |
1517 | template <class InputIterator> | |
1518 | flat_multimap(ordered_range_t, InputIterator first, InputIterator last, | |
1519 | const Compare& comp = Compare(), | |
1520 | const allocator_type& a = allocator_type()) | |
1521 | : m_flat_tree(ordered_range, first, last, comp, a) | |
1522 | { | |
1523 | //value_type must be std::pair<Key, T> | |
1524 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
1525 | } | |
1526 | ||
1527 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
1528 | //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and | |
1529 | //! allocator, and inserts elements from the range [il.begin(), il.end()). | |
1530 | //! | |
1531 | //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using | |
1532 | //! comp and otherwise N logN, where N is last - first. | |
1533 | flat_multimap(std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type()) | |
1534 | : m_flat_tree(false, il.begin(), il.end(), comp, container_detail::force<impl_allocator_type>(a)) | |
1535 | { | |
1536 | //value_type must be std::pair<Key, T> | |
1537 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
1538 | } | |
1539 | ||
1540 | //! <b>Effects</b>: Constructs an empty flat_map using the specified | |
1541 | //! allocator, and inserts elements from the range [il.begin(), il.end()). | |
1542 | //! | |
1543 | //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using | |
1544 | //! comp and otherwise N logN, where N is last - first. | |
1545 | flat_multimap(std::initializer_list<value_type> il, const allocator_type& a) | |
1546 | : m_flat_tree(false, il.begin(), il.end(), Compare(), container_detail::force<impl_allocator_type>(a)) | |
1547 | { | |
1548 | //value_type must be std::pair<Key, T> | |
1549 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
1550 | } | |
1551 | ||
1552 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and | |
1553 | //! allocator, and inserts elements from the ordered range [il.begin(), il.end()). This function | |
1554 | //! is more efficient than the normal range creation for ordered ranges. | |
1555 | //! | |
1556 | //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate. | |
1557 | //! | |
1558 | //! <b>Complexity</b>: Linear in N. | |
1559 | //! | |
1560 | //! <b>Note</b>: Non-standard extension. | |
1561 | flat_multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(), | |
1562 | const allocator_type& a = allocator_type()) | |
1563 | : m_flat_tree(ordered_range, il.begin(), il.end(), comp, a) | |
1564 | { | |
1565 | //value_type must be std::pair<Key, T> | |
1566 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
1567 | } | |
1568 | #endif | |
1569 | ||
1570 | //! <b>Effects</b>: Copy constructs a flat_multimap. | |
1571 | //! | |
1572 | //! <b>Complexity</b>: Linear in x.size(). | |
1573 | flat_multimap(const flat_multimap& x) | |
1574 | : m_flat_tree(x.m_flat_tree) | |
1575 | { | |
1576 | //value_type must be std::pair<Key, T> | |
1577 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
1578 | } | |
1579 | ||
1580 | //! <b>Effects</b>: Move constructs a flat_multimap. Constructs *this using x's resources. | |
1581 | //! | |
1582 | //! <b>Complexity</b>: Constant. | |
1583 | //! | |
1584 | //! <b>Postcondition</b>: x is emptied. | |
1585 | flat_multimap(BOOST_RV_REF(flat_multimap) x) | |
1586 | BOOST_NOEXCEPT_IF(boost::container::container_detail::is_nothrow_move_constructible<Compare>::value) | |
1587 | : m_flat_tree(boost::move(x.m_flat_tree)) | |
1588 | { | |
1589 | //value_type must be std::pair<Key, T> | |
1590 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
1591 | } | |
1592 | ||
1593 | //! <b>Effects</b>: Copy constructs a flat_multimap using the specified allocator. | |
1594 | //! | |
1595 | //! <b>Complexity</b>: Linear in x.size(). | |
1596 | flat_multimap(const flat_multimap& x, const allocator_type &a) | |
1597 | : m_flat_tree(x.m_flat_tree, a) | |
1598 | { | |
1599 | //value_type must be std::pair<Key, T> | |
1600 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
1601 | } | |
1602 | ||
1603 | //! <b>Effects</b>: Move constructs a flat_multimap using the specified allocator. | |
1604 | //! Constructs *this using x's resources. | |
1605 | //! | |
1606 | //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. | |
1607 | flat_multimap(BOOST_RV_REF(flat_multimap) x, const allocator_type &a) | |
1608 | : m_flat_tree(boost::move(x.m_flat_tree), a) | |
1609 | { | |
1610 | //value_type must be std::pair<Key, T> | |
1611 | BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value)); | |
1612 | } | |
1613 | ||
1614 | //! <b>Effects</b>: Makes *this a copy of x. | |
1615 | //! | |
1616 | //! <b>Complexity</b>: Linear in x.size(). | |
1617 | flat_multimap& operator=(BOOST_COPY_ASSIGN_REF(flat_multimap) x) | |
1618 | { m_flat_tree = x.m_flat_tree; return *this; } | |
1619 | ||
1620 | //! <b>Effects</b>: this->swap(x.get()). | |
1621 | //! | |
1622 | //! <b>Complexity</b>: Constant. | |
1623 | flat_multimap& operator=(BOOST_RV_REF(flat_multimap) x) | |
1624 | BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value || | |
1625 | allocator_traits_type::is_always_equal::value) && | |
1626 | boost::container::container_detail::is_nothrow_move_assignable<Compare>::value) | |
1627 | { m_flat_tree = boost::move(x.m_flat_tree); return *this; } | |
1628 | ||
1629 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
1630 | //! <b>Effects</b>: Assign content of il to *this | |
1631 | //! | |
1632 | //! <b>Complexity</b>: Linear in il.size(). | |
1633 | flat_multimap& operator=(std::initializer_list<value_type> il) | |
1634 | { | |
1635 | this->clear(); | |
1636 | this->insert(il.begin(), il.end()); | |
1637 | return *this; | |
1638 | } | |
1639 | #endif | |
1640 | ||
1641 | //! <b>Effects</b>: Returns a copy of the allocator that | |
1642 | //! was passed to the object's constructor. | |
1643 | //! | |
1644 | //! <b>Complexity</b>: Constant. | |
1645 | allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW | |
1646 | { return container_detail::force_copy<allocator_type>(m_flat_tree.get_allocator()); } | |
1647 | ||
1648 | //! <b>Effects</b>: Returns a reference to the internal allocator. | |
1649 | //! | |
1650 | //! <b>Throws</b>: Nothing | |
1651 | //! | |
1652 | //! <b>Complexity</b>: Constant. | |
1653 | //! | |
1654 | //! <b>Note</b>: Non-standard extension. | |
1655 | stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW | |
1656 | { return container_detail::force<stored_allocator_type>(m_flat_tree.get_stored_allocator()); } | |
1657 | ||
1658 | //! <b>Effects</b>: Returns a reference to the internal allocator. | |
1659 | //! | |
1660 | //! <b>Throws</b>: Nothing | |
1661 | //! | |
1662 | //! <b>Complexity</b>: Constant. | |
1663 | //! | |
1664 | //! <b>Note</b>: Non-standard extension. | |
1665 | const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW | |
1666 | { return container_detail::force<stored_allocator_type>(m_flat_tree.get_stored_allocator()); } | |
1667 | ||
1668 | ////////////////////////////////////////////// | |
1669 | // | |
1670 | // iterators | |
1671 | // | |
1672 | ////////////////////////////////////////////// | |
1673 | ||
1674 | //! <b>Effects</b>: Returns an iterator to the first element contained in the container. | |
1675 | //! | |
1676 | //! <b>Throws</b>: Nothing. | |
1677 | //! | |
1678 | //! <b>Complexity</b>: Constant. | |
1679 | iterator begin() BOOST_NOEXCEPT_OR_NOTHROW | |
1680 | { return container_detail::force_copy<iterator>(m_flat_tree.begin()); } | |
1681 | ||
1682 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. | |
1683 | //! | |
1684 | //! <b>Throws</b>: Nothing. | |
1685 | //! | |
1686 | //! <b>Complexity</b>: Constant. | |
1687 | const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW | |
1688 | { return container_detail::force_copy<const_iterator>(m_flat_tree.begin()); } | |
1689 | ||
1690 | //! <b>Effects</b>: Returns an iterator to the end of the container. | |
1691 | //! | |
1692 | //! <b>Throws</b>: Nothing. | |
1693 | //! | |
1694 | //! <b>Complexity</b>: Constant. | |
1695 | iterator end() BOOST_NOEXCEPT_OR_NOTHROW | |
1696 | { return container_detail::force_copy<iterator>(m_flat_tree.end()); } | |
1697 | ||
1698 | //! <b>Effects</b>: Returns a const_iterator to the end of the container. | |
1699 | //! | |
1700 | //! <b>Throws</b>: Nothing. | |
1701 | //! | |
1702 | //! <b>Complexity</b>: Constant. | |
1703 | const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW | |
1704 | { return container_detail::force_copy<const_iterator>(m_flat_tree.end()); } | |
1705 | ||
1706 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning | |
1707 | //! of the reversed container. | |
1708 | //! | |
1709 | //! <b>Throws</b>: Nothing. | |
1710 | //! | |
1711 | //! <b>Complexity</b>: Constant. | |
1712 | reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW | |
1713 | { return container_detail::force_copy<reverse_iterator>(m_flat_tree.rbegin()); } | |
1714 | ||
1715 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning | |
1716 | //! of the reversed container. | |
1717 | //! | |
1718 | //! <b>Throws</b>: Nothing. | |
1719 | //! | |
1720 | //! <b>Complexity</b>: Constant. | |
1721 | const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW | |
1722 | { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.rbegin()); } | |
1723 | ||
1724 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the end | |
1725 | //! of the reversed container. | |
1726 | //! | |
1727 | //! <b>Throws</b>: Nothing. | |
1728 | //! | |
1729 | //! <b>Complexity</b>: Constant. | |
1730 | reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW | |
1731 | { return container_detail::force_copy<reverse_iterator>(m_flat_tree.rend()); } | |
1732 | ||
1733 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end | |
1734 | //! of the reversed container. | |
1735 | //! | |
1736 | //! <b>Throws</b>: Nothing. | |
1737 | //! | |
1738 | //! <b>Complexity</b>: Constant. | |
1739 | const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW | |
1740 | { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.rend()); } | |
1741 | ||
1742 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. | |
1743 | //! | |
1744 | //! <b>Throws</b>: Nothing. | |
1745 | //! | |
1746 | //! <b>Complexity</b>: Constant. | |
1747 | const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW | |
1748 | { return container_detail::force_copy<const_iterator>(m_flat_tree.cbegin()); } | |
1749 | ||
1750 | //! <b>Effects</b>: Returns a const_iterator to the end of the container. | |
1751 | //! | |
1752 | //! <b>Throws</b>: Nothing. | |
1753 | //! | |
1754 | //! <b>Complexity</b>: Constant. | |
1755 | const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW | |
1756 | { return container_detail::force_copy<const_iterator>(m_flat_tree.cend()); } | |
1757 | ||
1758 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning | |
1759 | //! of the reversed container. | |
1760 | //! | |
1761 | //! <b>Throws</b>: Nothing. | |
1762 | //! | |
1763 | //! <b>Complexity</b>: Constant. | |
1764 | const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW | |
1765 | { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.crbegin()); } | |
1766 | ||
1767 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end | |
1768 | //! of the reversed container. | |
1769 | //! | |
1770 | //! <b>Throws</b>: Nothing. | |
1771 | //! | |
1772 | //! <b>Complexity</b>: Constant. | |
1773 | const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW | |
1774 | { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.crend()); } | |
1775 | ||
1776 | ////////////////////////////////////////////// | |
1777 | // | |
1778 | // capacity | |
1779 | // | |
1780 | ////////////////////////////////////////////// | |
1781 | ||
1782 | //! <b>Effects</b>: Returns true if the container contains no elements. | |
1783 | //! | |
1784 | //! <b>Throws</b>: Nothing. | |
1785 | //! | |
1786 | //! <b>Complexity</b>: Constant. | |
1787 | bool empty() const BOOST_NOEXCEPT_OR_NOTHROW | |
1788 | { return m_flat_tree.empty(); } | |
1789 | ||
1790 | //! <b>Effects</b>: Returns the number of the elements contained in the container. | |
1791 | //! | |
1792 | //! <b>Throws</b>: Nothing. | |
1793 | //! | |
1794 | //! <b>Complexity</b>: Constant. | |
1795 | size_type size() const BOOST_NOEXCEPT_OR_NOTHROW | |
1796 | { return m_flat_tree.size(); } | |
1797 | ||
1798 | //! <b>Effects</b>: Returns the largest possible size of the container. | |
1799 | //! | |
1800 | //! <b>Throws</b>: Nothing. | |
1801 | //! | |
1802 | //! <b>Complexity</b>: Constant. | |
1803 | size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW | |
1804 | { return m_flat_tree.max_size(); } | |
1805 | ||
1806 | //! <b>Effects</b>: Number of elements for which memory has been allocated. | |
1807 | //! capacity() is always greater than or equal to size(). | |
1808 | //! | |
1809 | //! <b>Throws</b>: Nothing. | |
1810 | //! | |
1811 | //! <b>Complexity</b>: Constant. | |
1812 | size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW | |
1813 | { return m_flat_tree.capacity(); } | |
1814 | ||
1815 | //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no | |
1816 | //! effect. Otherwise, it is a request for allocation of additional memory. | |
1817 | //! If the request is successful, then capacity() is greater than or equal to | |
1818 | //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged. | |
1819 | //! | |
1820 | //! <b>Throws</b>: If memory allocation allocation throws or T's copy constructor throws. | |
1821 | //! | |
1822 | //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to | |
1823 | //! to values might be invalidated. | |
1824 | void reserve(size_type cnt) | |
1825 | { m_flat_tree.reserve(cnt); } | |
1826 | ||
1827 | //! <b>Effects</b>: Tries to deallocate the excess of memory created | |
1828 | // with previous allocations. The size of the vector is unchanged | |
1829 | //! | |
1830 | //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. | |
1831 | //! | |
1832 | //! <b>Complexity</b>: Linear to size(). | |
1833 | void shrink_to_fit() | |
1834 | { m_flat_tree.shrink_to_fit(); } | |
1835 | ||
1836 | //! @copydoc ::boost::container::flat_set::nth(size_type) | |
1837 | iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW | |
1838 | { return container_detail::force_copy<iterator>(m_flat_tree.nth(n)); } | |
1839 | ||
1840 | //! @copydoc ::boost::container::flat_set::nth(size_type) const | |
1841 | const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW | |
1842 | { return container_detail::force_copy<iterator>(m_flat_tree.nth(n)); } | |
1843 | ||
1844 | //! @copydoc ::boost::container::flat_set::index_of(iterator) | |
1845 | size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW | |
1846 | { return m_flat_tree.index_of(container_detail::force_copy<impl_iterator>(p)); } | |
1847 | ||
1848 | //! @copydoc ::boost::container::flat_set::index_of(const_iterator) const | |
1849 | size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW | |
1850 | { return m_flat_tree.index_of(container_detail::force_copy<impl_const_iterator>(p)); } | |
1851 | ||
1852 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1853 | ||
1854 | //! <b>Effects</b>: Inserts an object of type T constructed with | |
1855 | //! std::forward<Args>(args)... and returns the iterator pointing to the | |
1856 | //! newly inserted element. | |
1857 | //! | |
1858 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
1859 | //! to the elements with bigger keys than x. | |
1860 | //! | |
1861 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1862 | template <class... Args> | |
1863 | iterator emplace(BOOST_FWD_REF(Args)... args) | |
1864 | { return container_detail::force_copy<iterator>(m_flat_tree.emplace_equal(boost::forward<Args>(args)...)); } | |
1865 | ||
1866 | //! <b>Effects</b>: Inserts an object of type T constructed with | |
1867 | //! std::forward<Args>(args)... in the container. | |
1868 | //! p is a hint pointing to where the insert should start to search. | |
1869 | //! | |
1870 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent | |
1871 | //! to the key of x. | |
1872 | //! | |
1873 | //! <b>Complexity</b>: Logarithmic search time (constant time if the value | |
1874 | //! is to be inserted before p) plus linear insertion | |
1875 | //! to the elements with bigger keys than x. | |
1876 | //! | |
1877 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1878 | template <class... Args> | |
1879 | iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args) | |
1880 | { | |
1881 | return container_detail::force_copy<iterator>(m_flat_tree.emplace_hint_equal | |
1882 | (container_detail::force_copy<impl_const_iterator>(hint), boost::forward<Args>(args)...)); | |
1883 | } | |
1884 | ||
1885 | #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
1886 | ||
1887 | #define BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE(N) \ | |
1888 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1889 | iterator emplace(BOOST_MOVE_UREF##N)\ | |
1890 | { return container_detail::force_copy<iterator>(m_flat_tree.emplace_equal(BOOST_MOVE_FWD##N)); }\ | |
1891 | \ | |
1892 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1893 | iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
1894 | {\ | |
1895 | return container_detail::force_copy<iterator>(m_flat_tree.emplace_hint_equal\ | |
1896 | (container_detail::force_copy<impl_const_iterator>(hint) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\ | |
1897 | }\ | |
1898 | // | |
1899 | BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE) | |
1900 | #undef BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE | |
1901 | ||
1902 | #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
1903 | ||
1904 | //! <b>Effects</b>: Inserts x and returns the iterator pointing to the | |
1905 | //! newly inserted element. | |
1906 | //! | |
1907 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
1908 | //! to the elements with bigger keys than x. | |
1909 | //! | |
1910 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1911 | iterator insert(const value_type& x) | |
1912 | { | |
1913 | return container_detail::force_copy<iterator>( | |
1914 | m_flat_tree.insert_equal(container_detail::force<impl_value_type>(x))); | |
1915 | } | |
1916 | ||
1917 | //! <b>Effects</b>: Inserts a new value move-constructed from x and returns | |
1918 | //! the iterator pointing to the newly inserted element. | |
1919 | //! | |
1920 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
1921 | //! to the elements with bigger keys than x. | |
1922 | //! | |
1923 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1924 | iterator insert(BOOST_RV_REF(value_type) x) | |
1925 | { return container_detail::force_copy<iterator>(m_flat_tree.insert_equal(boost::move(x))); } | |
1926 | ||
1927 | //! <b>Effects</b>: Inserts a new value move-constructed from x and returns | |
1928 | //! the iterator pointing to the newly inserted element. | |
1929 | //! | |
1930 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
1931 | //! to the elements with bigger keys than x. | |
1932 | //! | |
1933 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1934 | iterator insert(BOOST_RV_REF(impl_value_type) x) | |
1935 | { return container_detail::force_copy<iterator>(m_flat_tree.insert_equal(boost::move(x))); } | |
1936 | ||
1937 | //! <b>Effects</b>: Inserts a copy of x in the container. | |
1938 | //! p is a hint pointing to where the insert should start to search. | |
1939 | //! | |
1940 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent | |
1941 | //! to the key of x. | |
1942 | //! | |
1943 | //! <b>Complexity</b>: Logarithmic search time (constant time if the value | |
1944 | //! is to be inserted before p) plus linear insertion | |
1945 | //! to the elements with bigger keys than x. | |
1946 | //! | |
1947 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1948 | iterator insert(const_iterator p, const value_type& x) | |
1949 | { | |
1950 | return container_detail::force_copy<iterator> | |
1951 | (m_flat_tree.insert_equal( container_detail::force_copy<impl_const_iterator>(p) | |
1952 | , container_detail::force<impl_value_type>(x))); | |
1953 | } | |
1954 | ||
1955 | //! <b>Effects</b>: Inserts a value move constructed from x in the container. | |
1956 | //! p is a hint pointing to where the insert should start to search. | |
1957 | //! | |
1958 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent | |
1959 | //! to the key of x. | |
1960 | //! | |
1961 | //! <b>Complexity</b>: Logarithmic search time (constant time if the value | |
1962 | //! is to be inserted before p) plus linear insertion | |
1963 | //! to the elements with bigger keys than x. | |
1964 | //! | |
1965 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1966 | iterator insert(const_iterator p, BOOST_RV_REF(value_type) x) | |
1967 | { | |
1968 | return container_detail::force_copy<iterator> | |
1969 | (m_flat_tree.insert_equal(container_detail::force_copy<impl_const_iterator>(p) | |
1970 | , boost::move(x))); | |
1971 | } | |
1972 | ||
1973 | //! <b>Effects</b>: Inserts a value move constructed from x in the container. | |
1974 | //! p is a hint pointing to where the insert should start to search. | |
1975 | //! | |
1976 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent | |
1977 | //! to the key of x. | |
1978 | //! | |
1979 | //! <b>Complexity</b>: Logarithmic search time (constant time if the value | |
1980 | //! is to be inserted before p) plus linear insertion | |
1981 | //! to the elements with bigger keys than x. | |
1982 | //! | |
1983 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1984 | iterator insert(const_iterator p, BOOST_RV_REF(impl_value_type) x) | |
1985 | { | |
1986 | return container_detail::force_copy<iterator>( | |
1987 | m_flat_tree.insert_equal(container_detail::force_copy<impl_const_iterator>(p), boost::move(x))); | |
1988 | } | |
1989 | ||
1990 | //! <b>Requires</b>: first, last are not iterators into *this. | |
1991 | //! | |
1992 | //! <b>Effects</b>: inserts each element from the range [first,last) . | |
1993 | //! | |
1994 | //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) | |
1995 | //! search time plus N*size() insertion time. | |
1996 | //! | |
1997 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1998 | template <class InputIterator> | |
1999 | void insert(InputIterator first, InputIterator last) | |
2000 | { m_flat_tree.insert_equal(first, last); } | |
2001 | ||
2002 | //! <b>Requires</b>: first, last are not iterators into *this. | |
2003 | //! | |
2004 | //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. | |
2005 | //! | |
2006 | //! <b>Effects</b>: inserts each element from the range [first,last) if and only | |
2007 | //! if there is no element with key equivalent to the key of that element. This | |
2008 | //! function is more efficient than the normal range creation for ordered ranges. | |
2009 | //! | |
2010 | //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) | |
2011 | //! search time plus N*size() insertion time. | |
2012 | //! | |
2013 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
2014 | //! | |
2015 | //! <b>Note</b>: Non-standard extension. | |
2016 | template <class InputIterator> | |
2017 | void insert(ordered_range_t, InputIterator first, InputIterator last) | |
2018 | { m_flat_tree.insert_equal(ordered_range, first, last); } | |
2019 | ||
2020 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
2021 | //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) . | |
2022 | //! | |
2023 | //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) | |
2024 | //! search time plus N*size() insertion time. | |
2025 | //! | |
2026 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
2027 | void insert(std::initializer_list<value_type> il) | |
2028 | { m_flat_tree.insert_equal(il.begin(), il.end()); } | |
2029 | ||
2030 | //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate. | |
2031 | //! | |
2032 | //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only | |
2033 | //! if there is no element with key equivalent to the key of that element. This | |
2034 | //! function is more efficient than the normal range creation for ordered ranges. | |
2035 | //! | |
2036 | //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) | |
2037 | //! search time plus N*size() insertion time. | |
2038 | //! | |
2039 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
2040 | //! | |
2041 | //! <b>Note</b>: Non-standard extension. | |
2042 | void insert(ordered_range_t, std::initializer_list<value_type> il) | |
2043 | { m_flat_tree.insert_equal(ordered_range, il.begin(), il.end()); } | |
2044 | #endif | |
2045 | ||
2046 | //! <b>Requires</b>: this->get_allocator() == source.get_allocator(). | |
2047 | //! | |
2048 | //! <b>Effects</b>: Extracts each element in source and insert it into a using | |
2049 | //! the comparison object of *this. | |
2050 | //! | |
2051 | //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer | |
2052 | //! to those same elements but as members of *this. Iterators referring to the transferred | |
2053 | //! elements will continue to refer to their elements, but they now behave as iterators into *this, | |
2054 | //! not into source. | |
2055 | //! | |
2056 | //! <b>Throws</b>: Nothing unless the comparison object throws. | |
2057 | //! | |
2058 | //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size()) | |
2059 | template<class C2> | |
2060 | void merge(flat_multimap<Key, T, C2, Allocator>& source) | |
2061 | { m_flat_tree.merge_equal(source.tree()); } | |
2062 | ||
2063 | //! @copydoc ::boost::container::flat_multimap::merge(flat_multimap<Key, T, C2, Allocator>&) | |
2064 | template<class C2> | |
2065 | void merge(BOOST_RV_REF_BEG flat_multimap<Key, T, C2, Allocator> BOOST_RV_REF_END source) | |
2066 | { return this->merge(static_cast<flat_multimap<Key, T, C2, Allocator>&>(source)); } | |
2067 | ||
2068 | //! @copydoc ::boost::container::flat_multimap::merge(flat_multimap<Key, T, C2, Allocator>&) | |
2069 | template<class C2> | |
2070 | void merge(flat_map<Key, T, C2, Allocator>& source) | |
2071 | { m_flat_tree.merge_equal(source.tree()); } | |
2072 | ||
2073 | //! @copydoc ::boost::container::flat_multimap::merge(flat_multimap<Key, T, C2, Allocator>&) | |
2074 | template<class C2> | |
2075 | void merge(BOOST_RV_REF_BEG flat_map<Key, T, C2, Allocator> BOOST_RV_REF_END source) | |
2076 | { return this->merge(static_cast<flat_map<Key, T, C2, Allocator>&>(source)); } | |
2077 | ||
2078 | //! <b>Effects</b>: Erases the element pointed to by p. | |
2079 | //! | |
2080 | //! <b>Returns</b>: Returns an iterator pointing to the element immediately | |
2081 | //! following q prior to the element being erased. If no such element exists, | |
2082 | //! returns end(). | |
2083 | //! | |
2084 | //! <b>Complexity</b>: Linear to the elements with keys bigger than p | |
2085 | //! | |
2086 | //! <b>Note</b>: Invalidates elements with keys | |
2087 | //! not less than the erased element. | |
2088 | iterator erase(const_iterator p) | |
2089 | { | |
2090 | return container_detail::force_copy<iterator>( | |
2091 | m_flat_tree.erase(container_detail::force_copy<impl_const_iterator>(p))); | |
2092 | } | |
2093 | ||
2094 | //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. | |
2095 | //! | |
2096 | //! <b>Returns</b>: Returns the number of erased elements. | |
2097 | //! | |
2098 | //! <b>Complexity</b>: Logarithmic search time plus erasure time | |
2099 | //! linear to the elements with bigger keys. | |
2100 | size_type erase(const key_type& x) | |
2101 | { return m_flat_tree.erase(x); } | |
2102 | ||
2103 | //! <b>Effects</b>: Erases all the elements in the range [first, last). | |
2104 | //! | |
2105 | //! <b>Returns</b>: Returns last. | |
2106 | //! | |
2107 | //! <b>Complexity</b>: size()*N where N is the distance from first to last. | |
2108 | //! | |
2109 | //! <b>Complexity</b>: Logarithmic search time plus erasure time | |
2110 | //! linear to the elements with bigger keys. | |
2111 | iterator erase(const_iterator first, const_iterator last) | |
2112 | { | |
2113 | return container_detail::force_copy<iterator> | |
2114 | (m_flat_tree.erase( container_detail::force_copy<impl_const_iterator>(first) | |
2115 | , container_detail::force_copy<impl_const_iterator>(last))); | |
2116 | } | |
2117 | ||
2118 | //! <b>Effects</b>: Swaps the contents of *this and x. | |
2119 | //! | |
2120 | //! <b>Throws</b>: Nothing. | |
2121 | //! | |
2122 | //! <b>Complexity</b>: Constant. | |
2123 | void swap(flat_multimap& x) | |
2124 | BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value | |
2125 | && boost::container::container_detail::is_nothrow_swappable<Compare>::value ) | |
2126 | { m_flat_tree.swap(x.m_flat_tree); } | |
2127 | ||
2128 | //! <b>Effects</b>: erase(a.begin(),a.end()). | |
2129 | //! | |
2130 | //! <b>Postcondition</b>: size() == 0. | |
2131 | //! | |
2132 | //! <b>Complexity</b>: linear in size(). | |
2133 | void clear() BOOST_NOEXCEPT_OR_NOTHROW | |
2134 | { m_flat_tree.clear(); } | |
2135 | ||
2136 | ////////////////////////////////////////////// | |
2137 | // | |
2138 | // observers | |
2139 | // | |
2140 | ////////////////////////////////////////////// | |
2141 | ||
2142 | //! <b>Effects</b>: Returns the comparison object out | |
2143 | //! of which a was constructed. | |
2144 | //! | |
2145 | //! <b>Complexity</b>: Constant. | |
2146 | key_compare key_comp() const | |
2147 | { return container_detail::force_copy<key_compare>(m_flat_tree.key_comp()); } | |
2148 | ||
2149 | //! <b>Effects</b>: Returns an object of value_compare constructed out | |
2150 | //! of the comparison object. | |
2151 | //! | |
2152 | //! <b>Complexity</b>: Constant. | |
2153 | value_compare value_comp() const | |
2154 | { return value_compare(container_detail::force_copy<key_compare>(m_flat_tree.key_comp())); } | |
2155 | ||
2156 | ////////////////////////////////////////////// | |
2157 | // | |
2158 | // map operations | |
2159 | // | |
2160 | ////////////////////////////////////////////// | |
2161 | ||
2162 | //! <b>Returns</b>: An iterator pointing to an element with the key | |
2163 | //! equivalent to x, or end() if such an element is not found. | |
2164 | //! | |
2165 | //! <b>Complexity</b>: Logarithmic. | |
2166 | iterator find(const key_type& x) | |
2167 | { return container_detail::force_copy<iterator>(m_flat_tree.find(x)); } | |
2168 | ||
2169 | //! <b>Returns</b>: An const_iterator pointing to an element with the key | |
2170 | //! equivalent to x, or end() if such an element is not found. | |
2171 | //! | |
2172 | //! <b>Complexity</b>: Logarithmic. | |
2173 | const_iterator find(const key_type& x) const | |
2174 | { return container_detail::force_copy<const_iterator>(m_flat_tree.find(x)); } | |
2175 | ||
2176 | //! <b>Returns</b>: The number of elements with key equivalent to x. | |
2177 | //! | |
2178 | //! <b>Complexity</b>: log(size())+count(k) | |
2179 | size_type count(const key_type& x) const | |
2180 | { return m_flat_tree.count(x); } | |
2181 | ||
2182 | //! <b>Returns</b>: An iterator pointing to the first element with key not less | |
2183 | //! than k, or a.end() if such an element is not found. | |
2184 | //! | |
2185 | //! <b>Complexity</b>: Logarithmic | |
2186 | iterator lower_bound(const key_type& x) | |
2187 | { return container_detail::force_copy<iterator>(m_flat_tree.lower_bound(x)); } | |
2188 | ||
2189 | //! <b>Returns</b>: A const iterator pointing to the first element with key | |
2190 | //! not less than k, or a.end() if such an element is not found. | |
2191 | //! | |
2192 | //! <b>Complexity</b>: Logarithmic | |
2193 | const_iterator lower_bound(const key_type& x) const | |
2194 | { return container_detail::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); } | |
2195 | ||
2196 | //! <b>Returns</b>: An iterator pointing to the first element with key not less | |
2197 | //! than x, or end() if such an element is not found. | |
2198 | //! | |
2199 | //! <b>Complexity</b>: Logarithmic | |
2200 | iterator upper_bound(const key_type& x) | |
2201 | {return container_detail::force_copy<iterator>(m_flat_tree.upper_bound(x)); } | |
2202 | ||
2203 | //! <b>Returns</b>: A const iterator pointing to the first element with key | |
2204 | //! not less than x, or end() if such an element is not found. | |
2205 | //! | |
2206 | //! <b>Complexity</b>: Logarithmic | |
2207 | const_iterator upper_bound(const key_type& x) const | |
2208 | { return container_detail::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); } | |
2209 | ||
2210 | //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). | |
2211 | //! | |
2212 | //! <b>Complexity</b>: Logarithmic | |
2213 | std::pair<iterator,iterator> equal_range(const key_type& x) | |
2214 | { return container_detail::force_copy<std::pair<iterator,iterator> >(m_flat_tree.equal_range(x)); } | |
2215 | ||
2216 | //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). | |
2217 | //! | |
2218 | //! <b>Complexity</b>: Logarithmic | |
2219 | std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const | |
2220 | { return container_detail::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(x)); } | |
2221 | ||
2222 | //! <b>Effects</b>: Returns true if x and y are equal | |
2223 | //! | |
2224 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
2225 | friend bool operator==(const flat_multimap& x, const flat_multimap& y) | |
2226 | { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } | |
2227 | ||
2228 | //! <b>Effects</b>: Returns true if x and y are unequal | |
2229 | //! | |
2230 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
2231 | friend bool operator!=(const flat_multimap& x, const flat_multimap& y) | |
2232 | { return !(x == y); } | |
2233 | ||
2234 | //! <b>Effects</b>: Returns true if x is less than y | |
2235 | //! | |
2236 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
2237 | friend bool operator<(const flat_multimap& x, const flat_multimap& y) | |
2238 | { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } | |
2239 | ||
2240 | //! <b>Effects</b>: Returns true if x is greater than y | |
2241 | //! | |
2242 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
2243 | friend bool operator>(const flat_multimap& x, const flat_multimap& y) | |
2244 | { return y < x; } | |
2245 | ||
2246 | //! <b>Effects</b>: Returns true if x is equal or less than y | |
2247 | //! | |
2248 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
2249 | friend bool operator<=(const flat_multimap& x, const flat_multimap& y) | |
2250 | { return !(y < x); } | |
2251 | ||
2252 | //! <b>Effects</b>: Returns true if x is equal or greater than y | |
2253 | //! | |
2254 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
2255 | friend bool operator>=(const flat_multimap& x, const flat_multimap& y) | |
2256 | { return !(x < y); } | |
2257 | ||
2258 | //! <b>Effects</b>: x.swap(y) | |
2259 | //! | |
2260 | //! <b>Complexity</b>: Constant. | |
2261 | friend void swap(flat_multimap& x, flat_multimap& y) | |
2262 | { x.swap(y); } | |
2263 | }; | |
2264 | ||
2265 | }} | |
2266 | ||
2267 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
2268 | ||
2269 | namespace boost { | |
2270 | ||
2271 | //!has_trivial_destructor_after_move<> == true_type | |
2272 | //!specialization for optimizations | |
2273 | template <class Key, class T, class Compare, class Allocator> | |
2274 | struct has_trivial_destructor_after_move< boost::container::flat_multimap<Key, T, Compare, Allocator> > | |
2275 | { | |
2276 | typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; | |
2277 | static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && | |
2278 | ::boost::has_trivial_destructor_after_move<pointer>::value && | |
2279 | ::boost::has_trivial_destructor_after_move<Compare>::value; | |
2280 | }; | |
2281 | ||
2282 | } //namespace boost { | |
2283 | ||
2284 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
2285 | ||
2286 | #include <boost/container/detail/config_end.hpp> | |
2287 | ||
2288 | #endif // BOOST_CONTAINER_FLAT_MAP_HPP |