Write C++ container that fits neatly into STL

Question

I would like to write a container class in a style which fits very neatly into STL. It should look and behave as if it where a standard STL container.

Is there a manual, report, Q&A, etc., out there that describes how to write code with these set of features? Such a text should compromise design principles of the STL, pitfalls, coding conventions, and the like.

PS: This question has been partly inspired by that one: C++ vector with dynamic item size although that idea is not about template classes.

Paper

What is your container going to do? It's quite hard to think up useful new ones. – Teleplay

@Neil I can think of a few. There are numerous special purpose containers. Or, as an example of a general purpose container that’s not in C++ nor Boost: a skip list. – Salamone

@Konrad I said hard, not impossible. I still think writing your own STL compatible container should be a last resort, not (as it seems in this case) a first. – Teleplay

@Neil, this could simply be an exercise. I think the OP will learn a lot by going through the process of writing a new container, even if it's not necessarily useful in production code. – Ebneter

Answer 1

It is not very difficult (for simple data stuctures). You should read the chapter about containers in the C++ standard. You can download the draft of the upcoming C++1x standard here :

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/#mailing2011-04

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf

You might want to use boost::iterateror_facade when writing the iterators.

http://www.boost.org/doc/libs/1_46_1/libs/iterator/doc/iterator_facade.html

Parachute

Make sure you support the iterator requirements precisely - then all the STL algorithms will just work. The container requirements are less important - there isn't much that is intended to work with many different containers. The best idea is to make your container similar to one of the standard ones, but don't worry about being different when it's appropriate. – Lezley

I feel compelled to say that the actual draft standard is n3290 (FDIS) and it is behind a password wall. Therefore, it is mightily unhelpful to anyone not able or willing to pay for it. – Bouse

You can get the previous one. The difference bewteen n3290 and for example n3242 are probably not very important for the casual programmer (I don't know what happened recently but I guess it is probably minor editational details and/or things that matter for language implementors). (Anyone ?) I don't thinck you need the real definitive C++1x standard to implement a container. – Parachute

Answer 2

I recommend reading Herb Sutter's "Unstrung". It's an in-depth look at std::string, covering what went right and what could've been done better. I highly value his opinion on C++ programming matters. It's a long read, but I guarantee you'll learn a few useful things about writing classes in the style of the C++ standard library (and about writing classes in general).

You could also take a look at Scott Meyers' Effective STL. That book will give you a good overview of the expectations levied on the users of standard library containers. Having that insight will help you write better container classes yourself.

Ebneter

Answer 3

I'd recommending reading Josuttis, The C++ Standard Library: A Tutorial and Reference. It gives clear and easy to read explanations of the principles behind STL.

Alongshore

Answer 4

Besides the one recommended by user763305, I would also look at Austern, Generic Programmming and the STL: Using and Extending the C++ Standard Template Library. It discusses these sorts of issues and serves as a good reference for the concepts in STL.

Lightsome