3 * - By John Hodge (thePowersGang)
19 template <class ListType, class T> class list_iterator;
20 template <class T> class list_item;
23 template <class T, class Alloc = allocator<T> >
26 typedef ::std::_bits::list_item<T> item_type;
27 typedef ::std::_bits::list_item<const T> const_item_type;
28 friend class ::std::_bits::list_iterator<list, T>;
30 typedef typename Alloc::template rebind<item_type>::other item_allocator;
33 typedef Alloc allocator_type;
34 typedef typename allocator_type::reference reference;
35 typedef typename allocator_type::const_reference const_reference;
36 typedef typename allocator_type::pointer pointer;
37 typedef typename allocator_type::const_pointer const_pointer;
38 typedef _bits::list_iterator<list,T> iterator;
39 typedef _bits::list_iterator<list,const T> const_iterator;
40 typedef int difference_type;
41 typedef size_t size_type;
44 item_allocator m_item_allocator;
45 allocator_type m_allocator;
48 size_type m_item_count;
51 list(const allocator_type& alloc = allocator_type()):
57 list(size_t n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type()):
67 list& operator =(const list& x);
70 return iterator(*this, m_start);
72 const_iterator begin() const {
73 return const_iterator(*this, m_start);
77 return iterator(*this, 0);
79 const_iterator end() const {
80 return const_iterator(*this, 0);
89 size_t max_size() const {
90 return (size_type)-1 / sizeof(item_type);
94 return m_start->value;
96 const T& front() const {
97 return m_start->value;
102 const T& back() const {
106 void assign(size_type n, const value_type& val) {
108 for( size_t i = 0; i < n; i ++ )
114 void push_front(const value_type& val) {
115 insert(front(), val);
120 void push_back(const value_type& val) {
127 template <class... Args>
128 iterator emplace(iterator position, Args&&... args) {
129 item_type *newi = m_item_allocator.allocate(1);
130 m_allocator.construct(&newi->value, ::std::forward<Args>(args)...);
131 return insert_item(position, newi);
134 iterator insert(iterator position, const value_type& val) {
135 item_type *newi = m_item_allocator.allocate(1);
136 m_allocator.construct(&newi->value, val);
137 return insert_item(position, newi);
139 void insert(iterator position, size_type n, const value_type& val) {
140 for( size_type i = 0; i < n; i ++ )
142 position = insert(position, val);
145 iterator erase(iterator position) {
146 if( position == end() ) {
149 item_type *oldi = position.m_cur;
153 oldi->prev->next = oldi->next;
155 m_start = oldi->next;
157 oldi->next->prev = oldi->prev;
162 m_allocator.destroy(&oldi->value);
163 m_item_allocator.deallocate(oldi, 1);
170 item_type* item = m_start;
171 m_start = m_start->next;
177 void splice(iterator position, list& x) {
178 splice(position, x, x.begin(), x.end());
180 void splice(iterator position, list& x, iterator i) {
181 splice(position, x, i, x.end());
183 void splice(iterator position, list& x, iterator first, iterator last);
188 const value_type& m_val;
190 _equal(const value_type& val):
194 bool operator() (const value_type& v1)
200 void remove(const value_type& val) {
201 remove_if(_equal(val));
203 template <class Predicate> void remove_if(Predicate pred) {
204 for( iterator it = begin(); it != end(); )
214 template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
217 template <class Compare> void merge(list& x, Compare comp);
220 template <class Compare> void sort(Compare comp);
222 void reverse() throw();
224 iterator insert_item(iterator position, item_type *newi) {
233 if( position == end() ) {
240 else if( position == begin() ) {
241 newi->next = m_start;
244 m_start->prev = newi;
248 newi->prev = position.m_cur->prev;
249 newi->next = position.m_cur;
250 position.m_cur->prev->next = newi;
251 position.m_cur->prev = newi;
263 typedef T value_type;
269 template <class ListType, class T>
270 class list_iterator//:
271 //public bidirectional_iterator_tag;
273 const ListType* m_list;
277 list_iterator(const list_iterator& x):
282 list_iterator& operator=(const list_iterator& x) {
287 bool operator == (const list_iterator& other) const {
288 return m_cur == other.m_cur;
290 bool operator != (const list_iterator& other) const {
291 return !(*this == other);
300 list_iterator& operator ++ () {
302 throw ::std::logic_error("list iterator ++ on end");
306 list_iterator& operator -- () {
307 if( m_cur == m_list->m_start )
308 throw ::std::logic_error("list iterator -- on start");
310 m_cur = m_list->m_end;
317 list_iterator(const ListType& list, list_item<T> *item):
324 }; // namespace _bits