C++ annulus container.
Version of Sunday 14 December 2014.
Dave Barber's other pages.

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
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.
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:

Any binary tree implementation whose nodes have these four fields will suffice; among other customizations, programmers may supply their favorite balancing strategy. Use of a binary tree means that most operations take place in logarithmic time, O(log n).

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
    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:

vec_iter    vec_iter
vec_begin ();
vec_end ();
vec_con_iter   vec_con_iter
vec_cbegin () const;
vec_cend () const;
vec_rev_iter  vec_rev_iter
vec_rbegin ();
vec_rend ();
vec_con_rev_iter vec_con_rev_iter
vec_crbegin () const;
vec_crend () const;
lis_iter    lis_iter
lis_begin ();
lis_end ();
lis_con_iter   lis_con_iter
lis_cbegin () const;
lis_cend () const;
lis_rev_iter  lis_rev_iter
lis_rbegin ();
lis_rend ();
lis_con_rev_iter lis_con_rev_iter
lis_crbegin () const;
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.

vx ==
lx ==
vy ==
ly ==

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

vx ==
lx ==
ly ==5"eta"
vy ==6"theta"


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:

with similar results for the seven other categories of iterators; they all "cycle around". This behavior is not mandated by any C++ standard, although it is exhibited by some implementations of std::list. Further, the following functions interpret the index n according to modulo A.size()+1:
    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:

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
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
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
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
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
excluded to prevent corruption of data

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

these comparisons are possible: Similarly with these reverse iterators: these comparisons are possible: List-style iterators compare analogously. All six of the following operators are available for each style:

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 <	
    compo, int, compo *, compo & > {
    // EXCERPT
    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
    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
It is the opinion of the developer holds that this too subtly converts a const iterator into a non-const iterator. The output iterator of erase is normally calculated by simply incrementing the input iterator, and that is what annulus does. Such a de facto conversion should be handled by an operation with a more conspicuous syntax.