Files CCore/inc/ContainerList.h CCore/src/ContainerList.cpp
Here are six non-intrusive container list classes. They are parametrized by the object type and the node allocator type, which is defaulted to the NodeAllocator. The only requirement for the object type is its destructor must be no-throw. The default node allocator uses the new and delete operation to allocate/destroy each list node. It may be expensive. To improve the performance and reduce the heap usage consider the using of the NodePoolAllocator or compact lists.
All lists have much common methods and properties. So here is a "common class" AnyList.
Constant lists propagate constantness to its elements.
List ins/del methods do not move existing list elements, but may invalidate list cursors. If such method is using a cursor as the argument, this cursor remains valid and it is updated during the operation, if necessary.
template <class T,template <class Node> class Allocator=NodeAllocator>
class AnyList : NoCopy
{
....
public:
// constructors
template <class ... SS>
explicit AnyList(SS && ... ss) noexcept;
~AnyList();
// std move
AnyList(AnyList &&obj) noexcept;
AnyList & operator = (AnyList &&obj) noexcept;
// props
ulen operator + () const;
bool operator ! () const;
ulen getCount() const;
Constructor forwards its arguments to the node allocator. Destructor destroys the list with all its elements. It's assumed that the allocator constructor does not throw.
AnyList is not copyable, but std movable. The original object is nullified during the move.
operator + and operator ! can be used to check, if the list is empty.
getCount() returns the number of list elements.
// content [For some Elem] T * getElem(); const T * getElem() const; const T * getElem_const() const;
List has a set of methods to access some specific list elements. They are following the shown above pattern.
template <class S>
struct Cur
{
....
// object ptr
void * operator + () const;
bool operator ! () const;
S * getPtr() const;
S & operator * () const;
S * operator -> () const;
// cursor
void operator ++ ();
[may have] void operator -- ();
};
Cur<T> getStart();
Cur<const T> getStart() const;
Cur<const T> getStart_const() const;
[may have RevCur]
template <class S>
struct RevCur
{
....
// object ptr
void * operator + () const;
bool operator ! () const;
S * getPtr() const;
S & operator * () const;
S * operator -> () const;
// cursor
void operator ++ ();
void operator -- ();
};
RevCur<T> getStartReverse();
RevCur<const T> getStartReverse() const;
RevCur<const T> getStartReverse_const() const;
To access list elements a list cursor can be used. Any list always has a forward cursor. Methods getStart...() return a forward cursor, positioned on the first element, if any. For double linked lists the cursor type has the operator -- to move backward.
List may have a backward cursor. Methods getStartReverse...() return a backward cursor, positioned on the last element, if any.
template <class S>
struct CountCur
{
....
};
CountCur<T> begin();
CountCur<T> end();
CountCur<const T> begin() const;
CountCur<const T> end() const;
[may support reverse loops]
template <class S>
struct RevCountCur
{
....
};
RevCountCur<T> rbegin();
RevCountCur<T> rend();
RevCountCur<const T> rbegin() const;
RevCountCur<const T> rend() const;
template <class S>
struct ReverseAdapter
{
RevCountCur<S> cur;
ReverseAdapter(RevCountCur<S> cur_) : cur(cur_) {}
RevCountCur<S> begin() const { return cur; }
RevCountCur<S> end() const { return RevCountCur<S>(); }
};
ReverseAdapter<T> reverse();
ReverseAdapter<const T> reverse() const;
ReverseAdapter<const T> reverse_const() const;
Lists implement methods begin()/end() and can be used in range-based for.
List may support a reverse order for range-based for. To run a reverse loop methods reverse...() are provided.
// ins/del [ins/del methods] .... ulen erase();
Each list has a set of ins/del methods to insert or delete list elements. The method erase() destroys all elements, the number of destroyed elements is returned.
// apply template <class FuncInit> void apply(FuncInit func_init); template <class FuncInit> void apply(FuncInit func_init) const; template <class FuncInit> void apply_const(FuncInit func_init) const; [may have applyReverse] template <class FuncInit> void applyReverse(FuncInit func_init); template <class FuncInit> void applyReverse(FuncInit func_init) const; template <class FuncInit> void applyReverse_const(FuncInit func_init) const;
Methods apply...() can be used to apply a functor to list elements. Functor Init Pattern is used. Double linked lists can apply a functor in the reverse order using methods applyReverse...().
// swap/move objects void objSwap(AnyList<T,Allocator> &obj); explicit AnyList(ToMoveCtor<AnyList<T,Allocator> > obj); };
All lists are swappable and movable.
This is a linear single linked list with a top element pointer.
template <class T,template <class Node> class Allocator=NodeAllocator>
class LinearSList : NoCopy
{
....
public:
// constructors
template <class ... SS>
explicit LinearSList(SS && ... ss) noexcept;
~LinearSList();
// std move
LinearSList(LinearSList &&obj) noexcept;
LinearSList & operator = (LinearSList &&obj) noexcept;
// props
ulen operator + () const;
bool operator ! () const;
ulen getCount() const;
// content
T * getTop();
const T * getTop() const;
const T * getTop_const() const;
template <class S>
struct Cur
{
....
// object ptr
void * operator + () const;
bool operator ! () const;
S * getPtr() const;
S & operator * () const;
S * operator -> () const;
// cursor
void operator ++ ();
};
Cur<T> getStart();
Cur<const T> getStart() const;
Cur<const T> getStart_const() const;
template <class S>
struct CountCur
{
....
};
CountCur<T> begin();
CountCur<T> end();
CountCur<const T> begin() const;
CountCur<const T> end() const;
// ins/del
template <class ... SS>
T * ins(SS && ... ss);
template <class S,class ... SS>
T * insAfter(Cur<S> pos,SS && ... ss); // +pos
bool del();
ulen erase();
// apply
template <class FuncInit>
void apply(FuncInit func_init);
template <class FuncInit>
void apply(FuncInit func_init) const;
template <class FuncInit>
void apply_const(FuncInit func_init) const;
// swap/move objects
void objSwap(LinearSList<T,Allocator> &obj);
explicit LinearSList(ToMoveCtor<LinearSList<T,Allocator> > obj);
};
getTop...() methods return a pointer to the top element.
ins() creates a new element as a top element of the list and returns a pointer. Method arguments are forwarded to the object constructor.
insAfter() creates a new element in the list after the cursor given non-null position. Extra method arguments are forwarded to the object constructor.
del() deletes the top element, if any. The return value if true, if the element was deleted.
This is a linear single linked list with first and last element pointers.
template <class T,template <class Node> class Allocator>
class LinearSList2 : NoCopy
{
....
public:
// constructors
template <class ... SS>
explicit LinearSList2(SS && ... ss) noexcept;
~LinearSList2();
// std move
LinearSList2(LinearSList2 &&obj) noexcept;
LinearSList2 & operator = (LinearSList2 &&obj) noexcept;
// props
ulen operator + () const;
bool operator ! () const;
ulen getCount() const;
// content
T * getFirst();
const T * getFirst() const;
const T * getFirst_const() const;
T * getLast();
const T * getLast() const;
const T * getLast_const() const;
template <class S>
struct Cur
{
....
// object ptr
void * operator + () const;
bool operator ! () const;
S * getPtr() const;
S & operator * () const;
S * operator -> () const;
// cursor
void operator ++ ();
};
Cur<T> getStart();
Cur<const T> getStart() const;
Cur<const T> getStart_const() const;
template <class S>
struct CountCur
{
....
};
CountCur<T> begin();
CountCur<T> end();
CountCur<const T> begin() const;
CountCur<const T> end() const;
// ins/del
template <class ... SS>
T * insFirst(SS && ... ss);
template <class ... SS>
T * insLast(SS && ... ss);
template <class S,class ... SS>
T * insAfter(Cur<S> pos,SS && ... ss); // +pos
bool delFirst();
ulen erase();
// apply
template <class FuncInit>
void apply(FuncInit func_init);
template <class FuncInit>
void apply(FuncInit func_init) const;
template <class FuncInit>
void apply_const(FuncInit func_init) const;
// swap/move objects
void objSwap(LinearSList2<T,Allocator> &obj);
explicit LinearSList2(ToMoveCtor<LinearSList2<T,Allocator> > obj);
};
getFirst...() methods return a pointer to the first element.
getLast...() methods return a pointer to the last element.
insFirst() creates a new element as a first element of the list and returns a pointer. Method arguments are forwarded to the object constructor.
insLast() creates a new element as a last element of the list and returns a pointer. Method arguments are forwarded to the object constructor.
insAfter() creates a new element in the list after the cursor given non-null position. Extra method arguments are forwarded to the object constructor.
delFirst() deletes the first element, if any. The return value if true, if the element was deleted.
This is a circular single linked list with a bottom element pointer.
template <class T,template <class Node> class Allocator>
class CircularSList : NoCopy
{
....
public:
// constructors
template <class ... SS>
explicit CircularSList(SS && ... ss) noexcept;
~CircularSList();
// std move
CircularSList(CircularSList &&obj) noexcept;
CircularSList & operator = (CircularSList &&obj) noexcept;
// props
ulen operator + () const;
bool operator ! () const;
ulen getCount() const;
// content
T * getBottom();
const T * getBottom() const;
const T * getBottom_const() const;
template <class S>
struct Cur
{
....
// object ptr
void * operator + () const;
bool operator ! () const;
S * getPtr() const;
S & operator * () const;
S * operator -> () const;
// cursor
void operator ++ ();
};
Cur<T> getStart();
Cur<const T> getStart() const;
Cur<const T> getStart_const() const;
template <class S>
struct CountCur
{
....
};
CountCur<T> begin();
CountCur<T> end();
CountCur<const T> begin() const;
CountCur<const T> end() const;
// ins/del
template <class ... SS>
T * ins(SS && ... ss);
template <class S,class ... SS>
T * insAfter(Cur<S> &pos,SS && ... ss); // +pos
bool del();
ulen erase();
T * rotate(); // return top element moved to bottom
// apply
template <class FuncInit>
void apply(FuncInit func_init);
template <class FuncInit>
void apply(FuncInit func_init) const;
template <class FuncInit>
void apply_const(FuncInit func_init) const;
// swap/move objects
void objSwap(CircularSList<T,Allocator> &obj);
explicit CircularSList(ToMoveCtor<CircularSList<T,Allocator> > obj);
};
getBottom...() methods return a pointer to the bottom element.
ins() creates a new element as a top element of the list and returns a pointer. Method arguments are forwarded to the object constructor.
insAfter() creates a new element in the list after the cursor given non-null position. Extra method arguments are forwarded to the object constructor. Cursor is updated.
del() deletes the top element, if any. The return value if true, if the element was deleted.
The method rotate() is specific for circular lists. It rotates the list. The top element moves to bottom. Pointer to this element is returned.
This is a linear double linked list with a top element pointer.
template <class T,template <class Node> class Allocator>
class LinearDList : NoCopy
{
....
public:
// constructors
template <class ... SS>
explicit LinearDList(SS && ... ss) noexcept;
~LinearDList();
// std move
LinearDList(LinearDList &&obj) noexcept;
LinearDList & operator = (LinearDList &&obj) noexcept;
// props
ulen operator + () const;
bool operator ! () const;
ulen getCount() const;
// content
T * getTop();
const T * getTop() const;
const T * getTop_const() const;
template <class S>
struct Cur
{
....
// object ptr
void * operator + () const;
bool operator ! () const;
S * getPtr() const;
S & operator * () const;
S * operator -> () const;
// cursor
void operator ++ ();
void operator -- ();
};
Cur<T> getStart();
Cur<const T> getStart() const;
Cur<const T> getStart_const() const;
template <class S>
struct CountCur
{
....
};
CountCur<T> begin();
CountCur<T> end();
CountCur<const T> begin() const;
CountCur<const T> end() const;
// ins/del
template <class ... SS>
T * ins(SS && ... ss);
template <class S,class ... SS>
T * insBefore(Cur<S> pos,SS && ... ss); // +pos
template <class S,class ... SS>
T * insAfter(Cur<S> pos,SS && ... ss); // +pos
bool del();
template <class S>
void delAndMove(Cur<S> &pos); // +pos
ulen erase();
// apply
template <class FuncInit>
void apply(FuncInit func_init);
template <class FuncInit>
void apply(FuncInit func_init) const;
template <class FuncInit>
void apply_const(FuncInit func_init) const;
// swap/move objects
void objSwap(LinearDList<T,Allocator> &obj);
explicit LinearDList(ToMoveCtor<LinearDList<T,Allocator> > obj);
};
getTop...() methods return a pointer to the top element.
Cursor can move backward.
ins() creates a new element as a top element of the list and returns a pointer. Method arguments are forwarded to the object constructor.
insBefore() creates a new element in the list before the cursor given non-null position. Extra method arguments are forwarded to the object constructor.
insAfter() creates a new element in the list after the cursor given non-null position. Extra method arguments are forwarded to the object constructor.
del() deletes the top element, if any. The return value if true, if the element was deleted.
delAndMove() deletes the element at the cursor given non-null position. Cursor is updated to point to the next element.
This is a linear double linked list with first and last element pointers.
template <class T,template <class Node> class Allocator>
class LinearDList2 : NoCopy
{
....
public:
// constructors
template <class ... SS>
explicit LinearDList2(SS && ... ss) noexcept;
~LinearDList2();
// std move
LinearSList2(LinearSList2 &&obj) noexcept;
LinearSList2 & operator = (LinearSList2 &&obj) noexcept;
// props
ulen operator + () const;
bool operator ! () const;
ulen getCount() const;
// content
T * getFirst();
const T * getFirst() const;
const T * getFirst_const() const;
T * getLast();
const T * getLast() const;
const T * getLast_const() const;
template <class S>
struct Cur
{
....
// object ptr
void * operator + () const;
bool operator ! () const;
S * getPtr() const;
S & operator * () const;
S * operator -> () const;
// cursor
void operator ++ ();
void operator -- ();
};
Cur<T> getStart();
Cur<const T> getStart() const;
Cur<const T> getStart_const() const;
template <class S>
struct RevCur
{
....
// object ptr
void * operator + () const;
bool operator ! () const;
S * getPtr() const;
S & operator * () const;
S * operator -> () const;
// cursor
void operator ++ ();
void operator -- ();
};
RevCur<T> getStartReverse();
RevCur<const T> getStartReverse() const;
RevCur<const T> getStartReverse_const() const;
template <class S>
struct CountCur
{
....
};
CountCur<T> begin();
CountCur<T> end();
CountCur<const T> begin() const;
CountCur<const T> end() const;
template <class S>
struct RevCountCur
{
....
};
RevCountCur<T> rbegin();
RevCountCur<T> rend();
RevCountCur<const T> rbegin() const;
RevCountCur<const T> rend() const;
template <class S>
struct ReverseAdapter
{
RevCountCur<S> cur;
ReverseAdapter(RevCountCur<S> cur_) : cur(cur_) {}
RevCountCur<S> begin() const { return cur; }
RevCountCur<S> end() const { return RevCountCur<S>(); }
};
ReverseAdapter<T> reverse();
ReverseAdapter<const T> reverse() const;
ReverseAdapter<const T> reverse_const() const;
// ins/del
template <class ... SS>
T * insFirst(SS && ... ss);
template <class ... SS>
T * insLast(SS && ... ss);
template <class S,class ... SS>
T * insBefore(Cur<S> pos,SS && ... ss); // +pos
template <class S,class ... SS>
T * insBefore(RevCur<S> pos,SS && ... ss); // +pos
template <class S,class ... SS>
T * insAfter(Cur<S> pos,SS && ... ss); // +pos
template <class S,class ... SS>
T * insAfter(RevCur<S> pos,SS && ... ss); // +pos
bool delFirst();
bool delLast();
template <class S>
void delAndMove(Cur<S> &pos); // +pos
template <class S>
void delAndMove(RevCur<S> &pos); // +pos
ulen erase();
// apply
template <class FuncInit>
void apply(FuncInit func_init);
template <class FuncInit>
void apply(FuncInit func_init) const;
template <class FuncInit>
void apply_const(FuncInit func_init) const;
template <class FuncInit>
void applyReverse(FuncInit func_init);
template <class FuncInit>
void applyReverse(FuncInit func_init) const;
template <class FuncInit>
void applyReverse_const(FuncInit func_init) const;
// swap/move objects
void objSwap(LinearDList2<T,Allocator> &obj);
explicit LinearDList2(ToMoveCtor<LinearDList2<T,Allocator> > obj);
};
getFirst...() methods return a pointer to the first element.
getLast...() methods return a pointer to the last element.
Cursor can move backward.
This list supports a backward cursor.
This list supports a reverse order for range-based for.
insFirst() creates a new element as a first element of the list and returns a pointer. Method arguments are forwarded to the object constructor.
insLast() creates a new element as a last element of the list and returns a pointer. Method arguments are forwarded to the object constructor.
insBefore() creates a new element in the list before the cursor (forward or backward) given non-null position. Extra method arguments are forwarded to the object constructor.
insAfter() creates a new element in the list after the cursor (forward or backward) given non-null position. Extra method arguments are forwarded to the object constructor.
delFirst() deletes the first element, if any. The return value if true, if the element was deleted.
delLast() deletes the last element, if any. The return value if true, if the element was deleted.
delAndMove() deletes the element at the cursor (forward or backward) given non-null position. Cursor is updated to point to the next element (in respect to the cursor movement direction).
This list supports the reverse functor applying.
This is a circular double linked list with a top element pointer.
template <class T,template <class Node> class Allocator>
class CircularDList : NoCopy
{
....
public:
// constructors
template <class ... SS>
explicit CircularDList(SS && ... ss) noexcept;
~CircularDList();
// std move
CircularSList(CircularSList &&obj) noexcept;
CircularSList & operator = (CircularSList &&obj) noexcept;
// props
ulen operator + () const;
bool operator ! () const;
ulen getCount() const;
// content
T * getTop();
const T * getTop() const;
const T * getTop_const() const;
template <class S>
struct Cur
{
....
// object ptr
void * operator + () const;
bool operator ! () const;
S * getPtr() const;
S & operator * () const;
S * operator -> () const;
// cursor
void operator ++ ();
void operator -- ();
};
Cur<T> getStart();
Cur<const T> getStart() const;
Cur<const T> getStart_const() const;
template <class S>
struct RevCur
{
....
// object ptr
void * operator + () const;
bool operator ! () const;
S * getPtr() const;
S & operator * () const;
S * operator -> () const;
// cursor
void operator ++ ();
void operator -- ();
};
RevCur<T> getStartReverse();
RevCur<const T> getStartReverse() const;
RevCur<const T> getStartReverse_const() const;
template <class S>
struct CountCur
{
....
};
CountCur<T> begin();
CountCur<T> end();
CountCur<const T> begin() const;
CountCur<const T> end() const;
template <class S>
struct RevCountCur
{
....
};
RevCountCur<T> rbegin();
RevCountCur<T> rend();
RevCountCur<const T> rbegin() const;
RevCountCur<const T> rend() const;
template <class S>
struct ReverseAdapter
{
RevCountCur<S> cur;
ReverseAdapter(RevCountCur<S> cur_) : cur(cur_) {}
RevCountCur<S> begin() const { return cur; }
RevCountCur<S> end() const { return RevCountCur<S>(); }
};
ReverseAdapter<T> reverse();
ReverseAdapter<const T> reverse() const;
ReverseAdapter<const T> reverse_const() const;
// ins/del
template <class ... SS>
T * insFirst(SS && ... ss);
template <class ... SS>
T * insLast(SS && ... ss);
template <class S,class ... SS>
T * insBefore(Cur<S> pos,SS && ... ss); // +pos
template <class S,class ... SS>
T * insBefore(RevCur<S> &pos,SS && ... ss); // +pos
template <class S,class ... SS>
T * insAfter(Cur<S> &pos,SS && ... ss); // +pos
template <class S,class ... SS>
T * insAfter(RevCur<S> pos,SS && ... ss); // +pos
bool delFirst();
bool delLast();
template <class S>
void delAndMove(Cur<S> &pos); // +pos
template <class S>
void delAndMove(RevCur<S> &pos); // +pos
ulen erase();
T * rotateForward(); // return top element moved to bottom
T * rotateBackward(); // return bottom element moved to top
// apply
template <class FuncInit>
void apply(FuncInit func_init);
template <class FuncInit>
void apply(FuncInit func_init) const;
template <class FuncInit>
void apply_const(FuncInit func_init) const;
template <class FuncInit>
void applyReverse(FuncInit func_init);
template <class FuncInit>
void applyReverse(FuncInit func_init) const;
template <class FuncInit>
void applyReverse_const(FuncInit func_init) const;
// swap/move objects
void objSwap(CircularDList<T,Allocator> &obj);
explicit CircularDList(ToMoveCtor<CircularDList<T,Allocator> > obj);
};
getTop...() methods return a pointer to the top element.
Cursor can move backward.
This list supports a backward cursor.
This list supports a reverse order for range-based for.
insFirst() creates a new element as a first element of the list and returns a pointer. Method arguments are forwarded to the object constructor.
insLast() creates a new element as a last element of the list and returns a pointer. Method arguments are forwarded to the object constructor.
insBefore() creates a new element in the list before the cursor (forward or backward) given non-null position. Extra method arguments are forwarded to the object constructor. Backward cursor is updated.
insAfter() creates a new element in the list after the cursor (forward or backward) given non-null position. Extra method arguments are forwarded to the object constructor. Forward cursor is updated.
delFirst() deletes the first element, if any. The return value if true, if the element was deleted.
delLast() deletes the last element, if any. The return value if true, if the element was deleted.
delAndMove() deletes the element at the cursor (forward or backward) given non-null position. Cursor is updated to point to the next element (in respect to the cursor movement direction).
This list supports the reverse functor applying.
The following two methods rotate...() are specific for circular lists. They rotate the list.
rotateForward() rotates the list forward. The top element moves to bottom. Pointer to this element is returned.
rotateBackward() rotates the list backward. The bottom element moves to top. Pointer to this element is returned.