Wednesday, 19 November 2008

C++: An STL-like circular buffer (Part 2)

In part 1 we looked at what a circular buffer is, and why you'd want to use (or write) an STL-compliant circular buffer. Now let's start to write one.

First, a few preliminaries:
  • How will we ensure it is thread safe? This is a real issue, as most circular buffer applications are in producer/consumer applications where the consumer and producer are running on different threads. The answer: for an STL container, this is not an issue - we will ignore threading issues, as current STL container implementations do. It is up to the client of the circular_buffer class to use it in a thread safe manner.
  • Do we want to write a container adaptor? Some standard C++ containers are actually container adaptors - data types that wrap and adapt existing container types and give them a more specialised interface. For example, std::priority_queue is an adaptor that, by default, wraps a std::vector. In this instance, it is not particularly beneficial to wrap any other container type, and so we will not make the circular_buffer an adaptor type.
Every journey has a start

So let's kick off the data type by writing a simple starting scaffold:
template <typename T> //< See note below
class circular_buffer
circular_buffer(size_t capacity);
This defines the class, circular_buffer, that will store items of type T.

There is already one issue apparent that we will shelve for a while: allocators. STL containers all take an additional template parameter that describes how the container should allocate and free internal memory resources. We'll come back to that later. (Honest)

The constructor takes the fixed size of the internal data store of the circular buffer. We could chose to provide a default implementation to make using the class 'easier', but I don't see any advantage to doing so. Each use of a circular buffer is individual, and the storage requirements depend on the situation. Providing a default value could lead to problems in practice, so I'd like to force the programmer to consider the size of storage needed each time they instantiate a circular_buffer.

Although this is a very simple scaffold, let's write a unit test to i) prove that the code compiles OK, and to ii) check that it works.
int main()
circular_buffer cb1(10);
circular_buffer cb1(100);
Naturally, this compiles cleanly. However, it won't link or run, since we've not written the body of the constuctor yet. All this fun, and more, is yet to come.

Next time: the next step is to set up the basic typedefs required of an STL-compliant container.

1 comment:

lijialefw said...

Why was there no follow on bankruptcy then? The bailout of AIG FP went to (wow power leveling) hedge funds that bound credit swaps on Lehman failing or others betting on rating (wow power leveling) declines. AIG has drained over 100 billion from the government. Which had to go to (wow power leveling) those who bet on failures and downgrades. Many of whom (power leveling)were hedge funds. I-banks that had offsetting swaps needed the money from the AIG bailout or they would have been caught. Its an (wow powerleveling) insiders game and it takes just a little bit too much time for most people to think (wow gold) through where the AIG 100 billion bailout money went to, hedge funds and players, many of whom hire from the top ranks of DOJ, Fed, Treasury, CAOBO