I would like to try to write my own container, just as an exercise, and I'm aiming to produce something that will work according to the C++11 standard, and I'm also trying to avoid trivial and inefficient implementations like a linked list.
I would like an input about what is the easiest and less verbose container to implement and in what part of the C++11 standard I can find the description of the features that are required by the standard itself.
You might want to start from std::array, which is basically a C-style array on steroids.
You might want to implement the basics first, like begin and end (the const and reverse versions can come later), operator[], and the size functions.
Start with begin and end because:
For reference, you can get the C++11 standard here, a link which I got from The Definitive C++ Book Guide and List. The specific chapter would be number 23, "Containers library"/[containers].
But the C++ standard is full of standardese and often links around many other parts of it, which makes reading it linearly a pain. You may want to start with cppreference first, which provides accurate descriptions of almost everything in the standard library.
Strong suggestion: read either of Bjarne Stroustrup's last two books: "Programming: Principles and Practice Using C++", or "A Tour of C++".
In both of these books, he walks you through creating your own "vector" container. It's an informative exercise.
The easiest is probably std::array. Second is probably std::vector, which is similar but adds push_back, pop_back and (more importantly) all the internal code to expand the allocation as needed.
As to the level of difficulty: they're both more work than you probably expect initially. Quite a bit depends on your approach though. You can do a fairly simple approach that contains a fair amount of near-duplication (e.g., between iterator, reverse_iterator, const_iterator and const_reverse_iterator), or you can eliminate most of the duplication at the expense of the code being a little trickier.
For references: you're looking primarily at §23.2 and 23.3 of the standard. 23.2 contains requirements for containers in general (most of which apply to both array and vector) and 23.3 contains requirements specific to sequence containers (array, vector, deque, list, forward_list).
Try doing something like a std::vector. The underlying container would be something like:
T* someArray
You allocate the array as needed; create accessor functions etc. When the array fills up you have to allocate a new array (often double the original size), then copy the elements from the orig array to it.
I'm assuming you just want something to experiment with; not having to mess with std::allocators etc.
Doing a simple dynamic array will help give you insight into how these sort of containers work under the hood.
