]>
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() | |
b32b8144 | 33 | #include <boost/container/detail/container_or_allocator_rebind.hpp> |
7c673cae FG |
34 | // move |
35 | #include <boost/move/utility_core.hpp> | |
36 | #include <boost/move/traits.hpp> | |
37 | // move/detail | |
38 | #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
39 | #include <boost/move/detail/fwd_macros.hpp> | |
40 | #endif | |
41 | #include <boost/move/detail/move_helpers.hpp> | |
42 | // intrusive | |
43 | #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair | |
44 | #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal | |
45 | //others | |
46 | #include <boost/core/no_exceptions_support.hpp> | |
47 | ||
48 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
49 | #include <initializer_list> | |
50 | #endif | |
51 | ||
52 | namespace boost { | |
53 | namespace container { | |
54 | ||
55 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
56 | ||
b32b8144 | 57 | template <class Key, class T, class Compare, class AllocatorOrContainer> |
7c673cae FG |
58 | class flat_multimap; |
59 | ||
11fdf7f2 | 60 | namespace dtl{ |
7c673cae FG |
61 | |
62 | template<class D, class S> | |
b32b8144 FG |
63 | BOOST_CONTAINER_FORCEINLINE static D &force(S &s) |
64 | { return *reinterpret_cast<D*>(&s); } | |
7c673cae FG |
65 | |
66 | template<class D, class S> | |
b32b8144 | 67 | BOOST_CONTAINER_FORCEINLINE static D force_copy(const S &s) |
7c673cae | 68 | { |
b32b8144 FG |
69 | const D *const vp = reinterpret_cast<const D *>(&s); |
70 | D ret_val(*vp); | |
71 | return ret_val; | |
7c673cae FG |
72 | } |
73 | ||
11fdf7f2 | 74 | } //namespace dtl{ |
7c673cae FG |
75 | |
76 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
77 | ||
78 | //! A flat_map is a kind of associative container that supports unique keys (contains at | |
79 | //! most one of each key value) and provides for fast retrieval of values of another | |
b32b8144 | 80 | //! type T based on the keys. |
7c673cae | 81 | //! |
b32b8144 FG |
82 | //! A flat_map satisfies all of the requirements of a container, a reversible |
83 | //! container and an associative container. A flat_map also provides | |
7c673cae FG |
84 | //! most operations described for unique keys. For a |
85 | //! flat_map<Key,T> the key_type is Key and the value_type is std::pair<Key,T> | |
86 | //! (unlike std::map<Key, T> which value_type is std::pair<<b>const</b> Key, T>). | |
87 | //! | |
b32b8144 FG |
88 | //! flat_map is similar to std::map but it's implemented by as an ordered sequence container. |
89 | //! The underlying sequence container is by default <i>vector</i> but it can also work | |
90 | //! user-provided vector-like SequenceContainers (like <i>static_vector</i> or <i>small_vector</i>). | |
7c673cae | 91 | //! |
b32b8144 FG |
92 | //! Using vector-like sequence containers means that inserting a new element into a flat_map might invalidate |
93 | //! previous iterators and references (unless that sequence container is <i>stable_vector</i> or a similar | |
94 | //! container that offers stable pointers and references). Similarly, erasing an element might invalidate | |
95 | //! iterators and references pointing to elements that come after (their keys are bigger) the erased element. | |
7c673cae FG |
96 | //! |
97 | //! This container provides random-access iterators. | |
98 | //! | |
99 | //! \tparam Key is the key_type of the map | |
100 | //! \tparam Value is the <code>mapped_type</code> | |
101 | //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). | |
b32b8144 FG |
102 | //! \tparam AllocatorOrContainer is either: |
103 | //! - The allocator to allocate <code>value_type</code>s (e.g. <i>allocator< std::pair<Key, T> > </i>). | |
104 | //! (in this case <i>sequence_type</i> will be vector<value_type, AllocatorOrContainer>) | |
105 | //! - The SequenceContainer to be used as the underlying <i>sequence_type</i>. It must be a vector-like | |
106 | //! sequence container with random-access iterators.. | |
7c673cae | 107 | #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED |
b32b8144 | 108 | template <class Key, class T, class Compare = std::less<Key>, class AllocatorOrContainer = new_allocator< std::pair< Key, T> > > |
7c673cae | 109 | #else |
b32b8144 | 110 | template <class Key, class T, class Compare, class AllocatorOrContainer> |
7c673cae FG |
111 | #endif |
112 | class flat_map | |
113 | { | |
114 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
115 | private: | |
116 | BOOST_COPYABLE_AND_MOVABLE(flat_map) | |
117 | //This is the tree that we should store if pair was movable | |
11fdf7f2 | 118 | typedef dtl::flat_tree< |
7c673cae | 119 | std::pair<Key, T>, |
11fdf7f2 | 120 | dtl::select1st<Key>, |
7c673cae | 121 | Compare, |
b32b8144 | 122 | AllocatorOrContainer> tree_t; |
7c673cae FG |
123 | |
124 | //This is the real tree stored here. It's based on a movable pair | |
11fdf7f2 TL |
125 | typedef dtl::flat_tree< |
126 | dtl::pair<Key, T>, | |
127 | dtl::select1st<Key>, | |
7c673cae | 128 | Compare, |
11fdf7f2 | 129 | typename dtl::container_or_allocator_rebind<AllocatorOrContainer, dtl::pair<Key, T> >::type |
b32b8144 | 130 | > impl_tree_t; |
7c673cae FG |
131 | impl_tree_t m_flat_tree; // flat tree representing flat_map |
132 | ||
133 | typedef typename impl_tree_t::value_type impl_value_type; | |
134 | typedef typename impl_tree_t::const_iterator impl_const_iterator; | |
135 | typedef typename impl_tree_t::iterator impl_iterator; | |
136 | typedef typename impl_tree_t::allocator_type impl_allocator_type; | |
b32b8144 FG |
137 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) |
138 | typedef std::initializer_list<impl_value_type> impl_initializer_list; | |
139 | #endif | |
140 | ||
11fdf7f2 | 141 | typedef dtl::flat_tree_value_compare |
7c673cae | 142 | < Compare |
11fdf7f2 | 143 | , dtl::select1st<Key> |
b32b8144 FG |
144 | , std::pair<Key, T> > value_compare_t; |
145 | typedef typename tree_t::iterator iterator_t; | |
146 | typedef typename tree_t::const_iterator const_iterator_t; | |
147 | typedef typename tree_t::reverse_iterator reverse_iterator_t; | |
148 | typedef typename tree_t::const_reverse_iterator const_reverse_iterator_t; | |
149 | ||
7c673cae FG |
150 | public: |
151 | typedef typename impl_tree_t::stored_allocator_type impl_stored_allocator_type; | |
b32b8144 | 152 | typedef typename impl_tree_t::sequence_type impl_sequence_type; |
7c673cae | 153 | |
b32b8144 | 154 | BOOST_CONTAINER_FORCEINLINE impl_tree_t &tree() |
7c673cae FG |
155 | { return m_flat_tree; } |
156 | ||
b32b8144 | 157 | BOOST_CONTAINER_FORCEINLINE const impl_tree_t &tree() const |
7c673cae FG |
158 | { return m_flat_tree; } |
159 | ||
160 | private: | |
b32b8144 FG |
161 | typedef typename tree_t::get_stored_allocator_const_return_t get_stored_allocator_const_return_t; |
162 | typedef typename tree_t::get_stored_allocator_noconst_return_t get_stored_allocator_noconst_return_t; | |
163 | typedef typename impl_tree_t::get_stored_allocator_const_return_t impl_get_stored_allocator_const_return_t; | |
164 | typedef typename impl_tree_t::get_stored_allocator_noconst_return_t impl_get_stored_allocator_noconst_return_t; | |
165 | ||
7c673cae FG |
166 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED |
167 | ||
168 | public: | |
169 | ||
170 | ////////////////////////////////////////////// | |
171 | // | |
172 | // types | |
173 | // | |
174 | ////////////////////////////////////////////// | |
175 | typedef Key key_type; | |
176 | typedef T mapped_type; | |
7c673cae | 177 | typedef Compare key_compare; |
b32b8144 FG |
178 | typedef std::pair<Key, T> value_type; |
179 | typedef typename BOOST_CONTAINER_IMPDEF(tree_t::sequence_type) sequence_type; | |
180 | typedef typename sequence_type::allocator_type allocator_type; | |
181 | typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type; | |
182 | typedef typename sequence_type::pointer pointer; | |
183 | typedef typename sequence_type::const_pointer const_pointer; | |
184 | typedef typename sequence_type::reference reference; | |
185 | typedef typename sequence_type::const_reference const_reference; | |
186 | typedef typename sequence_type::size_type size_type; | |
187 | typedef typename sequence_type::difference_type difference_type; | |
188 | typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type; | |
189 | typedef typename BOOST_CONTAINER_IMPDEF(tree_t::value_compare) value_compare; | |
190 | ||
191 | typedef typename sequence_type::iterator iterator; | |
192 | typedef typename sequence_type::const_iterator const_iterator; | |
193 | typedef typename sequence_type::reverse_iterator reverse_iterator; | |
194 | typedef typename sequence_type::const_reverse_iterator const_reverse_iterator; | |
7c673cae FG |
195 | typedef BOOST_CONTAINER_IMPDEF(impl_value_type) movable_value_type; |
196 | ||
b32b8144 | 197 | //AllocatorOrContainer::value_type must be std::pair<Key, T> |
92f5a8d4 | 198 | BOOST_STATIC_ASSERT((dtl::is_same<std::pair<Key, T>, value_type>::value)); |
b32b8144 | 199 | |
7c673cae FG |
200 | ////////////////////////////////////////////// |
201 | // | |
202 | // construct/copy/destroy | |
203 | // | |
204 | ////////////////////////////////////////////// | |
205 | ||
206 | //! <b>Effects</b>: Default constructs an empty flat_map. | |
207 | //! | |
208 | //! <b>Complexity</b>: Constant. | |
11fdf7f2 TL |
209 | BOOST_CONTAINER_FORCEINLINE flat_map() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<AllocatorOrContainer>::value && |
210 | dtl::is_nothrow_default_constructible<Compare>::value) | |
7c673cae | 211 | : m_flat_tree() |
b32b8144 FG |
212 | {} |
213 | ||
214 | //! <b>Effects</b>: Constructs an empty flat_map using the specified allocator. | |
215 | //! | |
216 | //! <b>Complexity</b>: Constant. | |
217 | BOOST_CONTAINER_FORCEINLINE explicit flat_map(const allocator_type& a) | |
11fdf7f2 | 218 | : m_flat_tree(dtl::force<const impl_allocator_type>(a)) |
b32b8144 | 219 | {} |
7c673cae FG |
220 | |
221 | //! <b>Effects</b>: Constructs an empty flat_map using the specified | |
b32b8144 | 222 | //! comparison object. |
7c673cae FG |
223 | //! |
224 | //! <b>Complexity</b>: Constant. | |
b32b8144 FG |
225 | BOOST_CONTAINER_FORCEINLINE explicit flat_map(const Compare& comp) |
226 | : m_flat_tree(comp) | |
227 | {} | |
7c673cae | 228 | |
b32b8144 FG |
229 | //! <b>Effects</b>: Constructs an empty flat_map using the specified |
230 | //! comparison object and allocator. | |
7c673cae FG |
231 | //! |
232 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 233 | BOOST_CONTAINER_FORCEINLINE flat_map(const Compare& comp, const allocator_type& a) |
11fdf7f2 | 234 | : m_flat_tree(comp, dtl::force<const impl_allocator_type>(a)) |
b32b8144 | 235 | {} |
7c673cae | 236 | |
b32b8144 FG |
237 | //! <b>Effects</b>: Constructs an empty flat_map and |
238 | //! and inserts elements from the range [first ,last ). | |
7c673cae FG |
239 | //! |
240 | //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using | |
b32b8144 | 241 | //! the predicate and otherwise N logN, where N is last - first. |
7c673cae | 242 | template <class InputIterator> |
b32b8144 FG |
243 | BOOST_CONTAINER_FORCEINLINE flat_map(InputIterator first, InputIterator last) |
244 | : m_flat_tree(true, first, last) | |
245 | {} | |
7c673cae FG |
246 | |
247 | //! <b>Effects</b>: Constructs an empty flat_map using the specified | |
248 | //! allocator, and inserts elements from the range [first ,last ). | |
249 | //! | |
250 | //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using | |
b32b8144 | 251 | //! the predicate and otherwise N logN, where N is last - first. |
7c673cae | 252 | template <class InputIterator> |
b32b8144 | 253 | BOOST_CONTAINER_FORCEINLINE flat_map(InputIterator first, InputIterator last, const allocator_type& a) |
11fdf7f2 | 254 | : m_flat_tree(true, first, last, dtl::force<const impl_allocator_type>(a)) |
b32b8144 FG |
255 | {} |
256 | ||
257 | //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and | |
258 | //! and inserts elements from the range [first ,last ). | |
259 | //! | |
260 | //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using | |
261 | //! the predicate and otherwise N logN, where N is last - first. | |
262 | template <class InputIterator> | |
263 | BOOST_CONTAINER_FORCEINLINE flat_map(InputIterator first, InputIterator last, const Compare& comp) | |
264 | : m_flat_tree(true, first, last, comp) | |
265 | {} | |
7c673cae FG |
266 | |
267 | //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and | |
b32b8144 FG |
268 | //! allocator, and inserts elements from the range [first ,last ). |
269 | //! | |
270 | //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using | |
271 | //! the predicate and otherwise N logN, where N is last - first. | |
272 | template <class InputIterator> | |
273 | BOOST_CONTAINER_FORCEINLINE flat_map(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a) | |
11fdf7f2 | 274 | : m_flat_tree(true, first, last, comp, dtl::force<const impl_allocator_type>(a)) |
b32b8144 FG |
275 | {} |
276 | ||
277 | //! <b>Effects</b>: Constructs an empty flat_map | |
278 | //! and inserts elements from the ordered range [first ,last). This function | |
7c673cae FG |
279 | //! is more efficient than the normal range creation for ordered ranges. |
280 | //! | |
b32b8144 | 281 | //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. |
7c673cae FG |
282 | //! |
283 | //! <b>Complexity</b>: Linear in N. | |
284 | //! | |
285 | //! <b>Note</b>: Non-standard extension. | |
286 | template <class InputIterator> | |
b32b8144 FG |
287 | BOOST_CONTAINER_FORCEINLINE |
288 | flat_map(ordered_unique_range_t, InputIterator first, InputIterator last) | |
289 | : m_flat_tree(ordered_range, first, last) | |
290 | {} | |
7c673cae | 291 | |
7c673cae | 292 | //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and |
b32b8144 FG |
293 | //! inserts elements from the ordered range [first ,last). This function |
294 | //! is more efficient than the normal range creation for ordered ranges. | |
295 | //! | |
296 | //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. | |
297 | //! | |
298 | //! <b>Complexity</b>: Linear in N. | |
299 | //! | |
300 | //! <b>Note</b>: Non-standard extension. | |
301 | template <class InputIterator> | |
302 | BOOST_CONTAINER_FORCEINLINE | |
303 | flat_map(ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp) | |
304 | : m_flat_tree(ordered_range, first, last, comp) | |
305 | {} | |
306 | ||
307 | //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and | |
308 | //! allocator, and inserts elements from the ordered range [first ,last). This function | |
309 | //! is more efficient than the normal range creation for ordered ranges. | |
310 | //! | |
311 | //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. | |
312 | //! | |
313 | //! <b>Complexity</b>: Linear in N. | |
314 | //! | |
315 | //! <b>Note</b>: Non-standard extension. | |
316 | template <class InputIterator> | |
317 | BOOST_CONTAINER_FORCEINLINE | |
318 | flat_map(ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a) | |
11fdf7f2 | 319 | : m_flat_tree(ordered_range, first, last, comp, dtl::force<const impl_allocator_type>(a)) |
b32b8144 FG |
320 | {} |
321 | ||
92f5a8d4 TL |
322 | //! <b>Effects</b>: Constructs an empty flat_map using the specified allocator and |
323 | //! inserts elements from the ordered range [first ,last). This function | |
324 | //! is more efficient than the normal range creation for ordered ranges. | |
325 | //! | |
326 | //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. | |
327 | //! | |
328 | //! <b>Complexity</b>: Linear in N. | |
329 | //! | |
330 | //! <b>Note</b>: Non-standard extension. | |
331 | template <class InputIterator> | |
332 | BOOST_CONTAINER_FORCEINLINE | |
333 | flat_map(ordered_unique_range_t, InputIterator first, InputIterator last, const allocator_type& a) | |
334 | : m_flat_tree(ordered_range, first, last, Compare(), a) | |
335 | {} | |
336 | ||
b32b8144 FG |
337 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) |
338 | //! <b>Effects</b>: Constructs an empty flat_map and | |
339 | //! inserts elements from the range [il.begin() ,il.end()). | |
7c673cae FG |
340 | //! |
341 | //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using | |
b32b8144 FG |
342 | //! the predicate and otherwise N logN, where N is last - first. |
343 | BOOST_CONTAINER_FORCEINLINE flat_map(std::initializer_list<value_type> il) | |
344 | : m_flat_tree( true | |
11fdf7f2 TL |
345 | , dtl::force<impl_initializer_list>(il).begin() |
346 | , dtl::force<impl_initializer_list>(il).end()) | |
b32b8144 | 347 | {} |
7c673cae FG |
348 | |
349 | //! <b>Effects</b>: Constructs an empty flat_map using the specified | |
350 | //! allocator, and inserts elements from the range [il.begin() ,il.end()). | |
351 | //! | |
352 | //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using | |
b32b8144 FG |
353 | //! the predicate and otherwise N logN, where N is last - first. |
354 | BOOST_CONTAINER_FORCEINLINE flat_map(std::initializer_list<value_type> il, const allocator_type& a) | |
355 | : m_flat_tree( true | |
11fdf7f2 TL |
356 | , dtl::force<impl_initializer_list>(il).begin() |
357 | , dtl::force<impl_initializer_list>(il).end() | |
358 | , dtl::force<const impl_allocator_type>(a)) | |
b32b8144 FG |
359 | {} |
360 | ||
361 | //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and | |
362 | //! inserts elements from the range [il.begin() ,il.end()). | |
363 | //! | |
364 | //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using | |
365 | //! the predicate and otherwise N logN, where N is last - first. | |
366 | BOOST_CONTAINER_FORCEINLINE flat_map(std::initializer_list<value_type> il, const Compare& comp) | |
367 | : m_flat_tree(true | |
11fdf7f2 TL |
368 | , dtl::force<impl_initializer_list>(il).begin() |
369 | , dtl::force<impl_initializer_list>(il).end() | |
b32b8144 FG |
370 | , comp) |
371 | {} | |
372 | ||
373 | //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and | |
374 | //! allocator, and inserts elements from the range [il.begin() ,il.end()). | |
375 | //! | |
376 | //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using | |
377 | //! the predicate and otherwise N logN, where N is last - first. | |
378 | BOOST_CONTAINER_FORCEINLINE flat_map(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a) | |
379 | : m_flat_tree(true | |
11fdf7f2 TL |
380 | , dtl::force<impl_initializer_list>(il).begin() |
381 | , dtl::force<impl_initializer_list>(il).end() | |
b32b8144 | 382 | , comp |
11fdf7f2 | 383 | , dtl::force<const impl_allocator_type>(a)) |
b32b8144 FG |
384 | {} |
385 | ||
386 | //! <b>Effects</b>: Constructs an empty flat_map using and | |
387 | //! inserts elements from the ordered unique range [il.begin(), il.end()). This function | |
388 | //! is more efficient than the normal range creation for ordered ranges. | |
389 | //! | |
390 | //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be | |
391 | //! unique values. | |
392 | //! | |
393 | //! <b>Complexity</b>: Linear in N. | |
394 | //! | |
395 | //! <b>Note</b>: Non-standard extension. | |
396 | BOOST_CONTAINER_FORCEINLINE flat_map(ordered_unique_range_t, std::initializer_list<value_type> il) | |
397 | : m_flat_tree(ordered_unique_range | |
11fdf7f2 TL |
398 | , dtl::force<impl_initializer_list>(il).begin() |
399 | , dtl::force<impl_initializer_list>(il).end()) | |
b32b8144 FG |
400 | {} |
401 | ||
402 | //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and | |
403 | //! inserts elements from the ordered unique range [il.begin(), il.end()). This function | |
404 | //! is more efficient than the normal range creation for ordered ranges. | |
405 | //! | |
406 | //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be | |
407 | //! unique values. | |
408 | //! | |
409 | //! <b>Complexity</b>: Linear in N. | |
410 | //! | |
411 | //! <b>Note</b>: Non-standard extension. | |
412 | BOOST_CONTAINER_FORCEINLINE flat_map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp) | |
413 | : m_flat_tree(ordered_unique_range | |
11fdf7f2 TL |
414 | , dtl::force<impl_initializer_list>(il).begin() |
415 | , dtl::force<impl_initializer_list>(il).end() | |
b32b8144 FG |
416 | , comp) |
417 | {} | |
7c673cae FG |
418 | |
419 | //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and | |
420 | //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function | |
421 | //! is more efficient than the normal range creation for ordered ranges. | |
422 | //! | |
423 | //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be | |
424 | //! unique values. | |
425 | //! | |
426 | //! <b>Complexity</b>: Linear in N. | |
427 | //! | |
428 | //! <b>Note</b>: Non-standard extension. | |
b32b8144 FG |
429 | BOOST_CONTAINER_FORCEINLINE flat_map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a) |
430 | : m_flat_tree( ordered_unique_range | |
11fdf7f2 TL |
431 | , dtl::force<impl_initializer_list>(il).begin() |
432 | , dtl::force<impl_initializer_list>(il).end() | |
b32b8144 | 433 | , comp |
11fdf7f2 | 434 | , dtl::force<const impl_allocator_type>(a)) |
b32b8144 | 435 | {} |
7c673cae FG |
436 | #endif |
437 | ||
438 | //! <b>Effects</b>: Copy constructs a flat_map. | |
439 | //! | |
440 | //! <b>Complexity</b>: Linear in x.size(). | |
b32b8144 | 441 | BOOST_CONTAINER_FORCEINLINE flat_map(const flat_map& x) |
7c673cae | 442 | : m_flat_tree(x.m_flat_tree) |
b32b8144 | 443 | {} |
7c673cae FG |
444 | |
445 | //! <b>Effects</b>: Move constructs a flat_map. | |
446 | //! Constructs *this using x's resources. | |
447 | //! | |
448 | //! <b>Complexity</b>: Constant. | |
449 | //! | |
450 | //! <b>Postcondition</b>: x is emptied. | |
b32b8144 | 451 | BOOST_CONTAINER_FORCEINLINE flat_map(BOOST_RV_REF(flat_map) x) |
11fdf7f2 | 452 | BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value) |
7c673cae | 453 | : m_flat_tree(boost::move(x.m_flat_tree)) |
b32b8144 | 454 | {} |
7c673cae FG |
455 | |
456 | //! <b>Effects</b>: Copy constructs a flat_map using the specified allocator. | |
457 | //! | |
458 | //! <b>Complexity</b>: Linear in x.size(). | |
b32b8144 | 459 | BOOST_CONTAINER_FORCEINLINE flat_map(const flat_map& x, const allocator_type &a) |
11fdf7f2 | 460 | : m_flat_tree(x.m_flat_tree, dtl::force<const impl_allocator_type>(a)) |
b32b8144 | 461 | {} |
7c673cae FG |
462 | |
463 | //! <b>Effects</b>: Move constructs a flat_map using the specified allocator. | |
464 | //! Constructs *this using x's resources. | |
465 | //! | |
466 | //! <b>Complexity</b>: Constant if x.get_allocator() == a, linear otherwise. | |
b32b8144 | 467 | BOOST_CONTAINER_FORCEINLINE flat_map(BOOST_RV_REF(flat_map) x, const allocator_type &a) |
11fdf7f2 | 468 | : m_flat_tree(boost::move(x.m_flat_tree), dtl::force<const impl_allocator_type>(a)) |
b32b8144 | 469 | {} |
7c673cae FG |
470 | |
471 | //! <b>Effects</b>: Makes *this a copy of x. | |
472 | //! | |
473 | //! <b>Complexity</b>: Linear in x.size(). | |
b32b8144 | 474 | BOOST_CONTAINER_FORCEINLINE flat_map& operator=(BOOST_COPY_ASSIGN_REF(flat_map) x) |
7c673cae FG |
475 | { m_flat_tree = x.m_flat_tree; return *this; } |
476 | ||
477 | //! <b>Effects</b>: Move constructs a flat_map. | |
478 | //! Constructs *this using x's resources. | |
479 | //! | |
480 | //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment | |
481 | //! is false and (allocation throws or value_type's move constructor throws) | |
482 | //! | |
483 | //! <b>Complexity</b>: Constant if allocator_traits_type:: | |
484 | //! propagate_on_container_move_assignment is true or | |
485 | //! this->get>allocator() == x.get_allocator(). Linear otherwise. | |
b32b8144 | 486 | BOOST_CONTAINER_FORCEINLINE flat_map& operator=(BOOST_RV_REF(flat_map) x) |
7c673cae FG |
487 | BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value || |
488 | allocator_traits_type::is_always_equal::value) && | |
11fdf7f2 | 489 | boost::container::dtl::is_nothrow_move_assignable<Compare>::value) |
7c673cae FG |
490 | { m_flat_tree = boost::move(x.m_flat_tree); return *this; } |
491 | ||
492 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
493 | //! <b>Effects</b>: Assign elements from il to *this | |
494 | flat_map& operator=(std::initializer_list<value_type> il) | |
495 | { | |
496 | this->clear(); | |
497 | this->insert(il.begin(), il.end()); | |
498 | return *this; | |
499 | } | |
500 | #endif | |
501 | ||
502 | //! <b>Effects</b>: Returns a copy of the allocator that | |
503 | //! was passed to the object's constructor. | |
504 | //! | |
505 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 506 | BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 507 | { return dtl::force_copy<allocator_type>(m_flat_tree.get_allocator()); } |
7c673cae FG |
508 | |
509 | //! <b>Effects</b>: Returns a reference to the internal allocator. | |
510 | //! | |
511 | //! <b>Throws</b>: Nothing | |
512 | //! | |
513 | //! <b>Complexity</b>: Constant. | |
514 | //! | |
515 | //! <b>Note</b>: Non-standard extension. | |
b32b8144 FG |
516 | BOOST_CONTAINER_FORCEINLINE get_stored_allocator_noconst_return_t get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW |
517 | { | |
518 | impl_get_stored_allocator_noconst_return_t r = m_flat_tree.get_stored_allocator(); | |
11fdf7f2 | 519 | return dtl::force<stored_allocator_type>(r); |
b32b8144 | 520 | } |
7c673cae FG |
521 | |
522 | //! <b>Effects</b>: Returns a reference to the internal allocator. | |
523 | //! | |
524 | //! <b>Throws</b>: Nothing | |
525 | //! | |
526 | //! <b>Complexity</b>: Constant. | |
527 | //! | |
528 | //! <b>Note</b>: Non-standard extension. | |
b32b8144 FG |
529 | BOOST_CONTAINER_FORCEINLINE get_stored_allocator_const_return_t get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW |
530 | { | |
531 | impl_get_stored_allocator_const_return_t r = m_flat_tree.get_stored_allocator(); | |
11fdf7f2 | 532 | return dtl::force<const stored_allocator_type>(r); |
b32b8144 | 533 | } |
7c673cae FG |
534 | |
535 | ////////////////////////////////////////////// | |
536 | // | |
537 | // iterators | |
538 | // | |
539 | ////////////////////////////////////////////// | |
540 | ||
541 | //! <b>Effects</b>: Returns an iterator to the first element contained in the container. | |
542 | //! | |
543 | //! <b>Throws</b>: Nothing. | |
544 | //! | |
545 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 546 | BOOST_CONTAINER_FORCEINLINE iterator begin() BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 547 | { return dtl::force_copy<iterator>(m_flat_tree.begin()); } |
7c673cae FG |
548 | |
549 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. | |
550 | //! | |
551 | //! <b>Throws</b>: Nothing. | |
552 | //! | |
553 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 554 | BOOST_CONTAINER_FORCEINLINE const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 555 | { return dtl::force_copy<const_iterator>(m_flat_tree.begin()); } |
7c673cae FG |
556 | |
557 | //! <b>Effects</b>: Returns an iterator to the end of the container. | |
558 | //! | |
559 | //! <b>Throws</b>: Nothing. | |
560 | //! | |
561 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 562 | BOOST_CONTAINER_FORCEINLINE iterator end() BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 563 | { return dtl::force_copy<iterator>(m_flat_tree.end()); } |
7c673cae FG |
564 | |
565 | //! <b>Effects</b>: Returns a const_iterator to the end of the container. | |
566 | //! | |
567 | //! <b>Throws</b>: Nothing. | |
568 | //! | |
569 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 570 | BOOST_CONTAINER_FORCEINLINE const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 571 | { return dtl::force_copy<const_iterator>(m_flat_tree.end()); } |
7c673cae FG |
572 | |
573 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning | |
574 | //! of the reversed container. | |
575 | //! | |
576 | //! <b>Throws</b>: Nothing. | |
577 | //! | |
578 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 579 | BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 580 | { return dtl::force_copy<reverse_iterator>(m_flat_tree.rbegin()); } |
7c673cae FG |
581 | |
582 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning | |
583 | //! of the reversed container. | |
584 | //! | |
585 | //! <b>Throws</b>: Nothing. | |
586 | //! | |
587 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 588 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 589 | { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.rbegin()); } |
7c673cae FG |
590 | |
591 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the end | |
592 | //! of the reversed container. | |
593 | //! | |
594 | //! <b>Throws</b>: Nothing. | |
595 | //! | |
596 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 597 | BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 598 | { return dtl::force_copy<reverse_iterator>(m_flat_tree.rend()); } |
7c673cae FG |
599 | |
600 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end | |
601 | //! of the reversed container. | |
602 | //! | |
603 | //! <b>Throws</b>: Nothing. | |
604 | //! | |
605 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 606 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 607 | { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.rend()); } |
7c673cae FG |
608 | |
609 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. | |
610 | //! | |
611 | //! <b>Throws</b>: Nothing. | |
612 | //! | |
613 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 614 | BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 615 | { return dtl::force_copy<const_iterator>(m_flat_tree.cbegin()); } |
7c673cae FG |
616 | |
617 | //! <b>Effects</b>: Returns a const_iterator to the end of the container. | |
618 | //! | |
619 | //! <b>Throws</b>: Nothing. | |
620 | //! | |
621 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 622 | BOOST_CONTAINER_FORCEINLINE const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 623 | { return dtl::force_copy<const_iterator>(m_flat_tree.cend()); } |
7c673cae FG |
624 | |
625 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning | |
626 | //! of the reversed container. | |
627 | //! | |
628 | //! <b>Throws</b>: Nothing. | |
629 | //! | |
630 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 631 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 632 | { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.crbegin()); } |
7c673cae FG |
633 | |
634 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end | |
635 | //! of the reversed container. | |
636 | //! | |
637 | //! <b>Throws</b>: Nothing. | |
638 | //! | |
639 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 640 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 641 | { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.crend()); } |
7c673cae FG |
642 | |
643 | ////////////////////////////////////////////// | |
644 | // | |
645 | // capacity | |
646 | // | |
647 | ////////////////////////////////////////////// | |
648 | ||
649 | //! <b>Effects</b>: Returns true if the container contains no elements. | |
650 | //! | |
651 | //! <b>Throws</b>: Nothing. | |
652 | //! | |
653 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 654 | BOOST_CONTAINER_FORCEINLINE bool empty() const BOOST_NOEXCEPT_OR_NOTHROW |
7c673cae FG |
655 | { return m_flat_tree.empty(); } |
656 | ||
657 | //! <b>Effects</b>: Returns the number of the elements contained in the container. | |
658 | //! | |
659 | //! <b>Throws</b>: Nothing. | |
660 | //! | |
661 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 662 | BOOST_CONTAINER_FORCEINLINE size_type size() const BOOST_NOEXCEPT_OR_NOTHROW |
7c673cae FG |
663 | { return m_flat_tree.size(); } |
664 | ||
665 | //! <b>Effects</b>: Returns the largest possible size of the container. | |
666 | //! | |
667 | //! <b>Throws</b>: Nothing. | |
668 | //! | |
669 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 670 | BOOST_CONTAINER_FORCEINLINE size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW |
7c673cae FG |
671 | { return m_flat_tree.max_size(); } |
672 | ||
673 | //! <b>Effects</b>: Number of elements for which memory has been allocated. | |
674 | //! capacity() is always greater than or equal to size(). | |
675 | //! | |
676 | //! <b>Throws</b>: Nothing. | |
677 | //! | |
678 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 679 | BOOST_CONTAINER_FORCEINLINE size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW |
7c673cae FG |
680 | { return m_flat_tree.capacity(); } |
681 | ||
b32b8144 FG |
682 | //! <b>Effects</b>: If n is less than or equal to capacity(), or the |
683 | //! underlying container has no `reserve` member, this call has no | |
7c673cae FG |
684 | //! effect. Otherwise, it is a request for allocation of additional memory. |
685 | //! If the request is successful, then capacity() is greater than or equal to | |
686 | //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged. | |
687 | //! | |
688 | //! <b>Throws</b>: If memory allocation allocation throws or T's copy constructor throws. | |
689 | //! | |
690 | //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to | |
691 | //! to values might be invalidated. | |
b32b8144 | 692 | BOOST_CONTAINER_FORCEINLINE void reserve(size_type cnt) |
7c673cae FG |
693 | { m_flat_tree.reserve(cnt); } |
694 | ||
695 | //! <b>Effects</b>: Tries to deallocate the excess of memory created | |
696 | // with previous allocations. The size of the vector is unchanged | |
697 | //! | |
698 | //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. | |
699 | //! | |
700 | //! <b>Complexity</b>: Linear to size(). | |
b32b8144 | 701 | BOOST_CONTAINER_FORCEINLINE void shrink_to_fit() |
7c673cae FG |
702 | { m_flat_tree.shrink_to_fit(); } |
703 | ||
704 | ////////////////////////////////////////////// | |
705 | // | |
706 | // element access | |
707 | // | |
708 | ////////////////////////////////////////////// | |
709 | ||
710 | #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
711 | //! Effects: If there is no key equivalent to x in the flat_map, inserts | |
712 | //! value_type(x, T()) into the flat_map. | |
713 | //! | |
714 | //! Returns: A reference to the mapped_type corresponding to x in *this. | |
715 | //! | |
716 | //! Complexity: Logarithmic. | |
717 | mapped_type &operator[](const key_type& k); | |
718 | ||
719 | //! Effects: If there is no key equivalent to x in the flat_map, inserts | |
720 | //! value_type(move(x), T()) into the flat_map (the key is move-constructed) | |
721 | //! | |
722 | //! Returns: A reference to the mapped_type corresponding to x in *this. | |
723 | //! | |
724 | //! Complexity: Logarithmic. | |
725 | mapped_type &operator[](key_type &&k) ; | |
726 | #elif defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN) | |
727 | //in compilers like GCC 3.4, we can't catch temporaries | |
b32b8144 FG |
728 | BOOST_CONTAINER_FORCEINLINE mapped_type& operator[](const key_type &k) { return this->priv_subscript(k); } |
729 | BOOST_CONTAINER_FORCEINLINE mapped_type& operator[](BOOST_RV_REF(key_type) k) { return this->priv_subscript(::boost::move(k)); } | |
7c673cae FG |
730 | #else |
731 | BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript) | |
732 | #endif | |
733 | ||
734 | //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj) | |
735 | //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value | |
736 | //! as if by insert, constructing it from value_type(k, forward<M>(obj)). | |
737 | //! | |
738 | //! No iterators or references are invalidated. If the insertion is successful, pointers and references | |
739 | //! to the element obtained while it is held in the node handle are invalidated, and pointers and | |
740 | //! references obtained to that element before it was extracted become valid. | |
741 | //! | |
742 | //! Returns: The bool component is true if the insertion took place and false if the assignment | |
743 | //! took place. The iterator component is pointing at the element that was inserted or updated. | |
744 | //! | |
745 | //! Complexity: Logarithmic in the size of the container. | |
746 | template <class M> | |
747 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(const key_type& k, BOOST_FWD_REF(M) obj) | |
748 | { | |
11fdf7f2 | 749 | return dtl::force_copy< std::pair<iterator, bool> > |
7c673cae FG |
750 | (this->m_flat_tree.insert_or_assign |
751 | ( impl_const_iterator(), k, ::boost::forward<M>(obj)) | |
752 | ); | |
753 | } | |
754 | ||
755 | //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj) | |
756 | //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value | |
757 | //! as if by insert, constructing it from value_type(k, move(obj)). | |
758 | //! | |
759 | //! No iterators or references are invalidated. If the insertion is successful, pointers and references | |
760 | //! to the element obtained while it is held in the node handle are invalidated, and pointers and | |
761 | //! references obtained to that element before it was extracted become valid. | |
762 | //! | |
763 | //! Returns: The bool component is true if the insertion took place and false if the assignment | |
764 | //! took place. The iterator component is pointing at the element that was inserted or updated. | |
765 | //! | |
766 | //! Complexity: Logarithmic in the size of the container. | |
767 | template <class M> | |
768 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj) | |
769 | { | |
11fdf7f2 | 770 | return dtl::force_copy< std::pair<iterator, bool> > |
7c673cae FG |
771 | (this->m_flat_tree.insert_or_assign |
772 | ( impl_const_iterator(), ::boost::move(k), ::boost::forward<M>(obj)) | |
773 | ); | |
774 | } | |
775 | ||
776 | //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj) | |
777 | //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value | |
778 | //! as if by insert, constructing it from value_type(k, forward<M>(obj)) and the new element | |
779 | //! to the container as close as possible to the position just before hint. | |
780 | //! | |
781 | //! No iterators or references are invalidated. If the insertion is successful, pointers and references | |
782 | //! to the element obtained while it is held in the node handle are invalidated, and pointers and | |
783 | //! references obtained to that element before it was extracted become valid. | |
784 | //! | |
785 | //! Returns: The bool component is true if the insertion took place and false if the assignment | |
786 | //! took place. The iterator component is pointing at the element that was inserted or updated. | |
787 | //! | |
788 | //! Complexity: Logarithmic in the size of the container in general, but amortized constant if | |
789 | //! the new element is inserted just before hint. | |
790 | template <class M> | |
791 | BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, const key_type& k, BOOST_FWD_REF(M) obj) | |
792 | { | |
92f5a8d4 | 793 | return dtl::force_copy<iterator> |
7c673cae | 794 | (this->m_flat_tree.insert_or_assign |
11fdf7f2 | 795 | ( dtl::force_copy<impl_const_iterator>(hint) |
92f5a8d4 | 796 | , k, ::boost::forward<M>(obj)).first |
7c673cae FG |
797 | ); |
798 | } | |
799 | ||
800 | //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj) | |
801 | //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value | |
802 | //! as if by insert, constructing it from value_type(k, move(obj)) and the new element | |
803 | //! to the container as close as possible to the position just before hint. | |
804 | //! | |
805 | //! No iterators or references are invalidated. If the insertion is successful, pointers and references | |
806 | //! to the element obtained while it is held in the node handle are invalidated, and pointers and | |
807 | //! references obtained to that element before it was extracted become valid. | |
808 | //! | |
809 | //! Returns: The bool component is true if the insertion took place and false if the assignment | |
810 | //! took place. The iterator component is pointing at the element that was inserted or updated. | |
811 | //! | |
812 | //! Complexity: Logarithmic in the size of the container in general, but amortized constant if | |
813 | //! the new element is inserted just before hint. | |
814 | template <class M> | |
815 | BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj) | |
816 | { | |
92f5a8d4 | 817 | return dtl::force_copy<iterator> |
7c673cae | 818 | (this->m_flat_tree.insert_or_assign |
11fdf7f2 | 819 | ( dtl::force_copy<impl_const_iterator>(hint) |
92f5a8d4 | 820 | , ::boost::move(k), ::boost::forward<M>(obj)).first |
7c673cae FG |
821 | ); |
822 | } | |
823 | ||
824 | //! @copydoc ::boost::container::flat_set::nth(size_type) | |
b32b8144 | 825 | BOOST_CONTAINER_FORCEINLINE iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 826 | { return dtl::force_copy<iterator>(m_flat_tree.nth(n)); } |
7c673cae FG |
827 | |
828 | //! @copydoc ::boost::container::flat_set::nth(size_type) const | |
b32b8144 | 829 | BOOST_CONTAINER_FORCEINLINE const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 830 | { return dtl::force_copy<iterator>(m_flat_tree.nth(n)); } |
7c673cae FG |
831 | |
832 | //! @copydoc ::boost::container::flat_set::index_of(iterator) | |
b32b8144 | 833 | BOOST_CONTAINER_FORCEINLINE size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 834 | { return m_flat_tree.index_of(dtl::force_copy<impl_iterator>(p)); } |
7c673cae FG |
835 | |
836 | //! @copydoc ::boost::container::flat_set::index_of(const_iterator) const | |
b32b8144 | 837 | BOOST_CONTAINER_FORCEINLINE size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 838 | { return m_flat_tree.index_of(dtl::force_copy<impl_const_iterator>(p)); } |
7c673cae FG |
839 | |
840 | //! Returns: A reference to the element whose key is equivalent to x. | |
841 | //! | |
842 | //! Throws: An exception object of type out_of_range if no such element is present. | |
843 | //! | |
844 | //! Complexity: logarithmic. | |
845 | T& at(const key_type& k) | |
846 | { | |
847 | iterator i = this->find(k); | |
848 | if(i == this->end()){ | |
849 | throw_out_of_range("flat_map::at key not found"); | |
850 | } | |
851 | return i->second; | |
852 | } | |
853 | ||
854 | //! Returns: A reference to the element whose key is equivalent to x. | |
855 | //! | |
856 | //! Throws: An exception object of type out_of_range if no such element is present. | |
857 | //! | |
858 | //! Complexity: logarithmic. | |
859 | const T& at(const key_type& k) const | |
860 | { | |
861 | const_iterator i = this->find(k); | |
862 | if(i == this->end()){ | |
863 | throw_out_of_range("flat_map::at key not found"); | |
864 | } | |
865 | return i->second; | |
866 | } | |
867 | ||
868 | ////////////////////////////////////////////// | |
869 | // | |
870 | // modifiers | |
871 | // | |
872 | ////////////////////////////////////////////// | |
873 | ||
874 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
875 | ||
876 | //! <b>Effects</b>: Inserts an object x of type T constructed with | |
877 | //! std::forward<Args>(args)... if and only if there is no element in the container | |
878 | //! with key equivalent to the key of x. | |
879 | //! | |
880 | //! <b>Returns</b>: The bool component of the returned pair is true if and only | |
881 | //! if the insertion takes place, and the iterator component of the pair | |
882 | //! points to the element with key equivalent to the key of x. | |
883 | //! | |
884 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
885 | //! to the elements with bigger keys than x. | |
886 | //! | |
887 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
888 | template <class... Args> | |
b32b8144 | 889 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args) |
11fdf7f2 | 890 | { return dtl::force_copy< std::pair<iterator, bool> >(m_flat_tree.emplace_unique(boost::forward<Args>(args)...)); } |
7c673cae FG |
891 | |
892 | //! <b>Effects</b>: Inserts an object of type T constructed with | |
893 | //! std::forward<Args>(args)... in the container if and only if there is | |
894 | //! no element in the container with key equivalent to the key of x. | |
895 | //! p is a hint pointing to where the insert should start to search. | |
896 | //! | |
897 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent | |
898 | //! to the key of x. | |
899 | //! | |
900 | //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted | |
901 | //! right before p) plus insertion linear to the elements with bigger keys than x. | |
902 | //! | |
903 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
904 | template <class... Args> | |
b32b8144 | 905 | BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args) |
7c673cae | 906 | { |
11fdf7f2 TL |
907 | return dtl::force_copy<iterator> |
908 | (m_flat_tree.emplace_hint_unique( dtl::force_copy<impl_const_iterator>(hint) | |
7c673cae FG |
909 | , boost::forward<Args>(args)...)); |
910 | } | |
911 | ||
912 | //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, | |
913 | //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...). | |
914 | //! | |
915 | //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise | |
916 | //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k), | |
917 | //! forward_as_tuple(forward<Args>(args)...). | |
918 | //! | |
919 | //! <b>Returns</b>: The bool component of the returned pair is true if and only if the | |
920 | //! insertion took place. The returned iterator points to the map element whose key is equivalent to k. | |
921 | //! | |
922 | //! <b>Complexity</b>: Logarithmic. | |
923 | template <class... Args> | |
924 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k, BOOST_FWD_REF(Args)... args) | |
925 | { | |
11fdf7f2 | 926 | return dtl::force_copy< std::pair<iterator, bool> >( |
7c673cae FG |
927 | m_flat_tree.try_emplace(impl_const_iterator(), k, boost::forward<Args>(args)...)); |
928 | } | |
929 | ||
930 | //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, | |
931 | //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...). | |
932 | //! | |
933 | //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise | |
934 | //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k), | |
935 | //! forward_as_tuple(forward<Args>(args)...). | |
936 | //! | |
937 | //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k. | |
938 | //! | |
939 | //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value | |
940 | //! is inserted right before p. | |
941 | template <class... Args> | |
942 | BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k, BOOST_FWD_REF(Args)... args) | |
943 | { | |
11fdf7f2 TL |
944 | return dtl::force_copy<iterator>(m_flat_tree.try_emplace |
945 | (dtl::force_copy<impl_const_iterator>(hint), k, boost::forward<Args>(args)...).first); | |
7c673cae FG |
946 | } |
947 | ||
948 | //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, | |
949 | //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...). | |
950 | //! | |
951 | //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise | |
952 | //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)), | |
953 | //! forward_as_tuple(forward<Args>(args)...). | |
954 | //! | |
955 | //! <b>Returns</b>: The bool component of the returned pair is true if and only if the | |
956 | //! insertion took place. The returned iterator points to the map element whose key is equivalent to k. | |
957 | //! | |
958 | //! <b>Complexity</b>: Logarithmic. | |
959 | template <class... Args> | |
960 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args) | |
961 | { | |
11fdf7f2 | 962 | return dtl::force_copy< std::pair<iterator, bool> > |
7c673cae FG |
963 | (m_flat_tree.try_emplace(impl_const_iterator(), boost::move(k), boost::forward<Args>(args)...)); |
964 | } | |
965 | ||
966 | //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, | |
967 | //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...). | |
968 | //! | |
969 | //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise | |
970 | //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)), | |
971 | //! forward_as_tuple(forward<Args>(args)...). | |
972 | //! | |
973 | //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k. | |
974 | //! | |
975 | //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value | |
976 | //! is inserted right before p. | |
977 | template <class... Args> | |
978 | BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args) | |
979 | { | |
11fdf7f2 TL |
980 | return dtl::force_copy<iterator> |
981 | (m_flat_tree.try_emplace(dtl::force_copy | |
7c673cae FG |
982 | <impl_const_iterator>(hint), boost::move(k), boost::forward<Args>(args)...).first); |
983 | } | |
984 | ||
985 | #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
986 | ||
987 | #define BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE(N) \ | |
988 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
b32b8144 | 989 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\ |
7c673cae | 990 | {\ |
11fdf7f2 | 991 | return dtl::force_copy< std::pair<iterator, bool> >\ |
7c673cae FG |
992 | (m_flat_tree.emplace_unique(BOOST_MOVE_FWD##N));\ |
993 | }\ | |
994 | \ | |
995 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
b32b8144 | 996 | BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ |
7c673cae | 997 | {\ |
11fdf7f2 TL |
998 | return dtl::force_copy<iterator>(m_flat_tree.emplace_hint_unique\ |
999 | (dtl::force_copy<impl_const_iterator>(hint) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\ | |
7c673cae FG |
1000 | }\ |
1001 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1002 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
1003 | {\ | |
11fdf7f2 | 1004 | return dtl::force_copy< std::pair<iterator, bool> >\ |
7c673cae FG |
1005 | (m_flat_tree.try_emplace(impl_const_iterator(), k BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\ |
1006 | }\ | |
1007 | \ | |
1008 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1009 | BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
11fdf7f2 TL |
1010 | { return dtl::force_copy<iterator>(m_flat_tree.try_emplace\ |
1011 | (dtl::force_copy<impl_const_iterator>(hint), k BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first); }\ | |
7c673cae FG |
1012 | \ |
1013 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1014 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
1015 | {\ | |
11fdf7f2 | 1016 | return dtl::force_copy< std::pair<iterator, bool> >\ |
7c673cae FG |
1017 | (m_flat_tree.try_emplace(impl_const_iterator(), boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\ |
1018 | }\ | |
1019 | \ | |
1020 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1021 | BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
11fdf7f2 TL |
1022 | { return dtl::force_copy<iterator>(m_flat_tree.try_emplace\ |
1023 | (dtl::force_copy<impl_const_iterator>(hint), boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first); }\ | |
7c673cae FG |
1024 | // |
1025 | BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE) | |
1026 | #undef BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE | |
1027 | ||
1028 | #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
1029 | ||
1030 | //! <b>Effects</b>: Inserts x if and only if there is no element in the container | |
1031 | //! with key equivalent to the key of x. | |
1032 | //! | |
1033 | //! <b>Returns</b>: The bool component of the returned pair is true if and only | |
1034 | //! if the insertion takes place, and the iterator component of the pair | |
1035 | //! points to the element with key equivalent to the key of x. | |
1036 | //! | |
1037 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
1038 | //! to the elements with bigger keys than x. | |
1039 | //! | |
1040 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
b32b8144 | 1041 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(const value_type& x) |
11fdf7f2 TL |
1042 | { return dtl::force_copy<std::pair<iterator,bool> >( |
1043 | m_flat_tree.insert_unique(dtl::force<const impl_value_type>(x))); } | |
7c673cae FG |
1044 | |
1045 | //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and | |
1046 | //! only if there is no element in the container with key equivalent to the key of x. | |
1047 | //! | |
1048 | //! <b>Returns</b>: The bool component of the returned pair is true if and only | |
1049 | //! if the insertion takes place, and the iterator component of the pair | |
1050 | //! points to the element with key equivalent to the key of x. | |
1051 | //! | |
1052 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
1053 | //! to the elements with bigger keys than x. | |
1054 | //! | |
1055 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
b32b8144 | 1056 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x) |
11fdf7f2 TL |
1057 | { return dtl::force_copy<std::pair<iterator,bool> >( |
1058 | m_flat_tree.insert_unique(boost::move(dtl::force<impl_value_type>(x)))); } | |
7c673cae FG |
1059 | |
1060 | //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and | |
1061 | //! only if there is no element in the container with key equivalent to the key of x. | |
1062 | //! | |
1063 | //! <b>Returns</b>: The bool component of the returned pair is true if and only | |
1064 | //! if the insertion takes place, and the iterator component of the pair | |
1065 | //! points to the element with key equivalent to the key of x. | |
1066 | //! | |
1067 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
1068 | //! to the elements with bigger keys than x. | |
1069 | //! | |
1070 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
b32b8144 | 1071 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(movable_value_type) x) |
7c673cae | 1072 | { |
11fdf7f2 | 1073 | return dtl::force_copy<std::pair<iterator,bool> > |
7c673cae FG |
1074 | (m_flat_tree.insert_unique(boost::move(x))); |
1075 | } | |
1076 | ||
1077 | //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is | |
1078 | //! no element in the container with key equivalent to the key of x. | |
1079 | //! p is a hint pointing to where the insert should start to search. | |
1080 | //! | |
1081 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent | |
1082 | //! to the key of x. | |
1083 | //! | |
1084 | //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted | |
1085 | //! right before p) plus insertion linear to the elements with bigger keys than x. | |
1086 | //! | |
1087 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
b32b8144 | 1088 | BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const value_type& x) |
7c673cae | 1089 | { |
11fdf7f2 TL |
1090 | return dtl::force_copy<iterator>( |
1091 | m_flat_tree.insert_unique( dtl::force_copy<impl_const_iterator>(p) | |
1092 | , dtl::force<const impl_value_type>(x))); | |
7c673cae FG |
1093 | } |
1094 | ||
1095 | //! <b>Effects</b>: Inserts an element move constructed from x in the container. | |
1096 | //! p is a hint pointing to where the insert should start to search. | |
1097 | //! | |
1098 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x. | |
1099 | //! | |
1100 | //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted | |
1101 | //! right before p) plus insertion linear to the elements with bigger keys than x. | |
1102 | //! | |
1103 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
b32b8144 | 1104 | BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(value_type) x) |
7c673cae | 1105 | { |
11fdf7f2 TL |
1106 | return dtl::force_copy<iterator> |
1107 | (m_flat_tree.insert_unique( dtl::force_copy<impl_const_iterator>(p) | |
1108 | , boost::move(dtl::force<impl_value_type>(x)))); | |
7c673cae FG |
1109 | } |
1110 | ||
1111 | //! <b>Effects</b>: Inserts an element move constructed from x in the container. | |
1112 | //! p is a hint pointing to where the insert should start to search. | |
1113 | //! | |
1114 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x. | |
1115 | //! | |
1116 | //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted | |
1117 | //! right before p) plus insertion linear to the elements with bigger keys than x. | |
1118 | //! | |
1119 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
b32b8144 | 1120 | BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x) |
7c673cae | 1121 | { |
11fdf7f2 TL |
1122 | return dtl::force_copy<iterator>( |
1123 | m_flat_tree.insert_unique(dtl::force_copy<impl_const_iterator>(p), boost::move(x))); | |
7c673cae FG |
1124 | } |
1125 | ||
1126 | //! <b>Requires</b>: first, last are not iterators into *this. | |
1127 | //! | |
1128 | //! <b>Effects</b>: inserts each element from the range [first,last) if and only | |
1129 | //! if there is no element with key equivalent to the key of that element. | |
1130 | //! | |
11fdf7f2 | 1131 | //! <b>Complexity</b>: N log(size()+N). |
7c673cae FG |
1132 | //! |
1133 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1134 | template <class InputIterator> | |
b32b8144 | 1135 | BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last) |
7c673cae FG |
1136 | { m_flat_tree.insert_unique(first, last); } |
1137 | ||
1138 | //! <b>Requires</b>: first, last are not iterators into *this. | |
1139 | //! | |
1140 | //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be | |
1141 | //! unique values. | |
1142 | //! | |
1143 | //! <b>Effects</b>: inserts each element from the range [first,last) if and only | |
1144 | //! if there is no element with key equivalent to the key of that element. This | |
1145 | //! function is more efficient than the normal range creation for ordered ranges. | |
1146 | //! | |
11fdf7f2 | 1147 | //! <b>Complexity</b>: Linear. |
7c673cae FG |
1148 | //! |
1149 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1150 | //! | |
1151 | //! <b>Note</b>: Non-standard extension. | |
1152 | template <class InputIterator> | |
b32b8144 | 1153 | BOOST_CONTAINER_FORCEINLINE void insert(ordered_unique_range_t, InputIterator first, InputIterator last) |
7c673cae FG |
1154 | { m_flat_tree.insert_unique(ordered_unique_range, first, last); } |
1155 | ||
1156 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
1157 | //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only | |
1158 | //! if there is no element with key equivalent to the key of that element. | |
1159 | //! | |
11fdf7f2 | 1160 | //! <b>Complexity</b>: N log(N). |
7c673cae FG |
1161 | //! |
1162 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
b32b8144 FG |
1163 | BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il) |
1164 | { | |
11fdf7f2 TL |
1165 | m_flat_tree.insert_unique( dtl::force<impl_initializer_list>(il).begin() |
1166 | , dtl::force<impl_initializer_list>(il).end()); | |
b32b8144 | 1167 | } |
7c673cae FG |
1168 | |
1169 | //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be | |
1170 | //! unique values. | |
1171 | //! | |
1172 | //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only | |
1173 | //! if there is no element with key equivalent to the key of that element. This | |
1174 | //! function is more efficient than the normal range creation for ordered ranges. | |
1175 | //! | |
11fdf7f2 | 1176 | //! <b>Complexity</b>: Linear. |
7c673cae FG |
1177 | //! |
1178 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
1179 | //! | |
1180 | //! <b>Note</b>: Non-standard extension. | |
b32b8144 FG |
1181 | BOOST_CONTAINER_FORCEINLINE void insert(ordered_unique_range_t, std::initializer_list<value_type> il) |
1182 | { | |
1183 | m_flat_tree.insert_unique(ordered_unique_range | |
11fdf7f2 TL |
1184 | , dtl::force<impl_initializer_list>(il).begin() |
1185 | , dtl::force<impl_initializer_list>(il).end()); | |
b32b8144 | 1186 | } |
7c673cae FG |
1187 | #endif |
1188 | ||
1189 | //! <b>Requires</b>: this->get_allocator() == source.get_allocator(). | |
1190 | //! | |
1191 | //! <b>Effects</b>: Attempts to extract each element in source and insert it into a using | |
1192 | //! the comparison object of *this. If there is an element in a with key equivalent to the | |
1193 | //! key of an element from source, then that element is not extracted from source. | |
1194 | //! | |
1195 | //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer | |
1196 | //! to those same elements but as members of *this. Iterators referring to the transferred | |
1197 | //! elements will continue to refer to their elements, but they now behave as iterators into *this, | |
1198 | //! not into source. | |
1199 | //! | |
1200 | //! <b>Throws</b>: Nothing unless the comparison object throws. | |
1201 | //! | |
92f5a8d4 | 1202 | //! <b>Complexity</b>: N log(size() + N) (N has the value source.size()) |
7c673cae | 1203 | template<class C2> |
b32b8144 | 1204 | BOOST_CONTAINER_FORCEINLINE void merge(flat_map<Key, T, C2, AllocatorOrContainer>& source) |
7c673cae FG |
1205 | { m_flat_tree.merge_unique(source.tree()); } |
1206 | ||
b32b8144 | 1207 | //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, AllocatorOrContainer>&) |
7c673cae | 1208 | template<class C2> |
b32b8144 FG |
1209 | BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_map<Key, T, C2, AllocatorOrContainer> BOOST_RV_REF_END source) |
1210 | { return this->merge(static_cast<flat_map<Key, T, C2, AllocatorOrContainer>&>(source)); } | |
7c673cae | 1211 | |
b32b8144 | 1212 | //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, AllocatorOrContainer>&) |
7c673cae | 1213 | template<class C2> |
b32b8144 | 1214 | BOOST_CONTAINER_FORCEINLINE void merge(flat_multimap<Key, T, C2, AllocatorOrContainer>& source) |
7c673cae FG |
1215 | { m_flat_tree.merge_unique(source.tree()); } |
1216 | ||
b32b8144 | 1217 | //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, AllocatorOrContainer>&) |
7c673cae | 1218 | template<class C2> |
b32b8144 FG |
1219 | BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_multimap<Key, T, C2, AllocatorOrContainer> BOOST_RV_REF_END source) |
1220 | { return this->merge(static_cast<flat_multimap<Key, T, C2, AllocatorOrContainer>&>(source)); } | |
7c673cae FG |
1221 | |
1222 | //! <b>Effects</b>: Erases the element pointed to by p. | |
1223 | //! | |
1224 | //! <b>Returns</b>: Returns an iterator pointing to the element immediately | |
1225 | //! following q prior to the element being erased. If no such element exists, | |
1226 | //! returns end(). | |
1227 | //! | |
1228 | //! <b>Complexity</b>: Linear to the elements with keys bigger than p | |
1229 | //! | |
1230 | //! <b>Note</b>: Invalidates elements with keys | |
1231 | //! not less than the erased element. | |
b32b8144 | 1232 | BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator p) |
7c673cae | 1233 | { |
11fdf7f2 TL |
1234 | return dtl::force_copy<iterator> |
1235 | (m_flat_tree.erase(dtl::force_copy<impl_const_iterator>(p))); | |
7c673cae FG |
1236 | } |
1237 | ||
1238 | //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. | |
1239 | //! | |
1240 | //! <b>Returns</b>: Returns the number of erased elements. | |
1241 | //! | |
1242 | //! <b>Complexity</b>: Logarithmic search time plus erasure time | |
1243 | //! linear to the elements with bigger keys. | |
b32b8144 | 1244 | BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& x) |
7c673cae FG |
1245 | { return m_flat_tree.erase(x); } |
1246 | ||
1247 | //! <b>Effects</b>: Erases all the elements in the range [first, last). | |
1248 | //! | |
1249 | //! <b>Returns</b>: Returns last. | |
1250 | //! | |
1251 | //! <b>Complexity</b>: size()*N where N is the distance from first to last. | |
1252 | //! | |
1253 | //! <b>Complexity</b>: Logarithmic search time plus erasure time | |
1254 | //! linear to the elements with bigger keys. | |
b32b8144 | 1255 | BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator first, const_iterator last) |
7c673cae | 1256 | { |
11fdf7f2 TL |
1257 | return dtl::force_copy<iterator>( |
1258 | m_flat_tree.erase( dtl::force_copy<impl_const_iterator>(first) | |
1259 | , dtl::force_copy<impl_const_iterator>(last))); | |
7c673cae FG |
1260 | } |
1261 | ||
1262 | //! <b>Effects</b>: Swaps the contents of *this and x. | |
1263 | //! | |
1264 | //! <b>Throws</b>: Nothing. | |
1265 | //! | |
1266 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 1267 | BOOST_CONTAINER_FORCEINLINE void swap(flat_map& x) |
7c673cae | 1268 | BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value |
11fdf7f2 | 1269 | && boost::container::dtl::is_nothrow_swappable<Compare>::value ) |
7c673cae FG |
1270 | { m_flat_tree.swap(x.m_flat_tree); } |
1271 | ||
92f5a8d4 | 1272 | //! <b>Effects</b>: erase(begin(),end()). |
7c673cae FG |
1273 | //! |
1274 | //! <b>Postcondition</b>: size() == 0. | |
1275 | //! | |
1276 | //! <b>Complexity</b>: linear in size(). | |
b32b8144 | 1277 | BOOST_CONTAINER_FORCEINLINE void clear() BOOST_NOEXCEPT_OR_NOTHROW |
7c673cae FG |
1278 | { m_flat_tree.clear(); } |
1279 | ||
1280 | ////////////////////////////////////////////// | |
1281 | // | |
1282 | // observers | |
1283 | // | |
1284 | ////////////////////////////////////////////// | |
1285 | ||
1286 | //! <b>Effects</b>: Returns the comparison object out | |
1287 | //! of which a was constructed. | |
1288 | //! | |
1289 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 1290 | BOOST_CONTAINER_FORCEINLINE key_compare key_comp() const |
11fdf7f2 | 1291 | { return dtl::force_copy<key_compare>(m_flat_tree.key_comp()); } |
7c673cae FG |
1292 | |
1293 | //! <b>Effects</b>: Returns an object of value_compare constructed out | |
1294 | //! of the comparison object. | |
1295 | //! | |
1296 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 1297 | BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const |
11fdf7f2 | 1298 | { return value_compare(dtl::force_copy<key_compare>(m_flat_tree.key_comp())); } |
7c673cae FG |
1299 | |
1300 | ////////////////////////////////////////////// | |
1301 | // | |
1302 | // map operations | |
1303 | // | |
1304 | ////////////////////////////////////////////// | |
1305 | ||
1306 | //! <b>Returns</b>: An iterator pointing to an element with the key | |
1307 | //! equivalent to x, or end() if such an element is not found. | |
1308 | //! | |
1309 | //! <b>Complexity</b>: Logarithmic. | |
b32b8144 | 1310 | BOOST_CONTAINER_FORCEINLINE iterator find(const key_type& x) |
11fdf7f2 | 1311 | { return dtl::force_copy<iterator>(m_flat_tree.find(x)); } |
7c673cae FG |
1312 | |
1313 | //! <b>Returns</b>: A const_iterator pointing to an element with the key | |
1314 | //! equivalent to x, or end() if such an element is not found. | |
1315 | //! | |
1316 | //! <b>Complexity</b>: Logarithmic. | |
b32b8144 | 1317 | BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& x) const |
11fdf7f2 | 1318 | { return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); } |
7c673cae | 1319 | |
92f5a8d4 TL |
1320 | //! <b>Requires</b>: This overload is available only if |
1321 | //! key_compare::is_transparent exists. | |
1322 | //! | |
1323 | //! <b>Returns</b>: An iterator pointing to an element with the key | |
1324 | //! equivalent to x, or end() if such an element is not found. | |
1325 | //! | |
1326 | //! <b>Complexity</b>: Logarithmic. | |
1327 | template<class K> | |
1328 | BOOST_CONTAINER_FORCEINLINE iterator find(const K& x) | |
1329 | { return dtl::force_copy<iterator>(m_flat_tree.find(x)); } | |
1330 | ||
1331 | //! <b>Requires</b>: This overload is available only if | |
1332 | //! key_compare::is_transparent exists. | |
1333 | //! | |
1334 | //! <b>Returns</b>: A const_iterator pointing to an element with the key | |
1335 | //! equivalent to x, or end() if such an element is not found. | |
1336 | //! | |
1337 | //! <b>Complexity</b>: Logarithmic. | |
1338 | template<class K> | |
1339 | BOOST_CONTAINER_FORCEINLINE const_iterator find(const K& x) const | |
1340 | { return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); } | |
1341 | ||
7c673cae FG |
1342 | //! <b>Returns</b>: The number of elements with key equivalent to x. |
1343 | //! | |
1344 | //! <b>Complexity</b>: log(size())+count(k) | |
b32b8144 | 1345 | BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const |
7c673cae FG |
1346 | { return static_cast<size_type>(m_flat_tree.find(x) != m_flat_tree.end()); } |
1347 | ||
92f5a8d4 TL |
1348 | //! <b>Requires</b>: This overload is available only if |
1349 | //! key_compare::is_transparent exists. | |
1350 | //! | |
1351 | //! <b>Returns</b>: The number of elements with key equivalent to x. | |
1352 | //! | |
1353 | //! <b>Complexity</b>: log(size())+count(k) | |
1354 | template<class K> | |
1355 | BOOST_CONTAINER_FORCEINLINE size_type count(const K& x) const | |
1356 | //Don't use find() != end optimization here as transparent comparators with key K might | |
1357 | //return a different range than key_type (which can only return a single element range) | |
1358 | { return m_flat_tree.count(x); } | |
1359 | ||
1360 | //! <b>Returns</b>: Returns true if there is an element with key | |
1361 | //! equivalent to key in the container, otherwise false. | |
1362 | //! | |
1363 | //! <b>Complexity</b>: log(size()). | |
1364 | bool contains(const key_type& x) const | |
1365 | { return m_flat_tree.find(x) != m_flat_tree.end(); } | |
1366 | ||
1367 | //! <b>Requires</b>: This overload is available only if | |
1368 | //! key_compare::is_transparent exists. | |
1369 | //! | |
1370 | //! <b>Returns</b>: Returns true if there is an element with key | |
1371 | //! equivalent to key in the container, otherwise false. | |
1372 | //! | |
1373 | //! <b>Complexity</b>: log(size()). | |
1374 | template<typename K> | |
1375 | bool contains(const K& x) const | |
1376 | { return m_flat_tree.find(x) != m_flat_tree.end(); } | |
1377 | ||
7c673cae | 1378 | //! <b>Returns</b>: An iterator pointing to the first element with key not less |
92f5a8d4 | 1379 | //! than x, or end() if such an element is not found. |
7c673cae FG |
1380 | //! |
1381 | //! <b>Complexity</b>: Logarithmic. | |
b32b8144 | 1382 | BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& x) |
11fdf7f2 | 1383 | { return dtl::force_copy<iterator>(m_flat_tree.lower_bound(x)); } |
7c673cae FG |
1384 | |
1385 | //! <b>Returns</b>: A const iterator pointing to the first element with key not | |
92f5a8d4 | 1386 | //! less than x, or end() if such an element is not found. |
7c673cae FG |
1387 | //! |
1388 | //! <b>Complexity</b>: Logarithmic. | |
b32b8144 | 1389 | BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& x) const |
11fdf7f2 | 1390 | { return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); } |
7c673cae | 1391 | |
92f5a8d4 TL |
1392 | //! <b>Requires</b>: This overload is available only if |
1393 | //! key_compare::is_transparent exists. | |
1394 | //! | |
7c673cae FG |
1395 | //! <b>Returns</b>: An iterator pointing to the first element with key not less |
1396 | //! than x, or end() if such an element is not found. | |
1397 | //! | |
1398 | //! <b>Complexity</b>: Logarithmic. | |
92f5a8d4 TL |
1399 | template<class K> |
1400 | BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const K& x) | |
1401 | { return dtl::force_copy<iterator>(m_flat_tree.lower_bound(x)); } | |
7c673cae | 1402 | |
92f5a8d4 TL |
1403 | //! <b>Requires</b>: This overload is available only if |
1404 | //! key_compare::is_transparent exists. | |
1405 | //! | |
7c673cae FG |
1406 | //! <b>Returns</b>: A const iterator pointing to the first element with key not |
1407 | //! less than x, or end() if such an element is not found. | |
1408 | //! | |
1409 | //! <b>Complexity</b>: Logarithmic. | |
92f5a8d4 TL |
1410 | template<class K> |
1411 | BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const K& x) const | |
1412 | { return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); } | |
1413 | ||
1414 | //! <b>Returns</b>: An iterator pointing to the first element with key greater | |
1415 | //! than x, or end() if such an element is not found. | |
1416 | //! | |
1417 | //! <b>Complexity</b>: Logarithmic. | |
1418 | BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& x) | |
1419 | { return dtl::force_copy<iterator>(m_flat_tree.upper_bound(x)); } | |
1420 | ||
1421 | //! <b>Returns</b>: A const iterator pointing to the first element with key | |
1422 | //! greater than x, or end() if such an element is not found. | |
1423 | //! | |
1424 | //! <b>Complexity</b>: Logarithmic. | |
b32b8144 | 1425 | BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& x) const |
11fdf7f2 | 1426 | { return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); } |
7c673cae | 1427 | |
92f5a8d4 TL |
1428 | //! <b>Requires</b>: This overload is available only if |
1429 | //! key_compare::is_transparent exists. | |
1430 | //! | |
1431 | //! <b>Returns</b>: An iterator pointing to the first element with key greater | |
1432 | //! than x, or end() if such an element is not found. | |
1433 | //! | |
1434 | //! <b>Complexity</b>: Logarithmic. | |
1435 | template<class K> | |
1436 | BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const K& x) | |
1437 | { return dtl::force_copy<iterator>(m_flat_tree.upper_bound(x)); } | |
1438 | ||
1439 | //! <b>Requires</b>: This overload is available only if | |
1440 | //! key_compare::is_transparent exists. | |
1441 | //! | |
1442 | //! <b>Returns</b>: A const iterator pointing to the first element with key | |
1443 | //! greater than x, or end() if such an element is not found. | |
1444 | //! | |
1445 | //! <b>Complexity</b>: Logarithmic. | |
1446 | template<class K> | |
1447 | BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const K& x) const | |
1448 | { return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); } | |
1449 | ||
7c673cae FG |
1450 | //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). |
1451 | //! | |
1452 | //! <b>Complexity</b>: Logarithmic. | |
b32b8144 | 1453 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type& x) |
11fdf7f2 | 1454 | { return dtl::force_copy<std::pair<iterator,iterator> >(m_flat_tree.lower_bound_range(x)); } |
7c673cae FG |
1455 | |
1456 | //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). | |
1457 | //! | |
1458 | //! <b>Complexity</b>: Logarithmic. | |
b32b8144 | 1459 | BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const |
11fdf7f2 | 1460 | { return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.lower_bound_range(x)); } |
7c673cae | 1461 | |
92f5a8d4 TL |
1462 | //! <b>Requires</b>: This overload is available only if |
1463 | //! key_compare::is_transparent exists. | |
1464 | //! | |
1465 | //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). | |
1466 | //! | |
1467 | //! <b>Complexity</b>: Logarithmic. | |
1468 | template<class K> | |
1469 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const K& x) | |
1470 | //Don't use lower_bound_range optimization here as transparent comparators with key K might | |
1471 | //return a different range than key_type (which can only return a single element range) | |
1472 | { return dtl::force_copy<std::pair<iterator,iterator> >(m_flat_tree.equal_range(x)); } | |
1473 | ||
1474 | //! <b>Requires</b>: This overload is available only if | |
1475 | //! key_compare::is_transparent exists. | |
1476 | //! | |
1477 | //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). | |
1478 | //! | |
1479 | //! <b>Complexity</b>: Logarithmic. | |
1480 | template<class K> | |
1481 | BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const K& x) const | |
1482 | //Don't use lower_bound_range optimization here as transparent comparators with key K might | |
1483 | //return a different range than key_type (which can only return a single element range) | |
1484 | { return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(x)); } | |
1485 | ||
b32b8144 FG |
1486 | //! <b>Effects</b>: Extracts the internal sequence container. |
1487 | //! | |
1488 | //! <b>Complexity</b>: Same as the move constructor of sequence_type, usually constant. | |
1489 | //! | |
1490 | //! <b>Postcondition</b>: this->empty() | |
1491 | //! | |
1492 | //! <b>Throws</b>: If secuence_type's move constructor throws | |
1493 | BOOST_CONTAINER_FORCEINLINE sequence_type extract_sequence() | |
1494 | { | |
11fdf7f2 | 1495 | return boost::move(dtl::force<sequence_type>(m_flat_tree.get_sequence_ref())); |
b32b8144 FG |
1496 | } |
1497 | ||
1498 | //! <b>Effects</b>: Discards the internally hold sequence container and adopts the | |
1499 | //! one passed externally using the move assignment. Erases non-unique elements. | |
1500 | //! | |
1501 | //! <b>Complexity</b>: Assuming O(1) move assignment, O(NlogN) with N = seq.size() | |
1502 | //! | |
1503 | //! <b>Throws</b>: If the comparison or the move constructor throws | |
1504 | BOOST_CONTAINER_FORCEINLINE void adopt_sequence(BOOST_RV_REF(sequence_type) seq) | |
11fdf7f2 | 1505 | { this->m_flat_tree.adopt_sequence_unique(boost::move(dtl::force<impl_sequence_type>(seq))); } |
b32b8144 FG |
1506 | |
1507 | //! <b>Requires</b>: seq shall be ordered according to this->compare() | |
1508 | //! and shall contain unique elements. | |
1509 | //! | |
1510 | //! <b>Effects</b>: Discards the internally hold sequence container and adopts the | |
1511 | //! one passed externally using the move assignment. | |
1512 | //! | |
1513 | //! <b>Complexity</b>: Assuming O(1) move assignment, O(1) | |
1514 | //! | |
1515 | //! <b>Throws</b>: If the move assignment throws | |
1516 | BOOST_CONTAINER_FORCEINLINE void adopt_sequence(ordered_unique_range_t, BOOST_RV_REF(sequence_type) seq) | |
11fdf7f2 | 1517 | { this->m_flat_tree.adopt_sequence_unique(ordered_unique_range_t(), boost::move(dtl::force<impl_sequence_type>(seq))); } |
b32b8144 | 1518 | |
7c673cae FG |
1519 | //! <b>Effects</b>: Returns true if x and y are equal |
1520 | //! | |
1521 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
b32b8144 | 1522 | BOOST_CONTAINER_FORCEINLINE friend bool operator==(const flat_map& x, const flat_map& y) |
7c673cae FG |
1523 | { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } |
1524 | ||
1525 | //! <b>Effects</b>: Returns true if x and y are unequal | |
1526 | //! | |
1527 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
b32b8144 | 1528 | BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const flat_map& x, const flat_map& y) |
7c673cae FG |
1529 | { return !(x == y); } |
1530 | ||
1531 | //! <b>Effects</b>: Returns true if x is less than y | |
1532 | //! | |
1533 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
b32b8144 | 1534 | BOOST_CONTAINER_FORCEINLINE friend bool operator<(const flat_map& x, const flat_map& y) |
7c673cae FG |
1535 | { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } |
1536 | ||
1537 | //! <b>Effects</b>: Returns true if x is greater than y | |
1538 | //! | |
1539 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
b32b8144 | 1540 | BOOST_CONTAINER_FORCEINLINE friend bool operator>(const flat_map& x, const flat_map& y) |
7c673cae FG |
1541 | { return y < x; } |
1542 | ||
1543 | //! <b>Effects</b>: Returns true if x is equal or less than y | |
1544 | //! | |
1545 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
b32b8144 | 1546 | BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const flat_map& x, const flat_map& y) |
7c673cae FG |
1547 | { return !(y < x); } |
1548 | ||
1549 | //! <b>Effects</b>: Returns true if x is equal or greater than y | |
1550 | //! | |
1551 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
b32b8144 | 1552 | BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const flat_map& x, const flat_map& y) |
7c673cae FG |
1553 | { return !(x < y); } |
1554 | ||
1555 | //! <b>Effects</b>: x.swap(y) | |
1556 | //! | |
1557 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 1558 | BOOST_CONTAINER_FORCEINLINE friend void swap(flat_map& x, flat_map& y) |
7c673cae FG |
1559 | { x.swap(y); } |
1560 | ||
1561 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
1562 | private: | |
1563 | mapped_type &priv_subscript(const key_type& k) | |
1564 | { | |
1565 | iterator i = lower_bound(k); | |
1566 | // i->first is greater than or equivalent to k. | |
1567 | if (i == end() || key_comp()(k, (*i).first)){ | |
11fdf7f2 | 1568 | dtl::value_init<mapped_type> m; |
7c673cae FG |
1569 | i = insert(i, impl_value_type(k, ::boost::move(m.m_t))); |
1570 | } | |
1571 | return (*i).second; | |
1572 | } | |
1573 | mapped_type &priv_subscript(BOOST_RV_REF(key_type) mk) | |
1574 | { | |
1575 | key_type &k = mk; | |
1576 | iterator i = lower_bound(k); | |
1577 | // i->first is greater than or equivalent to k. | |
1578 | if (i == end() || key_comp()(k, (*i).first)){ | |
11fdf7f2 | 1579 | dtl::value_init<mapped_type> m; |
7c673cae FG |
1580 | i = insert(i, impl_value_type(boost::move(k), ::boost::move(m.m_t))); |
1581 | } | |
1582 | return (*i).second; | |
1583 | } | |
1584 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
1585 | }; | |
1586 | ||
92f5a8d4 TL |
1587 | #ifndef BOOST_CONTAINER_NO_CXX17_CTAD |
1588 | ||
1589 | template <typename InputIterator> | |
1590 | flat_map(InputIterator, InputIterator) -> | |
1591 | flat_map< it_based_non_const_first_type_t<InputIterator> | |
1592 | , it_based_second_type_t<InputIterator>>; | |
1593 | ||
1594 | template < typename InputIterator, typename AllocatorOrCompare> | |
1595 | flat_map(InputIterator, InputIterator, AllocatorOrCompare const&) -> | |
1596 | flat_map< it_based_non_const_first_type_t<InputIterator> | |
1597 | , it_based_second_type_t<InputIterator> | |
1598 | , typename dtl::if_c< // Compare | |
1599 | dtl::is_allocator<AllocatorOrCompare>::value | |
1600 | , std::less<it_based_non_const_first_type_t<InputIterator>> | |
1601 | , AllocatorOrCompare | |
1602 | >::type | |
1603 | , typename dtl::if_c< // Allocator | |
1604 | dtl::is_allocator<AllocatorOrCompare>::value | |
1605 | , AllocatorOrCompare | |
1606 | , new_allocator<std::pair<it_based_non_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>> | |
1607 | >::type | |
1608 | >; | |
1609 | ||
1610 | template < typename InputIterator, typename Compare, typename Allocator | |
1611 | , typename = dtl::require_nonallocator_t<Compare> | |
1612 | , typename = dtl::require_allocator_t<Allocator>> | |
1613 | flat_map(InputIterator, InputIterator, Compare const&, Allocator const&) -> | |
1614 | flat_map< it_based_non_const_first_type_t<InputIterator> | |
1615 | , it_based_second_type_t<InputIterator> | |
1616 | , Compare | |
1617 | , Allocator>; | |
1618 | ||
1619 | template <typename InputIterator> | |
1620 | flat_map(ordered_unique_range_t, InputIterator, InputIterator) -> | |
1621 | flat_map< it_based_non_const_first_type_t<InputIterator> | |
1622 | , it_based_second_type_t<InputIterator>>; | |
1623 | ||
1624 | template < typename InputIterator, typename AllocatorOrCompare> | |
1625 | flat_map(ordered_unique_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) -> | |
1626 | flat_map< it_based_non_const_first_type_t<InputIterator> | |
1627 | , it_based_second_type_t<InputIterator> | |
1628 | , typename dtl::if_c< // Compare | |
1629 | dtl::is_allocator<AllocatorOrCompare>::value | |
1630 | , std::less<it_based_non_const_first_type_t<InputIterator>> | |
1631 | , AllocatorOrCompare | |
1632 | >::type | |
1633 | , typename dtl::if_c< // Allocator | |
1634 | dtl::is_allocator<AllocatorOrCompare>::value | |
1635 | , AllocatorOrCompare | |
1636 | , new_allocator<std::pair<it_based_non_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>> | |
1637 | >::type | |
1638 | >; | |
1639 | ||
1640 | template < typename InputIterator, typename Compare, typename Allocator | |
1641 | , typename = dtl::require_nonallocator_t<Compare> | |
1642 | , typename = dtl::require_allocator_t<Allocator>> | |
1643 | flat_map(ordered_unique_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) -> | |
1644 | flat_map< it_based_non_const_first_type_t<InputIterator> | |
1645 | , it_based_second_type_t<InputIterator> | |
1646 | , Compare | |
1647 | , Allocator>; | |
1648 | ||
1649 | #endif | |
1650 | ||
7c673cae FG |
1651 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED |
1652 | ||
1653 | } //namespace container { | |
1654 | ||
1655 | //!has_trivial_destructor_after_move<> == true_type | |
1656 | //!specialization for optimizations | |
b32b8144 FG |
1657 | template <class Key, class T, class Compare, class AllocatorOrContainer> |
1658 | struct has_trivial_destructor_after_move<boost::container::flat_map<Key, T, Compare, AllocatorOrContainer> > | |
7c673cae | 1659 | { |
92f5a8d4 TL |
1660 | typedef ::boost::container::dtl::pair<Key, T> value_t; |
1661 | typedef typename ::boost::container::dtl::container_or_allocator_rebind<AllocatorOrContainer, value_t>::type alloc_or_cont_t; | |
1662 | typedef ::boost::container::dtl::flat_tree<value_t,::boost::container::dtl::select1st<Key>, Compare, alloc_or_cont_t> tree; | |
1663 | static const bool value = ::boost::has_trivial_destructor_after_move<tree>::value; | |
7c673cae FG |
1664 | }; |
1665 | ||
1666 | namespace container { | |
1667 | ||
1668 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
1669 | ||
1670 | //! A flat_multimap is a kind of associative container that supports equivalent keys | |
1671 | //! (possibly containing multiple copies of the same key value) and provides for | |
b32b8144 | 1672 | //! fast retrieval of values of another type T based on the keys. |
7c673cae FG |
1673 | //! |
1674 | //! A flat_multimap satisfies all of the requirements of a container and of a reversible | |
1675 | //! container and of an associative container. For a | |
1676 | //! flat_multimap<Key,T> the key_type is Key and the value_type is std::pair<Key,T> | |
1677 | //! (unlike std::multimap<Key, T> which value_type is std::pair<<b>const</b> Key, T>). | |
1678 | //! | |
b32b8144 FG |
1679 | //! flat_multimap is similar to std::multimap but it's implemented by as an ordered sequence container. |
1680 | //! The underlying sequence container is by default <i>vector</i> but it can also work | |
1681 | //! user-provided vector-like SequenceContainers (like <i>static_vector</i> or <i>small_vector</i>). | |
7c673cae | 1682 | //! |
b32b8144 FG |
1683 | //! Using vector-like sequence containers means that inserting a new element into a flat_multimap might invalidate |
1684 | //! previous iterators and references (unless that sequence container is <i>stable_vector</i> or a similar | |
1685 | //! container that offers stable pointers and references). Similarly, erasing an element might invalidate | |
1686 | //! iterators and references pointing to elements that come after (their keys are bigger) the erased element. | |
7c673cae FG |
1687 | //! |
1688 | //! This container provides random-access iterators. | |
1689 | //! | |
1690 | //! \tparam Key is the key_type of the map | |
1691 | //! \tparam Value is the <code>mapped_type</code> | |
1692 | //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). | |
b32b8144 FG |
1693 | //! \tparam AllocatorOrContainer is either: |
1694 | //! - The allocator to allocate <code>value_type</code>s (e.g. <i>allocator< std::pair<Key, T> > </i>). | |
1695 | //! (in this case <i>sequence_type</i> will be vector<value_type, AllocatorOrContainer>) | |
1696 | //! - The SequenceContainer to be used as the underlying <i>sequence_type</i>. It must be a vector-like | |
1697 | //! sequence container with random-access iterators. | |
7c673cae | 1698 | #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED |
b32b8144 | 1699 | template <class Key, class T, class Compare = std::less<Key>, class AllocatorOrContainer = new_allocator< std::pair< Key, T> > > |
7c673cae | 1700 | #else |
b32b8144 | 1701 | template <class Key, class T, class Compare, class AllocatorOrContainer> |
7c673cae FG |
1702 | #endif |
1703 | class flat_multimap | |
1704 | { | |
1705 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
1706 | private: | |
1707 | BOOST_COPYABLE_AND_MOVABLE(flat_multimap) | |
11fdf7f2 | 1708 | typedef dtl::flat_tree< |
7c673cae | 1709 | std::pair<Key, T>, |
11fdf7f2 | 1710 | dtl::select1st<Key>, |
7c673cae | 1711 | Compare, |
b32b8144 | 1712 | AllocatorOrContainer> tree_t; |
7c673cae | 1713 | //This is the real tree stored here. It's based on a movable pair |
11fdf7f2 TL |
1714 | typedef dtl::flat_tree< |
1715 | dtl::pair<Key, T>, | |
1716 | dtl::select1st<Key>, | |
7c673cae | 1717 | Compare, |
11fdf7f2 | 1718 | typename dtl::container_or_allocator_rebind<AllocatorOrContainer, dtl::pair<Key, T> >::type |
b32b8144 | 1719 | > impl_tree_t; |
7c673cae FG |
1720 | impl_tree_t m_flat_tree; // flat tree representing flat_map |
1721 | ||
1722 | typedef typename impl_tree_t::value_type impl_value_type; | |
1723 | typedef typename impl_tree_t::const_iterator impl_const_iterator; | |
1724 | typedef typename impl_tree_t::iterator impl_iterator; | |
1725 | typedef typename impl_tree_t::allocator_type impl_allocator_type; | |
b32b8144 FG |
1726 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) |
1727 | typedef std::initializer_list<impl_value_type> impl_initializer_list; | |
1728 | #endif | |
1729 | ||
11fdf7f2 | 1730 | typedef dtl::flat_tree_value_compare |
7c673cae | 1731 | < Compare |
11fdf7f2 | 1732 | , dtl::select1st<Key> |
b32b8144 FG |
1733 | , std::pair<Key, T> > value_compare_t; |
1734 | typedef typename tree_t::iterator iterator_t; | |
1735 | typedef typename tree_t::const_iterator const_iterator_t; | |
1736 | typedef typename tree_t::reverse_iterator reverse_iterator_t; | |
1737 | typedef typename tree_t::const_reverse_iterator const_reverse_iterator_t; | |
1738 | ||
7c673cae | 1739 | public: |
b32b8144 FG |
1740 | typedef typename impl_tree_t::stored_allocator_type impl_stored_allocator_type; |
1741 | typedef typename impl_tree_t::sequence_type impl_sequence_type; | |
7c673cae | 1742 | |
b32b8144 | 1743 | BOOST_CONTAINER_FORCEINLINE impl_tree_t &tree() |
7c673cae FG |
1744 | { return m_flat_tree; } |
1745 | ||
b32b8144 | 1746 | BOOST_CONTAINER_FORCEINLINE const impl_tree_t &tree() const |
7c673cae FG |
1747 | { return m_flat_tree; } |
1748 | ||
1749 | private: | |
1750 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
1751 | ||
1752 | public: | |
1753 | ||
1754 | ////////////////////////////////////////////// | |
1755 | // | |
1756 | // types | |
1757 | // | |
1758 | ////////////////////////////////////////////// | |
1759 | typedef Key key_type; | |
1760 | typedef T mapped_type; | |
7c673cae | 1761 | typedef Compare key_compare; |
b32b8144 FG |
1762 | typedef std::pair<Key, T> value_type; |
1763 | typedef typename BOOST_CONTAINER_IMPDEF(tree_t::sequence_type) sequence_type; | |
1764 | typedef typename sequence_type::allocator_type allocator_type; | |
1765 | typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type; | |
1766 | typedef typename sequence_type::pointer pointer; | |
1767 | typedef typename sequence_type::const_pointer const_pointer; | |
1768 | typedef typename sequence_type::reference reference; | |
1769 | typedef typename sequence_type::const_reference const_reference; | |
1770 | typedef typename sequence_type::size_type size_type; | |
1771 | typedef typename sequence_type::difference_type difference_type; | |
1772 | typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type; | |
1773 | typedef typename BOOST_CONTAINER_IMPDEF(tree_t::value_compare) value_compare; | |
1774 | ||
1775 | typedef typename sequence_type::iterator iterator; | |
1776 | typedef typename sequence_type::const_iterator const_iterator; | |
1777 | typedef typename sequence_type::reverse_iterator reverse_iterator; | |
1778 | typedef typename sequence_type::const_reverse_iterator const_reverse_iterator; | |
7c673cae FG |
1779 | typedef BOOST_CONTAINER_IMPDEF(impl_value_type) movable_value_type; |
1780 | ||
b32b8144 | 1781 | //AllocatorOrContainer::value_type must be std::pair<Key, T> |
92f5a8d4 | 1782 | BOOST_STATIC_ASSERT((dtl::is_same<std::pair<Key, T>, value_type>::value)); |
b32b8144 | 1783 | |
7c673cae FG |
1784 | ////////////////////////////////////////////// |
1785 | // | |
1786 | // construct/copy/destroy | |
1787 | // | |
1788 | ////////////////////////////////////////////// | |
1789 | ||
1790 | //! <b>Effects</b>: Default constructs an empty flat_map. | |
1791 | //! | |
1792 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 1793 | BOOST_CONTAINER_FORCEINLINE flat_multimap() |
11fdf7f2 TL |
1794 | BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<AllocatorOrContainer>::value && |
1795 | dtl::is_nothrow_default_constructible<Compare>::value) | |
7c673cae | 1796 | : m_flat_tree() |
b32b8144 FG |
1797 | {} |
1798 | ||
1799 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified allocator. | |
1800 | //! | |
1801 | //! <b>Complexity</b>: Constant. | |
1802 | BOOST_CONTAINER_FORCEINLINE explicit flat_multimap(const allocator_type& a) | |
11fdf7f2 | 1803 | : m_flat_tree(dtl::force<const impl_allocator_type>(a)) |
b32b8144 | 1804 | {} |
7c673cae FG |
1805 | |
1806 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison | |
b32b8144 | 1807 | //! object . |
7c673cae FG |
1808 | //! |
1809 | //! <b>Complexity</b>: Constant. | |
b32b8144 FG |
1810 | BOOST_CONTAINER_FORCEINLINE explicit flat_multimap(const Compare& comp) |
1811 | : m_flat_tree(comp) | |
1812 | {} | |
7c673cae | 1813 | |
b32b8144 FG |
1814 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison |
1815 | //! object and allocator. | |
7c673cae FG |
1816 | //! |
1817 | //! <b>Complexity</b>: Constant. | |
b32b8144 FG |
1818 | BOOST_CONTAINER_FORCEINLINE |
1819 | flat_multimap(const Compare& comp, const allocator_type& a) | |
11fdf7f2 | 1820 | : m_flat_tree(comp, dtl::force<const impl_allocator_type>(a)) |
b32b8144 | 1821 | {} |
7c673cae | 1822 | |
b32b8144 FG |
1823 | //! <b>Effects</b>: Constructs an empty flat_multimap |
1824 | //! and inserts elements from the range [first ,last ). | |
7c673cae FG |
1825 | //! |
1826 | //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using | |
b32b8144 | 1827 | //! the predicate and otherwise N logN, where N is last - first. |
7c673cae | 1828 | template <class InputIterator> |
b32b8144 FG |
1829 | BOOST_CONTAINER_FORCEINLINE |
1830 | flat_multimap(InputIterator first, InputIterator last) | |
1831 | : m_flat_tree(false, first, last) | |
1832 | {} | |
7c673cae FG |
1833 | |
1834 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified | |
1835 | //! allocator, and inserts elements from the range [first ,last ). | |
1836 | //! | |
1837 | //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using | |
b32b8144 | 1838 | //! the predicate and otherwise N logN, where N is last - first. |
7c673cae | 1839 | template <class InputIterator> |
b32b8144 | 1840 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 1841 | flat_multimap(InputIterator first, InputIterator last, const allocator_type& a) |
11fdf7f2 | 1842 | : m_flat_tree(false, first, last, dtl::force<const impl_allocator_type>(a)) |
b32b8144 FG |
1843 | {} |
1844 | ||
1845 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object | |
1846 | //! and inserts elements from the range [first ,last ). | |
1847 | //! | |
1848 | //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using | |
1849 | //! the predicate and otherwise N logN, where N is last - first. | |
1850 | template <class InputIterator> | |
1851 | BOOST_CONTAINER_FORCEINLINE | |
1852 | flat_multimap(InputIterator first, InputIterator last, const Compare& comp) | |
1853 | : m_flat_tree(false, first, last, comp) | |
1854 | {} | |
1855 | ||
1856 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object | |
1857 | //! and allocator, and inserts elements from the range [first ,last ). | |
1858 | //! | |
1859 | //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using | |
1860 | //! the predicate and otherwise N logN, where N is last - first. | |
1861 | template <class InputIterator> | |
1862 | BOOST_CONTAINER_FORCEINLINE | |
1863 | flat_multimap(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a) | |
11fdf7f2 | 1864 | : m_flat_tree(false, first, last, comp, dtl::force<const impl_allocator_type>(a)) |
b32b8144 FG |
1865 | {} |
1866 | ||
1867 | //! <b>Effects</b>: Constructs an empty flat_multimap | |
1868 | //! and inserts elements from the ordered range [first ,last). This function | |
1869 | //! is more efficient than the normal range creation for ordered ranges. | |
1870 | //! | |
1871 | //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. | |
1872 | //! | |
1873 | //! <b>Complexity</b>: Linear in N. | |
1874 | //! | |
1875 | //! <b>Note</b>: Non-standard extension. | |
1876 | template <class InputIterator> | |
1877 | BOOST_CONTAINER_FORCEINLINE | |
1878 | flat_multimap(ordered_range_t, InputIterator first, InputIterator last) | |
1879 | : m_flat_tree(ordered_range, first, last) | |
1880 | {} | |
1881 | ||
1882 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and | |
1883 | //! inserts elements from the ordered range [first ,last). This function | |
1884 | //! is more efficient than the normal range creation for ordered ranges. | |
1885 | //! | |
1886 | //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. | |
1887 | //! | |
1888 | //! <b>Complexity</b>: Linear in N. | |
1889 | //! | |
1890 | //! <b>Note</b>: Non-standard extension. | |
1891 | template <class InputIterator> | |
1892 | BOOST_CONTAINER_FORCEINLINE | |
1893 | flat_multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp) | |
1894 | : m_flat_tree(ordered_range, first, last, comp) | |
1895 | {} | |
7c673cae FG |
1896 | |
1897 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and | |
1898 | //! allocator, and inserts elements from the ordered range [first ,last). This function | |
1899 | //! is more efficient than the normal range creation for ordered ranges. | |
1900 | //! | |
1901 | //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. | |
1902 | //! | |
1903 | //! <b>Complexity</b>: Linear in N. | |
1904 | //! | |
1905 | //! <b>Note</b>: Non-standard extension. | |
1906 | template <class InputIterator> | |
b32b8144 FG |
1907 | BOOST_CONTAINER_FORCEINLINE |
1908 | flat_multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a) | |
7c673cae | 1909 | : m_flat_tree(ordered_range, first, last, comp, a) |
b32b8144 | 1910 | {} |
7c673cae | 1911 | |
92f5a8d4 TL |
1912 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and |
1913 | //! inserts elements from the ordered range [first ,last). This function | |
1914 | //! is more efficient than the normal range creation for ordered ranges. | |
1915 | //! | |
1916 | //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. | |
1917 | //! | |
1918 | //! <b>Complexity</b>: Linear in N. | |
1919 | //! | |
1920 | //! <b>Note</b>: Non-standard extension. | |
1921 | template <class InputIterator> | |
1922 | BOOST_CONTAINER_FORCEINLINE | |
1923 | flat_multimap(ordered_range_t, InputIterator first, InputIterator last, const allocator_type &a) | |
1924 | : m_flat_tree(ordered_range, first, last, Compare(), a) | |
1925 | {} | |
1926 | ||
7c673cae | 1927 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) |
b32b8144 FG |
1928 | //! <b>Effects</b>: Constructs an empty flat_map and |
1929 | //! inserts elements from the range [il.begin(), il.end()). | |
7c673cae FG |
1930 | //! |
1931 | //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using | |
b32b8144 FG |
1932 | //! the predicate and otherwise N logN, where N is last - first. |
1933 | BOOST_CONTAINER_FORCEINLINE | |
1934 | flat_multimap(std::initializer_list<value_type> il) | |
1935 | : m_flat_tree( false | |
11fdf7f2 TL |
1936 | , dtl::force<impl_initializer_list>(il).begin() |
1937 | , dtl::force<impl_initializer_list>(il).end()) | |
b32b8144 | 1938 | {} |
7c673cae FG |
1939 | |
1940 | //! <b>Effects</b>: Constructs an empty flat_map using the specified | |
1941 | //! allocator, and inserts elements from the range [il.begin(), il.end()). | |
1942 | //! | |
1943 | //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using | |
b32b8144 FG |
1944 | //! the predicate and otherwise N logN, where N is last - first. |
1945 | BOOST_CONTAINER_FORCEINLINE | |
7c673cae | 1946 | flat_multimap(std::initializer_list<value_type> il, const allocator_type& a) |
b32b8144 | 1947 | : m_flat_tree(false |
11fdf7f2 TL |
1948 | , dtl::force<impl_initializer_list>(il).begin() |
1949 | , dtl::force<impl_initializer_list>(il).end() | |
1950 | , dtl::force<const impl_allocator_type>(a)) | |
b32b8144 FG |
1951 | {} |
1952 | ||
1953 | //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and | |
1954 | //! inserts elements from the range [il.begin(), il.end()). | |
1955 | //! | |
1956 | //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using | |
1957 | //! the predicate and otherwise N logN, where N is last - first. | |
1958 | BOOST_CONTAINER_FORCEINLINE | |
1959 | flat_multimap(std::initializer_list<value_type> il, const Compare& comp) | |
1960 | : m_flat_tree(false | |
11fdf7f2 TL |
1961 | , dtl::force<impl_initializer_list>(il).begin() |
1962 | , dtl::force<impl_initializer_list>(il).end(), comp) | |
b32b8144 FG |
1963 | {} |
1964 | ||
1965 | //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and | |
1966 | //! allocator, and inserts elements from the range [il.begin(), il.end()). | |
1967 | //! | |
1968 | //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using | |
1969 | //! the predicate and otherwise N logN, where N is last - first. | |
1970 | BOOST_CONTAINER_FORCEINLINE | |
1971 | flat_multimap(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a) | |
1972 | : m_flat_tree( false | |
11fdf7f2 TL |
1973 | , dtl::force<impl_initializer_list>(il).begin() |
1974 | , dtl::force<impl_initializer_list>(il).end() | |
1975 | , comp, dtl::force<const impl_allocator_type>(a)) | |
b32b8144 FG |
1976 | {} |
1977 | ||
1978 | //! <b>Effects</b>: Constructs an empty flat_multimap and | |
1979 | //! inserts elements from the ordered range [il.begin(), il.end()). This function | |
1980 | //! is more efficient than the normal range creation for ordered ranges. | |
1981 | //! | |
1982 | //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate. | |
1983 | //! | |
1984 | //! <b>Complexity</b>: Linear in N. | |
1985 | //! | |
1986 | //! <b>Note</b>: Non-standard extension. | |
1987 | BOOST_CONTAINER_FORCEINLINE | |
1988 | flat_multimap(ordered_range_t, std::initializer_list<value_type> il) | |
1989 | : m_flat_tree( ordered_range | |
11fdf7f2 TL |
1990 | , dtl::force<impl_initializer_list>(il).begin() |
1991 | , dtl::force<impl_initializer_list>(il).end()) | |
b32b8144 FG |
1992 | {} |
1993 | ||
1994 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and | |
1995 | //! inserts elements from the ordered range [il.begin(), il.end()). This function | |
1996 | //! is more efficient than the normal range creation for ordered ranges. | |
1997 | //! | |
1998 | //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate. | |
1999 | //! | |
2000 | //! <b>Complexity</b>: Linear in N. | |
2001 | //! | |
2002 | //! <b>Note</b>: Non-standard extension. | |
2003 | BOOST_CONTAINER_FORCEINLINE | |
2004 | flat_multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp) | |
2005 | : m_flat_tree( ordered_range | |
11fdf7f2 TL |
2006 | , dtl::force<impl_initializer_list>(il).begin() |
2007 | , dtl::force<impl_initializer_list>(il).end(), comp) | |
b32b8144 | 2008 | {} |
7c673cae FG |
2009 | |
2010 | //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and | |
2011 | //! allocator, and inserts elements from the ordered range [il.begin(), il.end()). This function | |
2012 | //! is more efficient than the normal range creation for ordered ranges. | |
2013 | //! | |
2014 | //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate. | |
2015 | //! | |
2016 | //! <b>Complexity</b>: Linear in N. | |
2017 | //! | |
2018 | //! <b>Note</b>: Non-standard extension. | |
b32b8144 FG |
2019 | BOOST_CONTAINER_FORCEINLINE |
2020 | flat_multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a) | |
2021 | : m_flat_tree( ordered_range | |
11fdf7f2 TL |
2022 | , dtl::force<impl_initializer_list>(il).begin() |
2023 | , dtl::force<impl_initializer_list>(il).end() | |
2024 | , comp, dtl::force<const impl_allocator_type>(a)) | |
b32b8144 | 2025 | {} |
7c673cae FG |
2026 | #endif |
2027 | ||
2028 | //! <b>Effects</b>: Copy constructs a flat_multimap. | |
2029 | //! | |
2030 | //! <b>Complexity</b>: Linear in x.size(). | |
b32b8144 | 2031 | BOOST_CONTAINER_FORCEINLINE |
7c673cae FG |
2032 | flat_multimap(const flat_multimap& x) |
2033 | : m_flat_tree(x.m_flat_tree) | |
b32b8144 | 2034 | {} |
7c673cae FG |
2035 | |
2036 | //! <b>Effects</b>: Move constructs a flat_multimap. Constructs *this using x's resources. | |
2037 | //! | |
2038 | //! <b>Complexity</b>: Constant. | |
2039 | //! | |
2040 | //! <b>Postcondition</b>: x is emptied. | |
b32b8144 | 2041 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2042 | flat_multimap(BOOST_RV_REF(flat_multimap) x) |
11fdf7f2 | 2043 | BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value) |
7c673cae | 2044 | : m_flat_tree(boost::move(x.m_flat_tree)) |
b32b8144 | 2045 | {} |
7c673cae FG |
2046 | |
2047 | //! <b>Effects</b>: Copy constructs a flat_multimap using the specified allocator. | |
2048 | //! | |
2049 | //! <b>Complexity</b>: Linear in x.size(). | |
b32b8144 | 2050 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2051 | flat_multimap(const flat_multimap& x, const allocator_type &a) |
11fdf7f2 | 2052 | : m_flat_tree(x.m_flat_tree, dtl::force<const impl_allocator_type>(a)) |
b32b8144 | 2053 | {} |
7c673cae FG |
2054 | |
2055 | //! <b>Effects</b>: Move constructs a flat_multimap using the specified allocator. | |
2056 | //! Constructs *this using x's resources. | |
2057 | //! | |
2058 | //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. | |
b32b8144 | 2059 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2060 | flat_multimap(BOOST_RV_REF(flat_multimap) x, const allocator_type &a) |
11fdf7f2 | 2061 | : m_flat_tree(boost::move(x.m_flat_tree), dtl::force<const impl_allocator_type>(a)) |
b32b8144 | 2062 | {} |
7c673cae FG |
2063 | |
2064 | //! <b>Effects</b>: Makes *this a copy of x. | |
2065 | //! | |
2066 | //! <b>Complexity</b>: Linear in x.size(). | |
b32b8144 | 2067 | BOOST_CONTAINER_FORCEINLINE |
7c673cae FG |
2068 | flat_multimap& operator=(BOOST_COPY_ASSIGN_REF(flat_multimap) x) |
2069 | { m_flat_tree = x.m_flat_tree; return *this; } | |
2070 | ||
2071 | //! <b>Effects</b>: this->swap(x.get()). | |
2072 | //! | |
2073 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2074 | BOOST_CONTAINER_FORCEINLINE |
7c673cae FG |
2075 | flat_multimap& operator=(BOOST_RV_REF(flat_multimap) x) |
2076 | BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value || | |
2077 | allocator_traits_type::is_always_equal::value) && | |
11fdf7f2 | 2078 | boost::container::dtl::is_nothrow_move_assignable<Compare>::value) |
7c673cae FG |
2079 | { m_flat_tree = boost::move(x.m_flat_tree); return *this; } |
2080 | ||
2081 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
2082 | //! <b>Effects</b>: Assign content of il to *this | |
2083 | //! | |
2084 | //! <b>Complexity</b>: Linear in il.size(). | |
b32b8144 | 2085 | BOOST_CONTAINER_FORCEINLINE |
7c673cae FG |
2086 | flat_multimap& operator=(std::initializer_list<value_type> il) |
2087 | { | |
2088 | this->clear(); | |
2089 | this->insert(il.begin(), il.end()); | |
2090 | return *this; | |
2091 | } | |
2092 | #endif | |
2093 | ||
2094 | //! <b>Effects</b>: Returns a copy of the allocator that | |
2095 | //! was passed to the object's constructor. | |
2096 | //! | |
2097 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2098 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2099 | allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2100 | { return dtl::force_copy<allocator_type>(m_flat_tree.get_allocator()); } |
7c673cae FG |
2101 | |
2102 | //! <b>Effects</b>: Returns a reference to the internal allocator. | |
2103 | //! | |
2104 | //! <b>Throws</b>: Nothing | |
2105 | //! | |
2106 | //! <b>Complexity</b>: Constant. | |
2107 | //! | |
2108 | //! <b>Note</b>: Non-standard extension. | |
b32b8144 | 2109 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2110 | stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2111 | { return dtl::force<stored_allocator_type>(m_flat_tree.get_stored_allocator()); } |
7c673cae FG |
2112 | |
2113 | //! <b>Effects</b>: Returns a reference to the internal allocator. | |
2114 | //! | |
2115 | //! <b>Throws</b>: Nothing | |
2116 | //! | |
2117 | //! <b>Complexity</b>: Constant. | |
2118 | //! | |
2119 | //! <b>Note</b>: Non-standard extension. | |
b32b8144 | 2120 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2121 | const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2122 | { return dtl::force<const stored_allocator_type>(m_flat_tree.get_stored_allocator()); } |
7c673cae FG |
2123 | |
2124 | ////////////////////////////////////////////// | |
2125 | // | |
2126 | // iterators | |
2127 | // | |
2128 | ////////////////////////////////////////////// | |
2129 | ||
2130 | //! <b>Effects</b>: Returns an iterator to the first element contained in the container. | |
2131 | //! | |
2132 | //! <b>Throws</b>: Nothing. | |
2133 | //! | |
2134 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2135 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2136 | iterator begin() BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2137 | { return dtl::force_copy<iterator>(m_flat_tree.begin()); } |
7c673cae FG |
2138 | |
2139 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. | |
2140 | //! | |
2141 | //! <b>Throws</b>: Nothing. | |
2142 | //! | |
2143 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2144 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2145 | const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2146 | { return dtl::force_copy<const_iterator>(m_flat_tree.begin()); } |
7c673cae FG |
2147 | |
2148 | //! <b>Effects</b>: Returns an iterator to the end of the container. | |
2149 | //! | |
2150 | //! <b>Throws</b>: Nothing. | |
2151 | //! | |
2152 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2153 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2154 | iterator end() BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2155 | { return dtl::force_copy<iterator>(m_flat_tree.end()); } |
7c673cae FG |
2156 | |
2157 | //! <b>Effects</b>: Returns a const_iterator to the end of the container. | |
2158 | //! | |
2159 | //! <b>Throws</b>: Nothing. | |
2160 | //! | |
2161 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2162 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2163 | const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2164 | { return dtl::force_copy<const_iterator>(m_flat_tree.end()); } |
7c673cae FG |
2165 | |
2166 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning | |
2167 | //! of the reversed container. | |
2168 | //! | |
2169 | //! <b>Throws</b>: Nothing. | |
2170 | //! | |
2171 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2172 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2173 | reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2174 | { return dtl::force_copy<reverse_iterator>(m_flat_tree.rbegin()); } |
7c673cae FG |
2175 | |
2176 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning | |
2177 | //! of the reversed container. | |
2178 | //! | |
2179 | //! <b>Throws</b>: Nothing. | |
2180 | //! | |
2181 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2182 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2183 | const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2184 | { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.rbegin()); } |
7c673cae FG |
2185 | |
2186 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the end | |
2187 | //! of the reversed container. | |
2188 | //! | |
2189 | //! <b>Throws</b>: Nothing. | |
2190 | //! | |
2191 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2192 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2193 | reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2194 | { return dtl::force_copy<reverse_iterator>(m_flat_tree.rend()); } |
7c673cae FG |
2195 | |
2196 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end | |
2197 | //! of the reversed container. | |
2198 | //! | |
2199 | //! <b>Throws</b>: Nothing. | |
2200 | //! | |
2201 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2202 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2203 | const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2204 | { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.rend()); } |
7c673cae FG |
2205 | |
2206 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. | |
2207 | //! | |
2208 | //! <b>Throws</b>: Nothing. | |
2209 | //! | |
2210 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2211 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2212 | const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2213 | { return dtl::force_copy<const_iterator>(m_flat_tree.cbegin()); } |
7c673cae FG |
2214 | |
2215 | //! <b>Effects</b>: Returns a const_iterator to the end of the container. | |
2216 | //! | |
2217 | //! <b>Throws</b>: Nothing. | |
2218 | //! | |
2219 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2220 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2221 | const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2222 | { return dtl::force_copy<const_iterator>(m_flat_tree.cend()); } |
7c673cae FG |
2223 | |
2224 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning | |
2225 | //! of the reversed container. | |
2226 | //! | |
2227 | //! <b>Throws</b>: Nothing. | |
2228 | //! | |
2229 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2230 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2231 | const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2232 | { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.crbegin()); } |
7c673cae FG |
2233 | |
2234 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end | |
2235 | //! of the reversed container. | |
2236 | //! | |
2237 | //! <b>Throws</b>: Nothing. | |
2238 | //! | |
2239 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2240 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2241 | const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2242 | { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.crend()); } |
7c673cae FG |
2243 | |
2244 | ////////////////////////////////////////////// | |
2245 | // | |
2246 | // capacity | |
2247 | // | |
2248 | ////////////////////////////////////////////// | |
2249 | ||
2250 | //! <b>Effects</b>: Returns true if the container contains no elements. | |
2251 | //! | |
2252 | //! <b>Throws</b>: Nothing. | |
2253 | //! | |
2254 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2255 | BOOST_CONTAINER_FORCEINLINE |
7c673cae FG |
2256 | bool empty() const BOOST_NOEXCEPT_OR_NOTHROW |
2257 | { return m_flat_tree.empty(); } | |
2258 | ||
2259 | //! <b>Effects</b>: Returns the number of the elements contained in the container. | |
2260 | //! | |
2261 | //! <b>Throws</b>: Nothing. | |
2262 | //! | |
2263 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2264 | BOOST_CONTAINER_FORCEINLINE |
7c673cae FG |
2265 | size_type size() const BOOST_NOEXCEPT_OR_NOTHROW |
2266 | { return m_flat_tree.size(); } | |
2267 | ||
2268 | //! <b>Effects</b>: Returns the largest possible size of the container. | |
2269 | //! | |
2270 | //! <b>Throws</b>: Nothing. | |
2271 | //! | |
2272 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2273 | BOOST_CONTAINER_FORCEINLINE |
7c673cae FG |
2274 | size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW |
2275 | { return m_flat_tree.max_size(); } | |
2276 | ||
2277 | //! <b>Effects</b>: Number of elements for which memory has been allocated. | |
2278 | //! capacity() is always greater than or equal to size(). | |
2279 | //! | |
2280 | //! <b>Throws</b>: Nothing. | |
2281 | //! | |
2282 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2283 | BOOST_CONTAINER_FORCEINLINE |
7c673cae FG |
2284 | size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW |
2285 | { return m_flat_tree.capacity(); } | |
2286 | ||
b32b8144 FG |
2287 | //! <b>Effects</b>: If n is less than or equal to capacity(), or the |
2288 | //! underlying container has no `reserve` member, this call has no | |
7c673cae FG |
2289 | //! effect. Otherwise, it is a request for allocation of additional memory. |
2290 | //! If the request is successful, then capacity() is greater than or equal to | |
2291 | //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged. | |
2292 | //! | |
2293 | //! <b>Throws</b>: If memory allocation allocation throws or T's copy constructor throws. | |
2294 | //! | |
2295 | //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to | |
2296 | //! to values might be invalidated. | |
b32b8144 | 2297 | BOOST_CONTAINER_FORCEINLINE |
7c673cae FG |
2298 | void reserve(size_type cnt) |
2299 | { m_flat_tree.reserve(cnt); } | |
2300 | ||
2301 | //! <b>Effects</b>: Tries to deallocate the excess of memory created | |
2302 | // with previous allocations. The size of the vector is unchanged | |
2303 | //! | |
2304 | //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. | |
2305 | //! | |
2306 | //! <b>Complexity</b>: Linear to size(). | |
b32b8144 | 2307 | BOOST_CONTAINER_FORCEINLINE |
7c673cae FG |
2308 | void shrink_to_fit() |
2309 | { m_flat_tree.shrink_to_fit(); } | |
2310 | ||
2311 | //! @copydoc ::boost::container::flat_set::nth(size_type) | |
b32b8144 | 2312 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2313 | iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2314 | { return dtl::force_copy<iterator>(m_flat_tree.nth(n)); } |
7c673cae FG |
2315 | |
2316 | //! @copydoc ::boost::container::flat_set::nth(size_type) const | |
b32b8144 | 2317 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2318 | const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2319 | { return dtl::force_copy<iterator>(m_flat_tree.nth(n)); } |
7c673cae FG |
2320 | |
2321 | //! @copydoc ::boost::container::flat_set::index_of(iterator) | |
b32b8144 | 2322 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2323 | size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2324 | { return m_flat_tree.index_of(dtl::force_copy<impl_iterator>(p)); } |
7c673cae FG |
2325 | |
2326 | //! @copydoc ::boost::container::flat_set::index_of(const_iterator) const | |
b32b8144 | 2327 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2328 | size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW |
11fdf7f2 | 2329 | { return m_flat_tree.index_of(dtl::force_copy<impl_const_iterator>(p)); } |
7c673cae FG |
2330 | |
2331 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
2332 | ||
2333 | //! <b>Effects</b>: Inserts an object of type T constructed with | |
2334 | //! std::forward<Args>(args)... and returns the iterator pointing to the | |
2335 | //! newly inserted element. | |
2336 | //! | |
2337 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
2338 | //! to the elements with bigger keys than x. | |
2339 | //! | |
2340 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
2341 | template <class... Args> | |
b32b8144 | 2342 | BOOST_CONTAINER_FORCEINLINE |
7c673cae | 2343 | iterator emplace(BOOST_FWD_REF(Args)... args) |
11fdf7f2 | 2344 | { return dtl::force_copy<iterator>(m_flat_tree.emplace_equal(boost::forward<Args>(args)...)); } |
7c673cae FG |
2345 | |
2346 | //! <b>Effects</b>: Inserts an object of type T constructed with | |
2347 | //! std::forward<Args>(args)... in the container. | |
2348 | //! p is a hint pointing to where the insert should start to search. | |
2349 | //! | |
2350 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent | |
2351 | //! to the key of x. | |
2352 | //! | |
2353 | //! <b>Complexity</b>: Logarithmic search time (constant time if the value | |
2354 | //! is to be inserted before p) plus linear insertion | |
2355 | //! to the elements with bigger keys than x. | |
2356 | //! | |
2357 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
2358 | template <class... Args> | |
b32b8144 | 2359 | BOOST_CONTAINER_FORCEINLINE |
7c673cae FG |
2360 | iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args) |
2361 | { | |
11fdf7f2 TL |
2362 | return dtl::force_copy<iterator>(m_flat_tree.emplace_hint_equal |
2363 | (dtl::force_copy<impl_const_iterator>(hint), boost::forward<Args>(args)...)); | |
7c673cae FG |
2364 | } |
2365 | ||
2366 | #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
2367 | ||
2368 | #define BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE(N) \ | |
2369 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
b32b8144 | 2370 | BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_MOVE_UREF##N)\ |
11fdf7f2 | 2371 | { return dtl::force_copy<iterator>(m_flat_tree.emplace_equal(BOOST_MOVE_FWD##N)); }\ |
7c673cae FG |
2372 | \ |
2373 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
b32b8144 | 2374 | BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ |
7c673cae | 2375 | {\ |
11fdf7f2 TL |
2376 | return dtl::force_copy<iterator>(m_flat_tree.emplace_hint_equal\ |
2377 | (dtl::force_copy<impl_const_iterator>(hint) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\ | |
7c673cae FG |
2378 | }\ |
2379 | // | |
2380 | BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE) | |
2381 | #undef BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE | |
2382 | ||
2383 | #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
2384 | ||
2385 | //! <b>Effects</b>: Inserts x and returns the iterator pointing to the | |
2386 | //! newly inserted element. | |
2387 | //! | |
2388 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
2389 | //! to the elements with bigger keys than x. | |
2390 | //! | |
2391 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
b32b8144 | 2392 | BOOST_CONTAINER_FORCEINLINE iterator insert(const value_type& x) |
7c673cae | 2393 | { |
11fdf7f2 TL |
2394 | return dtl::force_copy<iterator>( |
2395 | m_flat_tree.insert_equal(dtl::force<const impl_value_type>(x))); | |
7c673cae FG |
2396 | } |
2397 | ||
2398 | //! <b>Effects</b>: Inserts a new value move-constructed from x and returns | |
2399 | //! the iterator pointing to the newly inserted element. | |
2400 | //! | |
2401 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
2402 | //! to the elements with bigger keys than x. | |
2403 | //! | |
2404 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
b32b8144 | 2405 | BOOST_CONTAINER_FORCEINLINE iterator insert(BOOST_RV_REF(value_type) x) |
11fdf7f2 | 2406 | { return dtl::force_copy<iterator>(m_flat_tree.insert_equal(boost::move(x))); } |
7c673cae FG |
2407 | |
2408 | //! <b>Effects</b>: Inserts a new value move-constructed from x and returns | |
2409 | //! the iterator pointing to the newly inserted element. | |
2410 | //! | |
2411 | //! <b>Complexity</b>: Logarithmic search time plus linear insertion | |
2412 | //! to the elements with bigger keys than x. | |
2413 | //! | |
2414 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
b32b8144 | 2415 | BOOST_CONTAINER_FORCEINLINE iterator insert(BOOST_RV_REF(impl_value_type) x) |
11fdf7f2 | 2416 | { return dtl::force_copy<iterator>(m_flat_tree.insert_equal(boost::move(x))); } |
7c673cae FG |
2417 | |
2418 | //! <b>Effects</b>: Inserts a copy of x in the container. | |
2419 | //! p is a hint pointing to where the insert should start to search. | |
2420 | //! | |
2421 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent | |
2422 | //! to the key of x. | |
2423 | //! | |
2424 | //! <b>Complexity</b>: Logarithmic search time (constant time if the value | |
2425 | //! is to be inserted before p) plus linear insertion | |
2426 | //! to the elements with bigger keys than x. | |
2427 | //! | |
2428 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
b32b8144 | 2429 | BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const value_type& x) |
7c673cae | 2430 | { |
11fdf7f2 TL |
2431 | return dtl::force_copy<iterator> |
2432 | (m_flat_tree.insert_equal( dtl::force_copy<impl_const_iterator>(p) | |
2433 | , dtl::force<const impl_value_type>(x))); | |
7c673cae FG |
2434 | } |
2435 | ||
2436 | //! <b>Effects</b>: Inserts a value move constructed from x in the container. | |
2437 | //! p is a hint pointing to where the insert should start to search. | |
2438 | //! | |
2439 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent | |
2440 | //! to the key of x. | |
2441 | //! | |
2442 | //! <b>Complexity</b>: Logarithmic search time (constant time if the value | |
2443 | //! is to be inserted before p) plus linear insertion | |
2444 | //! to the elements with bigger keys than x. | |
2445 | //! | |
2446 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
b32b8144 | 2447 | BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(value_type) x) |
7c673cae | 2448 | { |
11fdf7f2 TL |
2449 | return dtl::force_copy<iterator> |
2450 | (m_flat_tree.insert_equal(dtl::force_copy<impl_const_iterator>(p) | |
7c673cae FG |
2451 | , boost::move(x))); |
2452 | } | |
2453 | ||
2454 | //! <b>Effects</b>: Inserts a value move constructed from x in the container. | |
2455 | //! p is a hint pointing to where the insert should start to search. | |
2456 | //! | |
2457 | //! <b>Returns</b>: An iterator pointing to the element with key equivalent | |
2458 | //! to the key of x. | |
2459 | //! | |
2460 | //! <b>Complexity</b>: Logarithmic search time (constant time if the value | |
2461 | //! is to be inserted before p) plus linear insertion | |
2462 | //! to the elements with bigger keys than x. | |
2463 | //! | |
2464 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
b32b8144 | 2465 | BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(impl_value_type) x) |
7c673cae | 2466 | { |
11fdf7f2 TL |
2467 | return dtl::force_copy<iterator>( |
2468 | m_flat_tree.insert_equal(dtl::force_copy<impl_const_iterator>(p), boost::move(x))); | |
7c673cae FG |
2469 | } |
2470 | ||
2471 | //! <b>Requires</b>: first, last are not iterators into *this. | |
2472 | //! | |
2473 | //! <b>Effects</b>: inserts each element from the range [first,last) . | |
2474 | //! | |
11fdf7f2 | 2475 | //! <b>Complexity</b>: N log(N). |
7c673cae FG |
2476 | //! |
2477 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
2478 | template <class InputIterator> | |
b32b8144 | 2479 | BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last) |
7c673cae FG |
2480 | { m_flat_tree.insert_equal(first, last); } |
2481 | ||
2482 | //! <b>Requires</b>: first, last are not iterators into *this. | |
2483 | //! | |
2484 | //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. | |
2485 | //! | |
2486 | //! <b>Effects</b>: inserts each element from the range [first,last) if and only | |
2487 | //! if there is no element with key equivalent to the key of that element. This | |
2488 | //! function is more efficient than the normal range creation for ordered ranges. | |
2489 | //! | |
11fdf7f2 | 2490 | //! <b>Complexity</b>: Linear. |
7c673cae FG |
2491 | //! |
2492 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
2493 | //! | |
2494 | //! <b>Note</b>: Non-standard extension. | |
2495 | template <class InputIterator> | |
b32b8144 | 2496 | BOOST_CONTAINER_FORCEINLINE void insert(ordered_range_t, InputIterator first, InputIterator last) |
7c673cae FG |
2497 | { m_flat_tree.insert_equal(ordered_range, first, last); } |
2498 | ||
2499 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
2500 | //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) . | |
2501 | //! | |
11fdf7f2 | 2502 | //! <b>Complexity</b>: N log(N). |
7c673cae FG |
2503 | //! |
2504 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
b32b8144 FG |
2505 | BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il) |
2506 | { | |
11fdf7f2 TL |
2507 | m_flat_tree.insert_equal( dtl::force<impl_initializer_list>(il).begin() |
2508 | , dtl::force<impl_initializer_list>(il).end()); | |
b32b8144 | 2509 | } |
7c673cae FG |
2510 | |
2511 | //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate. | |
2512 | //! | |
2513 | //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only | |
2514 | //! if there is no element with key equivalent to the key of that element. This | |
2515 | //! function is more efficient than the normal range creation for ordered ranges. | |
2516 | //! | |
11fdf7f2 | 2517 | //! <b>Complexity</b>: Linear. |
7c673cae FG |
2518 | //! |
2519 | //! <b>Note</b>: If an element is inserted it might invalidate elements. | |
2520 | //! | |
2521 | //! <b>Note</b>: Non-standard extension. | |
b32b8144 FG |
2522 | BOOST_CONTAINER_FORCEINLINE void insert(ordered_range_t, std::initializer_list<value_type> il) |
2523 | { | |
2524 | m_flat_tree.insert_equal( ordered_range | |
11fdf7f2 TL |
2525 | , dtl::force<impl_initializer_list>(il).begin() |
2526 | , dtl::force<impl_initializer_list>(il).end()); | |
b32b8144 | 2527 | } |
7c673cae FG |
2528 | #endif |
2529 | ||
2530 | //! <b>Requires</b>: this->get_allocator() == source.get_allocator(). | |
2531 | //! | |
2532 | //! <b>Effects</b>: Extracts each element in source and insert it into a using | |
2533 | //! the comparison object of *this. | |
2534 | //! | |
2535 | //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer | |
2536 | //! to those same elements but as members of *this. Iterators referring to the transferred | |
2537 | //! elements will continue to refer to their elements, but they now behave as iterators into *this, | |
2538 | //! not into source. | |
2539 | //! | |
2540 | //! <b>Throws</b>: Nothing unless the comparison object throws. | |
2541 | //! | |
92f5a8d4 | 2542 | //! <b>Complexity</b>: N log(size() + N) (N has the value source.size()) |
7c673cae | 2543 | template<class C2> |
b32b8144 | 2544 | BOOST_CONTAINER_FORCEINLINE void merge(flat_multimap<Key, T, C2, AllocatorOrContainer>& source) |
7c673cae FG |
2545 | { m_flat_tree.merge_equal(source.tree()); } |
2546 | ||
b32b8144 | 2547 | //! @copydoc ::boost::container::flat_multimap::merge(flat_multimap<Key, T, C2, AllocatorOrContainer>&) |
7c673cae | 2548 | template<class C2> |
b32b8144 FG |
2549 | BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_multimap<Key, T, C2, AllocatorOrContainer> BOOST_RV_REF_END source) |
2550 | { return this->merge(static_cast<flat_multimap<Key, T, C2, AllocatorOrContainer>&>(source)); } | |
7c673cae | 2551 | |
b32b8144 | 2552 | //! @copydoc ::boost::container::flat_multimap::merge(flat_multimap<Key, T, C2, AllocatorOrContainer>&) |
7c673cae | 2553 | template<class C2> |
b32b8144 | 2554 | BOOST_CONTAINER_FORCEINLINE void merge(flat_map<Key, T, C2, AllocatorOrContainer>& source) |
7c673cae FG |
2555 | { m_flat_tree.merge_equal(source.tree()); } |
2556 | ||
b32b8144 | 2557 | //! @copydoc ::boost::container::flat_multimap::merge(flat_map<Key, T, C2, AllocatorOrContainer>&) |
7c673cae | 2558 | template<class C2> |
b32b8144 FG |
2559 | BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_map<Key, T, C2, AllocatorOrContainer> BOOST_RV_REF_END source) |
2560 | { return this->merge(static_cast<flat_map<Key, T, C2, AllocatorOrContainer>&>(source)); } | |
7c673cae FG |
2561 | |
2562 | //! <b>Effects</b>: Erases the element pointed to by p. | |
2563 | //! | |
2564 | //! <b>Returns</b>: Returns an iterator pointing to the element immediately | |
2565 | //! following q prior to the element being erased. If no such element exists, | |
2566 | //! returns end(). | |
2567 | //! | |
2568 | //! <b>Complexity</b>: Linear to the elements with keys bigger than p | |
2569 | //! | |
2570 | //! <b>Note</b>: Invalidates elements with keys | |
2571 | //! not less than the erased element. | |
b32b8144 | 2572 | BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator p) |
7c673cae | 2573 | { |
11fdf7f2 TL |
2574 | return dtl::force_copy<iterator>( |
2575 | m_flat_tree.erase(dtl::force_copy<impl_const_iterator>(p))); | |
7c673cae FG |
2576 | } |
2577 | ||
2578 | //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. | |
2579 | //! | |
2580 | //! <b>Returns</b>: Returns the number of erased elements. | |
2581 | //! | |
2582 | //! <b>Complexity</b>: Logarithmic search time plus erasure time | |
2583 | //! linear to the elements with bigger keys. | |
b32b8144 | 2584 | BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& x) |
7c673cae FG |
2585 | { return m_flat_tree.erase(x); } |
2586 | ||
2587 | //! <b>Effects</b>: Erases all the elements in the range [first, last). | |
2588 | //! | |
2589 | //! <b>Returns</b>: Returns last. | |
2590 | //! | |
2591 | //! <b>Complexity</b>: size()*N where N is the distance from first to last. | |
2592 | //! | |
2593 | //! <b>Complexity</b>: Logarithmic search time plus erasure time | |
2594 | //! linear to the elements with bigger keys. | |
b32b8144 | 2595 | BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator first, const_iterator last) |
7c673cae | 2596 | { |
11fdf7f2 TL |
2597 | return dtl::force_copy<iterator> |
2598 | (m_flat_tree.erase( dtl::force_copy<impl_const_iterator>(first) | |
2599 | , dtl::force_copy<impl_const_iterator>(last))); | |
7c673cae FG |
2600 | } |
2601 | ||
2602 | //! <b>Effects</b>: Swaps the contents of *this and x. | |
2603 | //! | |
2604 | //! <b>Throws</b>: Nothing. | |
2605 | //! | |
2606 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2607 | BOOST_CONTAINER_FORCEINLINE void swap(flat_multimap& x) |
7c673cae | 2608 | BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value |
11fdf7f2 | 2609 | && boost::container::dtl::is_nothrow_swappable<Compare>::value ) |
7c673cae FG |
2610 | { m_flat_tree.swap(x.m_flat_tree); } |
2611 | ||
92f5a8d4 | 2612 | //! <b>Effects</b>: erase(begin(),end()). |
7c673cae FG |
2613 | //! |
2614 | //! <b>Postcondition</b>: size() == 0. | |
2615 | //! | |
2616 | //! <b>Complexity</b>: linear in size(). | |
b32b8144 | 2617 | BOOST_CONTAINER_FORCEINLINE void clear() BOOST_NOEXCEPT_OR_NOTHROW |
7c673cae FG |
2618 | { m_flat_tree.clear(); } |
2619 | ||
2620 | ////////////////////////////////////////////// | |
2621 | // | |
2622 | // observers | |
2623 | // | |
2624 | ////////////////////////////////////////////// | |
2625 | ||
2626 | //! <b>Effects</b>: Returns the comparison object out | |
2627 | //! of which a was constructed. | |
2628 | //! | |
2629 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2630 | BOOST_CONTAINER_FORCEINLINE key_compare key_comp() const |
11fdf7f2 | 2631 | { return dtl::force_copy<key_compare>(m_flat_tree.key_comp()); } |
7c673cae FG |
2632 | |
2633 | //! <b>Effects</b>: Returns an object of value_compare constructed out | |
2634 | //! of the comparison object. | |
2635 | //! | |
2636 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2637 | BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const |
11fdf7f2 | 2638 | { return value_compare(dtl::force_copy<key_compare>(m_flat_tree.key_comp())); } |
7c673cae FG |
2639 | |
2640 | ////////////////////////////////////////////// | |
2641 | // | |
2642 | // map operations | |
2643 | // | |
2644 | ////////////////////////////////////////////// | |
2645 | ||
2646 | //! <b>Returns</b>: An iterator pointing to an element with the key | |
2647 | //! equivalent to x, or end() if such an element is not found. | |
2648 | //! | |
2649 | //! <b>Complexity</b>: Logarithmic. | |
b32b8144 | 2650 | BOOST_CONTAINER_FORCEINLINE iterator find(const key_type& x) |
11fdf7f2 | 2651 | { return dtl::force_copy<iterator>(m_flat_tree.find(x)); } |
7c673cae FG |
2652 | |
2653 | //! <b>Returns</b>: An const_iterator pointing to an element with the key | |
2654 | //! equivalent to x, or end() if such an element is not found. | |
2655 | //! | |
2656 | //! <b>Complexity</b>: Logarithmic. | |
b32b8144 | 2657 | BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& x) const |
11fdf7f2 | 2658 | { return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); } |
7c673cae | 2659 | |
92f5a8d4 TL |
2660 | //! <b>Requires</b>: This overload is available only if |
2661 | //! key_compare::is_transparent exists. | |
2662 | //! | |
2663 | //! <b>Returns</b>: An iterator pointing to an element with the key | |
2664 | //! equivalent to x, or end() if such an element is not found. | |
2665 | //! | |
2666 | //! <b>Complexity</b>: Logarithmic. | |
2667 | template<class K> | |
2668 | BOOST_CONTAINER_FORCEINLINE iterator find(const K& x) | |
2669 | { return dtl::force_copy<iterator>(m_flat_tree.find(x)); } | |
2670 | ||
2671 | //! <b>Requires</b>: This overload is available only if | |
2672 | //! key_compare::is_transparent exists. | |
2673 | //! | |
2674 | //! <b>Returns</b>: An const_iterator pointing to an element with the key | |
2675 | //! equivalent to x, or end() if such an element is not found. | |
2676 | //! | |
2677 | //! <b>Complexity</b>: Logarithmic. | |
2678 | template<class K> | |
2679 | BOOST_CONTAINER_FORCEINLINE const_iterator find(const K& x) const | |
2680 | { return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); } | |
2681 | ||
7c673cae FG |
2682 | //! <b>Returns</b>: The number of elements with key equivalent to x. |
2683 | //! | |
2684 | //! <b>Complexity</b>: log(size())+count(k) | |
b32b8144 | 2685 | BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const |
7c673cae FG |
2686 | { return m_flat_tree.count(x); } |
2687 | ||
92f5a8d4 TL |
2688 | //! <b>Requires</b>: This overload is available only if |
2689 | //! key_compare::is_transparent exists. | |
2690 | //! | |
2691 | //! <b>Returns</b>: The number of elements with key equivalent to x. | |
2692 | //! | |
2693 | //! <b>Complexity</b>: log(size())+count(k) | |
2694 | template<class K> | |
2695 | BOOST_CONTAINER_FORCEINLINE size_type count(const K& x) const | |
2696 | { return m_flat_tree.count(x); } | |
2697 | ||
2698 | //! <b>Returns</b>: Returns true if there is an element with key | |
2699 | //! equivalent to key in the container, otherwise false. | |
2700 | //! | |
2701 | //! <b>Complexity</b>: log(size()). | |
2702 | bool contains(const key_type& x) const | |
2703 | { return m_flat_tree.find(x) != m_flat_tree.end(); } | |
2704 | ||
2705 | //! <b>Requires</b>: This overload is available only if | |
2706 | //! key_compare::is_transparent exists. | |
2707 | //! | |
2708 | //! <b>Returns</b>: Returns true if there is an element with key | |
2709 | //! equivalent to key in the container, otherwise false. | |
2710 | //! | |
2711 | //! <b>Complexity</b>: log(size()). | |
2712 | template<typename K> | |
2713 | bool contains(const K& x) const | |
2714 | { return m_flat_tree.find(x) != m_flat_tree.end(); } | |
2715 | ||
7c673cae | 2716 | //! <b>Returns</b>: An iterator pointing to the first element with key not less |
92f5a8d4 | 2717 | //! than x, or end() if such an element is not found. |
7c673cae FG |
2718 | //! |
2719 | //! <b>Complexity</b>: Logarithmic | |
b32b8144 | 2720 | BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& x) |
11fdf7f2 | 2721 | { return dtl::force_copy<iterator>(m_flat_tree.lower_bound(x)); } |
7c673cae | 2722 | |
92f5a8d4 TL |
2723 | //! <b>Returns</b>: An iterator pointing to the first element with key not less |
2724 | //! than x, or end() if such an element is not found. | |
7c673cae FG |
2725 | //! |
2726 | //! <b>Complexity</b>: Logarithmic | |
b32b8144 | 2727 | BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& x) const |
92f5a8d4 | 2728 | { return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); } |
7c673cae | 2729 | |
92f5a8d4 TL |
2730 | //! <b>Requires</b>: This overload is available only if |
2731 | //! key_compare::is_transparent exists. | |
2732 | //! | |
7c673cae FG |
2733 | //! <b>Returns</b>: An iterator pointing to the first element with key not less |
2734 | //! than x, or end() if such an element is not found. | |
2735 | //! | |
2736 | //! <b>Complexity</b>: Logarithmic | |
92f5a8d4 TL |
2737 | template<class K> |
2738 | BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const K& x) | |
2739 | { return dtl::force_copy<iterator>(m_flat_tree.lower_bound(x)); } | |
2740 | ||
2741 | //! <b>Requires</b>: This overload is available only if | |
2742 | //! key_compare::is_transparent exists. | |
2743 | //! | |
2744 | //! <b>Returns</b>: An iterator pointing to the first element with key not less | |
2745 | //! than x, or end() if such an element is not found. | |
2746 | //! | |
2747 | //! <b>Complexity</b>: Logarithmic | |
2748 | template<class K> | |
2749 | BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const K& x) const | |
2750 | { return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); } | |
2751 | ||
2752 | //! <b>Returns</b>: An iterator pointing to the first element with key greater | |
2753 | //! than x, or end() if such an element is not found. | |
2754 | //! | |
2755 | //! <b>Complexity</b>: Logarithmic | |
b32b8144 | 2756 | BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& x) |
11fdf7f2 | 2757 | {return dtl::force_copy<iterator>(m_flat_tree.upper_bound(x)); } |
7c673cae FG |
2758 | |
2759 | //! <b>Returns</b>: A const iterator pointing to the first element with key | |
92f5a8d4 | 2760 | //! greater than x, or end() if such an element is not found. |
7c673cae FG |
2761 | //! |
2762 | //! <b>Complexity</b>: Logarithmic | |
b32b8144 | 2763 | BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& x) const |
11fdf7f2 | 2764 | { return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); } |
7c673cae | 2765 | |
92f5a8d4 TL |
2766 | //! <b>Requires</b>: This overload is available only if |
2767 | //! key_compare::is_transparent exists. | |
2768 | //! | |
2769 | //! <b>Returns</b>: An iterator pointing to the first element with key greater | |
2770 | //! than x, or end() if such an element is not found. | |
2771 | //! | |
2772 | //! <b>Complexity</b>: Logarithmic | |
2773 | template<class K> | |
2774 | BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const K& x) | |
2775 | {return dtl::force_copy<iterator>(m_flat_tree.upper_bound(x)); } | |
2776 | ||
2777 | //! <b>Requires</b>: This overload is available only if | |
2778 | //! key_compare::is_transparent exists. | |
2779 | //! | |
2780 | //! <b>Returns</b>: A const iterator pointing to the first element with key | |
2781 | //! greater than x, or end() if such an element is not found. | |
2782 | //! | |
2783 | //! <b>Complexity</b>: Logarithmic | |
2784 | template<class K> | |
2785 | BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const K& x) const | |
2786 | { return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); } | |
2787 | ||
7c673cae FG |
2788 | //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). |
2789 | //! | |
2790 | //! <b>Complexity</b>: Logarithmic | |
b32b8144 | 2791 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type& x) |
11fdf7f2 | 2792 | { return dtl::force_copy<std::pair<iterator,iterator> >(m_flat_tree.equal_range(x)); } |
7c673cae FG |
2793 | |
2794 | //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). | |
2795 | //! | |
2796 | //! <b>Complexity</b>: Logarithmic | |
b32b8144 | 2797 | BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const |
11fdf7f2 | 2798 | { return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(x)); } |
7c673cae | 2799 | |
92f5a8d4 TL |
2800 | //! <b>Requires</b>: This overload is available only if |
2801 | //! key_compare::is_transparent exists. | |
2802 | //! | |
2803 | //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). | |
2804 | //! | |
2805 | //! <b>Complexity</b>: Logarithmic | |
2806 | template<class K> | |
2807 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const K& x) | |
2808 | { return dtl::force_copy<std::pair<iterator,iterator> >(m_flat_tree.equal_range(x)); } | |
2809 | ||
2810 | //! <b>Requires</b>: This overload is available only if | |
2811 | //! key_compare::is_transparent exists. | |
2812 | //! | |
2813 | //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). | |
2814 | //! | |
2815 | //! <b>Complexity</b>: Logarithmic | |
2816 | template<class K> | |
2817 | BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const K& x) const | |
2818 | { return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(x)); } | |
2819 | ||
b32b8144 FG |
2820 | //! <b>Effects</b>: Extracts the internal sequence container. |
2821 | //! | |
2822 | //! <b>Complexity</b>: Same as the move constructor of sequence_type, usually constant. | |
2823 | //! | |
2824 | //! <b>Postcondition</b>: this->empty() | |
2825 | //! | |
2826 | //! <b>Throws</b>: If secuence_type's move constructor throws | |
2827 | BOOST_CONTAINER_FORCEINLINE sequence_type extract_sequence() | |
2828 | { | |
11fdf7f2 | 2829 | return boost::move(dtl::force<sequence_type>(m_flat_tree.get_sequence_ref())); |
b32b8144 FG |
2830 | } |
2831 | ||
2832 | //! <b>Effects</b>: Discards the internally hold sequence container and adopts the | |
2833 | //! one passed externally using the move assignment. | |
2834 | //! | |
2835 | //! <b>Complexity</b>: Assuming O(1) move assignment, O(NlogN) with N = seq.size() | |
2836 | //! | |
2837 | //! <b>Throws</b>: If the comparison or the move constructor throws | |
2838 | BOOST_CONTAINER_FORCEINLINE void adopt_sequence(BOOST_RV_REF(sequence_type) seq) | |
11fdf7f2 | 2839 | { this->m_flat_tree.adopt_sequence_equal(boost::move(dtl::force<impl_sequence_type>(seq))); } |
b32b8144 FG |
2840 | |
2841 | //! <b>Requires</b>: seq shall be ordered according to this->compare(). | |
2842 | //! | |
2843 | //! <b>Effects</b>: Discards the internally hold sequence container and adopts the | |
2844 | //! one passed externally using the move assignment. | |
2845 | //! | |
2846 | //! <b>Complexity</b>: Assuming O(1) move assignment, O(1) | |
2847 | //! | |
2848 | //! <b>Throws</b>: If the move assignment throws | |
2849 | BOOST_CONTAINER_FORCEINLINE void adopt_sequence(ordered_range_t, BOOST_RV_REF(sequence_type) seq) | |
11fdf7f2 | 2850 | { this->m_flat_tree.adopt_sequence_equal(ordered_range_t(), boost::move(dtl::force<impl_sequence_type>(seq))); } |
b32b8144 | 2851 | |
7c673cae FG |
2852 | //! <b>Effects</b>: Returns true if x and y are equal |
2853 | //! | |
2854 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
b32b8144 | 2855 | BOOST_CONTAINER_FORCEINLINE friend bool operator==(const flat_multimap& x, const flat_multimap& y) |
7c673cae FG |
2856 | { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } |
2857 | ||
2858 | //! <b>Effects</b>: Returns true if x and y are unequal | |
2859 | //! | |
2860 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
b32b8144 | 2861 | BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const flat_multimap& x, const flat_multimap& y) |
7c673cae FG |
2862 | { return !(x == y); } |
2863 | ||
2864 | //! <b>Effects</b>: Returns true if x is less than y | |
2865 | //! | |
2866 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
b32b8144 | 2867 | BOOST_CONTAINER_FORCEINLINE friend bool operator<(const flat_multimap& x, const flat_multimap& y) |
7c673cae FG |
2868 | { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } |
2869 | ||
2870 | //! <b>Effects</b>: Returns true if x is greater than y | |
2871 | //! | |
2872 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
b32b8144 | 2873 | BOOST_CONTAINER_FORCEINLINE friend bool operator>(const flat_multimap& x, const flat_multimap& y) |
7c673cae FG |
2874 | { return y < x; } |
2875 | ||
2876 | //! <b>Effects</b>: Returns true if x is equal or less than y | |
2877 | //! | |
2878 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
b32b8144 | 2879 | BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const flat_multimap& x, const flat_multimap& y) |
7c673cae FG |
2880 | { return !(y < x); } |
2881 | ||
2882 | //! <b>Effects</b>: Returns true if x is equal or greater than y | |
2883 | //! | |
2884 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
b32b8144 | 2885 | BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const flat_multimap& x, const flat_multimap& y) |
7c673cae FG |
2886 | { return !(x < y); } |
2887 | ||
2888 | //! <b>Effects</b>: x.swap(y) | |
2889 | //! | |
2890 | //! <b>Complexity</b>: Constant. | |
b32b8144 | 2891 | BOOST_CONTAINER_FORCEINLINE friend void swap(flat_multimap& x, flat_multimap& y) |
7c673cae FG |
2892 | { x.swap(y); } |
2893 | }; | |
2894 | ||
92f5a8d4 TL |
2895 | #ifndef BOOST_CONTAINER_NO_CXX17_CTAD |
2896 | ||
2897 | template <typename InputIterator> | |
2898 | flat_multimap(InputIterator, InputIterator) -> | |
2899 | flat_multimap< it_based_non_const_first_type_t<InputIterator> | |
2900 | , it_based_second_type_t<InputIterator>>; | |
2901 | ||
2902 | template < typename InputIterator, typename AllocatorOrCompare> | |
2903 | flat_multimap(InputIterator, InputIterator, AllocatorOrCompare const&) -> | |
2904 | flat_multimap< it_based_non_const_first_type_t<InputIterator> | |
2905 | , it_based_second_type_t<InputIterator> | |
2906 | , typename dtl::if_c< // Compare | |
2907 | dtl::is_allocator<AllocatorOrCompare>::value | |
2908 | , std::less<it_based_non_const_first_type_t<InputIterator>> | |
2909 | , AllocatorOrCompare | |
2910 | >::type | |
2911 | , typename dtl::if_c< // Allocator | |
2912 | dtl::is_allocator<AllocatorOrCompare>::value | |
2913 | , AllocatorOrCompare | |
2914 | , new_allocator<std::pair<it_based_non_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>> | |
2915 | >::type | |
2916 | >; | |
2917 | ||
2918 | template < typename InputIterator, typename Compare, typename Allocator | |
2919 | , typename = dtl::require_nonallocator_t<Compare> | |
2920 | , typename = dtl::require_allocator_t<Allocator>> | |
2921 | flat_multimap(InputIterator, InputIterator, Compare const&, Allocator const&) -> | |
2922 | flat_multimap< it_based_non_const_first_type_t<InputIterator> | |
2923 | , it_based_second_type_t<InputIterator> | |
2924 | , Compare | |
2925 | , Allocator>; | |
2926 | ||
2927 | template <typename InputIterator> | |
2928 | flat_multimap(ordered_range_t, InputIterator, InputIterator) -> | |
2929 | flat_multimap< it_based_non_const_first_type_t<InputIterator> | |
2930 | , it_based_second_type_t<InputIterator>>; | |
2931 | ||
2932 | template < typename InputIterator, typename AllocatorOrCompare> | |
2933 | flat_multimap(ordered_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) -> | |
2934 | flat_multimap< it_based_non_const_first_type_t<InputIterator> | |
2935 | , it_based_second_type_t<InputIterator> | |
2936 | , typename dtl::if_c< // Compare | |
2937 | dtl::is_allocator<AllocatorOrCompare>::value | |
2938 | , std::less<it_based_non_const_first_type_t<InputIterator>> | |
2939 | , AllocatorOrCompare | |
2940 | >::type | |
2941 | , typename dtl::if_c< // Allocator | |
2942 | dtl::is_allocator<AllocatorOrCompare>::value | |
2943 | , AllocatorOrCompare | |
2944 | , new_allocator<std::pair<it_based_non_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>> | |
2945 | >::type | |
2946 | >; | |
2947 | ||
2948 | template < typename InputIterator, typename Compare, typename Allocator | |
2949 | , typename = dtl::require_nonallocator_t<Compare> | |
2950 | , typename = dtl::require_allocator_t<Allocator>> | |
2951 | flat_multimap(ordered_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) -> | |
2952 | flat_multimap< it_based_non_const_first_type_t<InputIterator> | |
2953 | , it_based_second_type_t<InputIterator> | |
2954 | , Compare | |
2955 | , Allocator>; | |
2956 | ||
2957 | #endif | |
2958 | ||
7c673cae FG |
2959 | }} |
2960 | ||
2961 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
2962 | ||
2963 | namespace boost { | |
2964 | ||
2965 | //!has_trivial_destructor_after_move<> == true_type | |
2966 | //!specialization for optimizations | |
b32b8144 FG |
2967 | template <class Key, class T, class Compare, class AllocatorOrContainer> |
2968 | struct has_trivial_destructor_after_move< boost::container::flat_multimap<Key, T, Compare, AllocatorOrContainer> > | |
7c673cae | 2969 | { |
92f5a8d4 TL |
2970 | typedef ::boost::container::dtl::pair<Key, T> value_t; |
2971 | typedef typename ::boost::container::dtl::container_or_allocator_rebind<AllocatorOrContainer, value_t>::type alloc_or_cont_t; | |
2972 | typedef ::boost::container::dtl::flat_tree<value_t,::boost::container::dtl::select1st<Key>, Compare, alloc_or_cont_t> tree; | |
2973 | static const bool value = ::boost::has_trivial_destructor_after_move<tree>::value; | |
7c673cae FG |
2974 | }; |
2975 | ||
2976 | } //namespace boost { | |
2977 | ||
2978 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
2979 | ||
2980 | #include <boost/container/detail/config_end.hpp> | |
2981 | ||
2982 | #endif // BOOST_CONTAINER_FLAT_MAP_HPP |