stl_multimap.h revision 117397
1// Multimap implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 2, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30/* 31 * 32 * Copyright (c) 1994 33 * Hewlett-Packard Company 34 * 35 * Permission to use, copy, modify, distribute and sell this software 36 * and its documentation for any purpose is hereby granted without fee, 37 * provided that the above copyright notice appear in all copies and 38 * that both that copyright notice and this permission notice appear 39 * in supporting documentation. Hewlett-Packard Company makes no 40 * representations about the suitability of this software for any 41 * purpose. It is provided "as is" without express or implied warranty. 42 * 43 * 44 * Copyright (c) 1996,1997 45 * Silicon Graphics Computer Systems, Inc. 46 * 47 * Permission to use, copy, modify, distribute and sell this software 48 * and its documentation for any purpose is hereby granted without fee, 49 * provided that the above copyright notice appear in all copies and 50 * that both that copyright notice and this permission notice appear 51 * in supporting documentation. Silicon Graphics makes no 52 * representations about the suitability of this software for any 53 * purpose. It is provided "as is" without express or implied warranty. 54 */ 55 56/** @file stl_multimap.h 57 * This is an internal header file, included by other library headers. 58 * You should not attempt to use it directly. 59 */ 60 61#ifndef __GLIBCPP_INTERNAL_MULTIMAP_H 62#define __GLIBCPP_INTERNAL_MULTIMAP_H 63 64#include <bits/concept_check.h> 65 66namespace std 67{ 68 // Forward declaration of operators < and ==, needed for friend declaration. 69 70 template <typename _Key, typename _Tp, 71 typename _Compare = less<_Key>, 72 typename _Alloc = allocator<pair<const _Key, _Tp> > > 73 class multimap; 74 75 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 76 inline bool operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 77 const multimap<_Key,_Tp,_Compare,_Alloc>& __y); 78 79 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 80 inline bool operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 81 const multimap<_Key,_Tp,_Compare,_Alloc>& __y); 82 83 /** 84 * @brief A standard container made up of (key,value) pairs, which can be 85 * retrieved based on a key, in logarithmic time. 86 * 87 * @ingroup Containers 88 * @ingroup Assoc_containers 89 * 90 * Meets the requirements of a <a href="tables.html#65">container</a>, a 91 * <a href="tables.html#66">reversible container</a>, and an 92 * <a href="tables.html#69">associative container</a> (using equivalent 93 * keys). For a @c multimap<Key,T> the key_type is Key, the mapped_type 94 * is T, and the value_type is std::pair<const Key,T>. 95 * 96 * Multimaps support bidirectional iterators. 97 * 98 * @if maint 99 * The private tree data is declared exactly the same way for map and 100 * multimap; the distinction is made entirely in how the tree functions are 101 * called (*_unique versus *_equal, same as the standard). 102 * @endif 103 */ 104 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 105 class multimap 106 { 107 // concept requirements 108 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 109 __glibcpp_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept) 110 111 public: 112 typedef _Key key_type; 113 typedef _Tp mapped_type; 114 typedef pair<const _Key, _Tp> value_type; 115 typedef _Compare key_compare; 116 117 class value_compare 118 : public binary_function<value_type, value_type, bool> 119 { 120 friend class multimap<_Key,_Tp,_Compare,_Alloc>; 121 protected: 122 _Compare comp; 123 value_compare(_Compare __c) : comp(__c) {} 124 public: 125 bool operator()(const value_type& __x, const value_type& __y) const 126 { return comp(__x.first, __y.first); } 127 }; 128 129 private: 130 /// @if maint This turns a red-black tree into a [multi]map. @endif 131 typedef _Rb_tree<key_type, value_type, 132 _Select1st<value_type>, key_compare, _Alloc> _Rep_type; 133 /// @if maint The actual tree structure. @endif 134 _Rep_type _M_t; 135 136 public: 137 // many of these are specified differently in ISO, but the following are 138 // "functionally equivalent" 139 typedef typename _Rep_type::allocator_type allocator_type; 140 typedef typename _Rep_type::reference reference; 141 typedef typename _Rep_type::const_reference const_reference; 142 typedef typename _Rep_type::iterator iterator; 143 typedef typename _Rep_type::const_iterator const_iterator; 144 typedef typename _Rep_type::size_type size_type; 145 typedef typename _Rep_type::difference_type difference_type; 146 typedef typename _Rep_type::pointer pointer; 147 typedef typename _Rep_type::const_pointer const_pointer; 148 typedef typename _Rep_type::reverse_iterator reverse_iterator; 149 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 150 151 152 // [23.3.2] construct/copy/destroy 153 // (get_allocator() is also listed in this section) 154 /** 155 * @brief Default constructor creates no elements. 156 */ 157 multimap() : _M_t(_Compare(), allocator_type()) { } 158 159 // for some reason this was made a separate function 160 /** 161 * @brief Default constructor creates no elements. 162 */ 163 explicit 164 multimap(const _Compare& __comp, const allocator_type& __a = allocator_type()) 165 : _M_t(__comp, __a) { } 166 167 /** 168 * @brief %Multimap copy constructor. 169 * @param x A %multimap of identical element and allocator types. 170 * 171 * The newly-created %multimap uses a copy of the allocation object used 172 * by @a x. 173 */ 174 multimap(const multimap& __x) 175 : _M_t(__x._M_t) { } 176 177 /** 178 * @brief Builds a %multimap from a range. 179 * @param first An input iterator. 180 * @param last An input iterator. 181 * 182 * Create a %multimap consisting of copies of the elements from 183 * [first,last). This is linear in N if the range is already sorted, 184 * and NlogN otherwise (where N is distance(first,last)). 185 */ 186 template <typename _InputIterator> 187 multimap(_InputIterator __first, _InputIterator __last) 188 : _M_t(_Compare(), allocator_type()) 189 { _M_t.insert_equal(__first, __last); } 190 191 /** 192 * @brief Builds a %multimap from a range. 193 * @param first An input iterator. 194 * @param last An input iterator. 195 * @param comp A comparison functor. 196 * @param a An allocator object. 197 * 198 * Create a %multimap consisting of copies of the elements from 199 * [first,last). This is linear in N if the range is already sorted, 200 * and NlogN otherwise (where N is distance(first,last)). 201 */ 202 template <typename _InputIterator> 203 multimap(_InputIterator __first, _InputIterator __last, 204 const _Compare& __comp, 205 const allocator_type& __a = allocator_type()) 206 : _M_t(__comp, __a) 207 { _M_t.insert_equal(__first, __last); } 208 209 // FIXME There is no dtor declared, but we should have something generated 210 // by Doxygen. I don't know what tags to add to this paragraph to make 211 // that happen: 212 /** 213 * The dtor only erases the elements, and note that if the elements 214 * themselves are pointers, the pointed-to memory is not touched in any 215 * way. Managing the pointer is the user's responsibilty. 216 */ 217 218 /** 219 * @brief %Multimap assignment operator. 220 * @param x A %multimap of identical element and allocator types. 221 * 222 * All the elements of @a x are copied, but unlike the copy constructor, 223 * the allocator object is not copied. 224 */ 225 multimap& 226 operator=(const multimap& __x) 227 { 228 _M_t = __x._M_t; 229 return *this; 230 } 231 232 /// Get a copy of the memory allocation object. 233 allocator_type 234 get_allocator() const { return _M_t.get_allocator(); } 235 236 // iterators 237 /** 238 * Returns a read/write iterator that points to the first pair in the 239 * %multimap. Iteration is done in ascending order according to the keys. 240 */ 241 iterator 242 begin() { return _M_t.begin(); } 243 244 /** 245 * Returns a read-only (constant) iterator that points to the first pair 246 * in the %multimap. Iteration is done in ascending order according to the 247 * keys. 248 */ 249 const_iterator 250 begin() const { return _M_t.begin(); } 251 252 /** 253 * Returns a read/write iterator that points one past the last pair in the 254 * %multimap. Iteration is done in ascending order according to the keys. 255 */ 256 iterator 257 end() { return _M_t.end(); } 258 259 /** 260 * Returns a read-only (constant) iterator that points one past the last 261 * pair in the %multimap. Iteration is done in ascending order according 262 * to the keys. 263 */ 264 const_iterator 265 end() const { return _M_t.end(); } 266 267 /** 268 * Returns a read/write reverse iterator that points to the last pair in 269 * the %multimap. Iteration is done in descending order according to the 270 * keys. 271 */ 272 reverse_iterator 273 rbegin() { return _M_t.rbegin(); } 274 275 /** 276 * Returns a read-only (constant) reverse iterator that points to the last 277 * pair in the %multimap. Iteration is done in descending order according 278 * to the keys. 279 */ 280 const_reverse_iterator 281 rbegin() const { return _M_t.rbegin(); } 282 283 /** 284 * Returns a read/write reverse iterator that points to one before the 285 * first pair in the %multimap. Iteration is done in descending order 286 * according to the keys. 287 */ 288 reverse_iterator 289 rend() { return _M_t.rend(); } 290 291 /** 292 * Returns a read-only (constant) reverse iterator that points to one 293 * before the first pair in the %multimap. Iteration is done in descending 294 * order according to the keys. 295 */ 296 const_reverse_iterator 297 rend() const { return _M_t.rend(); } 298 299 // capacity 300 /** Returns true if the %multimap is empty. */ 301 bool 302 empty() const { return _M_t.empty(); } 303 304 /** Returns the size of the %multimap. */ 305 size_type 306 size() const { return _M_t.size(); } 307 308 /** Returns the maximum size of the %multimap. */ 309 size_type 310 max_size() const { return _M_t.max_size(); } 311 312 // modifiers 313 /** 314 * @brief Inserts a std::pair into the %multimap. 315 * @param x Pair to be inserted (see std::make_pair for easy creation of 316 * pairs). 317 * @return An iterator that points to the inserted (key,value) pair. 318 * 319 * This function inserts a (key, value) pair into the %multimap. Contrary 320 * to a std::map the %multimap does not rely on unique keys and thus 321 * multiple pairs with the same key can be inserted. 322 * 323 * Insertion requires logarithmic time. 324 */ 325 iterator 326 insert(const value_type& __x) { return _M_t.insert_equal(__x); } 327 328 /** 329 * @brief Inserts a std::pair into the %multimap. 330 * @param position An iterator that serves as a hint as to where the 331 * pair should be inserted. 332 * @param x Pair to be inserted (see std::make_pair for easy creation of 333 * pairs). 334 * @return An iterator that points to the inserted (key,value) pair. 335 * 336 * This function inserts a (key, value) pair into the %multimap. Contrary 337 * to a std::map the %multimap does not rely on unique keys and thus 338 * multiple pairs with the same key can be inserted. 339 * Note that the first parameter is only a hint and can potentially 340 * improve the performance of the insertion process. A bad hint would 341 * cause no gains in efficiency. 342 * 343 * See http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4 344 * for more on "hinting". 345 * 346 * Insertion requires logarithmic time (if the hint is not taken). 347 */ 348 iterator 349 insert(iterator __position, const value_type& __x) 350 { return _M_t.insert_equal(__position, __x); } 351 352 /** 353 * @brief A template function that attemps to insert a range of elements. 354 * @param first Iterator pointing to the start of the range to be 355 * inserted. 356 * @param last Iterator pointing to the end of the range. 357 * 358 * Complexity similar to that of the range constructor. 359 */ 360 template <typename _InputIterator> 361 void 362 insert(_InputIterator __first, _InputIterator __last) 363 { _M_t.insert_equal(__first, __last); } 364 365 /** 366 * @brief Erases an element from a %multimap. 367 * @param position An iterator pointing to the element to be erased. 368 * 369 * This function erases an element, pointed to by the given iterator, from 370 * a %multimap. Note that this function only erases the element, and that 371 * if the element is itself a pointer, the pointed-to memory is not 372 * touched in any way. Managing the pointer is the user's responsibilty. 373 */ 374 void 375 erase(iterator __position) { _M_t.erase(__position); } 376 377 /** 378 * @brief Erases elements according to the provided key. 379 * @param x Key of element to be erased. 380 * @return The number of elements erased. 381 * 382 * This function erases all elements located by the given key from a 383 * %multimap. 384 * Note that this function only erases the element, and that if 385 * the element is itself a pointer, the pointed-to memory is not touched 386 * in any way. Managing the pointer is the user's responsibilty. 387 */ 388 size_type 389 erase(const key_type& __x) { return _M_t.erase(__x); } 390 391 /** 392 * @brief Erases a [first,last) range of elements from a %multimap. 393 * @param first Iterator pointing to the start of the range to be erased. 394 * @param last Iterator pointing to the end of the range to be erased. 395 * 396 * This function erases a sequence of elements from a %multimap. 397 * Note that this function only erases the elements, and that if 398 * the elements themselves are pointers, the pointed-to memory is not 399 * touched in any way. Managing the pointer is the user's responsibilty. 400 */ 401 void 402 erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); } 403 404 /** 405 * @brief Swaps data with another %multimap. 406 * @param x A %multimap of the same element and allocator types. 407 * 408 * This exchanges the elements between two multimaps in constant time. 409 * (It is only swapping a pointer, an integer, and an instance of 410 * the @c Compare type (which itself is often stateless and empty), so it 411 * should be quite fast.) 412 * Note that the global std::swap() function is specialized such that 413 * std::swap(m1,m2) will feed to this function. 414 */ 415 void 416 swap(multimap& __x) { _M_t.swap(__x._M_t); } 417 418 /** 419 * Erases all elements in a %multimap. Note that this function only erases 420 * the elements, and that if the elements themselves are pointers, the 421 * pointed-to memory is not touched in any way. Managing the pointer is 422 * the user's responsibilty. 423 */ 424 void 425 clear() { _M_t.clear(); } 426 427 // observers 428 /** 429 * Returns the key comparison object out of which the %multimap 430 * was constructed. 431 */ 432 key_compare 433 key_comp() const { return _M_t.key_comp(); } 434 435 /** 436 * Returns a value comparison object, built from the key comparison 437 * object out of which the %multimap was constructed. 438 */ 439 value_compare 440 value_comp() const { return value_compare(_M_t.key_comp()); } 441 442 // multimap operations 443 /** 444 * @brief Tries to locate an element in a %multimap. 445 * @param x Key of (key, value) pair to be located. 446 * @return Iterator pointing to sought-after element, 447 * or end() if not found. 448 * 449 * This function takes a key and tries to locate the element with which 450 * the key matches. If successful the function returns an iterator 451 * pointing to the sought after %pair. If unsuccessful it returns the 452 * past-the-end ( @c end() ) iterator. 453 */ 454 iterator 455 find(const key_type& __x) { return _M_t.find(__x); } 456 457 /** 458 * @brief Tries to locate an element in a %multimap. 459 * @param x Key of (key, value) pair to be located. 460 * @return Read-only (constant) iterator pointing to sought-after 461 * element, or end() if not found. 462 * 463 * This function takes a key and tries to locate the element with which 464 * the key matches. If successful the function returns a constant iterator 465 * pointing to the sought after %pair. If unsuccessful it returns the 466 * past-the-end ( @c end() ) iterator. 467 */ 468 const_iterator 469 find(const key_type& __x) const { return _M_t.find(__x); } 470 471 /** 472 * @brief Finds the number of elements with given key. 473 * @param x Key of (key, value) pairs to be located. 474 * @return Number of elements with specified key. 475 */ 476 size_type 477 count(const key_type& __x) const { return _M_t.count(__x); } 478 479 /** 480 * @brief Finds the beginning of a subsequence matching given key. 481 * @param x Key of (key, value) pair to be located. 482 * @return Iterator pointing to first element matching given key, or 483 * end() if not found. 484 * 485 * This function returns the first element of a subsequence of elements 486 * that matches the given key. If unsuccessful it returns an iterator 487 * pointing to the first element that has a greater value than given key 488 * or end() if no such element exists. 489 */ 490 iterator 491 lower_bound(const key_type& __x) { return _M_t.lower_bound(__x); } 492 493 /** 494 * @brief Finds the beginning of a subsequence matching given key. 495 * @param x Key of (key, value) pair to be located. 496 * @return Read-only (constant) iterator pointing to first element 497 * matching given key, or end() if not found. 498 * 499 * This function returns the first element of a subsequence of elements 500 * that matches the given key. If unsuccessful the iterator will point 501 * to the next greatest element or, if no such greater element exists, to 502 * end(). 503 */ 504 const_iterator 505 lower_bound(const key_type& __x) const { return _M_t.lower_bound(__x); } 506 507 /** 508 * @brief Finds the end of a subsequence matching given key. 509 * @param x Key of (key, value) pair to be located. 510 * @return Iterator pointing to last element matching given key. 511 */ 512 iterator 513 upper_bound(const key_type& __x) { return _M_t.upper_bound(__x); } 514 515 /** 516 * @brief Finds the end of a subsequence matching given key. 517 * @param x Key of (key, value) pair to be located. 518 * @return Read-only (constant) iterator pointing to last element matching 519 * given key. 520 */ 521 const_iterator 522 upper_bound(const key_type& __x) const { return _M_t.upper_bound(__x); } 523 524 /** 525 * @brief Finds a subsequence matching given key. 526 * @param x Key of (key, value) pairs to be located. 527 * @return Pair of iterators that possibly points to the subsequence 528 * matching given key. 529 * 530 * This function returns a pair of which the first 531 * element possibly points to the first element matching the given key 532 * and the second element possibly points to the last element matching the 533 * given key. If unsuccessful the first element of the returned pair will 534 * contain an iterator pointing to the next greatest element or, if no such 535 * greater element exists, to end(). 536 */ 537 pair<iterator,iterator> 538 equal_range(const key_type& __x) { return _M_t.equal_range(__x); } 539 540 /** 541 * @brief Finds a subsequence matching given key. 542 * @param x Key of (key, value) pairs to be located. 543 * @return Pair of read-only (constant) iterators that possibly points to 544 * the subsequence matching given key. 545 * 546 * This function returns a pair of which the first 547 * element possibly points to the first element matching the given key 548 * and the second element possibly points to the last element matching the 549 * given key. If unsuccessful the first element of the returned pair will 550 * contain an iterator pointing to the next greatest element or, if no such 551 * a greater element exists, to end(). 552 */ 553 pair<const_iterator,const_iterator> 554 equal_range(const key_type& __x) const { return _M_t.equal_range(__x); } 555 556 template <typename _K1, typename _T1, typename _C1, typename _A1> 557 friend bool operator== (const multimap<_K1,_T1,_C1,_A1>&, 558 const multimap<_K1,_T1,_C1,_A1>&); 559 template <typename _K1, typename _T1, typename _C1, typename _A1> 560 friend bool operator< (const multimap<_K1,_T1,_C1,_A1>&, 561 const multimap<_K1,_T1,_C1,_A1>&); 562 }; 563 564 565 /** 566 * @brief Multimap equality comparison. 567 * @param x A %multimap. 568 * @param y A %multimap of the same type as @a x. 569 * @return True iff the size and elements of the maps are equal. 570 * 571 * This is an equivalence relation. It is linear in the size of the 572 * multimaps. Multimaps are considered equivalent if their sizes are equal, 573 * and if corresponding elements compare equal. 574 */ 575 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 576 inline bool 577 operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 578 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) 579 { 580 return __x._M_t == __y._M_t; 581 } 582 583 /** 584 * @brief Multimap ordering relation. 585 * @param x A %multimap. 586 * @param y A %multimap of the same type as @a x. 587 * @return True iff @a x is lexographically less than @a y. 588 * 589 * This is a total ordering relation. It is linear in the size of the 590 * multimaps. The elements must be comparable with @c <. 591 * 592 * See std::lexographical_compare() for how the determination is made. 593 */ 594 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 595 inline bool 596 operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 597 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) 598 { return __x._M_t < __y._M_t; } 599 600 /// Based on operator== 601 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 602 inline bool 603 operator!=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 604 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) 605 { return !(__x == __y); } 606 607 /// Based on operator< 608 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 609 inline bool 610 operator>(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 611 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) 612 { return __y < __x; } 613 614 /// Based on operator< 615 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 616 inline bool 617 operator<=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 618 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) 619 { return !(__y < __x); } 620 621 /// Based on operator< 622 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 623 inline bool 624 operator>=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 625 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) 626 { return !(__x < __y); } 627 628 /// See std::multimap::swap(). 629 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 630 inline void 631 swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x, 632 multimap<_Key,_Tp,_Compare,_Alloc>& __y) 633 { __x.swap(__y); } 634} // namespace std 635 636#endif /* __GLIBCPP_INTERNAL_MULTIMAP_H */ 637