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