What are the qualifications for a class in C++ to become a container?

Question

I'm new to C++ programming and came across the term containers with examples such as vector, deque, map, etc.

What should be the minimum requirements that a class should fulfill to be called a container in C++?

Answer 1

I will start with the concept Range.

Range has only two methods -- begin and end. They both return iterators of the same type (note: there are proposals to permit end to return a Sentinel instead).

Iterators are presumed to be understood by the reader.

A high quality Range can also expose empty, size, front, back, and operator [] (if random access especially).

For a for(:) loop, you can qualify as a Range by being a raw C array, having begin() and end() methods, or having free functions in the same namespace as your type that take your type as one argument (and return iterator-like things). As of this post, the only thing in the standard that consumes Ranges is for(:) loops. One could argue that this answer is the only practical definition of the concept Range in C++.

---

Next, Container.

A Container is a Range of at least forward iterators (input and output Ranges are usually not called Containers) that owns its elements. Sequential and Associative containers are different beasts, and both are defined in the standard.

Containers in the standard have a set of typedefs -- value type, iterator, const iterator. Most also have allocator (except array). They have empty, and most have size (except forward_list).

Containers can all be constructed by 2 input or forward iterators to a compatible value type, and from an initializer list.

Sequential containers have push and emplace back (except forward list) (and some have emplace/push front), and insert and emplace at iterator (or after for forward list).

Associative containers have a key type. Many of them are containers of pairs. The data stored is usually partially const (the "key" part of the data, be it the key or the entire field in the case of sets). They have insert and emplace with and without hints -- they manage their own order. They also have a .find and .count methods.

There are currently no functions in the std library that depend on Container-ness. And there is an active proposal to make Container-ness and Range-ness be formalized as a concept in C++17. The actual technical definition of Container is in the standard in case you need to create an actual container exactly; however, usually you really need a Range with a means to edit it and ownership mechanics. The Container concept is, in my experience, mostly there to make specifying behaviour easier in the standard.

After something like Ranges-v3 is added, the concepts of Range and Container will be actual things that exist in code, and there may be algorithms that depend on exactly those features. Prior to that, they are ad-hoc concepts more than anything.

Answer 2

The absolute minimum requirement should be that the container has a constant iterator class associated with it. Although a generator would satisfy that requirement as well. So it must be that there is a constant iterator and that the said container has begin and end values of the constant iterator type.

Answer 3

C++ concepts: Container

A Container is an object used to store other objects and taking care of the management of the memory used by the objects it contains.

http://en.cppreference.com/w/cpp/concept/Container

 

A container is a holder object that stores a collection of other objects (its elements). They are implemented as class templates, which allows a great flexibility in the types supported as elements.

http://www.cplusplus.com/reference/stl/

Given these definitions, I think we can say that containers should be able to store an arbitrary number of elements (although the number can be a compile-time constant). The container owns the objects it contains, including allocating space for them in the heap, or the stack (for the array container). Therefore, the programmer does not need to new or delete (allocate or free) the memory for the objects.

The following containers can be found in the STL: array, deque, vector, set, map, stack, queue, list, unordered_map, unordered_set

The container will usually allow you to access (or index) the elements it contains, although some only allow access to one or a few elements (eg. queue or stack). The container will provide methods to add or remove objects, or to search for an object.

Requirements:

• Must hold some arbitrary number of objects
• The objects it holds are an arbitrary type (although it may have to satisfy certain requirements, eg. sortable)

Possible features

• While some containers are allocator aware, it does not have to be.
• A container may hold more than one type of object (eg. map, although map can be considered to hold pairs of objects)
• While containers may be iterable, this is not required, eg. queue or stack.

Classes which are containers

• std::string: this is a collection of characters. Although is designed for characters, or wide-characters, it is a SequenceContainer

Some class which would not be considered containers:

• std::unique_ptr, std::shared_ptr: while these types have a concept of ownership, they only manage 1 object, so they are not a collection of objects
• std::tuple, std::pair: while a tuple can hold an arbitrary number of objects, the type of each object needs to be specified, so it doesn't have the flexibility expected of a general container. A tuple can be more accurately categorized as a type of structure.