Какой самый простой контейнер C++ 11 для реализации?

Question

Я хотел бы попытаться написать свой собственный контейнер, как упражнение, и я собираюсь создать что-то, что будет работать в соответствии со стандартом C++ 11, и я также пытаюсь избежать тривиальных и неэффективных реализаций как связанный список.

Я хотел бы получить информацию о том, что является самым простым и менее подробным контейнером для реализации, и в какой части стандарта C++ 11 я могу найти описание функций, которые требуются самим стандартом.

Answer 1

Сильное предложение: прочитайте две последние две книги Бьярна Страустрапа: «Программирование: принципы и практика с использованием C++» или «Тур по C++».

В обеих этих книгах он проводит вас через создание своего собственного «векторного» контейнера. Это информативное упражнение.

Answer 2

Попробуйте сделать что-то вроде std :: vector. Базовым контейнером будет что-то вроде:

T* someArray 

Вы выделяете массив по мере необходимости; создавать функции доступа и т. д. Когда массив заполняется, вам нужно выделить новый массив (часто удваивайте первоначальный размер), а затем скопируйте элементы из массива orig в него.

Я предполагаю, что вы просто хотите что-то экспериментировать; не нужно возиться со std :: allocators и т. д.

Выполнение простого динамического массива поможет вам понять, как эти типы контейнеров работают под капотом.

Answer 3

Возможно, вы захотите начать с std::array, что в основном представляет собой массив C-стиля на стероидах.

Вы можете первые реализовать основы, как begin и end (const и реверс версии может прийти позже), operator[] и функцию размера.

Начать с begin и end, потому что:

• с ними, вы можете сразу же использовать некоторые стандартные алгоритмы.
• диапазон для использования и итератора для ручных итераций

Для справки, вы можете получить C++11 standard here, ссылка, которую я получил от The Definitive C++ Book Guide and List. Конкретной главой будет номер 23 «Библиотека контейнеров»/[контейнеры].

Но стандарт C++ полон стандартизованных и часто ссылок вокруг многих других его частей, что делает чтение его линейно болью. Сначала вы можете начать с cppreference, который обеспечивает точное описание почти всего в стандартной библиотеке.

Answer 4

Самый простой, вероятно, std::array. Второй, вероятно, std::vector, который похож, но добавляет push_back, pop_back и (что еще более важно) весь внутренний код, чтобы расширить выделение по мере необходимости.

Что касается уровня сложности: они оба больше работают, чем вы, вероятно, ожидаете первоначально. Хотя это немного зависит от вашего подхода. Вы можете сделать довольно простой подход, который содержит достаточное количество близких к дублированию (например,, между iterator, reverse_iterator, const_iterator и const_reverse_iterator), или вы можете устранить большую часть дублирования за счет того, что код немного сложнее.

Для справок: вы смотрите в основном на §23.2 и 23.3 стандарта. 23.2 содержит требования к контейнерам в целом (большинство из них относятся как к array, так и к vector), а 23.3 содержит требования к контейнерам последовательностей (массив, вектор, дека, список, переадресация).