atlas  0.6
sl_list.h
Go to the documentation of this file.
1 /*
2  This is sl_list.h, a revolutionary singly linked list container type
3 */
4 /*
5  Copyright (C) 2014 Marc van Leeuwen
6  part of the Atlas of Lie Groups and Representations
7 
8  For license information see the LICENSE file
9 */
10 
11 #ifndef SL_LIST_H /* guard against multiple inclusions */
12 #define SL_LIST_H
13 
14 #include <cstddef>
15 #include <cstdlib>
16 #include <memory>
17 #include <iterator>
18 #include <type_traits>
19 #include <initializer_list>
20 
21 #include "tags.h"
22 
23 namespace atlas {
24 
25 namespace containers {
26 
27 template<typename T,typename Alloc = std::allocator<T> >
28  class simple_list;
29 template<typename T,typename Alloc = std::allocator<T> >
30  class sl_list;
31 
32 // when Alloc is not std::allocator, we need a deleter class for |unique_ptr|
33 // that calls the Alloc destroyer and then deallocator, rather than |::delete|
34 
35 template <typename Alloc> struct allocator_deleter
36 : private Alloc
37 { typedef typename Alloc::value_type value_type;
38  typedef typename Alloc::pointer pointer;
39 
40  constexpr allocator_deleter () = default;
41  allocator_deleter (const allocator_deleter&) = default;
42  void operator() (pointer p)
43  {
44 #ifdef incompletecpp11
45  if (p!=pointer())
46  {
47  this->destroy(&*p);
48  this->deallocate(p,1);
49  }
50 #else
51  this->destroy(std::addressof(*p));
52  this->deallocate(p,1);
53 #endif
54  }
55 };
56 
57 // exception safe replacement of (non-placement) |::new| for use with |Alloc|
58 template <typename Alloc, typename... Args>
59  typename Alloc::value_type *
60  allocator_new(Alloc& a, Args&&... args)
61 {
62  typedef typename Alloc::value_type value_type;
63  typedef typename Alloc::pointer pointer;
64 
65  pointer qq = a.allocate(1);
66  try
67  {
68 #ifdef incompletecpp11
69  value_type* q=&*qq; // this ought not throw
70 #else
71  value_type* q=std::addressof(*qq); // this ought not throw
72 #endif
73  a.construct(q,std::forward<Args>(args)...);
74  return q;
75  }
76  catch(...) // exception safety for throwing |construct|, as |::new| does
77  {
78  a.deallocate(qq,1);
79  throw;
80  }
81 }
82 /* The basic node type used by |simple_list| and |sl_list|
83  It needs the Alloc template parameter to paramaterise |std::unique_ptr|
84  */
85 template<typename T,typename Alloc = std::allocator<T> >
86 struct sl_node
87 {
88  typedef typename Alloc::template rebind<sl_node>::other alloc_type;
89  typedef std::unique_ptr<sl_node, allocator_deleter<alloc_type> > link_type;
90 
91  link_type next;
93 
94 sl_node(const T& contents) : next(nullptr), contents(contents) {}
95 sl_node(T&& contents) : next(nullptr), contents(std::move(contents)) {}
96  template<typename... Args> sl_node(Args&&... args)
97  : next(nullptr), contents(std::forward<Args>(args)...) {}
98 
99  sl_node(const sl_node&) = delete;
100  sl_node(sl_node&&) = default;
101  ~sl_node() // dtor could be empty, but would imply recursive destruction
102  { while (next.get()!=nullptr) // this loop bounds recursion depth to 2
103  next.reset(next->next.release()); // destroys just the following node
104  }
105 }; // |class sl_node| template
106 
107 template<typename T,typename Alloc> class sl_list_iterator;
108 template<typename T, typename Alloc = std::allocator<T> >
110  : public std::iterator<std::forward_iterator_tag, T>
111 {
112  friend class simple_list<T,Alloc>;
113  friend class sl_list<T,Alloc>;
114  friend class sl_list_iterator<T,Alloc>; // lest |link_loc| needs |protected|
115 
117 
118 private:
120 
121  // data
122  link_type* link_loc; // pointer to link field
123 
124 public:
125  // constructors
126  sl_list_const_iterator() : link_loc(nullptr) {} // default iterator is invalid
127  explicit sl_list_const_iterator(const link_type& link)
128  /* the following const_cast is safe because not exploitable using a mere
129  |const_iterator|; only used for |insert| and |erase| manipulators */
130  : link_loc(const_cast<link_type*>(&link)) {}
131 
132  // contents access methods; return |const| ref/ptr for |const_iterator|
133  const T& operator*() const { return (*link_loc)->contents; }
134  const T* operator->() const { return &(*link_loc)->contents; }
135 
136  self operator++() { link_loc = &(*link_loc)->next; return *this; }
137  self operator++(int) // post-increment
138  { self tmp=*this; link_loc = &(*link_loc)->next; return tmp; }
139 
140  // equality testing methods
141  bool operator==(const self& x) const { return link_loc == x.link_loc; }
142  bool operator!=(const self& x) const { return link_loc != x.link_loc; }
143 
144  bool at_end () const { return *link_loc==nullptr; }
145 }; // |struct sl_list_const_iterator| template
146 
147 
148 template<typename T,typename Alloc = std::allocator<T> >
149 class sl_list_iterator : public sl_list_const_iterator<T,Alloc>
150 {
151  friend class simple_list<T,Alloc>;
152  friend class sl_list<T,Alloc>;
153 
156 
157  // no extra data
158 
159 public:
160  // constructors
161  sl_list_iterator() : Base() {}
162  explicit sl_list_iterator(typename Base::link_type& link) : Base(link) {}
163 
164  // contents access methods; these override the base, return non-const ref/ptr
165  T& operator*() const { return (*Base::link_loc)->contents; }
166  T* operator->() const { return &(*Base::link_loc)->contents; }
167 
168  // increment operators also need overload, with covariant return type
169  self operator++() { Base::operator++(); return *this; }
170  self operator++(int) // post-increment
171  { self tmp=*this; Base::operator++(nullptr); return tmp; }
172 }; // |struct sl_list_iterator| template
173 
174 template<typename T, typename Alloc> struct weak_sl_list_iterator;
175 template<typename T, typename Alloc = std::allocator<T> >
177  : public std::iterator<std::forward_iterator_tag, T>
178 {
179  friend class weak_sl_list_iterator<T,Alloc>;
180  typedef sl_node<T,Alloc>* link_type; // here: a raw pointer
182 
183 private:
185 
186  // data
187  link_type link; // pointer to non-const, but only expoilitable by derived
188 
189 public:
190  // constructors
191  weak_sl_list_const_iterator() : link(nullptr) {} // default iterator: end
192  explicit weak_sl_list_const_iterator(const_link_type p)
193  /* the following const_cast is safe because not exploitable using a mere
194  |const_iterator|; only used to allow weak_iterator to be derived */
195  : link(const_cast<link_type>(p)) {}
196 
197  // contents access methods; return |const| ref/ptr for |const_iterator|
198  const T& operator*() const { return link->contents; }
199  const T* operator->() const { return &link->contents; }
200 
201  self operator++() { link = link->next.get(); return *this; }
202  self operator++(int) // post-increment
203  { self tmp=*this; link = link->next.get(); return tmp; }
204 
205  // equality testing methods
206  bool operator==(const self& x) const { return link == x.link; }
207  bool operator!=(const self& x) const { return link != x.link; }
208 
209  bool at_end () const { return link==nullptr; }
210 }; // |struct weak_sl_list_const_iterator| template
211 
212 
213 // weak iterators allow acces to list elements but not to the list structure
214 // so no insert/delete are possible using weak iterators
215 
216 template<typename T,typename Alloc = std::allocator<T> >
218  : public weak_sl_list_const_iterator<T,Alloc>
219 {
222 
223  // no extra data
224 
225 public:
226  // constructors
227  weak_sl_list_iterator() : Base() {} // default iterator: end
228  explicit weak_sl_list_iterator(typename Base::link_type p): Base(p) {}
229 
230  // contents access methods; return non-const ref/ptr
231  T& operator*() const { return Base::link->contents; }
232  T* operator->() const { return &Base::link->contents; }
233 
234  self operator++() { Base::link = Base::link->next.get(); return *this; }
235  self operator++(int) // post-increment
236  { self tmp=*this; Base::link = Base::link->next.get(); return tmp; }
237  // for other methods, including equality tests, use the Base methods
238 }; // |struct weak_sl_list_iterator| template
239 
240 
241 
242 
243 
244 /* Simple singly linked list, without |size| or |push_back| method */
245 
246 template<typename T, typename Alloc>
247  class simple_list
248  : private Alloc::template rebind<sl_node<T, Alloc> >::other
249 {
250  friend class sl_list<T, Alloc>;
251 
253  typedef typename Alloc::template rebind<node_type>::other alloc_type;
254  typedef typename Alloc::pointer node_ptr; // returned from |allocate|
255  typedef std::unique_ptr<node_type, allocator_deleter<alloc_type> > link_type;
256 
257 
258 
259  public:
260  typedef T value_type;
261  typedef std::size_t size_type;
262  typedef std::ptrdiff_t difference_type;
263  typedef value_type& reference;
264  typedef const value_type& const_reference;
265  typedef value_type* pointer;
266  typedef const value_type* const_pointer;
267 
272 
273  // data
274  private:
275  link_type head; // owns the first (if any), and recursively all nodes
276 
277  // constructors
278  public:
279  explicit simple_list () // empty list
280  : alloc_type(), head(nullptr) {}
281 
282  explicit simple_list (const alloc_type& a) // empty list, explicit allocator
283  : alloc_type(a), head(nullptr) {}
284 
285  explicit simple_list (alloc_type&& a) // empty list, explicit moved allocator
286  : alloc_type(std::move(a)), head(nullptr) {}
287 
288  explicit simple_list (node_type* raw) // convert from raw pointer
289  : alloc_type(), head(raw) {}
290 
291  explicit simple_list (node_type* raw,const alloc_type& a)
292  : alloc_type(a), head(raw) {}
293 
294  explicit simple_list (node_type* raw, alloc_type&& a)
295  : alloc_type(std::move(a)), head(raw) {}
296 
297  simple_list (const simple_list& x) // copy contructor
298  : alloc_type(x) // nothing better available with gcc 4.6
299  , head(nullptr)
300  {
301  link_type* tail = &head;
302  for (node_type* p=x.head.get(); p!=nullptr; p=p->next.get())
303  {
304  node_type* q = allocator_new(node_allocator(),p->contents);
305  tail->reset(q); // link in new final node
306  tail=&q->next; // point |tail| to its link field, to append there next
307  }
308  }
309 
310  simple_list (simple_list&& x) // move contructor
311  : alloc_type(std::move(x)), head(x.head.release())
312  { }
313 
314  template<typename InputIt, typename = typename std::enable_if<
315  std::is_base_of<std::input_iterator_tag,
316  typename std::iterator_traits<InputIt>::iterator_category
317  >::value>::type >
318  simple_list (InputIt first, InputIt last, const alloc_type& a=alloc_type())
319  : alloc_type(a), head(nullptr)
320  {
321  assign(first,last);
322  }
323 
324  simple_list (size_type n, const alloc_type& a=alloc_type())
325  : alloc_type(a), head(nullptr)
326  {
327  while (n-->0)
328  {
329  // construct new node with default constructed value
330  node_type* p = allocator_new(node_allocator());
331  p->next = std::move(head);
332  head.reset(p); // splice in new node
333  }
334  }
335 
336  simple_list (size_type n, const T& x, const alloc_type& a=alloc_type())
337  : alloc_type(a), head(nullptr)
338  {
339  assign(n,x);
340  }
341 
342  simple_list (std::initializer_list<T> l, const alloc_type& a=alloc_type())
343  : alloc_type(a), head(nullptr)
344  {
345  assign(l.begin(),l.end());
346  }
347 
348  ~simple_list() {} // when called, |head| is already destructed/cleaned up
349 
350  simple_list& operator= (const simple_list& x)
351  {
352  if (this!=&x) // self-assign is useless, though it would be safe
353  { // reuse existing nodes when possible
354  iterator p = begin();
355  node_type* q=x.head.get(); // maybe more efficient than an iterator
356  if (get_node_allocator() != x.get_node_allocator())
357  { // our old nodes need to be destroyed by our old allocator
358  clear(); // so we cannot reuse any of them: destroy them now
359  node_allocator() = x.get_node_allocator(); // now transfer allocator
360  }
361  else // now copy contents for as many nodes as possible
362  for ( ; not at_end(p) and q!=nullptr; ++p, q=q->next.get())
363  *p = q->contents;
364 
365  if (at_end(p)) // certainly true if previous condition was
366  for ( ; q!=nullptr; ++p, q=q->next.get()) // |insert(p,q->contents)|
367  p.link_loc->reset(allocator_new(node_allocator(),q->contents));
368  else // |q| was exhausted before |p|; we need to truncate after |p|
369  p.link_loc->reset();
370  }
371  return *this;
372  }
373 
374  simple_list& operator= (simple_list&& x)
375  { // self-assignment is safe, because safe for |std::unique_ptr| instances
376  if (get_node_allocator() == x.get_node_allocator() )
377  { // it is safe to just move the head pointer
378  // the next call starts clearing |*this|, except when |get()==x.get()|
379  head = std::move(x.head); // unique_ptr move assignment
380  if (false) // correct condition cannot be formulated with gcc 4.6
381  node_allocator() = std::move(x.node_allocator());
382  }
383  else // allocators differ and cannot be moved; so move node contents
384  { // effectively |move_assign(x.begin(),end(x));|
385  iterator p = begin();
386  node_type* q=x.head.get(); // maybe more efficient than an iterator
387  for ( ; not at_end(p) and q!=nullptr; ++p, q=q->next.get())
388  *p = std::move(q->contents);
389  if (at_end(p))
390  for ( ; q!=nullptr; ++p, q=q->next.get()) // |insert(p,q->contents)|
391  p.link_loc->reset
392  (allocator_new(node_allocator(),std::move(q->contents)));
393  else // |q| was exhausted before |p|; we need to truncate after |p|
394  p.link_loc->reset();
395  }
396  return *this;
397  }
398 
399  void swap (simple_list& other)
400  {
401  if (get_node_allocator() == other.get_node_allocator() )
402  { // easy case; swap head pointers and swap allocators
403  head.swap(other.head); // swap |std::unique_ptr| instances
404  using std::swap; // ensure some swap method will be found
405  swap(node_allocator(),other.node_allocator());
406  }
407  else // we must really exchange contents
408  {
409  iterator p=begin(), q=other.begin();
410  using std::swap;
411  for ( ; not (at_end(p) or at_end(q)); ++p,++q)
412  swap(*p,*q);
413  if (at_end(p))
414  while (not at_end(q))
415  {
416  insert(p,std::move(*q)); // move contents from node |q| points to
417  other.erase(q); // equivalent to |q=other.erase(q);|
418  }
419  else // now |at_end(q)|
420  while (not at_end(p))
421  {
422  other.insert(q,std::move(*p)); // move from node |p| points to
423  erase(p); // equivalent to |p=erase(p);|
424  }
425  }
426  }
427 
428  node_type* release() { return head.release(); } // convert to raw pointer
429 
430  // access to the allocator
431  const alloc_type& get_node_allocator () const { return *this; }
432  alloc_type& node_allocator () { return *this; }
433 
434  //iterators
435  iterator begin() { return iterator(head); }
436  weak_iterator wbegin() { return weak_iterator(head.get()); }
437 
438  T& front () { return head->contents; }
439  void pop_front ()
440  { head.reset(head->next.release()); }
441 
442  void push_front (const T& val)
443  {
444  // construct node value
445  node_type* p = allocator_new(node_allocator(),val);
446  p->next.reset(head.release()); // link trailing nodes here
447  head.reset(p); // make new node the first one in the list
448  }
449 
450  void push_front (T&& val)
451  {
452  // construct node value
453  node_type* p = allocator_new(node_allocator(),std::move(val));
454  p->next.reset(head.release()); // link trailing nodes here
455  head.reset(p); // make new node the first one in the list
456  }
457 
458  template<typename... Args>
459  void emplace_front (Args&&... args)
460  {
461  // construct node value
462  node_type* p =
463  allocator_new(node_allocator(),std::forward<Args>(args)...);
464  p->next.reset(head.release()); // link trailing nodes here
465  head.reset(p); // make new node the first one in the list
466  }
467 
468  bool empty () const { return head.get()==nullptr; }
469  bool singleton () const { return not empty() and head->next.get()==nullptr; }
470 
471  iterator insert (const_iterator pos, const T& val)
472  {
473  link_type& link = *pos.link_loc;
474  // construct node value
475  node_type* p = allocator_new(node_allocator(),val);
476  p->next.reset(link.release()); // link the trailing nodes here
477  link.reset(p); // and attach new node to previous ones
478  return iterator(link); // non-const version of |pos|, points to new node
479  }
480 
481  iterator insert (const_iterator pos, T&& val)
482  {
483  link_type& link = *pos.link_loc;
484  // construct node value
485  node_type* p = allocator_new(node_allocator(),std::move(val));
486  p->next.reset(link.release()); // link the trailing nodes here
487  link.reset(p); // and attach new node to previous ones
488  return iterator(link); // non-const version of |pos|, points to new node
489  }
490 
491  iterator insert (const_iterator pos, size_type n, const T& val)
492  {
493  while (n-->0)
494  insert(pos,val); // insert copies of |val| in back-to-front sense
495  return iterator(*pos.link_loc);
496  }
497 
498  template<typename InputIt, typename = typename std::enable_if<
499  std::is_base_of<std::input_iterator_tag,
500  typename std::iterator_traits<InputIt>::iterator_category
501  >::value>::type >
502  iterator insert (const_iterator pos, InputIt first, InputIt last)
503  {
504  iterator result(*pos.link_loc); // non-const copy of |pos|
505  for( ; first!=last; ++first,++pos)
506  { // |insert(pos++,*first);|
507  // construct node value
508  node_type* p = allocator_new(node_allocator(),*first);
509  p->next.reset(pos.link_loc->release()); // link the trailing nodes here
510  pos.link_loc->reset(p); // and attach new node to previous ones
511  }
512  return result; // copy of original |pos|, at first element inserted if any
513  }
514 
515  // splice in |other| and return advanced iterator |pos|
516  iterator splice (const_iterator pos, simple_list&& other)
517  { link_type tail = *pos.link_loc;
518  *pos.link_loc = std::move(other.head); // |std::unique_ptr| does the work
519  while (not pos.at_end())
520  ++pos;
521  *pos.link_loc = std::move(tail);
522  return pos; // point after inserted elements
523  }
524 
525 
526  iterator erase (const_iterator pos)
527  { link_type& link = *pos.link_loc;
528  link.reset(link->next.release());
529  return iterator(link);
530  }
531 
532  iterator erase (const_iterator first, const_iterator last)
533  { node_type* end = last.link_loc->get(); // copy because |last| gets invalid
534  link_type& link = *first.link_loc;
535  while (link.get()!=end)
536  link.reset(link->next.release()); // same as |erase(first);|
537  return iterator(link);
538  }
539 
540  void clear ()
541  {
542  head.reset(); // smart pointer magic destroys all nodes
543  }
544 
545  void assign (size_type n, const T& x)
546  {
547  iterator p = begin();
548  for ( ; not at_end(p) and n-->0; ++p)
549  *p = x;
550 
551  if (at_end(p))
552  while (n-->0)
553  insert(p,x); // this inserts backwards, which doesn't matter
554  else // we have exhausted |n| before |p|, and need to truncate after |p|
555  p.link_loc->reset();
556  }
557 
558  template<typename InputIt, typename = typename std::enable_if<
559  std::is_base_of<std::input_iterator_tag,
560  typename std::iterator_traits<InputIt>::iterator_category
561  >::value>::type >
562  void assign (InputIt first, InputIt last)
563  {
564  iterator p = begin();
565  for ( ; not at_end(p) and first!=last; ++p,++first)
566  *p = *first;
567 
568  if (at_end(p))
569  for ( ; first!=last; ++p,++first) // |insert(p,*first)|, realised as:
570  p.link_loc->reset(allocator_new(node_allocator(),*first));
571  else // input exhausted before |p|; we need to truncate after |p|
572  p.link_loc->reset();
573  }
574 
575  template<typename InputIt>
576  void move_assign (InputIt first, InputIt last)
577  {
578  iterator p = begin();
579  for ( ; not at_end(p) and first!=last; ++p,++first)
580  *p = std::move(*first);
581 
582  if (at_end(p))
583  for ( ; first!=last; ++p,++first) // |insert(p,std::move(*first))|
584  p.link_loc->reset(allocator_new(node_allocator(),std::move(*first)));
585  else // input exhausted before |p|; we need to truncate after |p|
586  p.link_loc->reset();
587  }
588 
589  void reverse ()
590  {
591  link_type result(nullptr);
592  while (head!=nullptr)
593  { // cycle forward |(result,p->next,p|)
594  result.swap(head->next); // attach result to next node
595  result.swap(head); // now |result| is extended, |head| shortened
596  }
597  head=std::move(result); // attach result at |head|
598  }
599 
600  void reverse (const_iterator from, const_iterator to)
601  {
602  link_type remainder((*to.link_loc).release());
603  link_type p((*from.link_loc).release());
604  while (p.get()!=nullptr)
605  { // cycle forward |(remainder,p->next,p|)
606  remainder.swap(p->next); // attach remainder to next node
607  remainder.swap(p); // now |remainder| is extended and |p| shortened
608  }
609  from.link_loc->reset(remainder.release()); // attach remainder at |from|
610  }
611 
612  // accessors
613  const T& front () const { return head->contents; }
614  const_iterator begin () const { return const_iterator(head); }
615  const_iterator cbegin () const { return const_iterator(head); }
616  weak_const_iterator wbegin () const
617  { return weak_const_iterator(head.get()); }
618  weak_const_iterator wcbegin () const
619  { return weak_const_iterator(head.get()); }
620  // instead of |end()| we provide the |at_end| condition
621  static bool at_end (const_iterator p) { return p.link_loc->get()==nullptr; }
622  static bool at_end (weak_const_iterator p) { return p.at_end(); }
623 
624 }; // |class simple_list<T,Alloc>|
625 
626 
627 
628 // external functions for |simple_list<T,Alloc>|
629 template<typename T,typename Alloc>
630 size_t length (const simple_list<T,Alloc>& l)
631 {
632  size_t result=0;
633  for (auto it=l.begin(); not l.at_end(it); ++it)
634  ++result;
635  return result;
636 }
637 
638 // allow the alternative of using a raw pointer for the length
639 template<typename T,typename Alloc>
640 size_t length (const sl_node<T,Alloc>* l)
641 {
642  size_t result=0;
643  for (; l!=nullptr; l=l->next.get())
644  ++result;
645  return result;
646 }
647 
648 template<typename T,typename Alloc>
651 {
652  auto it=l.cbegin();
653  while (not l.at_end(it))
654  ++it;
655  return it;
656 }
657 
658 template<typename T,typename Alloc>
661 { return end(l); }
662 
663 template<typename T,typename Alloc>
665 {
666  auto it=l.begin();
667  while (not l.at_end(it))
668  ++it;
669  return it;
670 }
671 
672 // overload non-member |swap|, so argument dependent lookup will find it
673 template<typename T,typename Alloc>
675 
676 
677 
678 
679 /* Fully featureed simply linked list */
680 
681 
682 template<typename T, typename Alloc>
683  class sl_list
684  : private Alloc::template rebind<sl_node<T, Alloc> >::other
685 {
687  typedef typename Alloc::template rebind<node_type>::other alloc_type;
688  typedef typename Alloc::pointer node_ptr; // returned from |allocate|
689  typedef std::unique_ptr<node_type, allocator_deleter<alloc_type> > link_type;
690 
691  public:
692  typedef T value_type;
693  typedef std::size_t size_type;
694  typedef std::ptrdiff_t difference_type;
695  typedef value_type& reference;
696  typedef const value_type& const_reference;
697  typedef value_type* pointer;
698  typedef const value_type* const_pointer;
699 
704 
705  // data
706  private:
707  link_type head; // owns the first (if any), and recursively all nodes
708  link_type* tail;
709  size_type node_count;
710 
711  // an auxiliary function occasionally called when |head| is released
712  void set_empty () { tail=&head; node_count=0; }
713 
714  class ensure // a helper class that exists for its destructor only
715  { link_type* &tail;
716  link_type* &dst;
717  public:
718  ensure(link_type*& tail, const_iterator& p) // maybe makes |tail=p.link_loc|
719  : tail(tail), dst(p.link_loc) {}
721  { if (dst->get()==nullptr) // if at destruction time |dst| is at end
722  tail = dst; // then make |tail| point to it
723  }
724  };
725 
726  // constructors
727  public:
728  explicit sl_list () // empty list
729  : alloc_type(), head(nullptr), tail(&head), node_count(0) {}
730 
731  explicit sl_list (const alloc_type& a) // empty list, explicit allocator
732  : alloc_type(a), head(nullptr), tail(&head), node_count(0) {}
733 
734  explicit sl_list (alloc_type&& a) // empty list, explicit moved allocator
735  : alloc_type(a), head(nullptr), tail(&head), node_count(0) {}
736 
737  sl_list (const sl_list& x) // copy contructor
738  : alloc_type(x)
739  , head(nullptr)
740  , tail(&head)
741  , node_count(x.node_count)
742  {
743  for (node_type* p=x.head.get(); p!=nullptr; p=p->next.get())
744  {
745  node_type* q = allocator_new(node_allocator(),p->contents);
746  tail->reset(q); // link in new final node
747  tail=&q->next; // point |tail| to its link field, to append there next
748  }
749  }
750 
751  sl_list (sl_list&& x) // move contructor
752  : alloc_type(std::move(x))
753  , head(x.head.release())
754  , tail(x.empty() ? &head : x.tail)
755  , node_count(x.node_count)
756  { x.set_empty(); }
757 
758  explicit sl_list (simple_list<T,Alloc>&& x) // move and complete constructor
759  : alloc_type(std::move(x))
760  , head(x.head.release())
761  , tail(&head)
762  , node_count(0)
763  {
764  for ( ; *tail!=nullptr; tail=&(*tail)->next)
765  ++node_count;
766  }
767 
768  template<typename InputIt, typename = typename std::enable_if<
769  std::is_base_of<std::input_iterator_tag,
770  typename std::iterator_traits<InputIt>::iterator_category
771  >::value>::type >
772  sl_list (InputIt first, InputIt last, const alloc_type& a=alloc_type())
773  : alloc_type(a), head(nullptr), tail(&head), node_count(0)
774  {
775  assign(first,last);
776  }
777 
778  sl_list (size_type n, const alloc_type& a=alloc_type())
779  : alloc_type(a), head(nullptr), tail(&head), node_count(n)
780  {
781  while (n-->0)
782  {
783  // construct new node with default constructed value
784  node_type* p = allocator_new(node_allocator());
785  tail->reset(p); // splice in new node
786  tail = &p->next; // then move |tail| to point to null smart ptr agin
787  }
788  }
789 
790  sl_list (size_type n, const T& x, const alloc_type& a=alloc_type())
791  : alloc_type(a), head(nullptr), tail(&head), node_count(n)
792  {
793  assign(n,x);
794  }
795 
796  sl_list (std::initializer_list<T> l, const alloc_type& a=alloc_type())
797  : alloc_type(a), head(nullptr), tail(&head), node_count(0)
798  {
799  assign(l.begin(),l.end());
800  }
801 
802  ~sl_list () {} // when called, |head| is already destructed/cleaned up
803 
804  sl_list& operator= (const sl_list& x)
805  {
806  if (this!=&x) // self-assign is useless, though it would be safe
807  { // reuse existing nodes when possible
808  if (get_node_allocator() != x.get_node_allocator())
809  { // our old nodes need to be destroyed by our old allocator
810  clear(); // so we cannot reuse any of them: destroy them now
811  node_allocator() = x.get_node_allocator(); // now transfer allocator
812  }
813  assign(x.begin(),x.end());
814  }
815  return *this;
816  }
817 
818  sl_list& operator= (sl_list&& x)
819  { // self-assignment is safe, because safe for |std::unique_ptr| instances
820  if (get_node_allocator() == x.get_node_allocator() )
821  { // it is safe to just move the head pointer
822  // the next call starts clearing |*this|, except when |get()==x.get()|
823  if (x.head.get()==nullptr)
824  clear(); // this modifies |tail|
825  else
826  {
827  head = std::move(x.head); // unique_ptr move assignment
828  tail = x.tail;
829  node_count = x.node_count;
830  }
831  if (false)
832  node_allocator() = std::move(x.node_allocator());
833  }
834  else
835  move_assign(x.begin(),x.end());
836  return *this;
837  }
838 
839  void swap (sl_list& other)
840  {
841  if (get_node_allocator() == other.get_node_allocator() )
842  { // easy case; swap almost everything (tails need some care)
843  using std::swap;
844  swap(node_allocator(),other.node_allocator());
845  head.swap(other.head); // swap |std::unique_ptr| instances
846  swap(node_count,other.node_count);
847  std::swap(tail,other.tail); // raw pointer swap
848  // uncross tail pointers if necessary
849  if (head.get()==nullptr)
850  tail=&head;
851  if (other.head.get()==nullptr)
852  other.tail=&other.head;
853  }
854  else // we must really exchange contents
855  {
856  iterator p=begin(), q=other.begin();
857  using std::swap;
858  for ( ; p!=end() and q!=other.end(); ++p,++q)
859  swap(*p,*q);
860  if (p==end())
861  insert(p,q,other.end());
862  else // now |q==other.end()|
863  other.insert(q,p,end());
864  }
865  }
866 
867  // access to the allocator
868  const alloc_type& get_node_allocator () const { return *this; }
869  alloc_type& node_allocator () { return *this; }
870 
871  //iterators
872  iterator begin () { return iterator(head); }
873  iterator end () { return iterator(*tail); }
874  weak_iterator wbegin () { return weak_iterator(head.get()); }
875  weak_iterator wend () { return weak_iterator(nullptr); }
876 
877  T& front () { return head->contents; }
878  void pop_front ()
879  {
880  head.reset(head->next.release());
881  --node_count;
882  if (head.get()==nullptr)
883  tail=&head;
884  }
885 
886  void push_front (const T& val)
887  {
888  // construct node value
889  node_type* p = allocator_new(node_allocator(),val);
890  if (head.get()==nullptr)
891  tail=&p->next; // adjusts |tail| if list was empty
892  else
893  p->next.reset(head.release()); // link trailing nodes here
894  head.reset(p); // make new node the first one in the list
895  ++node_count;
896  }
897 
898  void push_front (T&& val)
899  {
900  // construct node value
901  node_type* p = allocator_new(node_allocator(),std::move(val));
902  if (head.get()==nullptr)
903  tail=&p->next; // adjusts |tail| if list was empty
904  else
905  p->next.reset(head.release()); // link trailing nodes here
906  head.reset(p); // make new node the first one in the list
907  ++node_count;
908  }
909 
910  template<typename... Args>
911  void emplace_front (Args&&... args)
912  {
913  // construct node value
914  node_type* p =
915  allocator_new(node_allocator(),std::forward<Args>(args)...);
916  if (head.get()==nullptr)
917  tail=&p->next; // adjusts |tail| if list was empty
918  else
919  p->next.reset(head.release()); // link trailing nodes here
920  head.reset(p); // make new node the first one in the list
921  ++node_count;
922  }
923 
924  iterator push_back (const T& val)
925  {
926  link_type& last = *tail; // hold this link field for |return| statement
927  node_type* p = allocator_new(node_allocator(),val); // construct node value
928  tail = &p->next; // then move |tail| to point to null link again
929  last.reset(p); // append new node to previous ones
930  ++node_count;
931  return iterator(last);
932  }
933 
934  iterator push_back(T&& val)
935  {
936  link_type& last = *tail; // hold this link field for |return| statement
937  node_type* p = allocator_new(node_allocator(),std::move(val));
938  tail = &p->next; // then move |tail| to point to null smart ptr agin
939  last.reset(p); // append new node to previous ones
940  ++node_count;
941  return iterator(last);
942  }
943 
944  template<typename... Args>
945  iterator emplace_back (Args&&... args)
946  {
947  link_type& last = *tail; // hold this link field for |return| statement
948  // construct node value
949  node_type* p =
950  allocator_new(node_allocator(),std::forward<Args>(args)...);
951  tail = &p->next; // then move |tail| to point to null smart ptr agin
952  last.reset(p); // append new node to previous ones
953  ++node_count;
954  return iterator(last);
955  }
956 
957  bool empty () const { return tail==&head; } // or |node_count==0|
958  bool singleton () const { return node_count==1; }
959  size_type size () const { return node_count; }
960 
961  iterator insert (const_iterator pos, const T& val)
962  {
963  link_type& link = *pos.link_loc;
964  node_type* p = allocator_new(node_allocator(),val);
965  if (at_end(pos))
966  tail=&p->next;
967  else
968  p->next.reset(link.release()); // link the trailing nodes here
969  link.reset(p); // and attach new node to previous ones
970  ++node_count;
971  return iterator(link);
972  }
973 
974  iterator insert (const_iterator pos, T&& val)
975  {
976  link_type& link = *pos.link_loc;
977  node_type* p = allocator_new(node_allocator(),std::move(val));
978  if (at_end(pos))
979  tail=&p->next;
980  else
981  p->next.reset(link.release()); // link the trailing nodes here
982  link.reset(p); // and attach new node to previous ones
983  ++node_count;
984  return iterator(link);
985  }
986 
987  iterator insert (const_iterator pos, size_type n, const T& val)
988  {
989  link_type& link = *pos.link_loc;
990  if (n-->0)
991  {
992  insert(pos,val); // this takes care of changing |tail| if necessary
993  while (n-->0)
994  {
995  node_type* p = allocator_new(node_allocator(),val);
996  p->next.reset(link.release()); // link the trailing nodes here
997  link.reset(p); // and attach new node to previous ones
998  ++node_count; // exception safe tracking of the size
999  }
1000  }
1001  return iterator(link);
1002  }
1003 
1004  template<typename InputIt, typename = typename std::enable_if<
1005  std::is_base_of<std::input_iterator_tag,
1006  typename std::iterator_traits<InputIt>::iterator_category
1007  >::value>::type >
1008  iterator insert (const_iterator pos, InputIt first, InputIt last)
1009  {
1010  ensure me(tail,pos); // will adapt |tail| if |at_end(pos)| throughout
1011  for( ; first!=last; ++first)
1012  { // |insert(pos++,*first);|, except we don't update |tail|
1013  node_type* p = allocator_new(node_allocator(),*first);
1014  p->next.reset(pos.link_loc->release()); // link the trailing nodes here
1015  pos.link_loc->reset(p); // and attach new node to previous ones
1016  pos = iterator(p->next); // or simply |++pos|
1017  ++node_count;
1018  }
1019  }
1020 
1021  template<typename InputIt>
1022  void move_insert (const_iterator pos, InputIt first, InputIt last)
1023  {
1024  ensure me(tail,pos); // will adapt |tail| if |at_end(pos)| throughout
1025  for( ; first!=last; ++first)
1026  { // |insert(pos++,std::move(*first));|, except we don't update |tail|
1027  node_type* p = allocator_new(node_allocator(),std::move(*first));
1028  p->next.reset(pos.link_loc->release()); // link the trailing nodes here
1029  pos.link_loc->reset(p); // and attach new node to previous ones
1030  pos = iterator(p->next); // or simply |++pos|
1031  ++node_count;
1032  }
1033  }
1034 
1035  iterator erase (const_iterator pos)
1036  {
1037  link_type& link = *pos.link_loc;
1038  link.reset(link->next.release());
1039  if (link.get()==nullptr) // if final node was erased
1040  tail = &link; // we need to reestablish validity of |tail|
1041  --node_count;
1042  return iterator(link);
1043  }
1044 
1045  iterator erase (const_iterator first, const_iterator last)
1046  { const node_type* end_ptr = // we must store this pointer value
1047  last.link_loc->get(); // because |last| will get invalidated
1048  link_type& link = *first.link_loc;
1049  while (link.get()!=end_ptr)
1050  {
1051  link.reset(link->next.release()); // |erase(first);|
1052  --node_count;
1053  }
1054  if (end_ptr==nullptr) // if we had |last==end()| initially, then
1055  tail = &link; // we need to reestablish validity of |tail|
1056  return iterator(link);
1057  }
1058 
1059  void append (sl_list&& other)
1060  { if (not other.empty()) // avoid erroneously setting |tail| in trival case
1061  { *tail = std::move(other.head); // |std::unique_ptr| does the work
1062  tail = other.tail;
1063  node_count += other.node_count;
1064  other.set_empty();
1065  }
1066  }
1067 
1068  iterator splice (const_iterator pos, sl_list&& other)
1069  { if (other.empty())
1070  return iterator(*pos.link_loc);
1071  link_type& final = *other.tail;
1072  link_type& link = *pos.link_loc;
1073  if (pos==cend())
1074  tail = &final;
1075  else
1076  final = std::move(link); // attach our remainder
1077  link = std::move(other.head);
1078  node_count += other.node_count;
1079  other.set_empty();
1080  return iterator(final);
1081  }
1082 
1083  void clear ()
1084  {
1085  head.reset(); // smart pointer magic destroys all nodes
1086  set_empty();
1087  }
1088 
1089  void assign (size_type n, const T& x)
1090  {
1091  const size_type given_n = n; // cannot store yet for exception safety
1092  iterator p = begin();
1093  for ( ; p!=end() and n-->0; ++p)
1094  *p = x;
1095 
1096  if (p==end())
1097  insert(p,n,x); // this also increases |node_count|
1098  else // we have exhausted |n| before |p|, and need to truncate after |p|
1099  {
1100  (tail = p.link_loc)->reset();
1101  node_count = given_n;
1102  }
1103  }
1104 
1105  template<typename InputIt, typename = typename std::enable_if<
1106  std::is_base_of<std::input_iterator_tag,
1107  typename std::iterator_traits<InputIt>::iterator_category
1108  >::value>::type >
1109  void assign (InputIt first, InputIt last)
1110  {
1111  size_type count=0;
1112  iterator p = begin();
1113  for ( ; p!=end() and first!=last; ++p,++first,++count)
1114  *p = *first;
1115 
1116  if (p==end())
1117  insert(p,first,last); // this also increases |node_count|
1118  else // we have exhausted input before |p|, and need to truncate after |p|
1119  {
1120  (tail = p.link_loc)->reset();
1121  node_count = count;
1122  }
1123  }
1124 
1125  template<typename InputIt>
1126  void move_assign (InputIt first, InputIt last)
1127  {
1128  size_type count=0;
1129  iterator p = begin();
1130  for ( ; p!=end() and first!=last; ++p,++first,++count)
1131  *p = std::move(*first);
1132 
1133  if (p==end())
1134  move_insert(p,first,last); // this also increases |node_count|
1135  else // we have exhausted input before |p|, and need to truncate after |p|
1136  {
1137  (tail = p.link_loc)->reset();
1138  node_count = count;
1139  }
1140  }
1141 
1142  void reverse () { reverse(cbegin(),cend()); }
1143 
1144  void reverse (const_iterator from, const_iterator to)
1145  {
1146  if (to==end() and from!=to)
1147  tail = &(*from.link_loc)->next;
1148  link_type result((*to.link_loc).release());
1149  link_type p((*from.link_loc).release());
1150  while (p.get()!=nullptr)
1151  { // cycle forward |(result,p->next,p|)
1152  result.swap(p->next);
1153  result.swap(p);
1154  }
1155  from.link_loc->reset(result.release());
1156  }
1157 
1158  simple_list<T,Alloc> undress() // return only |head|, amputating other fields
1159  { set_empty(); // this is a sacrificial method
1160  return simple_list<T,Alloc>(head.release(),std::move(node_allocator()));
1161  }
1162 
1163  // accessors
1164  const T& front () const { return head->contents; }
1165  const_iterator begin () const { return const_iterator(head); }
1166  const_iterator end () const { return const_iterator(*tail); }
1167  const_iterator cbegin () const { return const_iterator(head); }
1168  const_iterator cend () const { return const_iterator(*tail); }
1169  weak_const_iterator wbegin () const
1170  { return weak_const_iterator(head.get()); }
1171  weak_const_iterator wcbegin () const
1172  { return weak_const_iterator(head.get()); }
1173  weak_const_iterator wend () const { return weak_const_iterator(nullptr); }
1174  weak_const_iterator wcend () const { return weak_const_iterator(nullptr); }
1175 
1176  // in addition to |end()| we provide the |at_end| condition
1177  static bool at_end (const_iterator p) { return p.link_loc->get()==nullptr; }
1178  static bool at_end (weak_const_iterator p) { return p.at_end(); }
1179 
1180 }; // |class sl_list<T,Alloc>|
1181 
1182 // external functions for |sl_list<T,Alloc>|
1183 template<typename T,typename Alloc>
1184 size_t length (const sl_list<T,Alloc>& l) { return l.size(); }
1185 
1186 template<typename T,typename Alloc>
1188 { return l.end(); }
1189 
1190 template<typename T,typename Alloc>
1192 { return end(l); }
1193 
1194 template<typename T,typename Alloc>
1196 { return l.end(); }
1197 
1198 // overload non-member |swap|, so argument dependent lookup will find it
1199 template<typename T,typename Alloc>
1201 
1202 
1203 template<typename T,typename Alloc = std::allocator<T> >
1204  class mirrored_simple_list // trivial adapter, to allow use with |std::stack|
1205  : public simple_list<T,Alloc>
1206 {
1209  typedef typename Alloc::template rebind<node_type>::other alloc_type;
1210 
1211  public:
1212  // forward most constructors, but reverse order for initialised ones
1213  // for this reason we cannot use perfect forwarding for the constructor
1214  mirrored_simple_list () : Base() {}
1215  explicit mirrored_simple_list (const Alloc& a) : Base(a) {}
1216  explicit mirrored_simple_list (Alloc&& a) : Base(std::move(a)) {}
1217 
1218  mirrored_simple_list (const Base& x) // lift base object to derived class
1219  : Base(x) {}
1220  mirrored_simple_list (Base&& x) // lift base object to derived class
1221  : Base(std::move(x)) {}
1222  mirrored_simple_list (sl_node<T, Alloc>* raw_list) // acquire from raw pointer
1223  : Base(raw_list) {}
1224  // compiler-generated copy constructor and assignment should be OK
1225 
1226  template<typename InputIt, typename = typename std::enable_if<
1227  std::is_base_of<std::input_iterator_tag,
1228  typename std::iterator_traits<InputIt>::iterator_category
1229  >::value>::type >
1230  mirrored_simple_list (InputIt first, InputIt last,
1231  const alloc_type& a=alloc_type())
1232  : Base(a)
1233  {
1234  for ( ; first!=last; ++first)
1235  Base::push_front(*first); // this reverses the order
1236  }
1237 
1238  mirrored_simple_list (typename Base::size_type n, const T& x,
1239  const alloc_type& a=alloc_type())
1240  : Base(n,x,a) {}
1241 
1242  // forward |push_front| method from |Base|, and its likes, as ...|back|
1243  template<typename... Args> void push_back(Args&&... args)
1244  { Base::push_front(std::forward<Args>(args)...); }
1245  template<typename... Args> void pop_back(Args&&... args)
1246  { Base::pop_front(std::forward<Args>(args)...); }
1247  template<typename... Args> void emplace_back (Args&&... args)
1248  { Base::emplace_front(std::forward<Args>(args)...); }
1249 
1250  template<typename... Args> const T& back(Args&&... args) const
1251  { return Base::front(std::forward<Args>(args)...); }
1252  template<typename... Args> T& back(Args&&... args)
1253  { return Base::front(std::forward<Args>(args)...); }
1254 
1255 }; // |class mirrored_simple_list<T,Alloc>|
1256 
1257 template<typename T,typename Alloc = std::allocator<T> >
1258  class mirrored_sl_list // trivial adapter, to allow use with |std::stack|
1259  : public sl_list<T,Alloc>
1260 {
1263  typedef typename Alloc::template rebind<node_type>::other alloc_type;
1264 
1265  // forward most constructors, but reverse order for initialised ones
1266  public:
1267  mirrored_sl_list () : Base() {}
1268  explicit mirrored_sl_list (const Alloc& a) : Base(a) {}
1269  explicit mirrored_sl_list (Alloc&& a) : Base(std::move(a)) {}
1270  mirrored_sl_list (const Base& x) // lift base object to derived class
1271  : Base(x) {}
1272  mirrored_sl_list (Base&& x) // lift base object to derived class
1273  : Base(std::move(x)) {}
1274  mirrored_sl_list (sl_node<T, Alloc>* raw_list) // acquire from raw pointer
1275  : Base(raw_list) {}
1276  // compiler-generated copy constructor and assignment should be OK
1277 
1278  template<typename InputIt, typename = typename std::enable_if<
1279  std::is_base_of<std::input_iterator_tag,
1280  typename std::iterator_traits<InputIt>::iterator_category
1281  >::value>::type >
1282  mirrored_sl_list (InputIt first, InputIt last,
1283  const alloc_type& a=alloc_type())
1284  : Base(a)
1285  {
1286  for ( ; first!=last; ++first)
1287  Base::insert(Base::begin(),*first); // this reverses the order
1288  }
1289 
1290  mirrored_sl_list (typename Base::size_type n, const T& x,
1291  const alloc_type& a=alloc_type())
1292  : Base(n,x,a) {}
1293 
1294  // forward |push_front| method from |Base|, and its likes, as ...|back|
1295  template<typename... Args> void push_back(Args&&... args)
1296  { Base::push_front(std::forward<Args>(args)...); }
1297  template<typename... Args> void pop_back(Args&&... args)
1298  { Base::pop_front(std::forward<Args>(args)...); }
1299  template<typename... Args> void emplace_back (Args&&... args)
1300  { Base::emplace_front(std::forward<Args>(args)...); }
1301 
1302  template<typename... Args> const T& back(Args&&... args) const
1303  { return Base::front(std::forward<Args>(args)...); }
1304  template<typename... Args> T& back(Args&&... args)
1305  { return Base::front(std::forward<Args>(args)...); }
1306 
1307  // also rename all ...|back| methods from |Base| to ...|front|
1308  template<typename... Args>
1309  typename Base::iterator push_front (Args&&... args)
1310  { return Base::push_back(std::forward<Args>(args)...); }
1311  template<typename... Args>
1312  typename Base::iterator emplace_front (Args&&... args)
1313  { return Base::emplace_back(std::forward<Args>(args)...); }
1314 
1315 }; // |class mirrored_sl_list<T,Alloc>|
1316 
1317 } // |namespace cantainers|
1318 
1319 } // |namespace atlas|
1320 
1321 
1322 #endif
1323 
sl_node(T &&contents)
Definition: sl_list.h:95
const value_type & const_reference
Definition: sl_list.h:696
weak_sl_list_const_iterator< T, Alloc > weak_const_iterator
Definition: sl_list.h:270
weak_iterator wbegin()
Definition: sl_list.h:436
iterator insert(const_iterator pos, InputIt first, InputIt last)
Definition: sl_list.h:1008
mirrored_sl_list(Base &&x)
Definition: sl_list.h:1272
Definition: sl_list.h:714
mirrored_simple_list(InputIt first, InputIt last, const alloc_type &a=alloc_type())
Definition: sl_list.h:1230
Denom_t remainder(I, Denom_t)
Definition: arithmetic.h:184
weak_sl_list_const_iterator< T, Alloc > weak_const_iterator
Definition: sl_list.h:702
sl_list(const sl_list &x)
Definition: sl_list.h:737
self operator++()
Definition: sl_list.h:234
T & operator*() const
Definition: sl_list.h:231
std::size_t size_type
Definition: sl_list.h:693
iterator push_back(T &&val)
Definition: sl_list.h:934
mirrored_sl_list(Alloc &&a)
Definition: sl_list.h:1269
simple_list(size_type n, const alloc_type &a=alloc_type())
Definition: sl_list.h:324
bool at_end() const
Definition: sl_list.h:209
simple_list()
Definition: sl_list.h:279
void pop_back(Args &&...args)
Definition: sl_list.h:1245
T & operator*() const
Definition: sl_list.h:165
void clear()
Definition: sl_list.h:540
simple_list(const alloc_type &a)
Definition: sl_list.h:282
T value_type
Definition: sl_list.h:692
~sl_node()
Definition: sl_list.h:101
mirrored_simple_list(typename Base::size_type n, const T &x, const alloc_type &a=alloc_type())
Definition: sl_list.h:1238
bool operator!=(const self &x) const
Definition: sl_list.h:142
Alloc::template rebind< node_type >::other alloc_type
Definition: sl_list.h:1263
iterator erase(const_iterator first, const_iterator last)
Definition: sl_list.h:1045
weak_sl_list_iterator(typename Base::link_type p)
Definition: sl_list.h:228
simple_list(node_type *raw, const alloc_type &a)
Definition: sl_list.h:291
sl_list_const_iterator()
Definition: sl_list.h:126
Definition: sl_list.h:1258
simple_list< T, Alloc > undress()
Definition: sl_list.h:1158
const_iterator cbegin() const
Definition: sl_list.h:615
iterator begin()
Definition: sl_list.h:872
weak_sl_list_const_iterator(const_link_type p)
Definition: sl_list.h:192
void clear()
Definition: sl_list.h:1083
void append(sl_list &&other)
Definition: sl_list.h:1059
sl_list(InputIt first, InputIt last, const alloc_type &a=alloc_type())
Definition: sl_list.h:772
void assign(size_type n, const T &x)
Definition: sl_list.h:545
void swap(sl_list< T, Alloc > &x, sl_list< T, Alloc > &y)
Definition: sl_list.h:1200
uA p
Definition: lists.cpp:26
simple_list(simple_list &&x)
Definition: sl_list.h:310
T value_type
Definition: sl_list.h:260
sl_list(simple_list< T, Alloc > &&x)
Definition: sl_list.h:758
bool empty() const
Definition: sl_list.h:468
void operator()(pointer p)
Definition: sl_list.h:42
void reverse(const_iterator from, const_iterator to)
Definition: sl_list.h:600
Base::iterator push_front(Args &&...args)
Definition: sl_list.h:1309
void pop_back(Args &&...args)
Definition: sl_list.h:1297
simple_list(size_type n, const T &x, const alloc_type &a=alloc_type())
Definition: sl_list.h:336
iterator insert(const_iterator pos, size_type n, const T &val)
Definition: sl_list.h:491
void pop_front()
Definition: sl_list.h:878
void swap(simple_list &other)
Definition: sl_list.h:399
Alloc::pointer node_ptr
Definition: sl_list.h:254
sl_list(std::initializer_list< T > l, const alloc_type &a=alloc_type())
Definition: sl_list.h:796
weak_sl_list_iterator< T, Alloc > weak_iterator
Definition: sl_list.h:703
self operator++()
Definition: sl_list.h:201
sl_list(sl_list &&x)
Definition: sl_list.h:751
simple_list(std::initializer_list< T > l, const alloc_type &a=alloc_type())
Definition: sl_list.h:342
weak_const_iterator wbegin() const
Definition: sl_list.h:1169
mirrored_sl_list(InputIt first, InputIt last, const alloc_type &a=alloc_type())
Definition: sl_list.h:1282
Alloc::value_type * allocator_new(Alloc &a, Args &&...args)
Definition: sl_list.h:60
value_base * value
Definition: axis-types.h:129
static bool at_end(const_iterator p)
Definition: sl_list.h:1177
Alloc::pointer pointer
Definition: sl_list.h:38
void push_front(const T &val)
Definition: sl_list.h:442
weak_iterator wbegin()
Definition: sl_list.h:874
const T & back(Args &&...args) const
Definition: sl_list.h:1250
simple_list(InputIt first, InputIt last, const alloc_type &a=alloc_type())
Definition: sl_list.h:318
~simple_list()
Definition: sl_list.h:348
mirrored_simple_list(Alloc &&a)
Definition: sl_list.h:1216
sl_list_iterator< T, Alloc > iterator
Definition: sl_list.h:701
size_type size() const
Definition: sl_list.h:959
void swap(simple_list< T, Alloc > &x, simple_list< T, Alloc > &y)
Definition: sl_list.h:674
T contents
Definition: sl_list.h:92
sl_node< T, Alloc >::link_type link_type
Definition: sl_list.h:116
value_type & reference
Definition: sl_list.h:263
iterator insert(const_iterator pos, InputIt first, InputIt last)
Definition: sl_list.h:502
mirrored_sl_list(const Alloc &a)
Definition: sl_list.h:1268
void assign(InputIt first, InputIt last)
Definition: sl_list.h:562
iterator insert(const_iterator pos, const T &val)
Definition: sl_list.h:471
self operator++()
Definition: sl_list.h:136
value_type * pointer
Definition: sl_list.h:697
void emplace_front(Args &&...args)
Definition: sl_list.h:459
mirrored_simple_list(Base &&x)
Definition: sl_list.h:1220
bool singleton() const
Definition: sl_list.h:958
sl_list_iterator< T, Alloc > iterator
Definition: sl_list.h:269
Alloc::template rebind< node_type >::other alloc_type
Definition: sl_list.h:1209
void reverse()
Definition: sl_list.h:589
static bool at_end(const_iterator p)
Definition: sl_list.h:621
Definition: cweave.c:245
iterator insert(const_iterator pos, size_type n, const T &val)
Definition: sl_list.h:987
mirrored_simple_list(const Alloc &a)
Definition: sl_list.h:1215
sl_node< T, Alloc > node_type
Definition: sl_list.h:1208
iterator insert(const_iterator pos, const T &val)
Definition: sl_list.h:961
std::unique_ptr< node_type, allocator_deleter< alloc_type > > link_type
Definition: sl_list.h:689
weak_const_iterator wcend() const
Definition: sl_list.h:1174
iterator end()
Definition: sl_list.h:873
link_type link
Definition: sl_list.h:187
const T * operator->() const
Definition: sl_list.h:134
sl_list_iterator(typename Base::link_type &link)
Definition: sl_list.h:162
Definition: sl_list.h:30
Alloc::pointer node_ptr
Definition: sl_list.h:688
const value_type * const_pointer
Definition: sl_list.h:266
std::size_t size_type
Definition: sl_list.h:261
sl_node(const T &contents)
Definition: sl_list.h:94
sl_list(const alloc_type &a)
Definition: sl_list.h:731
void emplace_front(Args &&...args)
Definition: sl_list.h:911
Alloc::value_type value_type
Definition: sl_list.h:37
simple_list< T, Alloc > Base
Definition: sl_list.h:1207
mirrored_simple_list(sl_node< T, Alloc > *raw_list)
Definition: sl_list.h:1222
mirrored_sl_list()
Definition: sl_list.h:1267
Definition: sl_list.h:1204
T & back(Args &&...args)
Definition: sl_list.h:1304
bool operator==(const self &x) const
Definition: sl_list.h:141
const T * operator->() const
Definition: sl_list.h:199
void reverse()
Definition: sl_list.h:1142
Alloc::template rebind< sl_node >::other alloc_type
Definition: sl_list.h:88
weak_iterator wend()
Definition: sl_list.h:875
weak_sl_list_iterator()
Definition: sl_list.h:227
std::ptrdiff_t difference_type
Definition: sl_list.h:694
constexpr allocator_deleter()=default
iterator erase(const_iterator pos)
Definition: sl_list.h:1035
self operator++(int)
Definition: sl_list.h:235
self operator++(int)
Definition: sl_list.h:202
bool operator!=(const self &x) const
Definition: sl_list.h:207
Definition: sl_list.h:86
sl_list_const_iterator< T, Alloc > const_iterator
Definition: sl_list.h:700
sl_node< T, Alloc > node_type
Definition: sl_list.h:1262
void assign(InputIt first, InputIt last)
Definition: sl_list.h:1109
iterator splice(const_iterator pos, simple_list &&other)
Definition: sl_list.h:516
iterator erase(const_iterator first, const_iterator last)
Definition: sl_list.h:532
alloc_type & node_allocator()
Definition: sl_list.h:432
weak_sl_list_const_iterator< T, Alloc > Base
Definition: sl_list.h:220
mirrored_sl_list(sl_node< T, Alloc > *raw_list)
Definition: sl_list.h:1274
void pop_front()
Definition: sl_list.h:439
const_iterator begin() const
Definition: sl_list.h:1165
void swap(sl_list &other)
Definition: sl_list.h:839
void push_back(Args &&...args)
Definition: sl_list.h:1295
const alloc_type & get_node_allocator() const
Definition: sl_list.h:431
value_type & reference
Definition: sl_list.h:695
Definition: sl_list.h:107
bool operator==(const self &x) const
Definition: sl_list.h:206
T & back(Args &&...args)
Definition: sl_list.h:1252
Definition: sl_list.h:35
~ensure()
Definition: sl_list.h:720
void emplace_back(Args &&...args)
Definition: sl_list.h:1299
const_iterator cbegin() const
Definition: sl_list.h:1167
iterator insert(const_iterator pos, T &&val)
Definition: sl_list.h:974
Definition: sl_list.h:28
Alloc::template rebind< node_type >::other alloc_type
Definition: sl_list.h:253
sl_list_const_iterator< T, Alloc > Base
Definition: sl_list.h:154
void move_assign(InputIt first, InputIt last)
Definition: sl_list.h:576
const T & front() const
Definition: sl_list.h:1164
weak_const_iterator wcbegin() const
Definition: sl_list.h:1171
void push_front(T &&val)
Definition: sl_list.h:898
iterator push_back(const T &val)
Definition: sl_list.h:924
mirrored_simple_list()
Definition: sl_list.h:1214
iterator insert(const_iterator pos, T &&val)
Definition: sl_list.h:481
link_type *& tail
Definition: sl_list.h:715
void push_front(T &&val)
Definition: sl_list.h:450
void assign(size_type n, const T &x)
Definition: sl_list.h:1089
const T & operator*() const
Definition: sl_list.h:198
size_t length(const simple_list< T, Alloc > &l)
Definition: sl_list.h:630
Alloc::template rebind< node_type >::other alloc_type
Definition: sl_list.h:687
simple_list(node_type *raw, alloc_type &&a)
Definition: sl_list.h:294
weak_const_iterator wend() const
Definition: sl_list.h:1173
iterator begin()
Definition: sl_list.h:435
mirrored_sl_list(const Base &x)
Definition: sl_list.h:1270
weak_sl_list_iterator< T, Alloc > weak_iterator
Definition: sl_list.h:271
link_type head
Definition: sl_list.h:707
~sl_list()
Definition: sl_list.h:802
void set_empty()
Definition: sl_list.h:712
size_type node_count
Definition: sl_list.h:709
bool at_end() const
Definition: sl_list.h:144
void push_front(const T &val)
Definition: sl_list.h:886
const_iterator begin() const
Definition: sl_list.h:614
const_iterator end() const
Definition: sl_list.h:1166
T * operator->() const
Definition: sl_list.h:166
sl_list(alloc_type &&a)
Definition: sl_list.h:734
sl_node< T, Alloc > node_type
Definition: sl_list.h:252
static bool at_end(weak_const_iterator p)
Definition: sl_list.h:622
std::unique_ptr< sl_node, allocator_deleter< alloc_type > > link_type
Definition: sl_list.h:89
value_type * pointer
Definition: sl_list.h:265
const alloc_type & get_node_allocator() const
Definition: sl_list.h:868
Base::iterator emplace_front(Args &&...args)
Definition: sl_list.h:1312
weak_const_iterator wcbegin() const
Definition: sl_list.h:618
link_type *& dst
Definition: sl_list.h:716
sl_list(size_type n, const T &x, const alloc_type &a=alloc_type())
Definition: sl_list.h:790
void move_assign(InputIt first, InputIt last)
Definition: sl_list.h:1126
weak_const_iterator wbegin() const
Definition: sl_list.h:616
simple_list(const simple_list &x)
Definition: sl_list.h:297
sl_list_const_iterator(const link_type &link)
Definition: sl_list.h:127
link_type head
Definition: sl_list.h:275
sl_node(Args &&...args)
Definition: sl_list.h:96
alloc_type & node_allocator()
Definition: sl_list.h:869
sl_list_iterator()
Definition: sl_list.h:161
simple_list< T, Alloc >::const_iterator cend(const simple_list< T, Alloc > &l)
Definition: sl_list.h:660
weak_sl_list_const_iterator()
Definition: sl_list.h:191
T * operator->() const
Definition: sl_list.h:232
const value_type * const_pointer
Definition: sl_list.h:698
void push_back(Args &&...args)
Definition: sl_list.h:1243
std::unique_ptr< node_type, allocator_deleter< alloc_type > > link_type
Definition: sl_list.h:255
unsigned long n
Definition: axis.cpp:77
sl_list< T, Alloc > Base
Definition: sl_list.h:1261
simple_list< T, Alloc >::const_iterator end(const simple_list< T, Alloc > &l)
Definition: sl_list.h:650
bool singleton() const
Definition: sl_list.h:469
sl_node< T, Alloc > node_type
Definition: sl_list.h:686
Definition: Atlas.h:38
Definition of dummy argument tags used for constructor overloading.
sl_list()
Definition: sl_list.h:728
sl_node< T, Alloc > * link_type
Definition: sl_list.h:180
simple_list(node_type *raw)
Definition: sl_list.h:288
void move_insert(const_iterator pos, InputIt first, InputIt last)
Definition: sl_list.h:1022
std::ptrdiff_t difference_type
Definition: sl_list.h:262
link_type next
Definition: sl_list.h:91
iterator erase(const_iterator pos)
Definition: sl_list.h:526
link_type * tail
Definition: sl_list.h:708
T & front()
Definition: sl_list.h:877
static bool at_end(weak_const_iterator p)
Definition: sl_list.h:1178
mirrored_simple_list(const Base &x)
Definition: sl_list.h:1218
void emplace_back(Args &&...args)
Definition: sl_list.h:1247
self operator++()
Definition: sl_list.h:169
link_type * link_loc
Definition: sl_list.h:122
sl_list(size_type n, const alloc_type &a=alloc_type())
Definition: sl_list.h:778
T & front()
Definition: sl_list.h:438
sl_list_const_iterator< T, Alloc > const_iterator
Definition: sl_list.h:268
ensure(link_type *&tail, const_iterator &p)
Definition: sl_list.h:718
const_iterator cend() const
Definition: sl_list.h:1168
const T & operator*() const
Definition: sl_list.h:133
void reverse(const_iterator from, const_iterator to)
Definition: sl_list.h:1144
self operator++(int)
Definition: sl_list.h:170
simple_list(alloc_type &&a)
Definition: sl_list.h:285
Definition: cweave.c:343
const value_type & const_reference
Definition: sl_list.h:264
const T & front() const
Definition: sl_list.h:613
iterator splice(const_iterator pos, sl_list &&other)
Definition: sl_list.h:1068
iterator emplace_back(Args &&...args)
Definition: sl_list.h:945
mirrored_sl_list(typename Base::size_type n, const T &x, const alloc_type &a=alloc_type())
Definition: sl_list.h:1290
const sl_node< T, Alloc > * const_link_type
Definition: sl_list.h:181
bool empty() const
Definition: sl_list.h:957
const T & back(Args &&...args) const
Definition: sl_list.h:1302
self operator++(int)
Definition: sl_list.h:137
node_type * release()
Definition: sl_list.h:428
const bool empty
Definition: axis.cpp:43