ocrm.bsky.social
the game where you go into mines and start crafting! but for consoles (forked directly from smartcmd's github)
1//////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Ion Gaztanaga 2005-2012. 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
11#ifndef BOOST_CONTAINER_MAP_HPP
12#define BOOST_CONTAINER_MAP_HPP
13
14#if (defined _MSC_VER) && (_MSC_VER >= 1200)
15# pragma once
16#endif
17
18#include <boost/container/detail/config_begin.hpp>
19#include <boost/container/detail/workaround.hpp>
20
21#include <boost/container/container_fwd.hpp>
22#include <utility>
23#include <functional>
24#include <memory>
25#include <stdexcept>
26#include <boost/container/detail/tree.hpp>
27#include <boost/container/detail/value_init.hpp>
28#include <boost/type_traits/has_trivial_destructor.hpp>
29#include <boost/container/detail/mpl.hpp>
30#include <boost/container/detail/utilities.hpp>
31#include <boost/container/detail/pair.hpp>
32#include <boost/container/detail/type_traits.hpp>
33#include <boost/move/utility.hpp>
34#include <boost/move/detail/move_helpers.hpp>
35#include <boost/static_assert.hpp>
36#include <boost/container/detail/value_init.hpp>
37
38namespace boost {
39namespace container {
40
41/// @cond
42// Forward declarations of operators == and <, needed for friend declarations.
43template <class Key, class T, class Compare, class Allocator>
44inline bool operator==(const map<Key,T,Compare,Allocator>& x,
45 const map<Key,T,Compare,Allocator>& y);
46
47template <class Key, class T, class Compare, class Allocator>
48inline bool operator<(const map<Key,T,Compare,Allocator>& x,
49 const map<Key,T,Compare,Allocator>& y);
50/// @endcond
51
52//! A map is a kind of associative container that supports unique keys (contains at
53//! most one of each key value) and provides for fast retrieval of values of another
54//! type T based on the keys. The map class supports bidirectional iterators.
55//!
56//! A map satisfies all of the requirements of a container and of a reversible
57//! container and of an associative container. For a
58//! map<Key,T> the key_type is Key and the value_type is std::pair<const Key,T>.
59//!
60//! Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
61//!
62//! Allocator is the allocator to allocate the value_types
63//! (e.g. <i>allocator< std::pair<const Key, T> > </i>).
64#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
65template <class Key, class T, class Compare = std::less<Key>, class Allocator = std::allocator< std::pair< const Key, T> > >
66#else
67template <class Key, class T, class Compare, class Allocator>
68#endif
69class map
70{
71 /// @cond
72 private:
73 BOOST_COPYABLE_AND_MOVABLE(map)
74
75 typedef std::pair<const Key, T> value_type_impl;
76 typedef container_detail::rbtree
77 <Key, value_type_impl, container_detail::select1st<value_type_impl>, Compare, Allocator> tree_t;
78 typedef container_detail::pair <Key, T> movable_value_type_impl;
79 typedef container_detail::tree_value_compare
80 < Key, value_type_impl, Compare, container_detail::select1st<value_type_impl>
81 > value_compare_impl;
82 tree_t m_tree; // red-black tree representing map
83 /// @endcond
84
85 public:
86 //////////////////////////////////////////////
87 //
88 // types
89 //
90 //////////////////////////////////////////////
91
92 typedef Key key_type;
93 typedef T mapped_type;
94 typedef std::pair<const Key, T> value_type;
95 typedef typename boost::container::allocator_traits<Allocator>::pointer pointer;
96 typedef typename boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
97 typedef typename boost::container::allocator_traits<Allocator>::reference reference;
98 typedef typename boost::container::allocator_traits<Allocator>::const_reference const_reference;
99 typedef typename boost::container::allocator_traits<Allocator>::size_type size_type;
100 typedef typename boost::container::allocator_traits<Allocator>::difference_type difference_type;
101 typedef Allocator allocator_type;
102 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type;
103 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare;
104 typedef Compare key_compare;
105 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::iterator) iterator;
106 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_iterator) const_iterator;
107 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator) reverse_iterator;
108 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator) const_reverse_iterator;
109 typedef std::pair<key_type, mapped_type> nonconst_value_type;
110 typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl) movable_value_type;
111
112 //////////////////////////////////////////////
113 //
114 // construct/copy/destroy
115 //
116 //////////////////////////////////////////////
117
118 //! <b>Effects</b>: Default constructs an empty map.
119 //!
120 //! <b>Complexity</b>: Constant.
121 map()
122 : m_tree()
123 {
124 //Allocator type must be std::pair<CONST Key, T>
125 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
126 }
127
128 //! <b>Effects</b>: Constructs an empty map using the specified comparison object
129 //! and allocator.
130 //!
131 //! <b>Complexity</b>: Constant.
132 explicit map(const Compare& comp,
133 const allocator_type& a = allocator_type())
134 : m_tree(comp, a)
135 {
136 //Allocator type must be std::pair<CONST Key, T>
137 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
138 }
139
140 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
141 //! allocator, and inserts elements from the range [first ,last ).
142 //!
143 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
144 //! comp and otherwise N logN, where N is last - first.
145 template <class InputIterator>
146 map(InputIterator first, InputIterator last, const Compare& comp = Compare(),
147 const allocator_type& a = allocator_type())
148 : m_tree(true, first, last, comp, a)
149 {
150 //Allocator type must be std::pair<CONST Key, T>
151 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
152 }
153
154 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
155 //! allocator, and inserts elements from the ordered unique range [first ,last). This function
156 //! is more efficient than the normal range creation for ordered ranges.
157 //!
158 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
159 //! unique values.
160 //!
161 //! <b>Complexity</b>: Linear in N.
162 template <class InputIterator>
163 map( ordered_unique_range_t, InputIterator first, InputIterator last
164 , const Compare& comp = Compare(), const allocator_type& a = allocator_type())
165 : m_tree(ordered_range, first, last, comp, a)
166 {
167 //Allocator type must be std::pair<CONST Key, T>
168 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
169 }
170
171 //! <b>Effects</b>: Copy constructs a map.
172 //!
173 //! <b>Complexity</b>: Linear in x.size().
174 map(const map& x)
175 : m_tree(x.m_tree)
176 {
177 //Allocator type must be std::pair<CONST Key, T>
178 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
179 }
180
181 //! <b>Effects</b>: Move constructs a map. Constructs *this using x's resources.
182 //!
183 //! <b>Complexity</b>: Constant.
184 //!
185 //! <b>Postcondition</b>: x is emptied.
186 map(BOOST_RV_REF(map) x)
187 : m_tree(boost::move(x.m_tree))
188 {
189 //Allocator type must be std::pair<CONST Key, T>
190 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
191 }
192
193 //! <b>Effects</b>: Copy constructs a map using the specified allocator.
194 //!
195 //! <b>Complexity</b>: Linear in x.size().
196 map(const map& x, const allocator_type &a)
197 : m_tree(x.m_tree, a)
198 {
199 //Allocator type must be std::pair<CONST Key, T>
200 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
201 }
202
203 //! <b>Effects</b>: Move constructs a map using the specified allocator.
204 //! Constructs *this using x's resources.
205 //!
206 //! <b>Complexity</b>: Constant if x == x.get_allocator(), linear otherwise.
207 //!
208 //! <b>Postcondition</b>: x is emptied.
209 map(BOOST_RV_REF(map) x, const allocator_type &a)
210 : m_tree(boost::move(x.m_tree), a)
211 {
212 //Allocator type must be std::pair<CONST Key, T>
213 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
214 }
215
216 //! <b>Effects</b>: Makes *this a copy of x.
217 //!
218 //! <b>Complexity</b>: Linear in x.size().
219 map& operator=(BOOST_COPY_ASSIGN_REF(map) x)
220 { m_tree = x.m_tree; return *this; }
221
222 //! <b>Effects</b>: this->swap(x.get()).
223 //!
224 //! <b>Complexity</b>: Constant.
225 map& operator=(BOOST_RV_REF(map) x)
226 { m_tree = boost::move(x.m_tree); return *this; }
227
228 //! <b>Effects</b>: Returns a copy of the Allocator that
229 //! was passed to the object's constructor.
230 //!
231 //! <b>Complexity</b>: Constant.
232 allocator_type get_allocator() const BOOST_CONTAINER_NOEXCEPT
233 { return m_tree.get_allocator(); }
234
235 //! <b>Effects</b>: Returns a reference to the internal allocator.
236 //!
237 //! <b>Throws</b>: Nothing
238 //!
239 //! <b>Complexity</b>: Constant.
240 //!
241 //! <b>Note</b>: Non-standard extension.
242 stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT
243 { return m_tree.get_stored_allocator(); }
244
245 //! <b>Effects</b>: Returns a reference to the internal allocator.
246 //!
247 //! <b>Throws</b>: Nothing
248 //!
249 //! <b>Complexity</b>: Constant.
250 //!
251 //! <b>Note</b>: Non-standard extension.
252 const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT
253 { return m_tree.get_stored_allocator(); }
254
255 //////////////////////////////////////////////
256 //
257 // iterators
258 //
259 //////////////////////////////////////////////
260
261 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
262 //!
263 //! <b>Throws</b>: Nothing.
264 //!
265 //! <b>Complexity</b>: Constant.
266 iterator begin() BOOST_CONTAINER_NOEXCEPT
267 { return m_tree.begin(); }
268
269 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
270 //!
271 //! <b>Throws</b>: Nothing.
272 //!
273 //! <b>Complexity</b>: Constant.
274 const_iterator begin() const BOOST_CONTAINER_NOEXCEPT
275 { return this->cbegin(); }
276
277 //! <b>Effects</b>: Returns an iterator to the end of the container.
278 //!
279 //! <b>Throws</b>: Nothing.
280 //!
281 //! <b>Complexity</b>: Constant.
282 iterator end() BOOST_CONTAINER_NOEXCEPT
283 { return m_tree.end(); }
284
285 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
286 //!
287 //! <b>Throws</b>: Nothing.
288 //!
289 //! <b>Complexity</b>: Constant.
290 const_iterator end() const BOOST_CONTAINER_NOEXCEPT
291 { return this->cend(); }
292
293 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
294 //! of the reversed container.
295 //!
296 //! <b>Throws</b>: Nothing.
297 //!
298 //! <b>Complexity</b>: Constant.
299 reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT
300 { return m_tree.rbegin(); }
301
302 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
303 //! of the reversed container.
304 //!
305 //! <b>Throws</b>: Nothing.
306 //!
307 //! <b>Complexity</b>: Constant.
308 const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT
309 { return this->crbegin(); }
310
311 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
312 //! of the reversed container.
313 //!
314 //! <b>Throws</b>: Nothing.
315 //!
316 //! <b>Complexity</b>: Constant.
317 reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT
318 { return m_tree.rend(); }
319
320 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
321 //! of the reversed container.
322 //!
323 //! <b>Throws</b>: Nothing.
324 //!
325 //! <b>Complexity</b>: Constant.
326 const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT
327 { return this->crend(); }
328
329 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
330 //!
331 //! <b>Throws</b>: Nothing.
332 //!
333 //! <b>Complexity</b>: Constant.
334 const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT
335 { return m_tree.begin(); }
336
337 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
338 //!
339 //! <b>Throws</b>: Nothing.
340 //!
341 //! <b>Complexity</b>: Constant.
342 const_iterator cend() const BOOST_CONTAINER_NOEXCEPT
343 { return m_tree.end(); }
344
345 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
346 //! of the reversed container.
347 //!
348 //! <b>Throws</b>: Nothing.
349 //!
350 //! <b>Complexity</b>: Constant.
351 const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT
352 { return m_tree.rbegin(); }
353
354 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
355 //! of the reversed container.
356 //!
357 //! <b>Throws</b>: Nothing.
358 //!
359 //! <b>Complexity</b>: Constant.
360 const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT
361 { return m_tree.rend(); }
362
363 //////////////////////////////////////////////
364 //
365 // capacity
366 //
367 //////////////////////////////////////////////
368
369 //! <b>Effects</b>: Returns true if the container contains no elements.
370 //!
371 //! <b>Throws</b>: Nothing.
372 //!
373 //! <b>Complexity</b>: Constant.
374 bool empty() const BOOST_CONTAINER_NOEXCEPT
375 { return m_tree.empty(); }
376
377 //! <b>Effects</b>: Returns the number of the elements contained in the container.
378 //!
379 //! <b>Throws</b>: Nothing.
380 //!
381 //! <b>Complexity</b>: Constant.
382 size_type size() const BOOST_CONTAINER_NOEXCEPT
383 { return m_tree.size(); }
384
385 //! <b>Effects</b>: Returns the largest possible size of the container.
386 //!
387 //! <b>Throws</b>: Nothing.
388 //!
389 //! <b>Complexity</b>: Constant.
390 size_type max_size() const BOOST_CONTAINER_NOEXCEPT
391 { return m_tree.max_size(); }
392
393 //////////////////////////////////////////////
394 //
395 // element access
396 //
397 //////////////////////////////////////////////
398
399 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
400 //! Effects: If there is no key equivalent to x in the map, inserts
401 //! value_type(x, T()) into the map.
402 //!
403 //! Returns: Allocator reference to the mapped_type corresponding to x in *this.
404 //!
405 //! Complexity: Logarithmic.
406 mapped_type& operator[](const key_type &k);
407
408 //! Effects: If there is no key equivalent to x in the map, inserts
409 //! value_type(boost::move(x), T()) into the map (the key is move-constructed)
410 //!
411 //! Returns: Allocator reference to the mapped_type corresponding to x in *this.
412 //!
413 //! Complexity: Logarithmic.
414 mapped_type& operator[](key_type &&k);
415 #else
416 BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript)
417 #endif
418
419 //! Returns: Allocator reference to the element whose key is equivalent to x.
420 //! Throws: An exception object of type out_of_range if no such element is present.
421 //! Complexity: logarithmic.
422 T& at(const key_type& k)
423 {
424 iterator i = this->find(k);
425 if(i == this->end()){
426 throw std::out_of_range("key not found");
427 }
428 return i->second;
429 }
430
431 //! Returns: Allocator reference to the element whose key is equivalent to x.
432 //! Throws: An exception object of type out_of_range if no such element is present.
433 //! Complexity: logarithmic.
434 const T& at(const key_type& k) const
435 {
436 const_iterator i = this->find(k);
437 if(i == this->end()){
438 throw std::out_of_range("key not found");
439 }
440 return i->second;
441 }
442
443 //////////////////////////////////////////////
444 //
445 // modifiers
446 //
447 //////////////////////////////////////////////
448
449 //! <b>Effects</b>: Inserts x if and only if there is no element in the container
450 //! with key equivalent to the key of x.
451 //!
452 //! <b>Returns</b>: The bool component of the returned pair is true if and only
453 //! if the insertion takes place, and the iterator component of the pair
454 //! points to the element with key equivalent to the key of x.
455 //!
456 //! <b>Complexity</b>: Logarithmic.
457 std::pair<iterator,bool> insert(const value_type& x)
458 { return m_tree.insert_unique(x); }
459
460 //! <b>Effects</b>: Inserts a new value_type created from the pair if and only if
461 //! there is no element in the container with key equivalent to the key of x.
462 //!
463 //! <b>Returns</b>: The bool component of the returned pair is true if and only
464 //! if the insertion takes place, and the iterator component of the pair
465 //! points to the element with key equivalent to the key of x.
466 //!
467 //! <b>Complexity</b>: Logarithmic.
468 std::pair<iterator,bool> insert(const nonconst_value_type& x)
469 { return m_tree.insert_unique(x); }
470
471 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
472 //! only if there is no element in the container with key equivalent to the key of x.
473 //!
474 //! <b>Returns</b>: The bool component of the returned pair is true if and only
475 //! if the insertion takes place, and the iterator component of the pair
476 //! points to the element with key equivalent to the key of x.
477 //!
478 //! <b>Complexity</b>: Logarithmic.
479 std::pair<iterator,bool> insert(BOOST_RV_REF(nonconst_value_type) x)
480 { return m_tree.insert_unique(boost::move(x)); }
481
482 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
483 //! only if there is no element in the container with key equivalent to the key of x.
484 //!
485 //! <b>Returns</b>: The bool component of the returned pair is true if and only
486 //! if the insertion takes place, and the iterator component of the pair
487 //! points to the element with key equivalent to the key of x.
488 //!
489 //! <b>Complexity</b>: Logarithmic.
490 std::pair<iterator,bool> insert(BOOST_RV_REF(movable_value_type) x)
491 { return m_tree.insert_unique(boost::move(x)); }
492
493 //! <b>Effects</b>: Move constructs a new value from x if and only if there is
494 //! no element in the container with key equivalent to the key of x.
495 //!
496 //! <b>Returns</b>: The bool component of the returned pair is true if and only
497 //! if the insertion takes place, and the iterator component of the pair
498 //! points to the element with key equivalent to the key of x.
499 //!
500 //! <b>Complexity</b>: Logarithmic.
501 std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
502 { return m_tree.insert_unique(boost::move(x)); }
503
504 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
505 //! no element in the container with key equivalent to the key of x.
506 //! p is a hint pointing to where the insert should start to search.
507 //!
508 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
509 //! to the key of x.
510 //!
511 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
512 //! is inserted right before p.
513 iterator insert(const_iterator position, const value_type& x)
514 { return m_tree.insert_unique(position, x); }
515
516 //! <b>Effects</b>: Move constructs a new value from x if and only if there is
517 //! no element in the container with key equivalent to the key of x.
518 //! p is a hint pointing to where the insert should start to search.
519 //!
520 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
521 //! to the key of x.
522 //!
523 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
524 //! is inserted right before p.
525 iterator insert(const_iterator position, BOOST_RV_REF(nonconst_value_type) x)
526 { return m_tree.insert_unique(position, boost::move(x)); }
527
528 //! <b>Effects</b>: Move constructs a new value from x if and only if there is
529 //! no element in the container with key equivalent to the key of x.
530 //! p is a hint pointing to where the insert should start to search.
531 //!
532 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
533 //! to the key of x.
534 //!
535 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
536 //! is inserted right before p.
537 iterator insert(const_iterator position, BOOST_RV_REF(movable_value_type) x)
538 { return m_tree.insert_unique(position, boost::move(x)); }
539
540 //! <b>Effects</b>: Inserts a copy of x in the container.
541 //! p is a hint pointing to where the insert should start to search.
542 //!
543 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
544 //!
545 //! <b>Complexity</b>: Logarithmic.
546 iterator insert(const_iterator position, const nonconst_value_type& x)
547 { return m_tree.insert_unique(position, x); }
548
549 //! <b>Effects</b>: Inserts an element move constructed from x in the container.
550 //! p is a hint pointing to where the insert should start to search.
551 //!
552 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
553 //!
554 //! <b>Complexity</b>: Logarithmic.
555 iterator insert(const_iterator position, BOOST_RV_REF(value_type) x)
556 { return m_tree.insert_unique(position, boost::move(x)); }
557
558 //! <b>Requires</b>: first, last are not iterators into *this.
559 //!
560 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
561 //! if there is no element with key equivalent to the key of that element.
562 //!
563 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
564 template <class InputIterator>
565 void insert(InputIterator first, InputIterator last)
566 { m_tree.insert_unique(first, last); }
567
568 #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
569
570 //! <b>Effects</b>: Inserts an object x of type T constructed with
571 //! std::forward<Args>(args)... in the container if and only if there is
572 //! no element in the container with an equivalent key.
573 //! p is a hint pointing to where the insert should start to search.
574 //!
575 //! <b>Returns</b>: The bool component of the returned pair is true if and only
576 //! if the insertion takes place, and the iterator component of the pair
577 //! points to the element with key equivalent to the key of x.
578 //!
579 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
580 //! is inserted right before p.
581 template <class... Args>
582 std::pair<iterator,bool> emplace(Args&&... args)
583 { return m_tree.emplace_unique(boost::forward<Args>(args)...); }
584
585 //! <b>Effects</b>: Inserts an object of type T constructed with
586 //! std::forward<Args>(args)... in the container if and only if there is
587 //! no element in the container with an equivalent key.
588 //! p is a hint pointing to where the insert should start to search.
589 //!
590 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
591 //! to the key of x.
592 //!
593 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
594 //! is inserted right before p.
595 template <class... Args>
596 iterator emplace_hint(const_iterator hint, Args&&... args)
597 { return m_tree.emplace_hint_unique(hint, boost::forward<Args>(args)...); }
598
599 #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
600
601 #define BOOST_PP_LOCAL_MACRO(n) \
602 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
603 std::pair<iterator,bool> emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
604 { return m_tree.emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \
605 \
606 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
607 iterator emplace_hint(const_iterator hint \
608 BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
609 { return m_tree.emplace_hint_unique(hint \
610 BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _));} \
611 //!
612 #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
613 #include BOOST_PP_LOCAL_ITERATE()
614
615 #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
616
617 //! <b>Effects</b>: Erases the element pointed to by position.
618 //!
619 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
620 //! following q prior to the element being erased. If no such element exists,
621 //! returns end().
622 //!
623 //! <b>Complexity</b>: Amortized constant time
624 iterator erase(const_iterator position) BOOST_CONTAINER_NOEXCEPT
625 { return m_tree.erase(position); }
626
627 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
628 //!
629 //! <b>Returns</b>: Returns the number of erased elements.
630 //!
631 //! <b>Complexity</b>: log(size()) + count(k)
632 size_type erase(const key_type& x) BOOST_CONTAINER_NOEXCEPT
633 { return m_tree.erase(x); }
634
635 //! <b>Effects</b>: Erases all the elements in the range [first, last).
636 //!
637 //! <b>Returns</b>: Returns last.
638 //!
639 //! <b>Complexity</b>: log(size())+N where N is the distance from first to last.
640 iterator erase(const_iterator first, const_iterator last) BOOST_CONTAINER_NOEXCEPT
641 { return m_tree.erase(first, last); }
642
643 //! <b>Effects</b>: Swaps the contents of *this and x.
644 //!
645 //! <b>Throws</b>: Nothing.
646 //!
647 //! <b>Complexity</b>: Constant.
648 void swap(map& x)
649 { m_tree.swap(x.m_tree); }
650
651 //! <b>Effects</b>: erase(a.begin(),a.end()).
652 //!
653 //! <b>Postcondition</b>: size() == 0.
654 //!
655 //! <b>Complexity</b>: linear in size().
656 void clear() BOOST_CONTAINER_NOEXCEPT
657 { m_tree.clear(); }
658
659 //////////////////////////////////////////////
660 //
661 // observers
662 //
663 //////////////////////////////////////////////
664
665 //! <b>Effects</b>: Returns the comparison object out
666 //! of which a was constructed.
667 //!
668 //! <b>Complexity</b>: Constant.
669 key_compare key_comp() const
670 { return m_tree.key_comp(); }
671
672 //! <b>Effects</b>: Returns an object of value_compare constructed out
673 //! of the comparison object.
674 //!
675 //! <b>Complexity</b>: Constant.
676 value_compare value_comp() const
677 { return value_compare(m_tree.key_comp()); }
678
679 //////////////////////////////////////////////
680 //
681 // map operations
682 //
683 //////////////////////////////////////////////
684
685 //! <b>Returns</b>: An iterator pointing to an element with the key
686 //! equivalent to x, or end() if such an element is not found.
687 //!
688 //! <b>Complexity</b>: Logarithmic.
689 iterator find(const key_type& x)
690 { return m_tree.find(x); }
691
692 //! <b>Returns</b>: Allocator const_iterator pointing to an element with the key
693 //! equivalent to x, or end() if such an element is not found.
694 //!
695 //! <b>Complexity</b>: Logarithmic.
696 const_iterator find(const key_type& x) const
697 { return m_tree.find(x); }
698
699 //! <b>Returns</b>: The number of elements with key equivalent to x.
700 //!
701 //! <b>Complexity</b>: log(size())+count(k)
702 size_type count(const key_type& x) const
703 { return m_tree.find(x) == m_tree.end() ? 0 : 1; }
704
705 //! <b>Returns</b>: An iterator pointing to the first element with key not less
706 //! than k, or a.end() if such an element is not found.
707 //!
708 //! <b>Complexity</b>: Logarithmic
709 iterator lower_bound(const key_type& x)
710 { return m_tree.lower_bound(x); }
711
712 //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
713 //! less than k, or a.end() if such an element is not found.
714 //!
715 //! <b>Complexity</b>: Logarithmic
716 const_iterator lower_bound(const key_type& x) const
717 { return m_tree.lower_bound(x); }
718
719 //! <b>Returns</b>: An iterator pointing to the first element with key not less
720 //! than x, or end() if such an element is not found.
721 //!
722 //! <b>Complexity</b>: Logarithmic
723 iterator upper_bound(const key_type& x)
724 { return m_tree.upper_bound(x); }
725
726 //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
727 //! less than x, or end() if such an element is not found.
728 //!
729 //! <b>Complexity</b>: Logarithmic
730 const_iterator upper_bound(const key_type& x) const
731 { return m_tree.upper_bound(x); }
732
733 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
734 //!
735 //! <b>Complexity</b>: Logarithmic
736 std::pair<iterator,iterator> equal_range(const key_type& x)
737 { return m_tree.equal_range(x); }
738
739 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
740 //!
741 //! <b>Complexity</b>: Logarithmic
742 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const
743 { return m_tree.equal_range(x); }
744
745 /// @cond
746 template <class K1, class T1, class C1, class A1>
747 friend bool operator== (const map<K1, T1, C1, A1>&,
748 const map<K1, T1, C1, A1>&);
749 template <class K1, class T1, class C1, class A1>
750 friend bool operator< (const map<K1, T1, C1, A1>&,
751 const map<K1, T1, C1, A1>&);
752 private:
753 mapped_type& priv_subscript(const key_type &k)
754 {
755 //we can optimize this
756 iterator i = lower_bound(k);
757 // i->first is greater than or equivalent to k.
758 if (i == end() || key_comp()(k, (*i).first)){
759 container_detail::value_init<mapped_type> m;
760 movable_value_type val(k, boost::move(m.m_t));
761 i = insert(i, boost::move(val));
762 }
763 return (*i).second;
764 }
765
766 mapped_type& priv_subscript(BOOST_RV_REF(key_type) mk)
767 {
768 key_type &k = mk;
769 //we can optimize this
770 iterator i = lower_bound(k);
771 // i->first is greater than or equivalent to k.
772 if (i == end() || key_comp()(k, (*i).first)){
773 container_detail::value_init<mapped_type> m;
774 movable_value_type val(boost::move(k), boost::move(m.m_t));
775 i = insert(i, boost::move(val));
776 }
777 return (*i).second;
778 }
779
780 /// @endcond
781};
782
783template <class Key, class T, class Compare, class Allocator>
784inline bool operator==(const map<Key,T,Compare,Allocator>& x,
785 const map<Key,T,Compare,Allocator>& y)
786 { return x.m_tree == y.m_tree; }
787
788template <class Key, class T, class Compare, class Allocator>
789inline bool operator<(const map<Key,T,Compare,Allocator>& x,
790 const map<Key,T,Compare,Allocator>& y)
791 { return x.m_tree < y.m_tree; }
792
793template <class Key, class T, class Compare, class Allocator>
794inline bool operator!=(const map<Key,T,Compare,Allocator>& x,
795 const map<Key,T,Compare,Allocator>& y)
796 { return !(x == y); }
797
798template <class Key, class T, class Compare, class Allocator>
799inline bool operator>(const map<Key,T,Compare,Allocator>& x,
800 const map<Key,T,Compare,Allocator>& y)
801 { return y < x; }
802
803template <class Key, class T, class Compare, class Allocator>
804inline bool operator<=(const map<Key,T,Compare,Allocator>& x,
805 const map<Key,T,Compare,Allocator>& y)
806 { return !(y < x); }
807
808template <class Key, class T, class Compare, class Allocator>
809inline bool operator>=(const map<Key,T,Compare,Allocator>& x,
810 const map<Key,T,Compare,Allocator>& y)
811 { return !(x < y); }
812
813template <class Key, class T, class Compare, class Allocator>
814inline void swap(map<Key,T,Compare,Allocator>& x, map<Key,T,Compare,Allocator>& y)
815 { x.swap(y); }
816
817/// @cond
818
819// Forward declaration of operators < and ==, needed for friend declaration.
820
821template <class Key, class T, class Compare, class Allocator>
822inline bool operator==(const multimap<Key,T,Compare,Allocator>& x,
823 const multimap<Key,T,Compare,Allocator>& y);
824
825template <class Key, class T, class Compare, class Allocator>
826inline bool operator<(const multimap<Key,T,Compare,Allocator>& x,
827 const multimap<Key,T,Compare,Allocator>& y);
828
829} //namespace container {
830
831//!has_trivial_destructor_after_move<> == true_type
832//!specialization for optimizations
833template <class K, class T, class C, class Allocator>
834struct has_trivial_destructor_after_move<boost::container::map<K, T, C, Allocator> >
835{
836 static const bool value = has_trivial_destructor_after_move<Allocator>::value && has_trivial_destructor_after_move<C>::value;
837};
838
839namespace container {
840
841/// @endcond
842
843//! A multimap is a kind of associative container that supports equivalent keys
844//! (possibly containing multiple copies of the same key value) and provides for
845//! fast retrieval of values of another type T based on the keys. The multimap class
846//! supports bidirectional iterators.
847//!
848//! A multimap satisfies all of the requirements of a container and of a reversible
849//! container and of an associative container. For a
850//! map<Key,T> the key_type is Key and the value_type is std::pair<const Key,T>.
851//!
852//! Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
853//!
854//! Allocator is the allocator to allocate the value_types
855//!(e.g. <i>allocator< std::pair<<b>const</b> Key, T> ></i>).
856#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
857template <class Key, class T, class Compare = std::less<Key>, class Allocator = std::allocator< std::pair< const Key, T> > >
858#else
859template <class Key, class T, class Compare, class Allocator>
860#endif
861class multimap
862{
863 /// @cond
864 private:
865 BOOST_COPYABLE_AND_MOVABLE(multimap)
866
867 typedef std::pair<const Key, T> value_type_impl;
868 typedef container_detail::rbtree
869 <Key, value_type_impl, container_detail::select1st<value_type_impl>, Compare, Allocator> tree_t;
870 typedef container_detail::pair <Key, T> movable_value_type_impl;
871 typedef container_detail::tree_value_compare
872 < Key, value_type_impl, Compare, container_detail::select1st<value_type_impl>
873 > value_compare_impl;
874 tree_t m_tree; // red-black tree representing map
875 /// @endcond
876
877 public:
878 //////////////////////////////////////////////
879 //
880 // types
881 //
882 //////////////////////////////////////////////
883
884 typedef Key key_type;
885 typedef T mapped_type;
886 typedef std::pair<const Key, T> value_type;
887 typedef typename boost::container::allocator_traits<Allocator>::pointer pointer;
888 typedef typename boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
889 typedef typename boost::container::allocator_traits<Allocator>::reference reference;
890 typedef typename boost::container::allocator_traits<Allocator>::const_reference const_reference;
891 typedef typename boost::container::allocator_traits<Allocator>::size_type size_type;
892 typedef typename boost::container::allocator_traits<Allocator>::difference_type difference_type;
893 typedef Allocator allocator_type;
894 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type;
895 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare;
896 typedef Compare key_compare;
897 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::iterator) iterator;
898 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_iterator) const_iterator;
899 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator) reverse_iterator;
900 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator) const_reverse_iterator;
901 typedef std::pair<key_type, mapped_type> nonconst_value_type;
902 typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl) movable_value_type;
903
904 //////////////////////////////////////////////
905 //
906 // construct/copy/destroy
907 //
908 //////////////////////////////////////////////
909
910 //! <b>Effects</b>: Default constructs an empty multimap.
911 //!
912 //! <b>Complexity</b>: Constant.
913 multimap()
914 : m_tree()
915 {
916 //Allocator type must be std::pair<CONST Key, T>
917 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
918 }
919
920 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison
921 //! object and allocator.
922 //!
923 //! <b>Complexity</b>: Constant.
924 explicit multimap(const Compare& comp, const allocator_type& a = allocator_type())
925 : m_tree(comp, a)
926 {
927 //Allocator type must be std::pair<CONST Key, T>
928 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
929 }
930
931 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object
932 //! and allocator, and inserts elements from the range [first ,last ).
933 //!
934 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
935 //! comp and otherwise N logN, where N is last - first.
936 template <class InputIterator>
937 multimap(InputIterator first, InputIterator last,
938 const Compare& comp = Compare(),
939 const allocator_type& a = allocator_type())
940 : m_tree(false, first, last, comp, a)
941 {
942 //Allocator type must be std::pair<CONST Key, T>
943 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
944 }
945
946 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and
947 //! allocator, and inserts elements from the ordered range [first ,last). This function
948 //! is more efficient than the normal range creation for ordered ranges.
949 //!
950 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
951 //!
952 //! <b>Complexity</b>: Linear in N.
953 template <class InputIterator>
954 multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp = Compare(),
955 const allocator_type& a = allocator_type())
956 : m_tree(ordered_range, first, last, comp, a)
957 {}
958
959 //! <b>Effects</b>: Copy constructs a multimap.
960 //!
961 //! <b>Complexity</b>: Linear in x.size().
962 multimap(const multimap& x)
963 : m_tree(x.m_tree)
964 {
965 //Allocator type must be std::pair<CONST Key, T>
966 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
967 }
968
969 //! <b>Effects</b>: Move constructs a multimap. Constructs *this using x's resources.
970 //!
971 //! <b>Complexity</b>: Constant.
972 //!
973 //! <b>Postcondition</b>: x is emptied.
974 multimap(BOOST_RV_REF(multimap) x)
975 : m_tree(boost::move(x.m_tree))
976 {
977 //Allocator type must be std::pair<CONST Key, T>
978 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
979 }
980
981 //! <b>Effects</b>: Copy constructs a multimap.
982 //!
983 //! <b>Complexity</b>: Linear in x.size().
984 multimap(const multimap& x, const allocator_type &a)
985 : m_tree(x.m_tree, a)
986 {
987 //Allocator type must be std::pair<CONST Key, T>
988 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
989 }
990
991 //! <b>Effects</b>: Move constructs a multimap using the specified allocator.
992 //! Constructs *this using x's resources.
993 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
994 //!
995 //! <b>Postcondition</b>: x is emptied.
996 multimap(BOOST_RV_REF(multimap) x, const allocator_type &a)
997 : m_tree(boost::move(x.m_tree), a)
998 {
999 //Allocator type must be std::pair<CONST Key, T>
1000 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
1001 }
1002
1003 //! <b>Effects</b>: Makes *this a copy of x.
1004 //!
1005 //! <b>Complexity</b>: Linear in x.size().
1006 multimap& operator=(BOOST_COPY_ASSIGN_REF(multimap) x)
1007 { m_tree = x.m_tree; return *this; }
1008
1009 //! <b>Effects</b>: this->swap(x.get()).
1010 //!
1011 //! <b>Complexity</b>: Constant.
1012 multimap& operator=(BOOST_RV_REF(multimap) x)
1013 { m_tree = boost::move(x.m_tree); return *this; }
1014
1015 //! <b>Effects</b>: Returns a copy of the Allocator that
1016 //! was passed to the object's constructor.
1017 //!
1018 //! <b>Complexity</b>: Constant.
1019 allocator_type get_allocator() const BOOST_CONTAINER_NOEXCEPT
1020 { return m_tree.get_allocator(); }
1021
1022 //! <b>Effects</b>: Returns a reference to the internal allocator.
1023 //!
1024 //! <b>Throws</b>: Nothing
1025 //!
1026 //! <b>Complexity</b>: Constant.
1027 //!
1028 //! <b>Note</b>: Non-standard extension.
1029 stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT
1030 { return m_tree.get_stored_allocator(); }
1031
1032 //! <b>Effects</b>: Returns a reference to the internal allocator.
1033 //!
1034 //! <b>Throws</b>: Nothing
1035 //!
1036 //! <b>Complexity</b>: Constant.
1037 //!
1038 //! <b>Note</b>: Non-standard extension.
1039 const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT
1040 { return m_tree.get_stored_allocator(); }
1041
1042 //////////////////////////////////////////////
1043 //
1044 // iterators
1045 //
1046 //////////////////////////////////////////////
1047
1048 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
1049 //!
1050 //! <b>Throws</b>: Nothing.
1051 //!
1052 //! <b>Complexity</b>: Constant.
1053 iterator begin() BOOST_CONTAINER_NOEXCEPT
1054 { return m_tree.begin(); }
1055
1056 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
1057 //!
1058 //! <b>Throws</b>: Nothing.
1059 //!
1060 //! <b>Complexity</b>: Constant.
1061 const_iterator begin() const BOOST_CONTAINER_NOEXCEPT
1062 { return this->cbegin(); }
1063
1064 //! <b>Effects</b>: Returns an iterator to the end of the container.
1065 //!
1066 //! <b>Throws</b>: Nothing.
1067 //!
1068 //! <b>Complexity</b>: Constant.
1069 iterator end() BOOST_CONTAINER_NOEXCEPT
1070 { return m_tree.end(); }
1071
1072 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
1073 //!
1074 //! <b>Throws</b>: Nothing.
1075 //!
1076 //! <b>Complexity</b>: Constant.
1077 const_iterator end() const BOOST_CONTAINER_NOEXCEPT
1078 { return this->cend(); }
1079
1080 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
1081 //! of the reversed container.
1082 //!
1083 //! <b>Throws</b>: Nothing.
1084 //!
1085 //! <b>Complexity</b>: Constant.
1086 reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT
1087 { return m_tree.rbegin(); }
1088
1089 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1090 //! of the reversed container.
1091 //!
1092 //! <b>Throws</b>: Nothing.
1093 //!
1094 //! <b>Complexity</b>: Constant.
1095 const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT
1096 { return this->crbegin(); }
1097
1098 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
1099 //! of the reversed container.
1100 //!
1101 //! <b>Throws</b>: Nothing.
1102 //!
1103 //! <b>Complexity</b>: Constant.
1104 reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT
1105 { return m_tree.rend(); }
1106
1107 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1108 //! of the reversed container.
1109 //!
1110 //! <b>Throws</b>: Nothing.
1111 //!
1112 //! <b>Complexity</b>: Constant.
1113 const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT
1114 { return this->crend(); }
1115
1116 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
1117 //!
1118 //! <b>Throws</b>: Nothing.
1119 //!
1120 //! <b>Complexity</b>: Constant.
1121 const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT
1122 { return m_tree.begin(); }
1123
1124 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
1125 //!
1126 //! <b>Throws</b>: Nothing.
1127 //!
1128 //! <b>Complexity</b>: Constant.
1129 const_iterator cend() const BOOST_CONTAINER_NOEXCEPT
1130 { return m_tree.end(); }
1131
1132 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1133 //! of the reversed container.
1134 //!
1135 //! <b>Throws</b>: Nothing.
1136 //!
1137 //! <b>Complexity</b>: Constant.
1138 const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT
1139 { return m_tree.rbegin(); }
1140
1141 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1142 //! of the reversed container.
1143 //!
1144 //! <b>Throws</b>: Nothing.
1145 //!
1146 //! <b>Complexity</b>: Constant.
1147 const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT
1148 { return m_tree.rend(); }
1149
1150 //////////////////////////////////////////////
1151 //
1152 // capacity
1153 //
1154 //////////////////////////////////////////////
1155
1156 //! <b>Effects</b>: Returns true if the container contains no elements.
1157 //!
1158 //! <b>Throws</b>: Nothing.
1159 //!
1160 //! <b>Complexity</b>: Constant.
1161 bool empty() const BOOST_CONTAINER_NOEXCEPT
1162 { return m_tree.empty(); }
1163
1164 //! <b>Effects</b>: Returns the number of the elements contained in the container.
1165 //!
1166 //! <b>Throws</b>: Nothing.
1167 //!
1168 //! <b>Complexity</b>: Constant.
1169 size_type size() const BOOST_CONTAINER_NOEXCEPT
1170 { return m_tree.size(); }
1171
1172 //! <b>Effects</b>: Returns the largest possible size of the container.
1173 //!
1174 //! <b>Throws</b>: Nothing.
1175 //!
1176 //! <b>Complexity</b>: Constant.
1177 size_type max_size() const BOOST_CONTAINER_NOEXCEPT
1178 { return m_tree.max_size(); }
1179
1180 //////////////////////////////////////////////
1181 //
1182 // modifiers
1183 //
1184 //////////////////////////////////////////////
1185
1186 #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1187
1188 //! <b>Effects</b>: Inserts an object of type T constructed with
1189 //! std::forward<Args>(args)... in the container.
1190 //! p is a hint pointing to where the insert should start to search.
1191 //!
1192 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1193 //! to the key of x.
1194 //!
1195 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1196 //! is inserted right before p.
1197 template <class... Args>
1198 iterator emplace(Args&&... args)
1199 { return m_tree.emplace_equal(boost::forward<Args>(args)...); }
1200
1201 //! <b>Effects</b>: Inserts an object of type T constructed with
1202 //! std::forward<Args>(args)... in the container.
1203 //! p is a hint pointing to where the insert should start to search.
1204 //!
1205 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1206 //! to the key of x.
1207 //!
1208 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1209 //! is inserted right before p.
1210 template <class... Args>
1211 iterator emplace_hint(const_iterator hint, Args&&... args)
1212 { return m_tree.emplace_hint_equal(hint, boost::forward<Args>(args)...); }
1213
1214 #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
1215
1216 #define BOOST_PP_LOCAL_MACRO(n) \
1217 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
1218 iterator emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
1219 { return m_tree.emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \
1220 \
1221 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
1222 iterator emplace_hint(const_iterator hint \
1223 BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
1224 { return m_tree.emplace_hint_equal(hint \
1225 BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _));} \
1226 //!
1227 #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
1228 #include BOOST_PP_LOCAL_ITERATE()
1229
1230 #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
1231
1232 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
1233 //! newly inserted element.
1234 //!
1235 //! <b>Complexity</b>: Logarithmic.
1236 iterator insert(const value_type& x)
1237 { return m_tree.insert_equal(x); }
1238
1239 //! <b>Effects</b>: Inserts a new value constructed from x and returns
1240 //! the iterator pointing to the newly inserted element.
1241 //!
1242 //! <b>Complexity</b>: Logarithmic.
1243 iterator insert(const nonconst_value_type& x)
1244 { return m_tree.insert_equal(x); }
1245
1246 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
1247 //! the iterator pointing to the newly inserted element.
1248 //!
1249 //! <b>Complexity</b>: Logarithmic.
1250 iterator insert(BOOST_RV_REF(nonconst_value_type) x)
1251 { return m_tree.insert_equal(boost::move(x)); }
1252
1253 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
1254 //! the iterator pointing to the newly inserted element.
1255 //!
1256 //! <b>Complexity</b>: Logarithmic.
1257 iterator insert(BOOST_RV_REF(movable_value_type) x)
1258 { return m_tree.insert_equal(boost::move(x)); }
1259
1260 //! <b>Effects</b>: Inserts a copy of x in the container.
1261 //! p is a hint pointing to where the insert should start to search.
1262 //!
1263 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1264 //! to the key of x.
1265 //!
1266 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1267 //! is inserted right before p.
1268 iterator insert(const_iterator position, const value_type& x)
1269 { return m_tree.insert_equal(position, x); }
1270
1271 //! <b>Effects</b>: Inserts a new value constructed from x in the container.
1272 //! p is a hint pointing to where the insert should start to search.
1273 //!
1274 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1275 //! to the key of x.
1276 //!
1277 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1278 //! is inserted right before p.
1279 iterator insert(const_iterator position, const nonconst_value_type& x)
1280 { return m_tree.insert_equal(position, x); }
1281
1282 //! <b>Effects</b>: Inserts a new value move constructed from x in the container.
1283 //! p is a hint pointing to where the insert should start to search.
1284 //!
1285 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1286 //! to the key of x.
1287 //!
1288 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1289 //! is inserted right before p.
1290 iterator insert(const_iterator position, BOOST_RV_REF(nonconst_value_type) x)
1291 { return m_tree.insert_equal(position, boost::move(x)); }
1292
1293 //! <b>Effects</b>: Inserts a new value move constructed from x in the container.
1294 //! p is a hint pointing to where the insert should start to search.
1295 //!
1296 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1297 //! to the key of x.
1298 //!
1299 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1300 //! is inserted right before p.
1301 iterator insert(const_iterator position, BOOST_RV_REF(movable_value_type) x)
1302 { return m_tree.insert_equal(position, boost::move(x)); }
1303
1304 //! <b>Requires</b>: first, last are not iterators into *this.
1305 //!
1306 //! <b>Effects</b>: inserts each element from the range [first,last) .
1307 //!
1308 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1309 template <class InputIterator>
1310 void insert(InputIterator first, InputIterator last)
1311 { m_tree.insert_equal(first, last); }
1312
1313 //! <b>Effects</b>: Erases the element pointed to by position.
1314 //!
1315 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
1316 //! following q prior to the element being erased. If no such element exists,
1317 //! returns end().
1318 //!
1319 //! <b>Complexity</b>: Amortized constant time
1320 iterator erase(const_iterator position) BOOST_CONTAINER_NOEXCEPT
1321 { return m_tree.erase(position); }
1322
1323 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
1324 //!
1325 //! <b>Returns</b>: Returns the number of erased elements.
1326 //!
1327 //! <b>Complexity</b>: log(size()) + count(k)
1328 size_type erase(const key_type& x) BOOST_CONTAINER_NOEXCEPT
1329 { return m_tree.erase(x); }
1330
1331 //! <b>Effects</b>: Erases all the elements in the range [first, last).
1332 //!
1333 //! <b>Returns</b>: Returns last.
1334 //!
1335 //! <b>Complexity</b>: log(size())+N where N is the distance from first to last.
1336 iterator erase(const_iterator first, const_iterator last) BOOST_CONTAINER_NOEXCEPT
1337 { return m_tree.erase(first, last); }
1338
1339 //! <b>Effects</b>: Swaps the contents of *this and x.
1340 //!
1341 //! <b>Throws</b>: Nothing.
1342 //!
1343 //! <b>Complexity</b>: Constant.
1344 void swap(multimap& x)
1345 { m_tree.swap(x.m_tree); }
1346
1347 //! <b>Effects</b>: erase(a.begin(),a.end()).
1348 //!
1349 //! <b>Postcondition</b>: size() == 0.
1350 //!
1351 //! <b>Complexity</b>: linear in size().
1352 void clear() BOOST_CONTAINER_NOEXCEPT
1353 { m_tree.clear(); }
1354
1355 //////////////////////////////////////////////
1356 //
1357 // observers
1358 //
1359 //////////////////////////////////////////////
1360
1361 //! <b>Effects</b>: Returns the comparison object out
1362 //! of which a was constructed.
1363 //!
1364 //! <b>Complexity</b>: Constant.
1365 key_compare key_comp() const
1366 { return m_tree.key_comp(); }
1367
1368 //! <b>Effects</b>: Returns an object of value_compare constructed out
1369 //! of the comparison object.
1370 //!
1371 //! <b>Complexity</b>: Constant.
1372 value_compare value_comp() const
1373 { return value_compare(m_tree.key_comp()); }
1374
1375 //////////////////////////////////////////////
1376 //
1377 // map operations
1378 //
1379 //////////////////////////////////////////////
1380
1381 //! <b>Returns</b>: An iterator pointing to an element with the key
1382 //! equivalent to x, or end() if such an element is not found.
1383 //!
1384 //! <b>Complexity</b>: Logarithmic.
1385 iterator find(const key_type& x)
1386 { return m_tree.find(x); }
1387
1388 //! <b>Returns</b>: Allocator const iterator pointing to an element with the key
1389 //! equivalent to x, or end() if such an element is not found.
1390 //!
1391 //! <b>Complexity</b>: Logarithmic.
1392 const_iterator find(const key_type& x) const
1393 { return m_tree.find(x); }
1394
1395 //! <b>Returns</b>: The number of elements with key equivalent to x.
1396 //!
1397 //! <b>Complexity</b>: log(size())+count(k)
1398 size_type count(const key_type& x) const
1399 { return m_tree.count(x); }
1400
1401 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1402 //! than k, or a.end() if such an element is not found.
1403 //!
1404 //! <b>Complexity</b>: Logarithmic
1405 iterator lower_bound(const key_type& x)
1406 {return m_tree.lower_bound(x); }
1407
1408 //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
1409 //! less than k, or a.end() if such an element is not found.
1410 //!
1411 //! <b>Complexity</b>: Logarithmic
1412 const_iterator lower_bound(const key_type& x) const
1413 { return m_tree.lower_bound(x); }
1414
1415 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1416 //! than x, or end() if such an element is not found.
1417 //!
1418 //! <b>Complexity</b>: Logarithmic
1419 iterator upper_bound(const key_type& x)
1420 { return m_tree.upper_bound(x); }
1421
1422 //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
1423 //! less than x, or end() if such an element is not found.
1424 //!
1425 //! <b>Complexity</b>: Logarithmic
1426 const_iterator upper_bound(const key_type& x) const
1427 { return m_tree.upper_bound(x); }
1428
1429 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1430 //!
1431 //! <b>Complexity</b>: Logarithmic
1432 std::pair<iterator,iterator> equal_range(const key_type& x)
1433 { return m_tree.equal_range(x); }
1434
1435 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1436 //!
1437 //! <b>Complexity</b>: Logarithmic
1438 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const
1439 { return m_tree.equal_range(x); }
1440
1441 /// @cond
1442 template <class K1, class T1, class C1, class A1>
1443 friend bool operator== (const multimap<K1, T1, C1, A1>& x,
1444 const multimap<K1, T1, C1, A1>& y);
1445
1446 template <class K1, class T1, class C1, class A1>
1447 friend bool operator< (const multimap<K1, T1, C1, A1>& x,
1448 const multimap<K1, T1, C1, A1>& y);
1449 /// @endcond
1450};
1451
1452template <class Key, class T, class Compare, class Allocator>
1453inline bool operator==(const multimap<Key,T,Compare,Allocator>& x,
1454 const multimap<Key,T,Compare,Allocator>& y)
1455{ return x.m_tree == y.m_tree; }
1456
1457template <class Key, class T, class Compare, class Allocator>
1458inline bool operator<(const multimap<Key,T,Compare,Allocator>& x,
1459 const multimap<Key,T,Compare,Allocator>& y)
1460{ return x.m_tree < y.m_tree; }
1461
1462template <class Key, class T, class Compare, class Allocator>
1463inline bool operator!=(const multimap<Key,T,Compare,Allocator>& x,
1464 const multimap<Key,T,Compare,Allocator>& y)
1465{ return !(x == y); }
1466
1467template <class Key, class T, class Compare, class Allocator>
1468inline bool operator>(const multimap<Key,T,Compare,Allocator>& x,
1469 const multimap<Key,T,Compare,Allocator>& y)
1470{ return y < x; }
1471
1472template <class Key, class T, class Compare, class Allocator>
1473inline bool operator<=(const multimap<Key,T,Compare,Allocator>& x,
1474 const multimap<Key,T,Compare,Allocator>& y)
1475{ return !(y < x); }
1476
1477template <class Key, class T, class Compare, class Allocator>
1478inline bool operator>=(const multimap<Key,T,Compare,Allocator>& x,
1479 const multimap<Key,T,Compare,Allocator>& y)
1480{ return !(x < y); }
1481
1482template <class Key, class T, class Compare, class Allocator>
1483inline void swap(multimap<Key,T,Compare,Allocator>& x, multimap<Key,T,Compare,Allocator>& y)
1484{ x.swap(y); }
1485
1486/// @cond
1487
1488} //namespace container {
1489
1490//!has_trivial_destructor_after_move<> == true_type
1491//!specialization for optimizations
1492template <class K, class T, class C, class Allocator>
1493struct has_trivial_destructor_after_move<boost::container::multimap<K, T, C, Allocator> >
1494{
1495 static const bool value = has_trivial_destructor_after_move<Allocator>::value && has_trivial_destructor_after_move<C>::value;
1496};
1497
1498namespace container {
1499
1500/// @endcond
1501
1502}}
1503
1504#include <boost/container/detail/config_end.hpp>
1505
1506#endif /* BOOST_CONTAINER_MAP_HPP */
1507