The source code is here; everyone may copy and modify it as desired.

The annulus is a container for use with C++ programs. It resembles sequential containers in the C++ Standard Library, in particular std::vector and std::list, and is intended as a cross between the two. The name annulus arises from the behavior of the iterators, which will be explained later.

Why create another kind of container? It has to do with speed, as detailed in the following table where the number of elements in a container is represented by n:

	std::vector, or almost any array	std::list, or almost any doubly-linked list
fast O(1)	The time required to access the ith element (counting from the beginning) is constant, and brief.	The time required to insert or delete an individual element at a known position is constant, and brief.
slow O(n)	The time required to insert or delete an individual element is proportional to the number of elements after it, because in the case of insertion, they must be shifted to make room, and in the case of deletion, they must be shifted to close the gap.	The time required to access the ith element is proportional to n, because counting must start with the first element, and proceed through elements one by one until the desired element is reached.

Some programs need reasonably fast performance in all four of these areas. When a container has only a few elements, practically any data structure will do; but when the container has thousands of elements, its internal design has a major influence on speed.

This implementation of annulus stores elements in a binary tree, although that structure is not visible to the user. Each element of the annulus is stored in one node which contains four principal fields:

• each node contains a pointer to its left subtree, if present;
• each node contains a pointer to its right subtree, if present;
• each node (except the root) contains a pointer to its parent;
• each node contains an integer representing its weight, which is calculated as the sum of the following:
  • the number 1
  • the weight of this node's left subtree, or 0 if the left subtree is not present
  • the weight of this node's right subtree, or 0 if the left subtree is not present

In this implementation, each node also contains a serial number to aid diagnostics; plus a bool which is true for an ordinary node, and false for a temporary node (only used internally) that contains no data.

Function annulus::size() returns the number of nodes in the tree, which is the weight of the root, or zero is the annulus is empty. This equals the number of elements apparent to the user.

The following are some important members of class annulus. The functions generally have the behavior that one would expect from std::vector or std::list. The main surprise is that there are two categories of iterators, one vector-style and one list-style.

Members pertaining to insertion, emplacement, and erasure will be introduced after iterators are discussed.

template <typename compo>
class annulus {
    // EXCERPT
public:
    annulus (); 
    annulus (annulus const &);
    annulus (annulus &&);
    annulus & operator= (annulus const &);
    annulus & operator= (annulus &&);
    ~annulus ();

    class vec_iter;
    class vec_con_iter;
    class vec_rev_iter;
    class vec_con_rev_iter;

    class lis_iter;
    class lis_con_iter;
    class lis_rev_iter;
    class lis_con_rev_iter;

    vec_iter         vec_begin   ();
    vec_iter         vec_end     ();
    vec_con_iter     vec_cbegin  () const;
    vec_con_iter     vec_cend    () const;
    vec_rev_iter     vec_rbegin  ();
    vec_rev_iter     vec_rend    ();
    vec_con_rev_iter vec_crbegin () const;
    vec_con_rev_iter vec_crend   () const;

    lis_iter         lis_begin   ();
    lis_iter         lis_end     ();
    lis_con_iter     lis_cbegin  () const;
    lis_con_iter     lis_cend    () const;
    lis_rev_iter     lis_rbegin  ();
    lis_rev_iter     lis_rend    ();
    lis_con_rev_iter lis_crbegin () const;
    lis_con_rev_iter lis_crend   () const;

    void swap (annulus &);
    void reverse ();

    compo       & front ();
    compo const & front () const;
    compo       & back ();
    compo const & back () const;

    compo       & at (size_t const);
    compo const & at (size_t const) const;
    compo       & operator[] (size_t const);
    compo const & operator[] (size_t const) const;

    void clear  ();
    size_t size () const;
    bool empty  () const;

    void view (ostream & o) const;
};

This implementation assumes use of the standard allocator, namely std::allocator. It may become a template parameter in a future version.

Iterators for std::vectors do not behave the same as iterators for std::lists, the difference becoming most apparent when elements are inserted or erased. Because annulus offers behavior encompassing that of both std::vector and std::list, annulus needs to offer eight iterators, all random-access, listed below with the corresponding begin and end functions:

iterator	vector -style?	list -style?	constant?	reverse?	begin	end
vec_iter	✓				vec_iter vec_begin ();	vec_iter vec_end ();
vec_con_iter	✓		✓		vec_con_iter vec_cbegin () const;	vec_con_iter vec_cend () const;
vec_rev_iter	✓			✓	vec_rev_iter vec_rbegin ();	vec_rev_iter vec_rend ();
vec_con_rev_iter	✓		✓	✓	vec_con_rev_iter vec_crbegin () const;	vec_con_rev_iter vec_crend () const;
lis_iter		✓			lis_iter lis_begin ();	lis_iter lis_end ();
lis_con_iter		✓	✓		lis_con_iter lis_cbegin () const;	lis_con_iter lis_cend () const;
lis_rev_iter		✓		✓	lis_rev_iter lis_rbegin ();	lis_rev_iter lis_rend ();
lis_con_rev_iter		✓	✓	✓	lis_con_rev_iter lis_crbegin () const;	lis_con_rev_iter lis_crend () const;

The notion of constant iterator is essentially the same as that in the C++ Standard Library, but the reverse iterators furnished with annulus do not exhibit the shift-by-one behavior characteristic of std::reverse_iterator. Instead, when an iterator is converted between forward and reverse, the resultant iterator refers to the same element as the original iterator. It was the opinion of the developer that the shift-by-one feature, although there is rationale to support it, is in practical use a nuisance. Programmers who require shift-by-one behavior can still get it by writing typenames such as std::reverse_iterator<annulus<your_type_here>::vec_iter>.

Here is an illustration of how vector-style and list-style iterators differ, using an annulus<std::string> loaded with letters of the Greek alphabet. In the "before" table below, vx and vy are vec_iters initialized to point to the elements at indices 2 and 6 respectively. Meanwhile, lx and ly are lis_iters initialized to point to the same elements. The asterisk is the usual C++ indirection operator.

before	iterators	index	contents
		0	"alpha"
		1	"beta"
	∗vx == ∗lx ==	2	"gamma"
		3	"delta"
		4	"epsilon"
		5	"zeta"
	∗vy == ∗ly ==	6	"eta"
		7	"theta"
		8	"iota"
		9	"kappa"

Next the element at index 4, containing "epsilon", is erased. Now ly != vy:

after	iterators	index	contents
		0	"alpha"
		1	"beta"
	∗vx == ∗lx ==	2	"gamma"
		3	"delta"
		4	"zeta"
	∗ly ==	5	"eta"
	∗vy ==	6	"theta"
		7	"iota"
		8	"kappa"

If three more elements are erased, vy equals end(). An unofficial interpretation of these iterators is that a vec_iter is a wrapper for an integer, and a lis_iter is a wrapper for a pointer to a location in main storage.

Now for an explanation of the annularity of these iterators. For any annulus A:

• A.vec_begin() == A.vec_end() + 1
• A.vec_begin() - 1 == A.vec_end()

    annulus::compo       & at         (size_t const n); 
    annulus::compo const & at         (size_t const n) const; 
    annulus::compo       & operator[] (size_t const n); 
    annulus::compo const & operator[] (size_t const n) const; 

    compo & annulus::vec_iter::operator[] (int const n) const;
    compo & annulus::lis_iter::operator[] (int const n) const;
    compo & annulus::vec_rev_iter::operator[] (int const n) const;
    compo & annulus::lis_rev_iter::operator[] (int const n) const;

    compo const & annulus::vec_con_iter::operator[] (int const n) const; 
    compo const & annulus::lis_con_iter::operator[] (int const n) const; 
    compo const & annulus::vec_con_rev_iter::operator[] (int const n) const; 
    compo const & annulus::lis_con_rev_iter::operator[] (int const n) const; 

The usual copy-assignment and move-assignment operators are provided for each of these iterators, as are copy and move constructors. Default constructors (in other words, constructors that take zero parameters) are not supplied, despite the C++ library standard, because they would generate iterators that are assuredly invalid. Numerous iterator conversion constructors are provided:

list-style to vector-style	explicit vec_iter (lis_iter); explicit vec_con_iter (lis_con_iter); explicit vec_rev_iter (lis_rev_iter); explicit vec_con_rev_iter (lis_con_rev_iter );	O(log n) time
vector-style to list-style	explicit lis_iter (vec_iter); explicit lis_con_iter (vec_con_iter); explicit lis_rev_iter (vec_rev_iter); explicit lis_con_rev_iter (vec_con_rev_iter);	O(log n) time
forward to reverse	explicit vec_rev_iter (vec_iter); explicit vec_con_rev_iter (vec_con_iter); explicit lis_rev_iter (lis_iter); explicit lis_con_rev_iter (lis_con_iter);	O(1) time
reverse to forward	explicit vec_iter (vec_rev_iter); explicit vec_con_iter (vec_con_rev_iter); explicit lis_iter (lis_rev_iter); explicit lis_con_iter (lis_con_rev_iter);	O(1) time
variable to constant	vec_con_iter (vec_iter); vec_con_rev_iter (vec_rev_iter); lis_con_iter (lis_iter); lis_con_rev_iter (lis_rev_iter);	O(1) time
constant to variable	excluded to prevent corruption of data

The usual iterator comparison operations are supplied. Given these definitions of vector-style iterators:

• vec_iter vi_a { /* init */ };
• vec_iter vi_b { /* init */ };
• vec_con_iter vci_a { /* init */ };
• vec_con_iter vci_b { /* init */ };

• vi_a == vi_b
• vi_a == vci_b
• vci_a == vi_b
• vci_a == vci_b

• vec_rev_iter vri_a { /* init */ };
• vec_rev_iter vri_b { /* init */ };
• vec_con_rev_iter vcri_a { /* init */ };
• vec_con_rev_iter vcri_b { /* init */ };

• vri_a == vri_b
• vri_a == vcri_b
• vcri_a == vri_b
• vcri_a == vcri_b

• operator==
• operator!=
• operator<=
• operator>=
• operator<
• operator>

Not provided is direct comparison of vector-style and list-style iterators; or of forward and reverse iterators. When needed, the programmer can introduce an explicit conversion of one operand or the other.

As a recap, the highlights of vec_iter follow. The other iterators are much the same.

class vec_iter : public std::iterator <	
    std::random_access_iterator_tag,
    compo, int, compo *, compo & > {
    // EXCERPT
public:
    vec_iter () = delete;
    vec_iter (vec_iter const &);
    vec_iter (vec_iter &&);
    vec_iter & operator= (vec_iter const &);
    vec_iter & operator= (vec_iter &&);
    ~vec_iter ();

    explicit vec_iter (lis_iter const &);
    explicit vec_iter (vec_rev_iter const &);

    vec_iter & operator+= (int const);
    vec_iter & operator-= (int const);
    vec_iter   operator+  (int const) const;
    vec_iter   operator-  (int const) const;

    vec_iter & operator++ ();
    vec_iter & operator-- ();
    vec_iter   operator++ (int);
    vec_iter   operator-- (int);

    bool operator== (vec_con_iter const &) const;
        // similarly for  !=  >=  <=  >  < 

    int operator- (vec_con_iter const &) const;
 
    compo & operator* () const;
    compo * operator-> () const;
    compo & operator[] (int const) const;
    size_t get_index () const;
};

With iterators established, the members of annulus for inserting, emplacing and erasing can be listed.

template <typename compo>
class annulus {
    // EXCERPT
public:
    void push_front (compo const &);
    void push_back  (compo const &);

    vec_iter insert_before (vec_iter const &, compo const &);
	// similarly for the other seven iterators
    vec_iter insert_after  (vec_iter const &, compo const &);
	// similarly for the other seven iterators

    template <typename ... ARGS> 
        void emplace_front (ARGS&& ...);
    template <typename ... ARGS> 
        void emplace_back  (ARGS&& ...);

    template <typename ... ARGS> 
        vec_iter emplace_before (vec_iter const &, ARGS&& ...);
            // similarly for the other seven iterators
    template <typename ... ARGS> 
        vec_iter emplace_after  (vec_iter const &, ARGS&& ...);
            // similarly for the other seven iterators

    void pop_front ();
    void pop_back  ();

    vec_iter     erase (vec_iter     const &);
        // similarly for the other three non-const iterators
    vec_con_iter erase (vec_con_iter const &);
        // similarly for the other three const iterators
};

Containers in the standard library generally have a function called insert. On the other hand, annulus has both insert_before and insert_after in order to emphasize the fore-and-aft symmetry of its structure.

The standard calls for erase to return a non-const iterator even if the parameter is a const iterator, as in

    vec_iter erase (vec_con_iter const &); // standard, but not annulus