ВСЕМ "ИЗВЕСТНЫЕ" АЗЫ
=====================

Начнем, как положено, с терминологии!
* Массив, array. Он же статический массив. Это int x[N]. Либо int *x.
* Вектор, vector. Он же динамический массив. class { int *data, length, capacity; } тащемта.
* В других языках и прочем CS все иначе (см. Java, C#, и разумеется PHP), здесь вроде так.

Зачем вообще нужны вектора?
* int x[16] vs alloca(64) vs malloc(64)
* int x[16] - быстрое; sub esp,64
* alloca(64) - быстрое; sub esp,64
* malloc(64) - как ни суй, как ни ворочай, (сильно) более 1 инструкции
=> локальный мелкий буфер ВСЕГДА быстрее vector!

Вектор == зачем?
* "Медленно", безопасно, с оверхедами.
* Про оверхеды: можно играться в спецмакросы даже в отладочных билдах.
* Иии главное: ПРОСТО. Просто берешь и пишешь код.
* Без дурацких len++ или resize() вручную.

Какие виды векторов нам вообще нужны?
1. Труёвый динамический, std::vector classic
2. Фиксированный размер, но с проверками, std::array, а до того eastl::fixed_vector
   * Обратите внимание, с динамичностью размер НЕ связан!
   * Говорят, std::array<T,N>, то есть нединамичный совсем никак
   * Точно знаю, иногда надо my::fixed_vector v(x) во втором смысле ("где данные лежат") динамичный
+ Как всегда, гибриды рулят, чтобы поменьше аллокаций

Пишем свой первый условно "полезный" вектор вообще за 1 минуту:

template<typename T>
class super_simple_vector {
public: // в нормальном, конечно, protected!
    T * data;
    int max_capacity;
    int cur_length;
public:
    T & operator[](int index) {
        // !!! вот она, радость-то! (ну или половина радости)
        assert(index >= 0 && index < cur_length);
        return data[index];
    }
};

Спорный (?) тезис #1
* 99% времени нужно условных 3 метода
* ctor, dtor, push_back, erase
* в остальных 95% случаев operator[]
* вроде и всё!!!

Понятное дело, нужно ещё всякое:
* resize, clear, reserve
* возможно, варианты конструкторов
* наверняка копирование (и оператором и конструктором)
* move semantics для любителей (я не они)
* если наконец C++11, то всякие begin()/end() итп
* всё равно, утверждаю, что ~99% вызовов будет не про них :)

Спорный (?) тезис #2
* Ключевой "параметр" у вектора примерно один
* Resize policy!
??? Со скольки элементов начинаем вектор? - 0, 1, 3, 4, 8, ... интуитивно, 4-32 довольно хорошо
??? Как подращиваем, когда кончилось? - *sqrt(2), *1.5, *2, ... внезапно! *1.2 для особо больших. Очевидно, любая конкретная константа в каком-то случае ПЛОХА И ВРЕДНА.
??? Скукоживаемся ли автоматически вниз, или как обычно? - наверное нет!!!

Спорный (?) тезис #3
* Стандарт необязателен ("it's more of a guideline")
* Стандарт не всеобъемлющ
* Зачем вам вообще именно итераторы?
* Что у вас в реалиях с инициализацией?
* Честный нудный .emplace_back() или грязный хак .add()?
* Как насчет .addn(int n)?
  - memcpy(buf.addn(len), ptr, len)

Развлечение для гиков #1
??? В каком порядке укладывать поля?

Развлечение для гиков #2
??? Попробовать автоматически "скукоживаться" (то есть reclaim-ить память)

struct hybrid_vector {
    T * data;
    int max_capacity;
    int cur_length;
    T * big_buffer; // можно выкинуть. if (data != small...)
    T small_buffer[32]; // дискуссионный вопрос!
};

Ура, теперь мы знаем всё.
Что ещё хочется рассказать про массивы и вектора?
* Напоминаю, массивы БЫСТРЕЕ. История про int *out вместо vector<int>.
* Напоминаю, C vs Pascal (terminator vs length) иногда работает.
* Напоминаю, SSO/SCO. Иногда аллокатор это решает; а иногда нет.

А ещё бывают стандартные баги.
И в реализации, и в использовании, и функционально, и про перф.

Про реализацию:
* POD vs non-POD
* Политика resize
* Политика инициализации
* [censored] [top-secret]

Про использование:
* int *ptr = &vec[123]; vec.push_back(456); // oops, crash
* for(;;) { ...; vec.clear(); } // oops, realloc NOT guaranteed
* for(;;) { ...; myvec.reset(); } // oops, realloc guaranteed
* Да, shrink_to_fit(). Нет, клевещут, non-binding.
* for(;;) { vec.reserve(vec.size() + 1); ... } // oops, O(N^2)
* А ещё клевещут, reserve() + push_back() vs new + assign не очень!

А ещё бывают совсем странные реализации.
* Chunked non-contiguous гибриды, чтобы manageable куски
* Разреженные массивы (это внезапно KV и сразу Judy arrays)

ЧЕМУ МЫ НАУЧИЛИСЬ СЕГОДНЯ?
---------------------------

* Свой вектор это совсем-совсем нехитро.
* Взгреть STL в отдельном месте совсем-совсем нетяжело.
* Всё дело в волшебных "частных" случаях!

--eof--