A container library must include the most common container:
buffers.
I have decided to provide two:
(1) An extensible linear buffer: You write into it, and if there is no
place the buffer resizes itself automatically.
(2) A circular buffer, designed to hold the last<n> items of a stream.
When the buffer is full the oldest item is overwritten with the new data.
OK, but I may have missed some.
What other kinds of buffers should be there?
The only buffer that I've used before that is kind of unique is
referred to as a bipartite buffer. It's essentially a circular buffer
except that the elements can be variable sized. It basically
maintains a large buffer using a queue of block pointers (referenced
using a struct { void*, size_t }), and if it runs out of space, the
buffer will overwrite enough elements to make room for it.
queue
[ A, 3 bytes ]
[ B, 7 bytes ]
[ C, 3 bytes ]
[ D, 5 bytes ]
[ |.1.|...2...|.3.|..4..| ]
A B C D
The bipartite nature of it is that sometimes the elements form two
contiguous blocks within the buffer.
[|.6.|7| |..4..|....5....| ]
The main advantage over say maintaining an array of pointer elements
is that one can avoid calling malloc for each variable sized element,
but with the added complexity of maintaining a queue of block
pointers. I use it when having to process a live stream of data where
the individual messages are variable sized, i.e. data sent via strings
over a serial port. Sometimes in the embedded domain, one does not
have malloc available, so a bipartite buffer can be hardwired to
support a fixed buffer (the queue maintaining the elements in
bipartite buffer is fixed as well).
Not sure that this kind of buffer belongs in a generic container
library, as in my opinion it's a pretty specialized kind of buffer.
The tradeoff between its complexity and value is unclear.
Best regards,
John D.