[boost] Re: Review Request: cyclic_buffer

From: Nigel Stewart (nigels_at_[hidden])
Date: 2003-06-09 18:59:07

> Ok, ok, but what with insert? What element should be removed: the first or the last
> one? And why the first approach or the latter.

        Indeed, that's an issue.  Let's look at the possibilities:
        (I'm speaking here about left/right or begin/end, rather than
         order in which items were inserted in FIFO fashion)

        1.	Shift everything after pos along to the right, overwriting
                the frontmost items if necessary.

        2.	Shift everything before pos along to the left, overwriting
                the backmost items if necessary.

        3.	Disallow insertions that don't fit in the available
                capacity, only push_front() and push_back() can utilise
                the cyclic characteristic of the container.

        4.	Disallow insert completely.

        Pros and cons:

        1.	+ Most consistant with std::vector semantics.
                + Consistency with resize() semantics (rightmost items lost
                  when shrinking)
        2.	- Counter intuitive(?)
        3.	- Forces client code to be capacity aware and do extra
                  handling.
        4.	- Consistency with other containers that support insert()

        I would lean towards (1), since if (2) is desired then the client
        code could swap which ends they push and pop from.  (3) and (4)
        don't seem satisfactory from a completeness point of view.

>>                This would allow use as a LIFO (last-in, last-out)
>>                with fixed sized "event horizon". (As an example.)

        The best example I can suggest an "undo buffer", such as in a
        text editor, which should have a stack-like behaviour but
        need not store an indefinite history.

        I agree that a circular_buffer can't be all things to all
        applications, but a generic general purpose container with
        a concise and rational behaviour should be possible.  We
        should look at ways that other policy could possibly be
        layered on top of a generic circular_buffer.  (One experiment
        would be whether std::stack and std::queue would behave
        sensibly as circular_buffer adaptors.)  Let's explore these
        before deciding that more containers or more elaborate
        policy aspects are necessary to solve the vast majority
        of uses.

        Cheers,

        Nigel