stl compliant container

Question

I've been curious as to what entails an stl-compliant container (or boost-compliant, my understanding is that their either the same, or very similar). I've seen a few examples of what people call stl-compliant (for example, this one over at codeproject, and obviously the actual stl containers), but I'm not exactly sure what components of those containers I need to have.

From what i could gather, I need at least these things:

1. STL-compliant Iterators (the current stl only uses bi-directional or higher iterators, don't know if this is a requirement or just happens-chance, still figuring out what's necessary to be considered a "stl-compliant iterator")

2. Mechanism for defining allocators (default to std::allocator), as well as using them correctly (still trying to figure out what this last part means)

3. public typedefs for metaprogramming (pointer type, const pointer type, reference type, value type, const reference type, difference type, maybe some others?). Side question: What is a difference type?

4. 'generic' (i.e. uses metaprogramming/templates to make the container able to hold pretty much any type)

Is there anything else I've missed, or worse, got wrong in the above list (perhaps things such as const-correctness, thread safety, exceptions generation/handling, etc.)? Also, is there a specifications doc somewhere detailing what is required, if such a thing even exists?

Answer 1

1. Iterators: the standard library defines iterator categories. You want to supply iterators that model one of those categories. Depending on your viewpoint, the istream_iterator and ostream_iterator allow streams to be containers that don't supply bidirectional iterators.

2. Basically, you use the allocator's allocate(n) to allocate space for n objects, and deallocate(p, n) to free the space for n objects pointed to by p. You normally don't use the allocator's construct or destroy members.

3. Yes, there are a few others (e.g., associative containers define a key_type). difference_type is a type that can represent the difference between two pointers. It's normally supplied by the allocator, so a container will just have a typedef something like:

   typedef Allocator::difference_type difference_type;
   

4. There's not necessarily (or even commonly) any metaprogramming involved, just (fairly basic) generic programming. I.e., you define a template, but don't necessarily carry out any computation at compile time (which would be metaprogramming).

The standard that was current when this was originally asked didn't define anything about threading or thread safety. Any threading support you used was entirely separate, and you needed to follow the rules it specified (usually that multiple threads could read a container, but a thread required exclusive access to write a container).

Starting with C++11, the standard did add support for threading, including definitions about thread safety, data races, and so on. This specifies that parallel reading is allowed, but writing needs to be exclusive.