00001 // List implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2005 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 2, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * 00032 * Copyright (c) 1994 00033 * Hewlett-Packard Company 00034 * 00035 * Permission to use, copy, modify, distribute and sell this software 00036 * and its documentation for any purpose is hereby granted without fee, 00037 * provided that the above copyright notice appear in all copies and 00038 * that both that copyright notice and this permission notice appear 00039 * in supporting documentation. Hewlett-Packard Company makes no 00040 * representations about the suitability of this software for any 00041 * purpose. It is provided "as is" without express or implied warranty. 00042 * 00043 * 00044 * Copyright (c) 1996,1997 00045 * Silicon Graphics Computer Systems, Inc. 00046 * 00047 * Permission to use, copy, modify, distribute and sell this software 00048 * and its documentation for any purpose is hereby granted without fee, 00049 * provided that the above copyright notice appear in all copies and 00050 * that both that copyright notice and this permission notice appear 00051 * in supporting documentation. Silicon Graphics makes no 00052 * representations about the suitability of this software for any 00053 * purpose. It is provided "as is" without express or implied warranty. 00054 */ 00055 00056 /** @file stl_list.h 00057 * This is an internal header file, included by other library headers. 00058 * You should not attempt to use it directly. 00059 */ 00060 00061 #ifndef __GLIBCPP_INTERNAL_LIST_H 00062 #define __GLIBCPP_INTERNAL_LIST_H 00063 00064 #include <bits/concept_check.h> 00065 00066 namespace std 00067 { 00068 // Supporting structures are split into common and templated types; the 00069 // latter publicly inherits from the former in an effort to reduce code 00070 // duplication. This results in some "needless" static_cast'ing later on, 00071 // but it's all safe downcasting. 00072 00073 /// @if maint Common part of a node in the %list. @endif 00074 struct _List_node_base 00075 { 00076 _List_node_base* _M_next; ///< Self-explanatory 00077 _List_node_base* _M_prev; ///< Self-explanatory 00078 }; 00079 00080 /// @if maint An actual node in the %list. @endif 00081 template<typename _Tp> 00082 struct _List_node : public _List_node_base 00083 { 00084 _Tp _M_data; ///< User's data. 00085 }; 00086 00087 00088 /** 00089 * @if maint 00090 * @brief Common part of a list::iterator. 00091 * 00092 * A simple type to walk a doubly-linked list. All operations here should 00093 * be self-explanatory after taking any decent introductory data structures 00094 * course. 00095 * @endif 00096 */ 00097 struct _List_iterator_base 00098 { 00099 typedef size_t size_type; 00100 typedef ptrdiff_t difference_type; 00101 typedef bidirectional_iterator_tag iterator_category; 00102 00103 /// The only member points to the %list element. 00104 _List_node_base* _M_node; 00105 00106 _List_iterator_base(_List_node_base* __x) 00107 : _M_node(__x) 00108 { } 00109 00110 _List_iterator_base() 00111 : _M_node() 00112 { } 00113 00114 /// Walk the %list forward. 00115 void 00116 _M_incr() 00117 { _M_node = _M_node->_M_next; } 00118 00119 /// Walk the %list backward. 00120 void 00121 _M_decr() 00122 { _M_node = _M_node->_M_prev; } 00123 00124 bool 00125 operator==(const _List_iterator_base& __x) const 00126 { return _M_node == __x._M_node; } 00127 00128 bool 00129 operator!=(const _List_iterator_base& __x) const 00130 { return _M_node != __x._M_node; } 00131 }; 00132 00133 /** 00134 * @brief A list::iterator. 00135 * 00136 * In addition to being used externally, a list holds one of these 00137 * internally, pointing to the sequence of data. 00138 * 00139 * @if maint 00140 * All the functions are op overloads. 00141 * @endif 00142 */ 00143 template<typename _Tp, typename _Ref, typename _Ptr> 00144 struct _List_iterator : public _List_iterator_base 00145 { 00146 typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator; 00147 typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; 00148 typedef _List_iterator<_Tp,_Ref,_Ptr> _Self; 00149 00150 typedef _Tp value_type; 00151 typedef _Ptr pointer; 00152 typedef _Ref reference; 00153 typedef _List_node<_Tp> _Node; 00154 00155 _List_iterator(_Node* __x) 00156 : _List_iterator_base(__x) 00157 { } 00158 00159 _List_iterator() 00160 : _List_iterator_base() 00161 { } 00162 00163 _List_iterator(const iterator& __x) 00164 : _List_iterator_base(__x._M_node) 00165 { } 00166 00167 reference 00168 operator*() const 00169 { return static_cast<_Node*>(_M_node)->_M_data; } 00170 // Must downcast from List_node_base to _List_node to get to _M_data. 00171 00172 pointer 00173 operator->() const 00174 { return &(operator*()); } 00175 00176 _Self& 00177 operator++() 00178 { 00179 this->_M_incr(); 00180 return *this; 00181 } 00182 00183 _Self 00184 operator++(int) 00185 { 00186 _Self __tmp = *this; 00187 this->_M_incr(); 00188 return __tmp; 00189 } 00190 00191 _Self& 00192 operator--() 00193 { 00194 this->_M_decr(); 00195 return *this; 00196 } 00197 00198 _Self 00199 operator--(int) 00200 { 00201 _Self __tmp = *this; 00202 this->_M_decr(); 00203 return __tmp; 00204 } 00205 }; 00206 00207 00208 /// @if maint Primary default version. @endif 00209 /** 00210 * @if maint 00211 * See bits/stl_deque.h's _Deque_alloc_base for an explanation. 00212 * @endif 00213 */ 00214 template<typename _Tp, typename _Allocator, bool _IsStatic> 00215 class _List_alloc_base 00216 { 00217 public: 00218 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type 00219 allocator_type; 00220 00221 allocator_type 00222 get_allocator() const { return _M_node_allocator; } 00223 00224 _List_alloc_base(const allocator_type& __a) 00225 : _M_node_allocator(__a) 00226 { } 00227 00228 protected: 00229 _List_node<_Tp>* 00230 _M_get_node() 00231 { return _M_node_allocator.allocate(1); } 00232 00233 void 00234 _M_put_node(_List_node<_Tp>* __p) 00235 { _M_node_allocator.deallocate(__p, 1); } 00236 00237 // NOTA BENE 00238 // The stored instance is not actually of "allocator_type"'s type. Instead 00239 // we rebind the type to Allocator<List_node<Tp>>, which according to 00240 // [20.1.5]/4 should probably be the same. List_node<Tp> is not the same 00241 // size as Tp (it's two pointers larger), and specializations on Tp may go 00242 // unused because List_node<Tp> is being bound instead. 00243 // 00244 // We put this to the test in get_allocator above; if the two types are 00245 // actually different, there had better be a conversion between them. 00246 // 00247 // None of the predefined allocators shipped with the library (as of 3.1) 00248 // use this instantiation anyhow; they're all instanceless. 00249 typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type 00250 _M_node_allocator; 00251 00252 _List_node<_Tp>* _M_node; 00253 }; 00254 00255 /// @if maint Specialization for instanceless allocators. @endif 00256 template<typename _Tp, typename _Allocator> 00257 class _List_alloc_base<_Tp, _Allocator, true> 00258 { 00259 public: 00260 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type 00261 allocator_type; 00262 00263 allocator_type 00264 get_allocator() const { return allocator_type(); } 00265 00266 _List_alloc_base(const allocator_type&) 00267 { } 00268 00269 protected: 00270 // See comment in primary template class about why this is safe for the 00271 // standard predefined classes. 00272 typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type 00273 _Alloc_type; 00274 00275 _List_node<_Tp>* 00276 _M_get_node() 00277 { return _Alloc_type::allocate(1); } 00278 00279 void 00280 _M_put_node(_List_node<_Tp>* __p) 00281 { _Alloc_type::deallocate(__p, 1); } 00282 00283 _List_node<_Tp>* _M_node; 00284 }; 00285 00286 00287 /** 00288 * @if maint 00289 * See bits/stl_deque.h's _Deque_base for an explanation. 00290 * @endif 00291 */ 00292 template <typename _Tp, typename _Alloc> 00293 class _List_base 00294 : public _List_alloc_base<_Tp, _Alloc, 00295 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 00296 { 00297 public: 00298 typedef _List_alloc_base<_Tp, _Alloc, 00299 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 00300 _Base; 00301 typedef typename _Base::allocator_type allocator_type; 00302 00303 _List_base(const allocator_type& __a) 00304 : _Base(__a) 00305 { 00306 _M_node = _M_get_node(); 00307 _M_node->_M_next = _M_node; 00308 _M_node->_M_prev = _M_node; 00309 } 00310 00311 // This is what actually destroys the list. 00312 ~_List_base() 00313 { 00314 __clear(); 00315 _M_put_node(_M_node); 00316 } 00317 00318 void 00319 __clear(); 00320 }; 00321 00322 00323 /** 00324 * @brief A standard container with linear time access to elements, and 00325 * fixed time insertion/deletion at any point in the sequence. 00326 * 00327 * @ingroup Containers 00328 * @ingroup Sequences 00329 * 00330 * Meets the requirements of a <a href="tables.html#65">container</a>, a 00331 * <a href="tables.html#66">reversible container</a>, and a 00332 * <a href="tables.html#67">sequence</a>, including the 00333 * <a href="tables.html#68">optional sequence requirements</a> with the 00334 * %exception of @c at and @c operator[]. 00335 * 00336 * This is a @e doubly @e linked %list. Traversal up and down the %list 00337 * requires linear time, but adding and removing elements (or @e nodes) is 00338 * done in constant time, regardless of where the change takes place. 00339 * Unlike std::vector and std::deque, random-access iterators are not 00340 * provided, so subscripting ( @c [] ) access is not allowed. For algorithms 00341 * which only need sequential access, this lack makes no difference. 00342 * 00343 * Also unlike the other standard containers, std::list provides specialized 00344 * algorithms %unique to linked lists, such as splicing, sorting, and 00345 * in-place reversal. 00346 * 00347 * @if maint 00348 * A couple points on memory allocation for list<Tp>: 00349 * 00350 * First, we never actually allocate a Tp, we allocate List_node<Tp>'s 00351 * and trust [20.1.5]/4 to DTRT. This is to ensure that after elements from 00352 * %list<X,Alloc1> are spliced into %list<X,Alloc2>, destroying the memory of 00353 * the second %list is a valid operation, i.e., Alloc1 giveth and Alloc2 00354 * taketh away. 00355 * 00356 * Second, a %list conceptually represented as 00357 * @code 00358 * A <---> B <---> C <---> D 00359 * @endcode 00360 * is actually circular; a link exists between A and D. The %list class 00361 * holds (as its only data member) a private list::iterator pointing to 00362 * @e D, not to @e A! To get to the head of the %list, we start at the tail 00363 * and move forward by one. When this member iterator's next/previous 00364 * pointers refer to itself, the %list is %empty. 00365 * @endif 00366 */ 00367 template<typename _Tp, typename _Alloc = allocator<_Tp> > 00368 class list : protected _List_base<_Tp, _Alloc> 00369 { 00370 // concept requirements 00371 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 00372 00373 typedef _List_base<_Tp, _Alloc> _Base; 00374 00375 public: 00376 typedef _Tp value_type; 00377 typedef value_type* pointer; 00378 typedef const value_type* const_pointer; 00379 typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator; 00380 typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; 00381 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00382 typedef std::reverse_iterator<iterator> reverse_iterator; 00383 typedef value_type& reference; 00384 typedef const value_type& const_reference; 00385 typedef size_t size_type; 00386 typedef ptrdiff_t difference_type; 00387 typedef typename _Base::allocator_type allocator_type; 00388 00389 protected: 00390 // Note that pointers-to-_Node's can be ctor-converted to iterator types. 00391 typedef _List_node<_Tp> _Node; 00392 00393 /** @if maint 00394 * One data member plus two memory-handling functions. If the _Alloc 00395 * type requires separate instances, then one of those will also be 00396 * included, accumulated from the topmost parent. 00397 * @endif 00398 */ 00399 using _Base::_M_node; 00400 using _Base::_M_put_node; 00401 using _Base::_M_get_node; 00402 00403 /** 00404 * @if maint 00405 * @param x An instance of user data. 00406 * 00407 * Allocates space for a new node and constructs a copy of @a x in it. 00408 * @endif 00409 */ 00410 _Node* 00411 _M_create_node(const value_type& __x) 00412 { 00413 _Node* __p = _M_get_node(); 00414 try { 00415 _Construct(&__p->_M_data, __x); 00416 } 00417 catch(...) 00418 { 00419 _M_put_node(__p); 00420 __throw_exception_again; 00421 } 00422 return __p; 00423 } 00424 00425 /** 00426 * @if maint 00427 * Allocates space for a new node and default-constructs a new instance 00428 * of @c value_type in it. 00429 * @endif 00430 */ 00431 _Node* 00432 _M_create_node() 00433 { 00434 _Node* __p = _M_get_node(); 00435 try { 00436 _Construct(&__p->_M_data); 00437 } 00438 catch(...) 00439 { 00440 _M_put_node(__p); 00441 __throw_exception_again; 00442 } 00443 return __p; 00444 } 00445 00446 public: 00447 // [23.2.2.1] construct/copy/destroy 00448 // (assign() and get_allocator() are also listed in this section) 00449 /** 00450 * @brief Default constructor creates no elements. 00451 */ 00452 explicit 00453 list(const allocator_type& __a = allocator_type()) 00454 : _Base(__a) { } 00455 00456 /** 00457 * @brief Create a %list with copies of an exemplar element. 00458 * @param n The number of elements to initially create. 00459 * @param value An element to copy. 00460 * 00461 * This constructor fills the %list with @a n copies of @a value. 00462 */ 00463 list(size_type __n, const value_type& __value, 00464 const allocator_type& __a = allocator_type()) 00465 : _Base(__a) 00466 { this->insert(begin(), __n, __value); } 00467 00468 /** 00469 * @brief Create a %list with default elements. 00470 * @param n The number of elements to initially create. 00471 * 00472 * This constructor fills the %list with @a n copies of a 00473 * default-constructed element. 00474 */ 00475 explicit 00476 list(size_type __n) 00477 : _Base(allocator_type()) 00478 { this->insert(begin(), __n, value_type()); } 00479 00480 /** 00481 * @brief %List copy constructor. 00482 * @param x A %list of identical element and allocator types. 00483 * 00484 * The newly-created %list uses a copy of the allocation object used 00485 * by @a x. 00486 */ 00487 list(const list& __x) 00488 : _Base(__x.get_allocator()) 00489 { this->insert(begin(), __x.begin(), __x.end()); } 00490 00491 /** 00492 * @brief Builds a %list from a range. 00493 * @param first An input iterator. 00494 * @param last An input iterator. 00495 * 00496 * Create a %list consisting of copies of the elements from [first,last). 00497 * This is linear in N (where N is distance(first,last)). 00498 * 00499 * @if maint 00500 * We don't need any dispatching tricks here, because insert does all of 00501 * that anyway. 00502 * @endif 00503 */ 00504 template<typename _InputIterator> 00505 list(_InputIterator __first, _InputIterator __last, 00506 const allocator_type& __a = allocator_type()) 00507 : _Base(__a) 00508 { this->insert(begin(), __first, __last); } 00509 00510 /** 00511 * The dtor only erases the elements, and note that if the elements 00512 * themselves are pointers, the pointed-to memory is not touched in any 00513 * way. Managing the pointer is the user's responsibilty. 00514 */ 00515 ~list() { } 00516 00517 /** 00518 * @brief %List assignment operator. 00519 * @param x A %list of identical element and allocator types. 00520 * 00521 * All the elements of @a x are copied, but unlike the copy constructor, 00522 * the allocator object is not copied. 00523 */ 00524 list& 00525 operator=(const list& __x); 00526 00527 /** 00528 * @brief Assigns a given value to a %list. 00529 * @param n Number of elements to be assigned. 00530 * @param val Value to be assigned. 00531 * 00532 * This function fills a %list with @a n copies of the given value. 00533 * Note that the assignment completely changes the %list and that the 00534 * resulting %list's size is the same as the number of elements assigned. 00535 * Old data may be lost. 00536 */ 00537 void 00538 assign(size_type __n, const value_type& __val) { _M_fill_assign(__n, __val); } 00539 00540 /** 00541 * @brief Assigns a range to a %list. 00542 * @param first An input iterator. 00543 * @param last An input iterator. 00544 * 00545 * This function fills a %list with copies of the elements in the 00546 * range [first,last). 00547 * 00548 * Note that the assignment completely changes the %list and that the 00549 * resulting %list's size is the same as the number of elements assigned. 00550 * Old data may be lost. 00551 */ 00552 template<typename _InputIterator> 00553 void 00554 assign(_InputIterator __first, _InputIterator __last) 00555 { 00556 // Check whether it's an integral type. If so, it's not an iterator. 00557 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 00558 _M_assign_dispatch(__first, __last, _Integral()); 00559 } 00560 00561 /// Get a copy of the memory allocation object. 00562 allocator_type 00563 get_allocator() const { return _Base::get_allocator(); } 00564 00565 // iterators 00566 /** 00567 * Returns a read/write iterator that points to the first element in the 00568 * %list. Iteration is done in ordinary element order. 00569 */ 00570 iterator 00571 begin() { return static_cast<_Node*>(_M_node->_M_next); } 00572 00573 /** 00574 * Returns a read-only (constant) iterator that points to the first element 00575 * in the %list. Iteration is done in ordinary element order. 00576 */ 00577 const_iterator 00578 begin() const { return static_cast<_Node*>(_M_node->_M_next); } 00579 00580 /** 00581 * Returns a read/write iterator that points one past the last element in 00582 * the %list. Iteration is done in ordinary element order. 00583 */ 00584 iterator 00585 end() { return _M_node; } 00586 00587 /** 00588 * Returns a read-only (constant) iterator that points one past the last 00589 * element in the %list. Iteration is done in ordinary element order. 00590 */ 00591 const_iterator 00592 end() const { return _M_node; } 00593 00594 /** 00595 * Returns a read/write reverse iterator that points to the last element in 00596 * the %list. Iteration is done in reverse element order. 00597 */ 00598 reverse_iterator 00599 rbegin() { return reverse_iterator(end()); } 00600 00601 /** 00602 * Returns a read-only (constant) reverse iterator that points to the last 00603 * element in the %list. Iteration is done in reverse element order. 00604 */ 00605 const_reverse_iterator 00606 rbegin() const { return const_reverse_iterator(end()); } 00607 00608 /** 00609 * Returns a read/write reverse iterator that points to one before the 00610 * first element in the %list. Iteration is done in reverse element 00611 * order. 00612 */ 00613 reverse_iterator 00614 rend() { return reverse_iterator(begin()); } 00615 00616 /** 00617 * Returns a read-only (constant) reverse iterator that points to one 00618 * before the first element in the %list. Iteration is done in reverse 00619 * element order. 00620 */ 00621 const_reverse_iterator 00622 rend() const 00623 { return const_reverse_iterator(begin()); } 00624 00625 // [23.2.2.2] capacity 00626 /** 00627 * Returns true if the %list is empty. (Thus begin() would equal end().) 00628 */ 00629 bool 00630 empty() const { return _M_node->_M_next == _M_node; } 00631 00632 /** Returns the number of elements in the %list. */ 00633 size_type 00634 size() const { return distance(begin(), end()); } 00635 00636 /** Returns the size() of the largest possible %list. */ 00637 size_type 00638 max_size() const { return size_type(-1); } 00639 00640 /** 00641 * @brief Resizes the %list to the specified number of elements. 00642 * @param new_size Number of elements the %list should contain. 00643 * @param x Data with which new elements should be populated. 00644 * 00645 * This function will %resize the %list to the specified number of 00646 * elements. If the number is smaller than the %list's current size the 00647 * %list is truncated, otherwise the %list is extended and new elements 00648 * are populated with given data. 00649 */ 00650 void 00651 resize(size_type __new_size, const value_type& __x); 00652 00653 /** 00654 * @brief Resizes the %list to the specified number of elements. 00655 * @param new_size Number of elements the %list should contain. 00656 * 00657 * This function will resize the %list to the specified number of 00658 * elements. If the number is smaller than the %list's current size the 00659 * %list is truncated, otherwise the %list is extended and new elements 00660 * are default-constructed. 00661 */ 00662 void 00663 resize(size_type __new_size) { this->resize(__new_size, value_type()); } 00664 00665 // element access 00666 /** 00667 * Returns a read/write reference to the data at the first element of the 00668 * %list. 00669 */ 00670 reference 00671 front() { return *begin(); } 00672 00673 /** 00674 * Returns a read-only (constant) reference to the data at the first 00675 * element of the %list. 00676 */ 00677 const_reference 00678 front() const { return *begin(); } 00679 00680 /** 00681 * Returns a read/write reference to the data at the last element of the 00682 * %list. 00683 */ 00684 reference 00685 back() { return *(--end()); } 00686 00687 /** 00688 * Returns a read-only (constant) reference to the data at the last 00689 * element of the %list. 00690 */ 00691 const_reference 00692 back() const { return *(--end()); } 00693 00694 // [23.2.2.3] modifiers 00695 /** 00696 * @brief Add data to the front of the %list. 00697 * @param x Data to be added. 00698 * 00699 * This is a typical stack operation. The function creates an element at 00700 * the front of the %list and assigns the given data to it. Due to the 00701 * nature of a %list this operation can be done in constant time, and 00702 * does not invalidate iterators and references. 00703 */ 00704 void 00705 push_front(const value_type& __x) { this->insert(begin(), __x); } 00706 00707 #ifdef _GLIBCPP_DEPRECATED 00708 /** 00709 * @brief Add data to the front of the %list. 00710 * 00711 * This is a typical stack operation. The function creates a 00712 * default-constructed element at the front of the %list. Due to the 00713 * nature of a %list this operation can be done in constant time. You 00714 * should consider using push_front(value_type()) instead. 00715 * 00716 * @note This was deprecated in 3.2 and will be removed in 3.4. You must 00717 * define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see 00718 * c++config.h. 00719 */ 00720 void 00721 push_front() { this->insert(begin(), value_type()); } 00722 #endif 00723 00724 /** 00725 * @brief Removes first element. 00726 * 00727 * This is a typical stack operation. It shrinks the %list by one. 00728 * Due to the nature of a %list this operation can be done in constant 00729 * time, and only invalidates iterators/references to the element being 00730 * removed. 00731 * 00732 * Note that no data is returned, and if the first element's data is 00733 * needed, it should be retrieved before pop_front() is called. 00734 */ 00735 void 00736 pop_front() { this->erase(begin()); } 00737 00738 /** 00739 * @brief Add data to the end of the %list. 00740 * @param x Data to be added. 00741 * 00742 * This is a typical stack operation. The function creates an element at 00743 * the end of the %list and assigns the given data to it. Due to the 00744 * nature of a %list this operation can be done in constant time, and 00745 * does not invalidate iterators and references. 00746 */ 00747 void 00748 push_back(const value_type& __x) { this->insert(end(), __x); } 00749 00750 #ifdef _GLIBCPP_DEPRECATED 00751 /** 00752 * @brief Add data to the end of the %list. 00753 * 00754 * This is a typical stack operation. The function creates a 00755 * default-constructed element at the end of the %list. Due to the nature 00756 * of a %list this operation can be done in constant time. You should 00757 * consider using push_back(value_type()) instead. 00758 * 00759 * @note This was deprecated in 3.2 and will be removed in 3.4. You must 00760 * define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see 00761 * c++config.h. 00762 */ 00763 void 00764 push_back() { this->insert(end(), value_type()); } 00765 #endif 00766 00767 /** 00768 * @brief Removes last element. 00769 * 00770 * This is a typical stack operation. It shrinks the %list by one. 00771 * Due to the nature of a %list this operation can be done in constant 00772 * time, and only invalidates iterators/references to the element being 00773 * removed. 00774 * 00775 * Note that no data is returned, and if the last element's data is 00776 * needed, it should be retrieved before pop_back() is called. 00777 */ 00778 void 00779 pop_back() 00780 { 00781 iterator __tmp = end(); 00782 this->erase(--__tmp); 00783 } 00784 00785 /** 00786 * @brief Inserts given value into %list before specified iterator. 00787 * @param position An iterator into the %list. 00788 * @param x Data to be inserted. 00789 * @return An iterator that points to the inserted data. 00790 * 00791 * This function will insert a copy of the given value before the specified 00792 * location. 00793 * Due to the nature of a %list this operation can be done in constant 00794 * time, and does not invalidate iterators and references. 00795 */ 00796 iterator 00797 insert(iterator __position, const value_type& __x); 00798 00799 #ifdef _GLIBCPP_DEPRECATED 00800 /** 00801 * @brief Inserts an element into the %list. 00802 * @param position An iterator into the %list. 00803 * @return An iterator that points to the inserted element. 00804 * 00805 * This function will insert a default-constructed element before the 00806 * specified location. You should consider using 00807 * insert(position,value_type()) instead. 00808 * Due to the nature of a %list this operation can be done in constant 00809 * time, and does not invalidate iterators and references. 00810 * 00811 * @note This was deprecated in 3.2 and will be removed in 3.4. You must 00812 * define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see 00813 * c++config.h. 00814 */ 00815 iterator 00816 insert(iterator __position) { return insert(__position, value_type()); } 00817 #endif 00818 00819 /** 00820 * @brief Inserts a number of copies of given data into the %list. 00821 * @param position An iterator into the %list. 00822 * @param n Number of elements to be inserted. 00823 * @param x Data to be inserted. 00824 * 00825 * This function will insert a specified number of copies of the given data 00826 * before the location specified by @a position. 00827 * 00828 * Due to the nature of a %list this operation can be done in constant 00829 * time, and does not invalidate iterators and references. 00830 */ 00831 void 00832 insert(iterator __pos, size_type __n, const value_type& __x) 00833 { _M_fill_insert(__pos, __n, __x); } 00834 00835 /** 00836 * @brief Inserts a range into the %list. 00837 * @param pos An iterator into the %list. 00838 * @param first An input iterator. 00839 * @param last An input iterator. 00840 * 00841 * This function will insert copies of the data in the range [first,last) 00842 * into the %list before the location specified by @a pos. 00843 * 00844 * Due to the nature of a %list this operation can be done in constant 00845 * time, and does not invalidate iterators and references. 00846 */ 00847 template<typename _InputIterator> 00848 void 00849 insert(iterator __pos, _InputIterator __first, _InputIterator __last) 00850 { 00851 // Check whether it's an integral type. If so, it's not an iterator. 00852 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 00853 _M_insert_dispatch(__pos, __first, __last, _Integral()); 00854 } 00855 00856 /** 00857 * @brief Remove element at given position. 00858 * @param position Iterator pointing to element to be erased. 00859 * @return An iterator pointing to the next element (or end()). 00860 * 00861 * This function will erase the element at the given position and thus 00862 * shorten the %list by one. 00863 * 00864 * Due to the nature of a %list this operation can be done in constant 00865 * time, and only invalidates iterators/references to the element being 00866 * removed. 00867 * The user is also cautioned that 00868 * this function only erases the element, and that if the element is itself 00869 * a pointer, the pointed-to memory is not touched in any way. Managing 00870 * the pointer is the user's responsibilty. 00871 */ 00872 iterator 00873 erase(iterator __position); 00874 00875 /** 00876 * @brief Remove a range of elements. 00877 * @param first Iterator pointing to the first element to be erased. 00878 * @param last Iterator pointing to one past the last element to be 00879 * erased. 00880 * @return An iterator pointing to the element pointed to by @a last 00881 * prior to erasing (or end()). 00882 * 00883 * This function will erase the elements in the range [first,last) and 00884 * shorten the %list accordingly. 00885 * 00886 * Due to the nature of a %list this operation can be done in constant 00887 * time, and only invalidates iterators/references to the element being 00888 * removed. 00889 * The user is also cautioned that 00890 * this function only erases the elements, and that if the elements 00891 * themselves are pointers, the pointed-to memory is not touched in any 00892 * way. Managing the pointer is the user's responsibilty. 00893 */ 00894 iterator 00895 erase(iterator __first, iterator __last) 00896 { 00897 while (__first != __last) 00898 erase(__first++); 00899 return __last; 00900 } 00901 00902 /** 00903 * @brief Swaps data with another %list. 00904 * @param x A %list of the same element and allocator types. 00905 * 00906 * This exchanges the elements between two lists in constant time. 00907 * (It is only swapping a single pointer, so it should be quite fast.) 00908 * Note that the global std::swap() function is specialized such that 00909 * std::swap(l1,l2) will feed to this function. 00910 */ 00911 void 00912 swap(list& __x) { std::swap(_M_node, __x._M_node); } 00913 00914 /** 00915 * Erases all the elements. Note that this function only erases the 00916 * elements, and that if the elements themselves are pointers, the 00917 * pointed-to memory is not touched in any way. Managing the pointer is 00918 * the user's responsibilty. 00919 */ 00920 void 00921 clear() { _Base::__clear(); } 00922 00923 // [23.2.2.4] list operations 00924 /** 00925 * @doctodo 00926 */ 00927 void 00928 splice(iterator __position, list& __x) 00929 { 00930 if (!__x.empty()) 00931 this->_M_transfer(__position, __x.begin(), __x.end()); 00932 } 00933 00934 /** 00935 * @doctodo 00936 */ 00937 void 00938 splice(iterator __position, list&, iterator __i) 00939 { 00940 iterator __j = __i; 00941 ++__j; 00942 if (__position == __i || __position == __j) return; 00943 this->_M_transfer(__position, __i, __j); 00944 } 00945 00946 /** 00947 * @doctodo 00948 */ 00949 void 00950 splice(iterator __position, list&, iterator __first, iterator __last) 00951 { 00952 if (__first != __last) 00953 this->_M_transfer(__position, __first, __last); 00954 } 00955 00956 /** 00957 * @doctodo 00958 */ 00959 void 00960 remove(const _Tp& __value); 00961 00962 /** 00963 * @doctodo 00964 */ 00965 template<typename _Predicate> 00966 void 00967 remove_if(_Predicate); 00968 00969 /** 00970 * @doctodo 00971 */ 00972 void 00973 unique(); 00974 00975 /** 00976 * @doctodo 00977 */ 00978 template<typename _BinaryPredicate> 00979 void 00980 unique(_BinaryPredicate); 00981 00982 /** 00983 * @doctodo 00984 */ 00985 void 00986 merge(list& __x); 00987 00988 /** 00989 * @doctodo 00990 */ 00991 template<typename _StrictWeakOrdering> 00992 void 00993 merge(list&, _StrictWeakOrdering); 00994 00995 /** 00996 * @doctodo 00997 */ 00998 void 00999 reverse() { __List_base_reverse(this->_M_node); } 01000 01001 /** 01002 * @doctodo 01003 */ 01004 void 01005 sort(); 01006 01007 /** 01008 * @doctodo 01009 */ 01010 template<typename _StrictWeakOrdering> 01011 void 01012 sort(_StrictWeakOrdering); 01013 01014 protected: 01015 // Internal assign functions follow. 01016 01017 // called by the range assign to implement [23.1.1]/9 01018 template<typename _Integer> 01019 void 01020 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 01021 { 01022 _M_fill_assign(static_cast<size_type>(__n), 01023 static_cast<value_type>(__val)); 01024 } 01025 01026 // called by the range assign to implement [23.1.1]/9 01027 template<typename _InputIter> 01028 void 01029 _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type); 01030 01031 // Called by assign(n,t), and the range assign when it turns out to be the 01032 // same thing. 01033 void 01034 _M_fill_assign(size_type __n, const value_type& __val); 01035 01036 01037 // Internal insert functions follow. 01038 01039 // called by the range insert to implement [23.1.1]/9 01040 template<typename _Integer> 01041 void 01042 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 01043 __true_type) 01044 { 01045 _M_fill_insert(__pos, static_cast<size_type>(__n), 01046 static_cast<value_type>(__x)); 01047 } 01048 01049 // called by the range insert to implement [23.1.1]/9 01050 template<typename _InputIterator> 01051 void 01052 _M_insert_dispatch(iterator __pos, 01053 _InputIterator __first, _InputIterator __last, 01054 __false_type) 01055 { 01056 for ( ; __first != __last; ++__first) 01057 insert(__pos, *__first); 01058 } 01059 01060 // Called by insert(p,n,x), and the range insert when it turns out to be 01061 // the same thing. 01062 void 01063 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) 01064 { 01065 for ( ; __n > 0; --__n) 01066 insert(__pos, __x); 01067 } 01068 01069 01070 // Moves the elements from [first,last) before position. 01071 void 01072 _M_transfer(iterator __position, iterator __first, iterator __last) 01073 { 01074 if (__position != __last) { 01075 // Remove [first, last) from its old position. 01076 __last._M_node->_M_prev->_M_next = __position._M_node; 01077 __first._M_node->_M_prev->_M_next = __last._M_node; 01078 __position._M_node->_M_prev->_M_next = __first._M_node; 01079 01080 // Splice [first, last) into its new position. 01081 _List_node_base* __tmp = __position._M_node->_M_prev; 01082 __position._M_node->_M_prev = __last._M_node->_M_prev; 01083 __last._M_node->_M_prev = __first._M_node->_M_prev; 01084 __first._M_node->_M_prev = __tmp; 01085 } 01086 } 01087 }; 01088 01089 01090 /** 01091 * @brief List equality comparison. 01092 * @param x A %list. 01093 * @param y A %list of the same type as @a x. 01094 * @return True iff the size and elements of the lists are equal. 01095 * 01096 * This is an equivalence relation. It is linear in the size of the 01097 * lists. Lists are considered equivalent if their sizes are equal, 01098 * and if corresponding elements compare equal. 01099 */ 01100 template<typename _Tp, typename _Alloc> 01101 inline bool 01102 operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) 01103 { 01104 typedef typename list<_Tp,_Alloc>::const_iterator const_iterator; 01105 const_iterator __end1 = __x.end(); 01106 const_iterator __end2 = __y.end(); 01107 01108 const_iterator __i1 = __x.begin(); 01109 const_iterator __i2 = __y.begin(); 01110 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) { 01111 ++__i1; 01112 ++__i2; 01113 } 01114 return __i1 == __end1 && __i2 == __end2; 01115 } 01116 01117 /** 01118 * @brief List ordering relation. 01119 * @param x A %list. 01120 * @param y A %list of the same type as @a x. 01121 * @return True iff @a x is lexographically less than @a y. 01122 * 01123 * This is a total ordering relation. It is linear in the size of the 01124 * lists. The elements must be comparable with @c <. 01125 * 01126 * See std::lexographical_compare() for how the determination is made. 01127 */ 01128 template<typename _Tp, typename _Alloc> 01129 inline bool 01130 operator<(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) 01131 { 01132 return lexicographical_compare(__x.begin(), __x.end(), 01133 __y.begin(), __y.end()); 01134 } 01135 01136 /// Based on operator== 01137 template<typename _Tp, typename _Alloc> 01138 inline bool 01139 operator!=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) 01140 { return !(__x == __y); } 01141 01142 /// Based on operator< 01143 template<typename _Tp, typename _Alloc> 01144 inline bool 01145 operator>(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) 01146 { return __y < __x; } 01147 01148 /// Based on operator< 01149 template<typename _Tp, typename _Alloc> 01150 inline bool 01151 operator<=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) 01152 { return !(__y < __x); } 01153 01154 /// Based on operator< 01155 template<typename _Tp, typename _Alloc> 01156 inline bool 01157 operator>=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) 01158 { return !(__x < __y); } 01159 01160 /// See std::list::swap(). 01161 template<typename _Tp, typename _Alloc> 01162 inline void 01163 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) 01164 { __x.swap(__y); } 01165 } // namespace std 01166 01167 #endif /* __GLIBCPP_INTERNAL_LIST_H */