In a modern system, random memory access is now the killer. The CPU has cycles to burn. Some of the lessons I've learned on performance recently taught the exact opposite of what was true twenty years ago.

To that end, a modern style of dealing with containers has to be bounded. You need to know where you are, and what your limits are. There's some issue with what operator++() should do when you reach those limits, but the one answer for sure is that it can't just go stepping past and start stomping on whatever's next. To that end, my current libraries have the following concepts for both buffers and containers:

A Range is a beginning and and end.

These never own the storage, they just indicate where it is. This can be used for both the available space to write to, and for the used space containing data within a buffer or container.

A cursor is a range + an iterator.

This is where I've gone a bit past all the other work in C++ containers, but I think this is important. Modern iterators (at least the fun ones), are bidirectional or random access. That means the beginning is as important to keep track of as the end. And copying a cursor should not narrow you to the space you had left, but should allow the copy to head backwards to the front just as easily as progressing to the end.

This also gives us a great data structure for those algorithms like std::rotate() that operate on three iterators.

There have been a lot of people banging around on this for some time. Andrei Alexandrescu wrote a great paper On Iteration that had lots of stuff to say about his implementation of containers and interators for D.

Labels: c++, programming