10b57cec5SDimitry Andric// -*- C++ -*- 2349cc55cSDimitry Andric//===----------------------------------------------------------------------===// 30b57cec5SDimitry Andric// 40b57cec5SDimitry Andric// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 50b57cec5SDimitry Andric// See https://llvm.org/LICENSE.txt for license information. 60b57cec5SDimitry Andric// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 70b57cec5SDimitry Andric// 80b57cec5SDimitry Andric//===----------------------------------------------------------------------===// 90b57cec5SDimitry Andric 100b57cec5SDimitry Andric#ifndef _LIBCPP_LIST 110b57cec5SDimitry Andric#define _LIBCPP_LIST 120b57cec5SDimitry Andric 130b57cec5SDimitry Andric/* 140b57cec5SDimitry Andric list synopsis 150b57cec5SDimitry Andric 160b57cec5SDimitry Andricnamespace std 170b57cec5SDimitry Andric{ 180b57cec5SDimitry Andric 190b57cec5SDimitry Andrictemplate <class T, class Alloc = allocator<T> > 200b57cec5SDimitry Andricclass list 210b57cec5SDimitry Andric{ 220b57cec5SDimitry Andricpublic: 230b57cec5SDimitry Andric 240b57cec5SDimitry Andric // types: 250b57cec5SDimitry Andric typedef T value_type; 260b57cec5SDimitry Andric typedef Alloc allocator_type; 270b57cec5SDimitry Andric typedef typename allocator_type::reference reference; 280b57cec5SDimitry Andric typedef typename allocator_type::const_reference const_reference; 290b57cec5SDimitry Andric typedef typename allocator_type::pointer pointer; 300b57cec5SDimitry Andric typedef typename allocator_type::const_pointer const_pointer; 310b57cec5SDimitry Andric typedef implementation-defined iterator; 320b57cec5SDimitry Andric typedef implementation-defined const_iterator; 330b57cec5SDimitry Andric typedef implementation-defined size_type; 340b57cec5SDimitry Andric typedef implementation-defined difference_type; 350b57cec5SDimitry Andric typedef reverse_iterator<iterator> reverse_iterator; 360b57cec5SDimitry Andric typedef reverse_iterator<const_iterator> const_reverse_iterator; 370b57cec5SDimitry Andric 380b57cec5SDimitry Andric list() 390b57cec5SDimitry Andric noexcept(is_nothrow_default_constructible<allocator_type>::value); 400b57cec5SDimitry Andric explicit list(const allocator_type& a); 410b57cec5SDimitry Andric explicit list(size_type n); 420b57cec5SDimitry Andric explicit list(size_type n, const allocator_type& a); // C++14 430b57cec5SDimitry Andric list(size_type n, const value_type& value); 440b57cec5SDimitry Andric list(size_type n, const value_type& value, const allocator_type& a); 450b57cec5SDimitry Andric template <class Iter> 460b57cec5SDimitry Andric list(Iter first, Iter last); 470b57cec5SDimitry Andric template <class Iter> 480b57cec5SDimitry Andric list(Iter first, Iter last, const allocator_type& a); 4906c3fb27SDimitry Andric template<container-compatible-range<T> R> 5006c3fb27SDimitry Andric list(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23 510b57cec5SDimitry Andric list(const list& x); 520b57cec5SDimitry Andric list(const list&, const allocator_type& a); 530b57cec5SDimitry Andric list(list&& x) 540b57cec5SDimitry Andric noexcept(is_nothrow_move_constructible<allocator_type>::value); 550b57cec5SDimitry Andric list(list&&, const allocator_type& a); 560b57cec5SDimitry Andric list(initializer_list<value_type>); 570b57cec5SDimitry Andric list(initializer_list<value_type>, const allocator_type& a); 580b57cec5SDimitry Andric 590b57cec5SDimitry Andric ~list(); 600b57cec5SDimitry Andric 610b57cec5SDimitry Andric list& operator=(const list& x); 620b57cec5SDimitry Andric list& operator=(list&& x) 630b57cec5SDimitry Andric noexcept( 640b57cec5SDimitry Andric allocator_type::propagate_on_container_move_assignment::value && 650b57cec5SDimitry Andric is_nothrow_move_assignable<allocator_type>::value); 660b57cec5SDimitry Andric list& operator=(initializer_list<value_type>); 670b57cec5SDimitry Andric template <class Iter> 680b57cec5SDimitry Andric void assign(Iter first, Iter last); 6906c3fb27SDimitry Andric template<container-compatible-range<T> R> 7006c3fb27SDimitry Andric void assign_range(R&& rg); // C++23 710b57cec5SDimitry Andric void assign(size_type n, const value_type& t); 720b57cec5SDimitry Andric void assign(initializer_list<value_type>); 730b57cec5SDimitry Andric 740b57cec5SDimitry Andric allocator_type get_allocator() const noexcept; 750b57cec5SDimitry Andric 760b57cec5SDimitry Andric iterator begin() noexcept; 770b57cec5SDimitry Andric const_iterator begin() const noexcept; 780b57cec5SDimitry Andric iterator end() noexcept; 790b57cec5SDimitry Andric const_iterator end() const noexcept; 800b57cec5SDimitry Andric reverse_iterator rbegin() noexcept; 810b57cec5SDimitry Andric const_reverse_iterator rbegin() const noexcept; 820b57cec5SDimitry Andric reverse_iterator rend() noexcept; 830b57cec5SDimitry Andric const_reverse_iterator rend() const noexcept; 840b57cec5SDimitry Andric const_iterator cbegin() const noexcept; 850b57cec5SDimitry Andric const_iterator cend() const noexcept; 860b57cec5SDimitry Andric const_reverse_iterator crbegin() const noexcept; 870b57cec5SDimitry Andric const_reverse_iterator crend() const noexcept; 880b57cec5SDimitry Andric 890b57cec5SDimitry Andric reference front(); 900b57cec5SDimitry Andric const_reference front() const; 910b57cec5SDimitry Andric reference back(); 920b57cec5SDimitry Andric const_reference back() const; 930b57cec5SDimitry Andric 940b57cec5SDimitry Andric bool empty() const noexcept; 950b57cec5SDimitry Andric size_type size() const noexcept; 960b57cec5SDimitry Andric size_type max_size() const noexcept; 970b57cec5SDimitry Andric 980b57cec5SDimitry Andric template <class... Args> 990b57cec5SDimitry Andric reference emplace_front(Args&&... args); // reference in C++17 1000b57cec5SDimitry Andric void pop_front(); 1010b57cec5SDimitry Andric template <class... Args> 1020b57cec5SDimitry Andric reference emplace_back(Args&&... args); // reference in C++17 1030b57cec5SDimitry Andric void pop_back(); 1040b57cec5SDimitry Andric void push_front(const value_type& x); 1050b57cec5SDimitry Andric void push_front(value_type&& x); 10606c3fb27SDimitry Andric template<container-compatible-range<T> R> 10706c3fb27SDimitry Andric void prepend_range(R&& rg); // C++23 1080b57cec5SDimitry Andric void push_back(const value_type& x); 1090b57cec5SDimitry Andric void push_back(value_type&& x); 11006c3fb27SDimitry Andric template<container-compatible-range<T> R> 11106c3fb27SDimitry Andric void append_range(R&& rg); // C++23 1120b57cec5SDimitry Andric template <class... Args> 1130b57cec5SDimitry Andric iterator emplace(const_iterator position, Args&&... args); 1140b57cec5SDimitry Andric iterator insert(const_iterator position, const value_type& x); 1150b57cec5SDimitry Andric iterator insert(const_iterator position, value_type&& x); 1160b57cec5SDimitry Andric iterator insert(const_iterator position, size_type n, const value_type& x); 1170b57cec5SDimitry Andric template <class Iter> 1180b57cec5SDimitry Andric iterator insert(const_iterator position, Iter first, Iter last); 11906c3fb27SDimitry Andric template<container-compatible-range<T> R> 12006c3fb27SDimitry Andric iterator insert_range(const_iterator position, R&& rg); // C++23 1210b57cec5SDimitry Andric iterator insert(const_iterator position, initializer_list<value_type> il); 1220b57cec5SDimitry Andric 1230b57cec5SDimitry Andric iterator erase(const_iterator position); 1240b57cec5SDimitry Andric iterator erase(const_iterator position, const_iterator last); 1250b57cec5SDimitry Andric 1260b57cec5SDimitry Andric void resize(size_type sz); 1270b57cec5SDimitry Andric void resize(size_type sz, const value_type& c); 1280b57cec5SDimitry Andric 1290b57cec5SDimitry Andric void swap(list&) 1300b57cec5SDimitry Andric noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17 1310b57cec5SDimitry Andric void clear() noexcept; 1320b57cec5SDimitry Andric 1330b57cec5SDimitry Andric void splice(const_iterator position, list& x); 1340b57cec5SDimitry Andric void splice(const_iterator position, list&& x); 1350b57cec5SDimitry Andric void splice(const_iterator position, list& x, const_iterator i); 1360b57cec5SDimitry Andric void splice(const_iterator position, list&& x, const_iterator i); 1370b57cec5SDimitry Andric void splice(const_iterator position, list& x, const_iterator first, 1380b57cec5SDimitry Andric const_iterator last); 1390b57cec5SDimitry Andric void splice(const_iterator position, list&& x, const_iterator first, 1400b57cec5SDimitry Andric const_iterator last); 1410b57cec5SDimitry Andric 1420b57cec5SDimitry Andric size_type remove(const value_type& value); // void before C++20 1430b57cec5SDimitry Andric template <class Pred> 1440b57cec5SDimitry Andric size_type remove_if(Pred pred); // void before C++20 1450b57cec5SDimitry Andric size_type unique(); // void before C++20 1460b57cec5SDimitry Andric template <class BinaryPredicate> 1470b57cec5SDimitry Andric size_type unique(BinaryPredicate binary_pred); // void before C++20 1480b57cec5SDimitry Andric void merge(list& x); 1490b57cec5SDimitry Andric void merge(list&& x); 1500b57cec5SDimitry Andric template <class Compare> 1510b57cec5SDimitry Andric void merge(list& x, Compare comp); 1520b57cec5SDimitry Andric template <class Compare> 1530b57cec5SDimitry Andric void merge(list&& x, Compare comp); 1540b57cec5SDimitry Andric void sort(); 1550b57cec5SDimitry Andric template <class Compare> 1560b57cec5SDimitry Andric void sort(Compare comp); 1570b57cec5SDimitry Andric void reverse() noexcept; 1580b57cec5SDimitry Andric}; 1590b57cec5SDimitry Andric 1600b57cec5SDimitry Andric 1610b57cec5SDimitry Andrictemplate <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 1620b57cec5SDimitry Andric list(InputIterator, InputIterator, Allocator = Allocator()) 1630b57cec5SDimitry Andric -> list<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17 1640b57cec5SDimitry Andric 16506c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>> 16606c3fb27SDimitry Andric list(from_range_t, R&&, Allocator = Allocator()) 16706c3fb27SDimitry Andric -> list<ranges::range_value_t<R>, Allocator>; // C++23 16806c3fb27SDimitry Andric 1690b57cec5SDimitry Andrictemplate <class T, class Alloc> 1700b57cec5SDimitry Andric bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y); 1710b57cec5SDimitry Andrictemplate <class T, class Alloc> 17206c3fb27SDimitry Andric bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y); // removed in C++20 1730b57cec5SDimitry Andrictemplate <class T, class Alloc> 17406c3fb27SDimitry Andric bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y); // removed in C++20 1750b57cec5SDimitry Andrictemplate <class T, class Alloc> 17606c3fb27SDimitry Andric bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y); // removed in C++20 1770b57cec5SDimitry Andrictemplate <class T, class Alloc> 17806c3fb27SDimitry Andric bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y); // removed in C++20 1790b57cec5SDimitry Andrictemplate <class T, class Alloc> 18006c3fb27SDimitry Andric bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y); // removed in C++20 18106c3fb27SDimitry Andrictemplate<class T, class Allocator> 18206c3fb27SDimitry Andric synth-three-way-result<T> operator<=>(const list<T, Allocator>& x, 18306c3fb27SDimitry Andric const list<T, Allocator>& y); // since C++20 1840b57cec5SDimitry Andric 1850b57cec5SDimitry Andrictemplate <class T, class Alloc> 1860b57cec5SDimitry Andric void swap(list<T,Alloc>& x, list<T,Alloc>& y) 1870b57cec5SDimitry Andric noexcept(noexcept(x.swap(y))); 1880b57cec5SDimitry Andric 1890b57cec5SDimitry Andrictemplate <class T, class Allocator, class U> 1905ffd83dbSDimitry Andric typename list<T, Allocator>::size_type 19106c3fb27SDimitry Andric erase(list<T, Allocator>& c, const U& value); // since C++20 1920b57cec5SDimitry Andrictemplate <class T, class Allocator, class Predicate> 1935ffd83dbSDimitry Andric typename list<T, Allocator>::size_type 19406c3fb27SDimitry Andric erase_if(list<T, Allocator>& c, Predicate pred); // since C++20 1950b57cec5SDimitry Andric 1960b57cec5SDimitry Andric} // std 1970b57cec5SDimitry Andric 1980b57cec5SDimitry Andric*/ 1990b57cec5SDimitry Andric 20081ad6265SDimitry Andric#include <__algorithm/comp.h> 20181ad6265SDimitry Andric#include <__algorithm/equal.h> 20281ad6265SDimitry Andric#include <__algorithm/lexicographical_compare.h> 20306c3fb27SDimitry Andric#include <__algorithm/lexicographical_compare_three_way.h> 20481ad6265SDimitry Andric#include <__algorithm/min.h> 20581ad6265SDimitry Andric#include <__assert> // all public C++ headers provide the assertion handler 20606c3fb27SDimitry Andric#include <__availability> 2070b57cec5SDimitry Andric#include <__config> 20881ad6265SDimitry Andric#include <__format/enable_insertable.h> 20981ad6265SDimitry Andric#include <__iterator/distance.h> 21081ad6265SDimitry Andric#include <__iterator/iterator_traits.h> 21181ad6265SDimitry Andric#include <__iterator/move_iterator.h> 21281ad6265SDimitry Andric#include <__iterator/next.h> 21381ad6265SDimitry Andric#include <__iterator/prev.h> 21481ad6265SDimitry Andric#include <__iterator/reverse_iterator.h> 215bdd1243dSDimitry Andric#include <__memory/addressof.h> 2165f757f3fSDimitry Andric#include <__memory/allocation_guard.h> 217bdd1243dSDimitry Andric#include <__memory/allocator.h> 218bdd1243dSDimitry Andric#include <__memory/allocator_traits.h> 219bdd1243dSDimitry Andric#include <__memory/compressed_pair.h> 2205f757f3fSDimitry Andric#include <__memory/construct_at.h> 221bdd1243dSDimitry Andric#include <__memory/pointer_traits.h> 222972a253aSDimitry Andric#include <__memory/swap_allocator.h> 223bdd1243dSDimitry Andric#include <__memory_resource/polymorphic_allocator.h> 22406c3fb27SDimitry Andric#include <__ranges/access.h> 22506c3fb27SDimitry Andric#include <__ranges/concepts.h> 22606c3fb27SDimitry Andric#include <__ranges/container_compatible_range.h> 22706c3fb27SDimitry Andric#include <__ranges/from_range.h> 22806c3fb27SDimitry Andric#include <__type_traits/conditional.h> 229bdd1243dSDimitry Andric#include <__type_traits/is_allocator.h> 23006c3fb27SDimitry Andric#include <__type_traits/is_nothrow_default_constructible.h> 23106c3fb27SDimitry Andric#include <__type_traits/is_nothrow_move_assignable.h> 23206c3fb27SDimitry Andric#include <__type_traits/is_nothrow_move_constructible.h> 23306c3fb27SDimitry Andric#include <__type_traits/is_pointer.h> 23406c3fb27SDimitry Andric#include <__type_traits/is_same.h> 23506c3fb27SDimitry Andric#include <__type_traits/type_identity.h> 236fe6060f1SDimitry Andric#include <__utility/forward.h> 23781ad6265SDimitry Andric#include <__utility/move.h> 23881ad6265SDimitry Andric#include <__utility/swap.h> 239bdd1243dSDimitry Andric#include <cstring> 240fe6060f1SDimitry Andric#include <limits> 2415f757f3fSDimitry Andric#include <new> // __launder 2420b57cec5SDimitry Andric#include <version> 2430b57cec5SDimitry Andric 24481ad6265SDimitry Andric// standard-mandated includes 24581ad6265SDimitry Andric 24681ad6265SDimitry Andric// [iterator.range] 24781ad6265SDimitry Andric#include <__iterator/access.h> 24881ad6265SDimitry Andric#include <__iterator/data.h> 24981ad6265SDimitry Andric#include <__iterator/empty.h> 25081ad6265SDimitry Andric#include <__iterator/reverse_access.h> 25181ad6265SDimitry Andric#include <__iterator/size.h> 25281ad6265SDimitry Andric 25381ad6265SDimitry Andric// [list.syn] 25481ad6265SDimitry Andric#include <compare> 25581ad6265SDimitry Andric#include <initializer_list> 25681ad6265SDimitry Andric 2570b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 2580b57cec5SDimitry Andric# pragma GCC system_header 2590b57cec5SDimitry Andric#endif 2600b57cec5SDimitry Andric 2610b57cec5SDimitry Andric_LIBCPP_PUSH_MACROS 2620b57cec5SDimitry Andric#include <__undef_macros> 2630b57cec5SDimitry Andric 2640b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 2650b57cec5SDimitry Andric 266cb14a3feSDimitry Andrictemplate <class _Tp, class _VoidPtr> 267cb14a3feSDimitry Andricstruct __list_node; 268cb14a3feSDimitry Andrictemplate <class _Tp, class _VoidPtr> 269cb14a3feSDimitry Andricstruct __list_node_base; 2700b57cec5SDimitry Andric 2710b57cec5SDimitry Andrictemplate <class _Tp, class _VoidPtr> 2720b57cec5SDimitry Andricstruct __list_node_pointer_traits { 273cb14a3feSDimitry Andric typedef __rebind_pointer_t<_VoidPtr, __list_node<_Tp, _VoidPtr> > __node_pointer; 274cb14a3feSDimitry Andric typedef __rebind_pointer_t<_VoidPtr, __list_node_base<_Tp, _VoidPtr> > __base_pointer; 2750b57cec5SDimitry Andric 2760b57cec5SDimitry Andric#if defined(_LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB) 2770b57cec5SDimitry Andric typedef __base_pointer __link_pointer; 2780b57cec5SDimitry Andric#else 279bdd1243dSDimitry Andric typedef __conditional_t<is_pointer<_VoidPtr>::value, __base_pointer, __node_pointer> __link_pointer; 2800b57cec5SDimitry Andric#endif 2810b57cec5SDimitry Andric 282bdd1243dSDimitry Andric typedef __conditional_t<is_same<__link_pointer, __node_pointer>::value, __base_pointer, __node_pointer> 283bdd1243dSDimitry Andric __non_link_pointer; 2840b57cec5SDimitry Andric 285cb14a3feSDimitry Andric static _LIBCPP_HIDE_FROM_ABI __link_pointer __unsafe_link_pointer_cast(__link_pointer __p) { return __p; } 2860b57cec5SDimitry Andric 287cb14a3feSDimitry Andric static _LIBCPP_HIDE_FROM_ABI __link_pointer __unsafe_link_pointer_cast(__non_link_pointer __p) { 2880b57cec5SDimitry Andric return static_cast<__link_pointer>(static_cast<_VoidPtr>(__p)); 2890b57cec5SDimitry Andric } 2900b57cec5SDimitry Andric}; 2910b57cec5SDimitry Andric 2920b57cec5SDimitry Andrictemplate <class _Tp, class _VoidPtr> 293cb14a3feSDimitry Andricstruct __list_node_base { 2940b57cec5SDimitry Andric typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits; 2950b57cec5SDimitry Andric typedef typename _NodeTraits::__node_pointer __node_pointer; 2960b57cec5SDimitry Andric typedef typename _NodeTraits::__base_pointer __base_pointer; 2970b57cec5SDimitry Andric typedef typename _NodeTraits::__link_pointer __link_pointer; 2980b57cec5SDimitry Andric 2990b57cec5SDimitry Andric __link_pointer __prev_; 3000b57cec5SDimitry Andric __link_pointer __next_; 3010b57cec5SDimitry Andric 302cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_node_base() 303cb14a3feSDimitry Andric : __prev_(_NodeTraits::__unsafe_link_pointer_cast(__self())), 3040b57cec5SDimitry Andric __next_(_NodeTraits::__unsafe_link_pointer_cast(__self())) {} 3050b57cec5SDimitry Andric 3065f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit __list_node_base(__link_pointer __prev, __link_pointer __next) 3075f757f3fSDimitry Andric : __prev_(__prev), __next_(__next) {} 3085f757f3fSDimitry Andric 309cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __base_pointer __self() { return pointer_traits<__base_pointer>::pointer_to(*this); } 3100b57cec5SDimitry Andric 311cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __node_pointer __as_node() { return static_cast<__node_pointer>(__self()); } 3120b57cec5SDimitry Andric}; 3130b57cec5SDimitry Andric 3140b57cec5SDimitry Andrictemplate <class _Tp, class _VoidPtr> 315cb14a3feSDimitry Andricstruct __list_node : public __list_node_base<_Tp, _VoidPtr> { 3165f757f3fSDimitry Andric // We allow starting the lifetime of nodes without initializing the value held by the node, 3175f757f3fSDimitry Andric // since that is handled by the list itself in order to be allocator-aware. 3185f757f3fSDimitry Andric#ifndef _LIBCPP_CXX03_LANG 319cb14a3feSDimitry Andric 3205f757f3fSDimitry Andricprivate: 3215f757f3fSDimitry Andric union { 3220b57cec5SDimitry Andric _Tp __value_; 3235f757f3fSDimitry Andric }; 3245f757f3fSDimitry Andric 3255f757f3fSDimitry Andricpublic: 3265f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; } 3275f757f3fSDimitry Andric#else 328cb14a3feSDimitry Andric 3295f757f3fSDimitry Andricprivate: 3305f757f3fSDimitry Andric _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)]; 3315f757f3fSDimitry Andric 3325f757f3fSDimitry Andricpublic: 333cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); } 3345f757f3fSDimitry Andric#endif 3350b57cec5SDimitry Andric 3360b57cec5SDimitry Andric typedef __list_node_base<_Tp, _VoidPtr> __base; 3370b57cec5SDimitry Andric typedef typename __base::__link_pointer __link_pointer; 3380b57cec5SDimitry Andric 3395f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit __list_node(__link_pointer __prev, __link_pointer __next) : __base(__prev, __next) {} 3405f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI ~__list_node() {} 3415f757f3fSDimitry Andric 342cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __link_pointer __as_link() { return static_cast<__link_pointer>(__base::__self()); } 3430b57cec5SDimitry Andric}; 3440b57cec5SDimitry Andric 345cb14a3feSDimitry Andrictemplate <class _Tp, class _Alloc = allocator<_Tp> > 346cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS list; 347cb14a3feSDimitry Andrictemplate <class _Tp, class _Alloc> 348cb14a3feSDimitry Andricclass __list_imp; 349cb14a3feSDimitry Andrictemplate <class _Tp, class _VoidPtr> 350cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS __list_const_iterator; 3510b57cec5SDimitry Andric 3520b57cec5SDimitry Andrictemplate <class _Tp, class _VoidPtr> 353cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS __list_iterator { 3540b57cec5SDimitry Andric typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits; 3550b57cec5SDimitry Andric typedef typename _NodeTraits::__link_pointer __link_pointer; 3560b57cec5SDimitry Andric 3570b57cec5SDimitry Andric __link_pointer __ptr_; 3580b57cec5SDimitry Andric 359cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit __list_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {} 3600b57cec5SDimitry Andric 361cb14a3feSDimitry Andric template <class, class> 362cb14a3feSDimitry Andric friend class list; 363cb14a3feSDimitry Andric template <class, class> 364cb14a3feSDimitry Andric friend class __list_imp; 365cb14a3feSDimitry Andric template <class, class> 366cb14a3feSDimitry Andric friend class __list_const_iterator; 367cb14a3feSDimitry Andric 3680b57cec5SDimitry Andricpublic: 3690b57cec5SDimitry Andric typedef bidirectional_iterator_tag iterator_category; 3700b57cec5SDimitry Andric typedef _Tp value_type; 3710b57cec5SDimitry Andric typedef value_type& reference; 372bdd1243dSDimitry Andric typedef __rebind_pointer_t<_VoidPtr, value_type> pointer; 3730b57cec5SDimitry Andric typedef typename pointer_traits<pointer>::difference_type difference_type; 3740b57cec5SDimitry Andric 375cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_iterator() _NOEXCEPT : __ptr_(nullptr) {} 3760b57cec5SDimitry Andric 377cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __ptr_->__as_node()->__get_value(); } 378cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pointer operator->() const { 3795f757f3fSDimitry Andric return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__get_value()); 3800b57cec5SDimitry Andric } 3810b57cec5SDimitry Andric 382cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_iterator& operator++() { 3830b57cec5SDimitry Andric __ptr_ = __ptr_->__next_; 3840b57cec5SDimitry Andric return *this; 3850b57cec5SDimitry Andric } 386cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_iterator operator++(int) { 387cb14a3feSDimitry Andric __list_iterator __t(*this); 388cb14a3feSDimitry Andric ++(*this); 389cb14a3feSDimitry Andric return __t; 390cb14a3feSDimitry Andric } 3910b57cec5SDimitry Andric 392cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_iterator& operator--() { 3930b57cec5SDimitry Andric __ptr_ = __ptr_->__prev_; 3940b57cec5SDimitry Andric return *this; 3950b57cec5SDimitry Andric } 396cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_iterator operator--(int) { 397cb14a3feSDimitry Andric __list_iterator __t(*this); 398cb14a3feSDimitry Andric --(*this); 399cb14a3feSDimitry Andric return __t; 400cb14a3feSDimitry Andric } 4010b57cec5SDimitry Andric 402cb14a3feSDimitry Andric friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __list_iterator& __x, const __list_iterator& __y) { 4030b57cec5SDimitry Andric return __x.__ptr_ == __y.__ptr_; 4040b57cec5SDimitry Andric } 405cb14a3feSDimitry Andric friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __list_iterator& __x, const __list_iterator& __y) { 406cb14a3feSDimitry Andric return !(__x == __y); 407cb14a3feSDimitry Andric } 4080b57cec5SDimitry Andric}; 4090b57cec5SDimitry Andric 4100b57cec5SDimitry Andrictemplate <class _Tp, class _VoidPtr> 411cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS __list_const_iterator { 4120b57cec5SDimitry Andric typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits; 4130b57cec5SDimitry Andric typedef typename _NodeTraits::__link_pointer __link_pointer; 4140b57cec5SDimitry Andric 4150b57cec5SDimitry Andric __link_pointer __ptr_; 4160b57cec5SDimitry Andric 417cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit __list_const_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {} 4180b57cec5SDimitry Andric 419cb14a3feSDimitry Andric template <class, class> 420cb14a3feSDimitry Andric friend class list; 421cb14a3feSDimitry Andric template <class, class> 422cb14a3feSDimitry Andric friend class __list_imp; 423cb14a3feSDimitry Andric 4240b57cec5SDimitry Andricpublic: 4250b57cec5SDimitry Andric typedef bidirectional_iterator_tag iterator_category; 4260b57cec5SDimitry Andric typedef _Tp value_type; 4270b57cec5SDimitry Andric typedef const value_type& reference; 428bdd1243dSDimitry Andric typedef __rebind_pointer_t<_VoidPtr, const value_type> pointer; 4290b57cec5SDimitry Andric typedef typename pointer_traits<pointer>::difference_type difference_type; 4300b57cec5SDimitry Andric 431cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {} 432cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT 433cb14a3feSDimitry Andric : __ptr_(__p.__ptr_) {} 4340b57cec5SDimitry Andric 435cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __ptr_->__as_node()->__get_value(); } 436cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pointer operator->() const { 4375f757f3fSDimitry Andric return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__get_value()); 4380b57cec5SDimitry Andric } 4390b57cec5SDimitry Andric 440cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_const_iterator& operator++() { 4410b57cec5SDimitry Andric __ptr_ = __ptr_->__next_; 4420b57cec5SDimitry Andric return *this; 4430b57cec5SDimitry Andric } 444cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_const_iterator operator++(int) { 445cb14a3feSDimitry Andric __list_const_iterator __t(*this); 446cb14a3feSDimitry Andric ++(*this); 447cb14a3feSDimitry Andric return __t; 448cb14a3feSDimitry Andric } 4490b57cec5SDimitry Andric 450cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_const_iterator& operator--() { 4510b57cec5SDimitry Andric __ptr_ = __ptr_->__prev_; 4520b57cec5SDimitry Andric return *this; 4530b57cec5SDimitry Andric } 454cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_const_iterator operator--(int) { 455cb14a3feSDimitry Andric __list_const_iterator __t(*this); 456cb14a3feSDimitry Andric --(*this); 457cb14a3feSDimitry Andric return __t; 458cb14a3feSDimitry Andric } 4590b57cec5SDimitry Andric 460cb14a3feSDimitry Andric friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y) { 4610b57cec5SDimitry Andric return __x.__ptr_ == __y.__ptr_; 4620b57cec5SDimitry Andric } 463cb14a3feSDimitry Andric friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y) { 464cb14a3feSDimitry Andric return !(__x == __y); 465cb14a3feSDimitry Andric } 4660b57cec5SDimitry Andric}; 4670b57cec5SDimitry Andric 4680b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 469cb14a3feSDimitry Andricclass __list_imp { 4700b57cec5SDimitry Andric __list_imp(const __list_imp&); 4710b57cec5SDimitry Andric __list_imp& operator=(const __list_imp&); 472cb14a3feSDimitry Andric 4730b57cec5SDimitry Andricpublic: 4740b57cec5SDimitry Andric typedef _Alloc allocator_type; 4750b57cec5SDimitry Andric typedef allocator_traits<allocator_type> __alloc_traits; 4760b57cec5SDimitry Andric typedef typename __alloc_traits::size_type size_type; 477cb14a3feSDimitry Andric 4780b57cec5SDimitry Andricprotected: 4790b57cec5SDimitry Andric typedef _Tp value_type; 4800b57cec5SDimitry Andric typedef typename __alloc_traits::void_pointer __void_pointer; 4810b57cec5SDimitry Andric typedef __list_iterator<value_type, __void_pointer> iterator; 4820b57cec5SDimitry Andric typedef __list_const_iterator<value_type, __void_pointer> const_iterator; 4830b57cec5SDimitry Andric typedef __list_node_base<value_type, __void_pointer> __node_base; 4845f757f3fSDimitry Andric typedef __list_node<value_type, __void_pointer> __node_type; 4855f757f3fSDimitry Andric typedef __rebind_alloc<__alloc_traits, __node_type> __node_allocator; 4860b57cec5SDimitry Andric typedef allocator_traits<__node_allocator> __node_alloc_traits; 4870b57cec5SDimitry Andric typedef typename __node_alloc_traits::pointer __node_pointer; 4880b57cec5SDimitry Andric typedef typename __node_alloc_traits::pointer __node_const_pointer; 4890b57cec5SDimitry Andric typedef __list_node_pointer_traits<value_type, __void_pointer> __node_pointer_traits; 4900b57cec5SDimitry Andric typedef typename __node_pointer_traits::__link_pointer __link_pointer; 4910b57cec5SDimitry Andric typedef __link_pointer __link_const_pointer; 4920b57cec5SDimitry Andric typedef typename __alloc_traits::pointer pointer; 4930b57cec5SDimitry Andric typedef typename __alloc_traits::const_pointer const_pointer; 4940b57cec5SDimitry Andric typedef typename __alloc_traits::difference_type difference_type; 4950b57cec5SDimitry Andric 496bdd1243dSDimitry Andric typedef __rebind_alloc<__alloc_traits, __node_base> __node_base_allocator; 4970b57cec5SDimitry Andric typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer; 4980b57cec5SDimitry Andric static_assert((!is_same<allocator_type, __node_allocator>::value), 4990b57cec5SDimitry Andric "internal allocator type must differ from user-specified " 5000b57cec5SDimitry Andric "type; otherwise overload resolution breaks"); 5010b57cec5SDimitry Andric 5020b57cec5SDimitry Andric __node_base __end_; 5030b57cec5SDimitry Andric __compressed_pair<size_type, __node_allocator> __size_alloc_; 5040b57cec5SDimitry Andric 505cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __link_pointer __end_as_link() const _NOEXCEPT { 506cb14a3feSDimitry Andric return __node_pointer_traits::__unsafe_link_pointer_cast(const_cast<__node_base&>(__end_).__self()); 5070b57cec5SDimitry Andric } 5080b57cec5SDimitry Andric 509cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type& __sz() _NOEXCEPT { return __size_alloc_.first(); } 510cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const size_type& __sz() const _NOEXCEPT { return __size_alloc_.first(); } 511cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT { return __size_alloc_.second(); } 512cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT { return __size_alloc_.second(); } 5130b57cec5SDimitry Andric 514cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type __node_alloc_max_size() const _NOEXCEPT { 5150b57cec5SDimitry Andric return __node_alloc_traits::max_size(__node_alloc()); 5160b57cec5SDimitry Andric } 517cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI static void __unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT; 5180b57cec5SDimitry Andric 519cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_imp() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value); 520cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_imp(const allocator_type& __a); 521cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_imp(const __node_allocator& __a); 5220b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 52306c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI __list_imp(__node_allocator&& __a) _NOEXCEPT; 5240b57cec5SDimitry Andric#endif 52506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI ~__list_imp(); 52606c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT; 527cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __sz() == 0; } 5280b57cec5SDimitry Andric 529cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(__end_.__next_); } 530cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return const_iterator(__end_.__next_); } 531cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(__end_as_link()); } 532cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(__end_as_link()); } 5330b57cec5SDimitry Andric 53406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void swap(__list_imp& __c) 5350b57cec5SDimitry Andric#if _LIBCPP_STD_VER >= 14 5360b57cec5SDimitry Andric _NOEXCEPT; 5370b57cec5SDimitry Andric#else 538cb14a3feSDimitry Andric _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable<allocator_type>::value); 5390b57cec5SDimitry Andric#endif 5400b57cec5SDimitry Andric 541cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __list_imp& __c) { 542cb14a3feSDimitry Andric __copy_assign_alloc( 543cb14a3feSDimitry Andric __c, integral_constant<bool, __node_alloc_traits::propagate_on_container_copy_assignment::value>()); 544cb14a3feSDimitry Andric } 5450b57cec5SDimitry Andric 546cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__list_imp& __c) 547cb14a3feSDimitry Andric _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_move_assignment::value || 548cb14a3feSDimitry Andric is_nothrow_move_assignable<__node_allocator>::value) { 549cb14a3feSDimitry Andric __move_assign_alloc( 550cb14a3feSDimitry Andric __c, integral_constant<bool, __node_alloc_traits::propagate_on_container_move_assignment::value>()); 551cb14a3feSDimitry Andric } 5520b57cec5SDimitry Andric 5535f757f3fSDimitry Andric template <class... _Args> 5545f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI __node_pointer __create_node(__link_pointer __prev, __link_pointer __next, _Args&&... __args) { 5555f757f3fSDimitry Andric __node_allocator& __alloc = __node_alloc(); 5565f757f3fSDimitry Andric __allocation_guard<__node_allocator> __guard(__alloc, 1); 5575f757f3fSDimitry Andric // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value 5585f757f3fSDimitry Andric // held inside the node, since we need to use the allocator's construct() method for that. 5595f757f3fSDimitry Andric // 5605f757f3fSDimitry Andric // We don't use the allocator's construct() method to construct the node itself since the 5615f757f3fSDimitry Andric // Cpp17FooInsertable named requirements don't require the allocator's construct() method 5625f757f3fSDimitry Andric // to work on anything other than the value_type. 5635f757f3fSDimitry Andric std::__construct_at(std::addressof(*__guard.__get()), __prev, __next); 5645f757f3fSDimitry Andric 5655f757f3fSDimitry Andric // Now construct the value_type using the allocator's construct() method. 566cb14a3feSDimitry Andric __node_alloc_traits::construct( 567cb14a3feSDimitry Andric __alloc, std::addressof(__guard.__get()->__get_value()), std::forward<_Args>(__args)...); 5685f757f3fSDimitry Andric return __guard.__release_ptr(); 5695f757f3fSDimitry Andric } 5705f757f3fSDimitry Andric 5715f757f3fSDimitry Andric template <class... _Args> 5725f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI void __delete_node(__node_pointer __node) { 5735f757f3fSDimitry Andric // For the same reason as above, we use the allocator's destroy() method for the value_type, 5745f757f3fSDimitry Andric // but not for the node itself. 5755f757f3fSDimitry Andric __node_allocator& __alloc = __node_alloc(); 5765f757f3fSDimitry Andric __node_alloc_traits::destroy(__alloc, std::addressof(__node->__get_value())); 5775f757f3fSDimitry Andric std::__destroy_at(std::addressof(*__node)); 5785f757f3fSDimitry Andric __node_alloc_traits::deallocate(__alloc, __node, 1); 5795f757f3fSDimitry Andric } 5805f757f3fSDimitry Andric 5810b57cec5SDimitry Andricprivate: 582cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __list_imp& __c, true_type) { 5830b57cec5SDimitry Andric if (__node_alloc() != __c.__node_alloc()) 5840b57cec5SDimitry Andric clear(); 5850b57cec5SDimitry Andric __node_alloc() = __c.__node_alloc(); 5860b57cec5SDimitry Andric } 5870b57cec5SDimitry Andric 588cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __list_imp&, false_type) {} 5890b57cec5SDimitry Andric 590cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__list_imp& __c, true_type) 591cb14a3feSDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) { 5925f757f3fSDimitry Andric __node_alloc() = std::move(__c.__node_alloc()); 5930b57cec5SDimitry Andric } 5940b57cec5SDimitry Andric 595cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__list_imp&, false_type) _NOEXCEPT {} 5960b57cec5SDimitry Andric}; 5970b57cec5SDimitry Andric 5980b57cec5SDimitry Andric// Unlink nodes [__f, __l] 5990b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 600cb14a3feSDimitry Andricinline void __list_imp<_Tp, _Alloc>::__unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT { 6010b57cec5SDimitry Andric __f->__prev_->__next_ = __l->__next_; 6020b57cec5SDimitry Andric __l->__next_->__prev_ = __f->__prev_; 6030b57cec5SDimitry Andric} 6040b57cec5SDimitry Andric 6050b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 606cb14a3feSDimitry Andricinline __list_imp<_Tp, _Alloc>::__list_imp() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 607cb14a3feSDimitry Andric : __size_alloc_(0, __default_init_tag()) {} 6080b57cec5SDimitry Andric 6090b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 610cb14a3feSDimitry Andricinline __list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a) : __size_alloc_(0, __node_allocator(__a)) {} 6110b57cec5SDimitry Andric 6120b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 613cb14a3feSDimitry Andricinline __list_imp<_Tp, _Alloc>::__list_imp(const __node_allocator& __a) : __size_alloc_(0, __a) {} 6140b57cec5SDimitry Andric 6150b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 6160b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 617cb14a3feSDimitry Andricinline __list_imp<_Tp, _Alloc>::__list_imp(__node_allocator&& __a) _NOEXCEPT : __size_alloc_(0, std::move(__a)) {} 6180b57cec5SDimitry Andric#endif 6190b57cec5SDimitry Andric 6200b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 6210b57cec5SDimitry Andric__list_imp<_Tp, _Alloc>::~__list_imp() { 6220b57cec5SDimitry Andric clear(); 6230b57cec5SDimitry Andric} 6240b57cec5SDimitry Andric 6250b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 626cb14a3feSDimitry Andricvoid __list_imp<_Tp, _Alloc>::clear() _NOEXCEPT { 627cb14a3feSDimitry Andric if (!empty()) { 6280b57cec5SDimitry Andric __link_pointer __f = __end_.__next_; 6290b57cec5SDimitry Andric __link_pointer __l = __end_as_link(); 6300b57cec5SDimitry Andric __unlink_nodes(__f, __l->__prev_); 6310b57cec5SDimitry Andric __sz() = 0; 632cb14a3feSDimitry Andric while (__f != __l) { 6330b57cec5SDimitry Andric __node_pointer __np = __f->__as_node(); 6340b57cec5SDimitry Andric __f = __f->__next_; 6355f757f3fSDimitry Andric __delete_node(__np); 6360b57cec5SDimitry Andric } 6370b57cec5SDimitry Andric } 6380b57cec5SDimitry Andric} 6390b57cec5SDimitry Andric 6400b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 641cb14a3feSDimitry Andricvoid __list_imp<_Tp, _Alloc>::swap(__list_imp& __c) 6420b57cec5SDimitry Andric#if _LIBCPP_STD_VER >= 14 6430b57cec5SDimitry Andric _NOEXCEPT 6440b57cec5SDimitry Andric#else 645cb14a3feSDimitry Andric _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable<allocator_type>::value) 6460b57cec5SDimitry Andric#endif 6470b57cec5SDimitry Andric{ 648cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 649cb14a3feSDimitry Andric __alloc_traits::propagate_on_container_swap::value || this->__node_alloc() == __c.__node_alloc(), 6500b57cec5SDimitry Andric "list::swap: Either propagate_on_container_swap must be true" 6510b57cec5SDimitry Andric " or the allocators must compare equal"); 6525f757f3fSDimitry Andric using std::swap; 6535f757f3fSDimitry Andric std::__swap_allocator(__node_alloc(), __c.__node_alloc()); 6540b57cec5SDimitry Andric swap(__sz(), __c.__sz()); 6550b57cec5SDimitry Andric swap(__end_, __c.__end_); 6560b57cec5SDimitry Andric if (__sz() == 0) 6570b57cec5SDimitry Andric __end_.__next_ = __end_.__prev_ = __end_as_link(); 6580b57cec5SDimitry Andric else 6590b57cec5SDimitry Andric __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_as_link(); 6600b57cec5SDimitry Andric if (__c.__sz() == 0) 6610b57cec5SDimitry Andric __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_as_link(); 6620b57cec5SDimitry Andric else 6630b57cec5SDimitry Andric __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_as_link(); 6640b57cec5SDimitry Andric} 6650b57cec5SDimitry Andric 6660b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc /*= allocator<_Tp>*/> 667cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS list : private __list_imp<_Tp, _Alloc> { 6680b57cec5SDimitry Andric typedef __list_imp<_Tp, _Alloc> base; 6695f757f3fSDimitry Andric typedef typename base::__node_type __node_type; 6700b57cec5SDimitry Andric typedef typename base::__node_allocator __node_allocator; 6710b57cec5SDimitry Andric typedef typename base::__node_pointer __node_pointer; 6720b57cec5SDimitry Andric typedef typename base::__node_alloc_traits __node_alloc_traits; 6730b57cec5SDimitry Andric typedef typename base::__node_base __node_base; 6740b57cec5SDimitry Andric typedef typename base::__node_base_pointer __node_base_pointer; 6750b57cec5SDimitry Andric typedef typename base::__link_pointer __link_pointer; 6760b57cec5SDimitry Andric 6770b57cec5SDimitry Andricpublic: 6780b57cec5SDimitry Andric typedef _Tp value_type; 6790b57cec5SDimitry Andric typedef _Alloc allocator_type; 6800b57cec5SDimitry Andric static_assert((is_same<value_type, typename allocator_type::value_type>::value), 68106c3fb27SDimitry Andric "Allocator::value_type must be same type as value_type"); 6820b57cec5SDimitry Andric typedef value_type& reference; 6830b57cec5SDimitry Andric typedef const value_type& const_reference; 6840b57cec5SDimitry Andric typedef typename base::pointer pointer; 6850b57cec5SDimitry Andric typedef typename base::const_pointer const_pointer; 6864824e7fdSDimitry Andric typedef typename base::size_type size_type; 6870b57cec5SDimitry Andric typedef typename base::difference_type difference_type; 6880b57cec5SDimitry Andric typedef typename base::iterator iterator; 6890b57cec5SDimitry Andric typedef typename base::const_iterator const_iterator; 6905f757f3fSDimitry Andric typedef std::reverse_iterator<iterator> reverse_iterator; 6915f757f3fSDimitry Andric typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 69206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 6930b57cec5SDimitry Andric typedef size_type __remove_return_type; 6940b57cec5SDimitry Andric#else 6950b57cec5SDimitry Andric typedef void __remove_return_type; 6960b57cec5SDimitry Andric#endif 6970b57cec5SDimitry Andric 698bdd1243dSDimitry Andric static_assert(is_same<allocator_type, __rebind_alloc<allocator_traits<allocator_type>, value_type> >::value, 699bdd1243dSDimitry Andric "[allocator.requirements] states that rebinding an allocator to the same type should result in the " 700bdd1243dSDimitry Andric "original allocator"); 701bdd1243dSDimitry Andric 702cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI list() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) {} 703cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit list(const allocator_type& __a) : base(__a) {} 70406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit list(size_type __n); 70506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 70606c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit list(size_type __n, const allocator_type& __a); 7070b57cec5SDimitry Andric#endif 70806c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x); 7094824e7fdSDimitry Andric template <class = __enable_if_t<__is_allocator<_Alloc>::value> > 710cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x, const allocator_type& __a) : base(__a) { 7114824e7fdSDimitry Andric for (; __n > 0; --__n) 7124824e7fdSDimitry Andric push_back(__x); 7134824e7fdSDimitry Andric } 7144824e7fdSDimitry Andric 7150b57cec5SDimitry Andric template <class _InpIter> 716cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI 717cb14a3feSDimitry Andric list(_InpIter __f, _InpIter __l, __enable_if_t<__has_input_iterator_category<_InpIter>::value>* = 0); 7180b57cec5SDimitry Andric template <class _InpIter> 719cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI 720cb14a3feSDimitry Andric list(_InpIter __f, 721cb14a3feSDimitry Andric _InpIter __l, 722cb14a3feSDimitry Andric const allocator_type& __a, 72306c3fb27SDimitry Andric __enable_if_t<__has_input_iterator_category<_InpIter>::value>* = 0); 7240b57cec5SDimitry Andric 72506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 72606c3fb27SDimitry Andric template <_ContainerCompatibleRange<_Tp> _Range> 727cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI list(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type()) : base(__a) { 72806c3fb27SDimitry Andric prepend_range(std::forward<_Range>(__range)); 72906c3fb27SDimitry Andric } 73006c3fb27SDimitry Andric#endif 73106c3fb27SDimitry Andric 73206c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI list(const list& __c); 73306c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI list(const list& __c, const __type_identity_t<allocator_type>& __a); 734cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI list& operator=(const list& __c); 7350b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 73606c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI list(initializer_list<value_type> __il); 73706c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI list(initializer_list<value_type> __il, const allocator_type& __a); 7380b57cec5SDimitry Andric 739cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI list(list&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value); 740cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI list(list&& __c, const __type_identity_t<allocator_type>& __a); 741cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI list& operator=(list&& __c) 742cb14a3feSDimitry Andric _NOEXCEPT_(__node_alloc_traits::propagate_on_container_move_assignment::value&& 7430b57cec5SDimitry Andric is_nothrow_move_assignable<__node_allocator>::value); 7440b57cec5SDimitry Andric 745cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI list& operator=(initializer_list<value_type> __il) { 746cb14a3feSDimitry Andric assign(__il.begin(), __il.end()); 747cb14a3feSDimitry Andric return *this; 748cb14a3feSDimitry Andric } 7490b57cec5SDimitry Andric 750cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void assign(initializer_list<value_type> __il) { assign(__il.begin(), __il.end()); } 7510b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 7520b57cec5SDimitry Andric 7530b57cec5SDimitry Andric template <class _InpIter> 754cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void 755cb14a3feSDimitry Andric assign(_InpIter __f, _InpIter __l, __enable_if_t<__has_input_iterator_category<_InpIter>::value>* = 0); 75606c3fb27SDimitry Andric 75706c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 75806c3fb27SDimitry Andric template <_ContainerCompatibleRange<_Tp> _Range> 759cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void assign_range(_Range&& __range) { 76006c3fb27SDimitry Andric __assign_with_sentinel(ranges::begin(__range), ranges::end(__range)); 76106c3fb27SDimitry Andric } 76206c3fb27SDimitry Andric#endif 76306c3fb27SDimitry Andric 76406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __x); 7650b57cec5SDimitry Andric 766cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT; 7670b57cec5SDimitry Andric 768cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return base::__sz(); } 769cb14a3feSDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return base::empty(); } 770cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { 771cb14a3feSDimitry Andric return std::min<size_type>(base::__node_alloc_max_size(), numeric_limits<difference_type >::max()); 7720b57cec5SDimitry Andric } 7730b57cec5SDimitry Andric 774cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return base::begin(); } 775cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return base::begin(); } 776cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return base::end(); } 777cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return base::end(); } 778cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return base::begin(); } 779cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return base::end(); } 7800b57cec5SDimitry Andric 781cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); } 782cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); } 783cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); } 784cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); } 785cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return const_reverse_iterator(end()); } 786cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return const_reverse_iterator(begin()); } 7870b57cec5SDimitry Andric 788cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI reference front() { 78906c3fb27SDimitry Andric _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::front called on empty list"); 7905f757f3fSDimitry Andric return base::__end_.__next_->__as_node()->__get_value(); 7910b57cec5SDimitry Andric } 792cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_reference front() const { 79306c3fb27SDimitry Andric _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::front called on empty list"); 7945f757f3fSDimitry Andric return base::__end_.__next_->__as_node()->__get_value(); 7950b57cec5SDimitry Andric } 796cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI reference back() { 79706c3fb27SDimitry Andric _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::back called on empty list"); 7985f757f3fSDimitry Andric return base::__end_.__prev_->__as_node()->__get_value(); 7990b57cec5SDimitry Andric } 800cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_reference back() const { 80106c3fb27SDimitry Andric _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::back called on empty list"); 8025f757f3fSDimitry Andric return base::__end_.__prev_->__as_node()->__get_value(); 8030b57cec5SDimitry Andric } 8040b57cec5SDimitry Andric 8050b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 80606c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __x); 80706c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __x); 80806c3fb27SDimitry Andric 80906c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 81006c3fb27SDimitry Andric template <_ContainerCompatibleRange<_Tp> _Range> 811cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void prepend_range(_Range&& __range) { 81206c3fb27SDimitry Andric insert_range(begin(), std::forward<_Range>(__range)); 81306c3fb27SDimitry Andric } 81406c3fb27SDimitry Andric 81506c3fb27SDimitry Andric template <_ContainerCompatibleRange<_Tp> _Range> 816cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void append_range(_Range&& __range) { 81706c3fb27SDimitry Andric insert_range(end(), std::forward<_Range>(__range)); 81806c3fb27SDimitry Andric } 81906c3fb27SDimitry Andric# endif 8200b57cec5SDimitry Andric 8210b57cec5SDimitry Andric template <class... _Args> 82206c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 17 82306c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI reference emplace_front(_Args&&... __args); 8240b57cec5SDimitry Andric# else 82506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void emplace_front(_Args&&... __args); 8260b57cec5SDimitry Andric# endif 8270b57cec5SDimitry Andric template <class... _Args> 82806c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 17 82906c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI reference emplace_back(_Args&&... __args); 8300b57cec5SDimitry Andric# else 83106c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args); 8320b57cec5SDimitry Andric# endif 8330b57cec5SDimitry Andric template <class... _Args> 83406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator emplace(const_iterator __p, _Args&&... __args); 8350b57cec5SDimitry Andric 83606c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x); 8370b57cec5SDimitry Andric 838cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, initializer_list<value_type> __il) { 839cb14a3feSDimitry Andric return insert(__p, __il.begin(), __il.end()); 840cb14a3feSDimitry Andric } 8410b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 8420b57cec5SDimitry Andric 84306c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __x); 84406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void push_back(const value_type& __x); 8450b57cec5SDimitry Andric 8460b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 8470b57cec5SDimitry Andric template <class _Arg> 848cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void __emplace_back(_Arg&& __arg) { 849cb14a3feSDimitry Andric emplace_back(std::forward<_Arg>(__arg)); 850cb14a3feSDimitry Andric } 8510b57cec5SDimitry Andric#else 852cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void __emplace_back(value_type const& __arg) { push_back(__arg); } 8530b57cec5SDimitry Andric#endif 8540b57cec5SDimitry Andric 85506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x); 85606c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, size_type __n, const value_type& __x); 8570b57cec5SDimitry Andric template <class _InpIter> 858cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator 859cb14a3feSDimitry Andric insert(const_iterator __p, 860cb14a3feSDimitry Andric _InpIter __f, 861cb14a3feSDimitry Andric _InpIter __l, 86206c3fb27SDimitry Andric __enable_if_t<__has_input_iterator_category<_InpIter>::value>* = 0); 86306c3fb27SDimitry Andric 86406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 86506c3fb27SDimitry Andric template <_ContainerCompatibleRange<_Tp> _Range> 866cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert_range(const_iterator __position, _Range&& __range) { 86706c3fb27SDimitry Andric return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range)); 86806c3fb27SDimitry Andric } 86906c3fb27SDimitry Andric#endif 8700b57cec5SDimitry Andric 871cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void swap(list& __c) 8720b57cec5SDimitry Andric#if _LIBCPP_STD_VER >= 14 8730b57cec5SDimitry Andric _NOEXCEPT 8740b57cec5SDimitry Andric#else 8750b57cec5SDimitry Andric _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 8760b57cec5SDimitry Andric __is_nothrow_swappable<__node_allocator>::value) 8770b57cec5SDimitry Andric#endif 878cb14a3feSDimitry Andric { 879cb14a3feSDimitry Andric base::swap(__c); 880cb14a3feSDimitry Andric } 881cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { base::clear(); } 8820b57cec5SDimitry Andric 88306c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void pop_front(); 88406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void pop_back(); 8850b57cec5SDimitry Andric 88606c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p); 88706c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l); 8880b57cec5SDimitry Andric 88906c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void resize(size_type __n); 89006c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __x); 8910b57cec5SDimitry Andric 89206c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c); 8930b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 894cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list&& __c) { splice(__p, __c); } 895cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list&& __c, const_iterator __i) { splice(__p, __c, __i); } 896cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l) { 897cb14a3feSDimitry Andric splice(__p, __c, __f, __l); 898cb14a3feSDimitry Andric } 8990b57cec5SDimitry Andric#endif 90006c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c, const_iterator __i); 90106c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l); 9020b57cec5SDimitry Andric 90306c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI __remove_return_type remove(const value_type& __x); 90406c3fb27SDimitry Andric template <class _Pred> 90506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI __remove_return_type remove_if(_Pred __pred); 906cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __remove_return_type unique() { return unique(__equal_to()); } 9070b57cec5SDimitry Andric template <class _BinaryPred> 90806c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPred __binary_pred); 909cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(list& __c); 9100b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 911cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(list&& __c) { merge(__c); } 9120b57cec5SDimitry Andric 9130b57cec5SDimitry Andric template <class _Comp> 914cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(list&& __c, _Comp __comp) { 915cb14a3feSDimitry Andric merge(__c, __comp); 916cb14a3feSDimitry Andric } 9170b57cec5SDimitry Andric#endif 9180b57cec5SDimitry Andric template <class _Comp> 91906c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(list& __c, _Comp __comp); 9200b57cec5SDimitry Andric 921cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void sort(); 9220b57cec5SDimitry Andric template <class _Comp> 923cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void sort(_Comp __comp); 9240b57cec5SDimitry Andric 92506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT; 9260b57cec5SDimitry Andric 92706c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI bool __invariants() const; 9280b57cec5SDimitry Andric 9290b57cec5SDimitry Andricprivate: 93006c3fb27SDimitry Andric template <class _Iterator, class _Sentinel> 931cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __f, _Sentinel __l); 93206c3fb27SDimitry Andric 93306c3fb27SDimitry Andric template <class _Iterator, class _Sentinel> 934cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator __insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l); 93506c3fb27SDimitry Andric 936cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI static void __link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l); 937cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void __link_nodes_at_front(__link_pointer __f, __link_pointer __l); 938cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void __link_nodes_at_back(__link_pointer __f, __link_pointer __l); 93906c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator __iterator(size_type __n); 94006c3fb27SDimitry Andric // TODO: Make this _LIBCPP_HIDE_FROM_ABI 9410b57cec5SDimitry Andric template <class _Comp> 94206c3fb27SDimitry Andric _LIBCPP_HIDDEN static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp); 9430b57cec5SDimitry Andric 94406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void __move_assign(list& __c, true_type) 9450b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value); 94606c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI void __move_assign(list& __c, false_type); 9470b57cec5SDimitry Andric}; 9480b57cec5SDimitry Andric 949349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17 9500b57cec5SDimitry Andrictemplate <class _InputIterator, 951fe6060f1SDimitry Andric class _Alloc = allocator<__iter_value_type<_InputIterator>>, 95206c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 953cb14a3feSDimitry Andric class = enable_if_t<__is_allocator<_Alloc>::value> > 954cb14a3feSDimitry Andriclist(_InputIterator, _InputIterator) -> list<__iter_value_type<_InputIterator>, _Alloc>; 9550b57cec5SDimitry Andric 9560b57cec5SDimitry Andrictemplate <class _InputIterator, 9570b57cec5SDimitry Andric class _Alloc, 95806c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 959cb14a3feSDimitry Andric class = enable_if_t<__is_allocator<_Alloc>::value> > 960cb14a3feSDimitry Andriclist(_InputIterator, _InputIterator, _Alloc) -> list<__iter_value_type<_InputIterator>, _Alloc>; 9610b57cec5SDimitry Andric#endif 9620b57cec5SDimitry Andric 96306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 96406c3fb27SDimitry Andrictemplate <ranges::input_range _Range, 96506c3fb27SDimitry Andric class _Alloc = allocator<ranges::range_value_t<_Range>>, 966cb14a3feSDimitry Andric class = enable_if_t<__is_allocator<_Alloc>::value> > 967cb14a3feSDimitry Andriclist(from_range_t, _Range&&, _Alloc = _Alloc()) -> list<ranges::range_value_t<_Range>, _Alloc>; 96806c3fb27SDimitry Andric#endif 96906c3fb27SDimitry Andric 9700b57cec5SDimitry Andric// Link in nodes [__f, __l] just prior to __p 9710b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 972cb14a3feSDimitry Andricinline void list<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l) { 9730b57cec5SDimitry Andric __p->__prev_->__next_ = __f; 9740b57cec5SDimitry Andric __f->__prev_ = __p->__prev_; 9750b57cec5SDimitry Andric __p->__prev_ = __l; 9760b57cec5SDimitry Andric __l->__next_ = __p; 9770b57cec5SDimitry Andric} 9780b57cec5SDimitry Andric 9790b57cec5SDimitry Andric// Link in nodes [__f, __l] at the front of the list 9800b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 981cb14a3feSDimitry Andricinline void list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l) { 9820b57cec5SDimitry Andric __f->__prev_ = base::__end_as_link(); 9830b57cec5SDimitry Andric __l->__next_ = base::__end_.__next_; 9840b57cec5SDimitry Andric __l->__next_->__prev_ = __l; 9850b57cec5SDimitry Andric base::__end_.__next_ = __f; 9860b57cec5SDimitry Andric} 9870b57cec5SDimitry Andric 9880b57cec5SDimitry Andric// Link in nodes [__f, __l] at the back of the list 9890b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 990cb14a3feSDimitry Andricinline void list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l) { 9910b57cec5SDimitry Andric __l->__next_ = base::__end_as_link(); 9920b57cec5SDimitry Andric __f->__prev_ = base::__end_.__prev_; 9930b57cec5SDimitry Andric __f->__prev_->__next_ = __f; 9940b57cec5SDimitry Andric base::__end_.__prev_ = __l; 9950b57cec5SDimitry Andric} 9960b57cec5SDimitry Andric 9970b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 998cb14a3feSDimitry Andricinline typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::__iterator(size_type __n) { 999cb14a3feSDimitry Andric return __n <= base::__sz() / 2 ? std::next(begin(), __n) : std::prev(end(), base::__sz() - __n); 10000b57cec5SDimitry Andric} 10010b57cec5SDimitry Andric 10020b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1003cb14a3feSDimitry Andriclist<_Tp, _Alloc>::list(size_type __n) { 10040b57cec5SDimitry Andric for (; __n > 0; --__n) 10050b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 10060b57cec5SDimitry Andric emplace_back(); 10070b57cec5SDimitry Andric#else 10080b57cec5SDimitry Andric push_back(value_type()); 10090b57cec5SDimitry Andric#endif 10100b57cec5SDimitry Andric} 10110b57cec5SDimitry Andric 101206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 10130b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1014cb14a3feSDimitry Andriclist<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a) { 10150b57cec5SDimitry Andric for (; __n > 0; --__n) 10160b57cec5SDimitry Andric emplace_back(); 10170b57cec5SDimitry Andric} 10180b57cec5SDimitry Andric#endif 10190b57cec5SDimitry Andric 10200b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1021cb14a3feSDimitry Andriclist<_Tp, _Alloc>::list(size_type __n, const value_type& __x) { 10220b57cec5SDimitry Andric for (; __n > 0; --__n) 10230b57cec5SDimitry Andric push_back(__x); 10240b57cec5SDimitry Andric} 10250b57cec5SDimitry Andric 10260b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 10270b57cec5SDimitry Andrictemplate <class _InpIter> 1028cb14a3feSDimitry Andriclist<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, __enable_if_t<__has_input_iterator_category<_InpIter>::value>*) { 10290b57cec5SDimitry Andric for (; __f != __l; ++__f) 10300b57cec5SDimitry Andric __emplace_back(*__f); 10310b57cec5SDimitry Andric} 10320b57cec5SDimitry Andric 10330b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 10340b57cec5SDimitry Andrictemplate <class _InpIter> 1035cb14a3feSDimitry Andriclist<_Tp, _Alloc>::list(_InpIter __f, 1036cb14a3feSDimitry Andric _InpIter __l, 1037cb14a3feSDimitry Andric const allocator_type& __a, 103806c3fb27SDimitry Andric __enable_if_t<__has_input_iterator_category<_InpIter>::value>*) 1039cb14a3feSDimitry Andric : base(__a) { 10400b57cec5SDimitry Andric for (; __f != __l; ++__f) 10410b57cec5SDimitry Andric __emplace_back(*__f); 10420b57cec5SDimitry Andric} 10430b57cec5SDimitry Andric 10440b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 10450b57cec5SDimitry Andriclist<_Tp, _Alloc>::list(const list& __c) 1046cb14a3feSDimitry Andric : base(__node_alloc_traits::select_on_container_copy_construction(__c.__node_alloc())) { 10470b57cec5SDimitry Andric for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 10480b57cec5SDimitry Andric push_back(*__i); 10490b57cec5SDimitry Andric} 10500b57cec5SDimitry Andric 10510b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1052cb14a3feSDimitry Andriclist<_Tp, _Alloc>::list(const list& __c, const __type_identity_t<allocator_type>& __a) : base(__a) { 10530b57cec5SDimitry Andric for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 10540b57cec5SDimitry Andric push_back(*__i); 10550b57cec5SDimitry Andric} 10560b57cec5SDimitry Andric 10570b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 10580b57cec5SDimitry Andric 10590b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1060cb14a3feSDimitry Andriclist<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a) : base(__a) { 1061cb14a3feSDimitry Andric for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), __e = __il.end(); __i != __e; ++__i) 10620b57cec5SDimitry Andric push_back(*__i); 10630b57cec5SDimitry Andric} 10640b57cec5SDimitry Andric 10650b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1066cb14a3feSDimitry Andriclist<_Tp, _Alloc>::list(initializer_list<value_type> __il) { 1067cb14a3feSDimitry Andric for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), __e = __il.end(); __i != __e; ++__i) 10680b57cec5SDimitry Andric push_back(*__i); 10690b57cec5SDimitry Andric} 10700b57cec5SDimitry Andric 10710b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1072cb14a3feSDimitry Andricinline list<_Tp, _Alloc>::list(list&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value) 10735f757f3fSDimitry Andric : base(std::move(__c.__node_alloc())) { 10740b57cec5SDimitry Andric splice(end(), __c); 10750b57cec5SDimitry Andric} 10760b57cec5SDimitry Andric 10770b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1078cb14a3feSDimitry Andricinline list<_Tp, _Alloc>::list(list&& __c, const __type_identity_t<allocator_type>& __a) : base(__a) { 10790b57cec5SDimitry Andric if (__a == __c.get_allocator()) 10800b57cec5SDimitry Andric splice(end(), __c); 1081cb14a3feSDimitry Andric else { 10820b57cec5SDimitry Andric typedef move_iterator<iterator> _Ip; 10830b57cec5SDimitry Andric assign(_Ip(__c.begin()), _Ip(__c.end())); 10840b57cec5SDimitry Andric } 10850b57cec5SDimitry Andric} 10860b57cec5SDimitry Andric 10870b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1088cb14a3feSDimitry Andricinline list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(list&& __c) 1089cb14a3feSDimitry Andric _NOEXCEPT_(__node_alloc_traits::propagate_on_container_move_assignment::value&& 1090cb14a3feSDimitry Andric is_nothrow_move_assignable<__node_allocator>::value) { 1091cb14a3feSDimitry Andric __move_assign(__c, integral_constant<bool, __node_alloc_traits::propagate_on_container_move_assignment::value>()); 10920b57cec5SDimitry Andric return *this; 10930b57cec5SDimitry Andric} 10940b57cec5SDimitry Andric 10950b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1096cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::__move_assign(list& __c, false_type) { 1097cb14a3feSDimitry Andric if (base::__node_alloc() != __c.__node_alloc()) { 10980b57cec5SDimitry Andric typedef move_iterator<iterator> _Ip; 10990b57cec5SDimitry Andric assign(_Ip(__c.begin()), _Ip(__c.end())); 1100cb14a3feSDimitry Andric } else 11010b57cec5SDimitry Andric __move_assign(__c, true_type()); 11020b57cec5SDimitry Andric} 11030b57cec5SDimitry Andric 11040b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1105cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::__move_assign(list& __c, true_type) 1106cb14a3feSDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) { 11070b57cec5SDimitry Andric clear(); 11080b57cec5SDimitry Andric base::__move_assign_alloc(__c); 11090b57cec5SDimitry Andric splice(end(), __c); 11100b57cec5SDimitry Andric} 11110b57cec5SDimitry Andric 11120b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 11130b57cec5SDimitry Andric 11140b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1115cb14a3feSDimitry Andricinline list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list& __c) { 1116cb14a3feSDimitry Andric if (this != std::addressof(__c)) { 11170b57cec5SDimitry Andric base::__copy_assign_alloc(__c); 11180b57cec5SDimitry Andric assign(__c.begin(), __c.end()); 11190b57cec5SDimitry Andric } 11200b57cec5SDimitry Andric return *this; 11210b57cec5SDimitry Andric} 11220b57cec5SDimitry Andric 11230b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 11240b57cec5SDimitry Andrictemplate <class _InpIter> 1125cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::assign( 1126cb14a3feSDimitry Andric _InpIter __f, _InpIter __l, __enable_if_t<__has_input_iterator_category<_InpIter>::value>*) { 112706c3fb27SDimitry Andric __assign_with_sentinel(__f, __l); 112806c3fb27SDimitry Andric} 112906c3fb27SDimitry Andric 113006c3fb27SDimitry Andrictemplate <class _Tp, class _Alloc> 113106c3fb27SDimitry Andrictemplate <class _Iterator, class _Sentinel> 1132cb14a3feSDimitry Andric_LIBCPP_HIDE_FROM_ABI void list<_Tp, _Alloc>::__assign_with_sentinel(_Iterator __f, _Sentinel __l) { 11330b57cec5SDimitry Andric iterator __i = begin(); 11340b57cec5SDimitry Andric iterator __e = end(); 1135349cc55cSDimitry Andric for (; __f != __l && __i != __e; ++__f, (void)++__i) 11360b57cec5SDimitry Andric *__i = *__f; 11370b57cec5SDimitry Andric if (__i == __e) 113806c3fb27SDimitry Andric __insert_with_sentinel(__e, std::move(__f), std::move(__l)); 11390b57cec5SDimitry Andric else 11400b57cec5SDimitry Andric erase(__i, __e); 11410b57cec5SDimitry Andric} 11420b57cec5SDimitry Andric 11430b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1144cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x) { 11450b57cec5SDimitry Andric iterator __i = begin(); 11460b57cec5SDimitry Andric iterator __e = end(); 1147349cc55cSDimitry Andric for (; __n > 0 && __i != __e; --__n, (void)++__i) 11480b57cec5SDimitry Andric *__i = __x; 11490b57cec5SDimitry Andric if (__i == __e) 11500b57cec5SDimitry Andric insert(__e, __n, __x); 11510b57cec5SDimitry Andric else 11520b57cec5SDimitry Andric erase(__i, __e); 11530b57cec5SDimitry Andric} 11540b57cec5SDimitry Andric 11550b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1156cb14a3feSDimitry Andricinline _Alloc list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT { 11570b57cec5SDimitry Andric return allocator_type(base::__node_alloc()); 11580b57cec5SDimitry Andric} 11590b57cec5SDimitry Andric 11600b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1161cb14a3feSDimitry Andrictypename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x) { 11625f757f3fSDimitry Andric __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x); 11635f757f3fSDimitry Andric __link_nodes(__p.__ptr_, __node->__as_link(), __node->__as_link()); 11640b57cec5SDimitry Andric ++base::__sz(); 11655f757f3fSDimitry Andric return iterator(__node->__as_link()); 11660b57cec5SDimitry Andric} 11670b57cec5SDimitry Andric 11680b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 11690b57cec5SDimitry Andrictypename list<_Tp, _Alloc>::iterator 1170cb14a3feSDimitry Andriclist<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x) { 117106c3fb27SDimitry Andric iterator __r(__p.__ptr_); 1172cb14a3feSDimitry Andric if (__n > 0) { 11730b57cec5SDimitry Andric size_type __ds = 0; 11745f757f3fSDimitry Andric __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x); 11750b57cec5SDimitry Andric ++__ds; 11765f757f3fSDimitry Andric __r = iterator(__node->__as_link()); 11770b57cec5SDimitry Andric iterator __e = __r; 117806c3fb27SDimitry Andric#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1179cb14a3feSDimitry Andric try { 118006c3fb27SDimitry Andric#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1181cb14a3feSDimitry Andric for (--__n; __n != 0; --__n, (void)++__e, ++__ds) { 11825f757f3fSDimitry Andric __e.__ptr_->__next_ = this->__create_node(/* prev = */ __e.__ptr_, /* next = */ nullptr, __x)->__as_link(); 11830b57cec5SDimitry Andric } 118406c3fb27SDimitry Andric#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1185cb14a3feSDimitry Andric } catch (...) { 1186cb14a3feSDimitry Andric while (true) { 11870b57cec5SDimitry Andric __link_pointer __prev = __e.__ptr_->__prev_; 11885f757f3fSDimitry Andric __node_pointer __current = __e.__ptr_->__as_node(); 11895f757f3fSDimitry Andric this->__delete_node(__current); 11900b57cec5SDimitry Andric if (__prev == 0) 11910b57cec5SDimitry Andric break; 119206c3fb27SDimitry Andric __e = iterator(__prev); 11930b57cec5SDimitry Andric } 11940b57cec5SDimitry Andric throw; 11950b57cec5SDimitry Andric } 119606c3fb27SDimitry Andric#endif // _LIBCPP_HAS_NO_EXCEPTIONS 11970b57cec5SDimitry Andric __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); 11980b57cec5SDimitry Andric base::__sz() += __ds; 11990b57cec5SDimitry Andric } 12000b57cec5SDimitry Andric return __r; 12010b57cec5SDimitry Andric} 12020b57cec5SDimitry Andric 12030b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 12040b57cec5SDimitry Andrictemplate <class _InpIter> 1205cb14a3feSDimitry Andrictypename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::insert( 1206cb14a3feSDimitry Andric const_iterator __p, _InpIter __f, _InpIter __l, __enable_if_t<__has_input_iterator_category<_InpIter>::value>*) { 120706c3fb27SDimitry Andric return __insert_with_sentinel(__p, __f, __l); 120806c3fb27SDimitry Andric} 120906c3fb27SDimitry Andric 121006c3fb27SDimitry Andrictemplate <class _Tp, class _Alloc> 121106c3fb27SDimitry Andrictemplate <class _Iterator, class _Sentinel> 1212cb14a3feSDimitry Andric_LIBCPP_HIDE_FROM_ABI typename list<_Tp, _Alloc>::iterator 121306c3fb27SDimitry Andriclist<_Tp, _Alloc>::__insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l) { 121406c3fb27SDimitry Andric iterator __r(__p.__ptr_); 1215cb14a3feSDimitry Andric if (__f != __l) { 12160b57cec5SDimitry Andric size_type __ds = 0; 12175f757f3fSDimitry Andric __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, *__f); 12180b57cec5SDimitry Andric ++__ds; 12195f757f3fSDimitry Andric __r = iterator(__node->__as_link()); 12200b57cec5SDimitry Andric iterator __e = __r; 122106c3fb27SDimitry Andric#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1222cb14a3feSDimitry Andric try { 122306c3fb27SDimitry Andric#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1224cb14a3feSDimitry Andric for (++__f; __f != __l; ++__f, (void)++__e, ++__ds) { 12255f757f3fSDimitry Andric __e.__ptr_->__next_ = this->__create_node(/* prev = */ __e.__ptr_, /* next = */ nullptr, *__f)->__as_link(); 12260b57cec5SDimitry Andric } 122706c3fb27SDimitry Andric#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1228cb14a3feSDimitry Andric } catch (...) { 1229cb14a3feSDimitry Andric while (true) { 12300b57cec5SDimitry Andric __link_pointer __prev = __e.__ptr_->__prev_; 12315f757f3fSDimitry Andric __node_pointer __current = __e.__ptr_->__as_node(); 12325f757f3fSDimitry Andric this->__delete_node(__current); 12330b57cec5SDimitry Andric if (__prev == 0) 12340b57cec5SDimitry Andric break; 123506c3fb27SDimitry Andric __e = iterator(__prev); 12360b57cec5SDimitry Andric } 12370b57cec5SDimitry Andric throw; 12380b57cec5SDimitry Andric } 123906c3fb27SDimitry Andric#endif // _LIBCPP_HAS_NO_EXCEPTIONS 12400b57cec5SDimitry Andric __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); 12410b57cec5SDimitry Andric base::__sz() += __ds; 12420b57cec5SDimitry Andric } 12430b57cec5SDimitry Andric return __r; 12440b57cec5SDimitry Andric} 12450b57cec5SDimitry Andric 12460b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1247cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::push_front(const value_type& __x) { 12485f757f3fSDimitry Andric __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x); 12495f757f3fSDimitry Andric __link_pointer __nl = __node->__as_link(); 12500b57cec5SDimitry Andric __link_nodes_at_front(__nl, __nl); 12510b57cec5SDimitry Andric ++base::__sz(); 12520b57cec5SDimitry Andric} 12530b57cec5SDimitry Andric 12540b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1255cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::push_back(const value_type& __x) { 12565f757f3fSDimitry Andric __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x); 12575f757f3fSDimitry Andric __link_pointer __nl = __node->__as_link(); 12585f757f3fSDimitry Andric __link_nodes_at_back(__nl, __nl); 12590b57cec5SDimitry Andric ++base::__sz(); 12600b57cec5SDimitry Andric} 12610b57cec5SDimitry Andric 12620b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 12630b57cec5SDimitry Andric 12640b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1265cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::push_front(value_type&& __x) { 12665f757f3fSDimitry Andric __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, std::move(__x)); 12675f757f3fSDimitry Andric __link_pointer __nl = __node->__as_link(); 12685f757f3fSDimitry Andric __link_nodes_at_front(__nl, __nl); 12690b57cec5SDimitry Andric ++base::__sz(); 12700b57cec5SDimitry Andric} 12710b57cec5SDimitry Andric 12720b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1273cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::push_back(value_type&& __x) { 12745f757f3fSDimitry Andric __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, std::move(__x)); 12755f757f3fSDimitry Andric __link_pointer __nl = __node->__as_link(); 12765f757f3fSDimitry Andric __link_nodes_at_back(__nl, __nl); 12770b57cec5SDimitry Andric ++base::__sz(); 12780b57cec5SDimitry Andric} 12790b57cec5SDimitry Andric 12800b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 12810b57cec5SDimitry Andrictemplate <class... _Args> 128206c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 17 12830b57cec5SDimitry Andrictypename list<_Tp, _Alloc>::reference 12840b57cec5SDimitry Andric# else 12850b57cec5SDimitry Andricvoid 12860b57cec5SDimitry Andric# endif 1287cb14a3feSDimitry Andriclist<_Tp, _Alloc>::emplace_front(_Args&&... __args) { 1288cb14a3feSDimitry Andric __node_pointer __node = 1289cb14a3feSDimitry Andric this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, std::forward<_Args>(__args)...); 12905f757f3fSDimitry Andric __link_pointer __nl = __node->__as_link(); 12915f757f3fSDimitry Andric __link_nodes_at_front(__nl, __nl); 12920b57cec5SDimitry Andric ++base::__sz(); 129306c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 17 12945f757f3fSDimitry Andric return __node->__get_value(); 12950b57cec5SDimitry Andric# endif 12960b57cec5SDimitry Andric} 12970b57cec5SDimitry Andric 12980b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 12990b57cec5SDimitry Andrictemplate <class... _Args> 130006c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 17 13010b57cec5SDimitry Andrictypename list<_Tp, _Alloc>::reference 13020b57cec5SDimitry Andric# else 13030b57cec5SDimitry Andricvoid 13040b57cec5SDimitry Andric# endif 1305cb14a3feSDimitry Andriclist<_Tp, _Alloc>::emplace_back(_Args&&... __args) { 1306cb14a3feSDimitry Andric __node_pointer __node = 1307cb14a3feSDimitry Andric this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, std::forward<_Args>(__args)...); 13085f757f3fSDimitry Andric __link_pointer __nl = __node->__as_link(); 13090b57cec5SDimitry Andric __link_nodes_at_back(__nl, __nl); 13100b57cec5SDimitry Andric ++base::__sz(); 131106c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 17 13125f757f3fSDimitry Andric return __node->__get_value(); 13130b57cec5SDimitry Andric# endif 13140b57cec5SDimitry Andric} 13150b57cec5SDimitry Andric 13160b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 13170b57cec5SDimitry Andrictemplate <class... _Args> 1318cb14a3feSDimitry Andrictypename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args) { 1319cb14a3feSDimitry Andric __node_pointer __node = 1320cb14a3feSDimitry Andric this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, std::forward<_Args>(__args)...); 13215f757f3fSDimitry Andric __link_pointer __nl = __node->__as_link(); 13220b57cec5SDimitry Andric __link_nodes(__p.__ptr_, __nl, __nl); 13230b57cec5SDimitry Andric ++base::__sz(); 132406c3fb27SDimitry Andric return iterator(__nl); 13250b57cec5SDimitry Andric} 13260b57cec5SDimitry Andric 13270b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1328cb14a3feSDimitry Andrictypename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x) { 13295f757f3fSDimitry Andric __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, std::move(__x)); 13305f757f3fSDimitry Andric __link_pointer __nl = __node->__as_link(); 13310b57cec5SDimitry Andric __link_nodes(__p.__ptr_, __nl, __nl); 13320b57cec5SDimitry Andric ++base::__sz(); 133306c3fb27SDimitry Andric return iterator(__nl); 13340b57cec5SDimitry Andric} 13350b57cec5SDimitry Andric 13360b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 13370b57cec5SDimitry Andric 13380b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1339cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::pop_front() { 134006c3fb27SDimitry Andric _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::pop_front() called with empty list"); 13410b57cec5SDimitry Andric __link_pointer __n = base::__end_.__next_; 13420b57cec5SDimitry Andric base::__unlink_nodes(__n, __n); 13430b57cec5SDimitry Andric --base::__sz(); 13445f757f3fSDimitry Andric this->__delete_node(__n->__as_node()); 13450b57cec5SDimitry Andric} 13460b57cec5SDimitry Andric 13470b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1348cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::pop_back() { 134906c3fb27SDimitry Andric _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::pop_back() called on an empty list"); 13500b57cec5SDimitry Andric __link_pointer __n = base::__end_.__prev_; 13510b57cec5SDimitry Andric base::__unlink_nodes(__n, __n); 13520b57cec5SDimitry Andric --base::__sz(); 13535f757f3fSDimitry Andric this->__delete_node(__n->__as_node()); 13540b57cec5SDimitry Andric} 13550b57cec5SDimitry Andric 13560b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1357cb14a3feSDimitry Andrictypename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::erase(const_iterator __p) { 1358cb14a3feSDimitry Andric _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__p != end(), "list::erase(iterator) called with a non-dereferenceable iterator"); 13590b57cec5SDimitry Andric __link_pointer __n = __p.__ptr_; 13600b57cec5SDimitry Andric __link_pointer __r = __n->__next_; 13610b57cec5SDimitry Andric base::__unlink_nodes(__n, __n); 13620b57cec5SDimitry Andric --base::__sz(); 13635f757f3fSDimitry Andric this->__delete_node(__n->__as_node()); 136406c3fb27SDimitry Andric return iterator(__r); 13650b57cec5SDimitry Andric} 13660b57cec5SDimitry Andric 13670b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1368cb14a3feSDimitry Andrictypename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l) { 1369cb14a3feSDimitry Andric if (__f != __l) { 13700b57cec5SDimitry Andric base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_); 1371cb14a3feSDimitry Andric while (__f != __l) { 13720b57cec5SDimitry Andric __link_pointer __n = __f.__ptr_; 13730b57cec5SDimitry Andric ++__f; 13740b57cec5SDimitry Andric --base::__sz(); 13755f757f3fSDimitry Andric this->__delete_node(__n->__as_node()); 13760b57cec5SDimitry Andric } 13770b57cec5SDimitry Andric } 137806c3fb27SDimitry Andric return iterator(__l.__ptr_); 13790b57cec5SDimitry Andric} 13800b57cec5SDimitry Andric 13810b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1382cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::resize(size_type __n) { 13830b57cec5SDimitry Andric if (__n < base::__sz()) 13840b57cec5SDimitry Andric erase(__iterator(__n), end()); 1385cb14a3feSDimitry Andric else if (__n > base::__sz()) { 13860b57cec5SDimitry Andric __n -= base::__sz(); 13870b57cec5SDimitry Andric size_type __ds = 0; 13885f757f3fSDimitry Andric __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr); 13890b57cec5SDimitry Andric ++__ds; 13905f757f3fSDimitry Andric iterator __r = iterator(__node->__as_link()); 13910b57cec5SDimitry Andric iterator __e = __r; 139206c3fb27SDimitry Andric#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1393cb14a3feSDimitry Andric try { 139406c3fb27SDimitry Andric#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1395cb14a3feSDimitry Andric for (--__n; __n != 0; --__n, (void)++__e, ++__ds) { 13965f757f3fSDimitry Andric __e.__ptr_->__next_ = this->__create_node(/* prev = */ __e.__ptr_, /* next = */ nullptr)->__as_link(); 13970b57cec5SDimitry Andric } 139806c3fb27SDimitry Andric#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1399cb14a3feSDimitry Andric } catch (...) { 1400cb14a3feSDimitry Andric while (true) { 14010b57cec5SDimitry Andric __link_pointer __prev = __e.__ptr_->__prev_; 14025f757f3fSDimitry Andric __node_pointer __current = __e.__ptr_->__as_node(); 14035f757f3fSDimitry Andric this->__delete_node(__current); 14040b57cec5SDimitry Andric if (__prev == 0) 14050b57cec5SDimitry Andric break; 140606c3fb27SDimitry Andric __e = iterator(__prev); 14070b57cec5SDimitry Andric } 14080b57cec5SDimitry Andric throw; 14090b57cec5SDimitry Andric } 141006c3fb27SDimitry Andric#endif // _LIBCPP_HAS_NO_EXCEPTIONS 14110b57cec5SDimitry Andric __link_nodes_at_back(__r.__ptr_, __e.__ptr_); 14120b57cec5SDimitry Andric base::__sz() += __ds; 14130b57cec5SDimitry Andric } 14140b57cec5SDimitry Andric} 14150b57cec5SDimitry Andric 14160b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1417cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x) { 14180b57cec5SDimitry Andric if (__n < base::__sz()) 14190b57cec5SDimitry Andric erase(__iterator(__n), end()); 1420cb14a3feSDimitry Andric else if (__n > base::__sz()) { 14210b57cec5SDimitry Andric __n -= base::__sz(); 14220b57cec5SDimitry Andric size_type __ds = 0; 14235f757f3fSDimitry Andric __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x); 14240b57cec5SDimitry Andric ++__ds; 14255f757f3fSDimitry Andric __link_pointer __nl = __node->__as_link(); 142606c3fb27SDimitry Andric iterator __r = iterator(__nl); 14270b57cec5SDimitry Andric iterator __e = __r; 142806c3fb27SDimitry Andric#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1429cb14a3feSDimitry Andric try { 143006c3fb27SDimitry Andric#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1431cb14a3feSDimitry Andric for (--__n; __n != 0; --__n, (void)++__e, ++__ds) { 14325f757f3fSDimitry Andric __e.__ptr_->__next_ = this->__create_node(/* prev = */ __e.__ptr_, /* next = */ nullptr, __x)->__as_link(); 14330b57cec5SDimitry Andric } 143406c3fb27SDimitry Andric#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1435cb14a3feSDimitry Andric } catch (...) { 1436cb14a3feSDimitry Andric while (true) { 14370b57cec5SDimitry Andric __link_pointer __prev = __e.__ptr_->__prev_; 14385f757f3fSDimitry Andric __node_pointer __current = __e.__ptr_->__as_node(); 14395f757f3fSDimitry Andric this->__delete_node(__current); 14400b57cec5SDimitry Andric if (__prev == 0) 14410b57cec5SDimitry Andric break; 144206c3fb27SDimitry Andric __e = iterator(__prev); 14430b57cec5SDimitry Andric } 14440b57cec5SDimitry Andric throw; 14450b57cec5SDimitry Andric } 144606c3fb27SDimitry Andric#endif // _LIBCPP_HAS_NO_EXCEPTIONS 14470b57cec5SDimitry Andric __link_nodes(base::__end_as_link(), __r.__ptr_, __e.__ptr_); 14480b57cec5SDimitry Andric base::__sz() += __ds; 14490b57cec5SDimitry Andric } 14500b57cec5SDimitry Andric} 14510b57cec5SDimitry Andric 14520b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1453cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::splice(const_iterator __p, list& __c) { 1454cb14a3feSDimitry Andric _LIBCPP_ASSERT_VALID_INPUT_RANGE( 1455cb14a3feSDimitry Andric this != std::addressof(__c), "list::splice(iterator, list) called with this == &list"); 1456cb14a3feSDimitry Andric if (!__c.empty()) { 14570b57cec5SDimitry Andric __link_pointer __f = __c.__end_.__next_; 14580b57cec5SDimitry Andric __link_pointer __l = __c.__end_.__prev_; 14590b57cec5SDimitry Andric base::__unlink_nodes(__f, __l); 14600b57cec5SDimitry Andric __link_nodes(__p.__ptr_, __f, __l); 14610b57cec5SDimitry Andric base::__sz() += __c.__sz(); 14620b57cec5SDimitry Andric __c.__sz() = 0; 14630b57cec5SDimitry Andric } 14640b57cec5SDimitry Andric} 14650b57cec5SDimitry Andric 14660b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1467cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i) { 1468cb14a3feSDimitry Andric if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_) { 14690b57cec5SDimitry Andric __link_pointer __f = __i.__ptr_; 14700b57cec5SDimitry Andric base::__unlink_nodes(__f, __f); 14710b57cec5SDimitry Andric __link_nodes(__p.__ptr_, __f, __f); 14720b57cec5SDimitry Andric --__c.__sz(); 14730b57cec5SDimitry Andric ++base::__sz(); 14740b57cec5SDimitry Andric } 14750b57cec5SDimitry Andric} 14760b57cec5SDimitry Andric 14770b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1478cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l) { 1479cb14a3feSDimitry Andric if (__f != __l) { 14800b57cec5SDimitry Andric __link_pointer __first = __f.__ptr_; 14810b57cec5SDimitry Andric --__l; 14820b57cec5SDimitry Andric __link_pointer __last = __l.__ptr_; 1483cb14a3feSDimitry Andric if (this != std::addressof(__c)) { 14845f757f3fSDimitry Andric size_type __s = std::distance(__f, __l) + 1; 14850b57cec5SDimitry Andric __c.__sz() -= __s; 14860b57cec5SDimitry Andric base::__sz() += __s; 14870b57cec5SDimitry Andric } 14880b57cec5SDimitry Andric base::__unlink_nodes(__first, __last); 14890b57cec5SDimitry Andric __link_nodes(__p.__ptr_, __first, __last); 14900b57cec5SDimitry Andric } 14910b57cec5SDimitry Andric} 14920b57cec5SDimitry Andric 14930b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1494cb14a3feSDimitry Andrictypename list<_Tp, _Alloc>::__remove_return_type list<_Tp, _Alloc>::remove(const value_type& __x) { 14950b57cec5SDimitry Andric list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing 1496cb14a3feSDimitry Andric for (const_iterator __i = begin(), __e = end(); __i != __e;) { 1497cb14a3feSDimitry Andric if (*__i == __x) { 14985f757f3fSDimitry Andric const_iterator __j = std::next(__i); 14990b57cec5SDimitry Andric for (; __j != __e && *__j == __x; ++__j) 15000b57cec5SDimitry Andric ; 15010b57cec5SDimitry Andric __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j); 15020b57cec5SDimitry Andric __i = __j; 15030b57cec5SDimitry Andric if (__i != __e) 15040b57cec5SDimitry Andric ++__i; 1505cb14a3feSDimitry Andric } else 15060b57cec5SDimitry Andric ++__i; 15070b57cec5SDimitry Andric } 15080b57cec5SDimitry Andric 15090b57cec5SDimitry Andric return (__remove_return_type)__deleted_nodes.size(); 15100b57cec5SDimitry Andric} 15110b57cec5SDimitry Andric 15120b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 15130b57cec5SDimitry Andrictemplate <class _Pred> 1514cb14a3feSDimitry Andrictypename list<_Tp, _Alloc>::__remove_return_type list<_Tp, _Alloc>::remove_if(_Pred __pred) { 15150b57cec5SDimitry Andric list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing 1516cb14a3feSDimitry Andric for (iterator __i = begin(), __e = end(); __i != __e;) { 1517cb14a3feSDimitry Andric if (__pred(*__i)) { 15185f757f3fSDimitry Andric iterator __j = std::next(__i); 15190b57cec5SDimitry Andric for (; __j != __e && __pred(*__j); ++__j) 15200b57cec5SDimitry Andric ; 15210b57cec5SDimitry Andric __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j); 15220b57cec5SDimitry Andric __i = __j; 15230b57cec5SDimitry Andric if (__i != __e) 15240b57cec5SDimitry Andric ++__i; 1525cb14a3feSDimitry Andric } else 15260b57cec5SDimitry Andric ++__i; 15270b57cec5SDimitry Andric } 15280b57cec5SDimitry Andric 15290b57cec5SDimitry Andric return (__remove_return_type)__deleted_nodes.size(); 15300b57cec5SDimitry Andric} 15310b57cec5SDimitry Andric 15320b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 15330b57cec5SDimitry Andrictemplate <class _BinaryPred> 1534cb14a3feSDimitry Andrictypename list<_Tp, _Alloc>::__remove_return_type list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred) { 15350b57cec5SDimitry Andric list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing 1536cb14a3feSDimitry Andric for (iterator __i = begin(), __e = end(); __i != __e;) { 15375f757f3fSDimitry Andric iterator __j = std::next(__i); 15380b57cec5SDimitry Andric for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 15390b57cec5SDimitry Andric ; 15400b57cec5SDimitry Andric if (++__i != __j) { 15410b57cec5SDimitry Andric __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j); 15420b57cec5SDimitry Andric __i = __j; 15430b57cec5SDimitry Andric } 15440b57cec5SDimitry Andric } 15450b57cec5SDimitry Andric 15460b57cec5SDimitry Andric return (__remove_return_type)__deleted_nodes.size(); 15470b57cec5SDimitry Andric} 15480b57cec5SDimitry Andric 15490b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1550cb14a3feSDimitry Andricinline void list<_Tp, _Alloc>::merge(list& __c) { 155106c3fb27SDimitry Andric merge(__c, __less<>()); 15520b57cec5SDimitry Andric} 15530b57cec5SDimitry Andric 15540b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 15550b57cec5SDimitry Andrictemplate <class _Comp> 1556cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::merge(list& __c, _Comp __comp) { 1557cb14a3feSDimitry Andric if (this != std::addressof(__c)) { 15580b57cec5SDimitry Andric iterator __f1 = begin(); 15590b57cec5SDimitry Andric iterator __e1 = end(); 15600b57cec5SDimitry Andric iterator __f2 = __c.begin(); 15610b57cec5SDimitry Andric iterator __e2 = __c.end(); 1562cb14a3feSDimitry Andric while (__f1 != __e1 && __f2 != __e2) { 1563cb14a3feSDimitry Andric if (__comp(*__f2, *__f1)) { 15640b57cec5SDimitry Andric size_type __ds = 1; 15655f757f3fSDimitry Andric iterator __m2 = std::next(__f2); 1566349cc55cSDimitry Andric for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, (void)++__ds) 15670b57cec5SDimitry Andric ; 15680b57cec5SDimitry Andric base::__sz() += __ds; 15690b57cec5SDimitry Andric __c.__sz() -= __ds; 15700b57cec5SDimitry Andric __link_pointer __f = __f2.__ptr_; 15710b57cec5SDimitry Andric __link_pointer __l = __m2.__ptr_->__prev_; 15720b57cec5SDimitry Andric __f2 = __m2; 15730b57cec5SDimitry Andric base::__unlink_nodes(__f, __l); 15745f757f3fSDimitry Andric __m2 = std::next(__f1); 15750b57cec5SDimitry Andric __link_nodes(__f1.__ptr_, __f, __l); 15760b57cec5SDimitry Andric __f1 = __m2; 1577cb14a3feSDimitry Andric } else 15780b57cec5SDimitry Andric ++__f1; 15790b57cec5SDimitry Andric } 15800b57cec5SDimitry Andric splice(__e1, __c); 15810b57cec5SDimitry Andric } 15820b57cec5SDimitry Andric} 15830b57cec5SDimitry Andric 15840b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1585cb14a3feSDimitry Andricinline void list<_Tp, _Alloc>::sort() { 158606c3fb27SDimitry Andric sort(__less<>()); 15870b57cec5SDimitry Andric} 15880b57cec5SDimitry Andric 15890b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 15900b57cec5SDimitry Andrictemplate <class _Comp> 1591cb14a3feSDimitry Andricinline void list<_Tp, _Alloc>::sort(_Comp __comp) { 15920b57cec5SDimitry Andric __sort(begin(), end(), base::__sz(), __comp); 15930b57cec5SDimitry Andric} 15940b57cec5SDimitry Andric 15950b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 15960b57cec5SDimitry Andrictemplate <class _Comp> 15970b57cec5SDimitry Andrictypename list<_Tp, _Alloc>::iterator 1598cb14a3feSDimitry Andriclist<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp) { 1599cb14a3feSDimitry Andric switch (__n) { 16000b57cec5SDimitry Andric case 0: 16010b57cec5SDimitry Andric case 1: 16020b57cec5SDimitry Andric return __f1; 16030b57cec5SDimitry Andric case 2: 1604cb14a3feSDimitry Andric if (__comp(*--__e2, *__f1)) { 16050b57cec5SDimitry Andric __link_pointer __f = __e2.__ptr_; 16060b57cec5SDimitry Andric base::__unlink_nodes(__f, __f); 16070b57cec5SDimitry Andric __link_nodes(__f1.__ptr_, __f, __f); 16080b57cec5SDimitry Andric return __e2; 16090b57cec5SDimitry Andric } 16100b57cec5SDimitry Andric return __f1; 16110b57cec5SDimitry Andric } 16120b57cec5SDimitry Andric size_type __n2 = __n / 2; 16135f757f3fSDimitry Andric iterator __e1 = std::next(__f1, __n2); 16140b57cec5SDimitry Andric iterator __r = __f1 = __sort(__f1, __e1, __n2, __comp); 16150b57cec5SDimitry Andric iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp); 1616cb14a3feSDimitry Andric if (__comp(*__f2, *__f1)) { 16175f757f3fSDimitry Andric iterator __m2 = std::next(__f2); 16180b57cec5SDimitry Andric for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 16190b57cec5SDimitry Andric ; 16200b57cec5SDimitry Andric __link_pointer __f = __f2.__ptr_; 16210b57cec5SDimitry Andric __link_pointer __l = __m2.__ptr_->__prev_; 16220b57cec5SDimitry Andric __r = __f2; 16230b57cec5SDimitry Andric __e1 = __f2 = __m2; 16240b57cec5SDimitry Andric base::__unlink_nodes(__f, __l); 16255f757f3fSDimitry Andric __m2 = std::next(__f1); 16260b57cec5SDimitry Andric __link_nodes(__f1.__ptr_, __f, __l); 16270b57cec5SDimitry Andric __f1 = __m2; 1628cb14a3feSDimitry Andric } else 16290b57cec5SDimitry Andric ++__f1; 1630cb14a3feSDimitry Andric while (__f1 != __e1 && __f2 != __e2) { 1631cb14a3feSDimitry Andric if (__comp(*__f2, *__f1)) { 16325f757f3fSDimitry Andric iterator __m2 = std::next(__f2); 16330b57cec5SDimitry Andric for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 16340b57cec5SDimitry Andric ; 16350b57cec5SDimitry Andric __link_pointer __f = __f2.__ptr_; 16360b57cec5SDimitry Andric __link_pointer __l = __m2.__ptr_->__prev_; 16370b57cec5SDimitry Andric if (__e1 == __f2) 16380b57cec5SDimitry Andric __e1 = __m2; 16390b57cec5SDimitry Andric __f2 = __m2; 16400b57cec5SDimitry Andric base::__unlink_nodes(__f, __l); 16415f757f3fSDimitry Andric __m2 = std::next(__f1); 16420b57cec5SDimitry Andric __link_nodes(__f1.__ptr_, __f, __l); 16430b57cec5SDimitry Andric __f1 = __m2; 1644cb14a3feSDimitry Andric } else 16450b57cec5SDimitry Andric ++__f1; 16460b57cec5SDimitry Andric } 16470b57cec5SDimitry Andric return __r; 16480b57cec5SDimitry Andric} 16490b57cec5SDimitry Andric 16500b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1651cb14a3feSDimitry Andricvoid list<_Tp, _Alloc>::reverse() _NOEXCEPT { 1652cb14a3feSDimitry Andric if (base::__sz() > 1) { 16530b57cec5SDimitry Andric iterator __e = end(); 1654cb14a3feSDimitry Andric for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;) { 16555f757f3fSDimitry Andric std::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_); 16560b57cec5SDimitry Andric __i.__ptr_ = __i.__ptr_->__prev_; 16570b57cec5SDimitry Andric } 16585f757f3fSDimitry Andric std::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_); 16590b57cec5SDimitry Andric } 16600b57cec5SDimitry Andric} 16610b57cec5SDimitry Andric 16620b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1663cb14a3feSDimitry Andricbool list<_Tp, _Alloc>::__invariants() const { 16645f757f3fSDimitry Andric return size() == std::distance(begin(), end()); 16650b57cec5SDimitry Andric} 16660b57cec5SDimitry Andric 16670b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1668cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) { 16695f757f3fSDimitry Andric return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); 16700b57cec5SDimitry Andric} 16710b57cec5SDimitry Andric 167206c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17 167306c3fb27SDimitry Andric 16740b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1675cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) { 16765f757f3fSDimitry Andric return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 16770b57cec5SDimitry Andric} 16780b57cec5SDimitry Andric 16790b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1680cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) { 16810b57cec5SDimitry Andric return !(__x == __y); 16820b57cec5SDimitry Andric} 16830b57cec5SDimitry Andric 16840b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1685cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) { 16860b57cec5SDimitry Andric return __y < __x; 16870b57cec5SDimitry Andric} 16880b57cec5SDimitry Andric 16890b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1690cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) { 16910b57cec5SDimitry Andric return !(__x < __y); 16920b57cec5SDimitry Andric} 16930b57cec5SDimitry Andric 16940b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1695cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) { 16960b57cec5SDimitry Andric return !(__y < __x); 16970b57cec5SDimitry Andric} 16980b57cec5SDimitry Andric 169906c3fb27SDimitry Andric#else // _LIBCPP_STD_VER <= 17 170006c3fb27SDimitry Andric 170106c3fb27SDimitry Andrictemplate <class _Tp, class _Allocator> 170206c3fb27SDimitry Andric_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Tp> 170306c3fb27SDimitry Andricoperator<=>(const list<_Tp, _Allocator>& __x, const list<_Tp, _Allocator>& __y) { 170406c3fb27SDimitry Andric return std::lexicographical_compare_three_way( 170506c3fb27SDimitry Andric __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way<_Tp, _Tp>); 170606c3fb27SDimitry Andric} 170706c3fb27SDimitry Andric 170806c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER <= 17 170906c3fb27SDimitry Andric 17100b57cec5SDimitry Andrictemplate <class _Tp, class _Alloc> 1711cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) 1712cb14a3feSDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 17130b57cec5SDimitry Andric __x.swap(__y); 17140b57cec5SDimitry Andric} 17150b57cec5SDimitry Andric 171606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 17170b57cec5SDimitry Andrictemplate <class _Tp, class _Allocator, class _Predicate> 17185f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI typename list<_Tp, _Allocator>::size_type 17195ffd83dbSDimitry Andricerase_if(list<_Tp, _Allocator>& __c, _Predicate __pred) { 17205ffd83dbSDimitry Andric return __c.remove_if(__pred); 17215ffd83dbSDimitry Andric} 17220b57cec5SDimitry Andric 17230b57cec5SDimitry Andrictemplate <class _Tp, class _Allocator, class _Up> 17245f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI typename list<_Tp, _Allocator>::size_type 17255ffd83dbSDimitry Andricerase(list<_Tp, _Allocator>& __c, const _Up& __v) { 17265f757f3fSDimitry Andric return std::erase_if(__c, [&](auto& __elem) { return __elem == __v; }); 17275ffd83dbSDimitry Andric} 172881ad6265SDimitry Andric 172981ad6265SDimitry Andrictemplate <> 173081ad6265SDimitry Andricinline constexpr bool __format::__enable_insertable<std::list<char>> = true; 173181ad6265SDimitry Andric# ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 173281ad6265SDimitry Andrictemplate <> 173381ad6265SDimitry Andricinline constexpr bool __format::__enable_insertable<std::list<wchar_t>> = true; 17340b57cec5SDimitry Andric# endif 17350b57cec5SDimitry Andric 173606c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 173781ad6265SDimitry Andric 17380b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD 17390b57cec5SDimitry Andric 174006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 1741bdd1243dSDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 1742bdd1243dSDimitry Andricnamespace pmr { 1743bdd1243dSDimitry Andrictemplate <class _ValueT> 174406c3fb27SDimitry Andricusing list _LIBCPP_AVAILABILITY_PMR = std::list<_ValueT, polymorphic_allocator<_ValueT>>; 1745bdd1243dSDimitry Andric} // namespace pmr 1746bdd1243dSDimitry Andric_LIBCPP_END_NAMESPACE_STD 1747bdd1243dSDimitry Andric#endif 1748bdd1243dSDimitry Andric 17490b57cec5SDimitry Andric_LIBCPP_POP_MACROS 17500b57cec5SDimitry Andric 1751bdd1243dSDimitry Andric#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 1752bdd1243dSDimitry Andric# include <algorithm> 1753bdd1243dSDimitry Andric# include <atomic> 1754bdd1243dSDimitry Andric# include <concepts> 17555f757f3fSDimitry Andric# include <cstdint> 175606c3fb27SDimitry Andric# include <cstdlib> 1757bdd1243dSDimitry Andric# include <functional> 1758bdd1243dSDimitry Andric# include <iosfwd> 1759bdd1243dSDimitry Andric# include <iterator> 17605f757f3fSDimitry Andric# include <stdexcept> 176106c3fb27SDimitry Andric# include <type_traits> 1762bdd1243dSDimitry Andric# include <typeinfo> 1763bdd1243dSDimitry Andric#endif 1764bdd1243dSDimitry Andric 17650b57cec5SDimitry Andric#endif // _LIBCPP_LIST 1766