std::vector в C++: от основ к оптимизации производительности

// Эффективный доступ к элементам из-за непрерывного размещения
std::vector<int> v = {1, 2, 3, 4, 5};
int* rawPointer = v.data(); // Получение указателя на первый элемент
int thirdElement = *(rawPointer + 2); // Прямой доступ через арифметику указателей

// Демонстрация разницы в производительности между
// операциями константного и линейного времени
std::vector<int> v(10000, 0);
 
// O(1) операция
auto start = std::chrono::high_resolution_clock::now();
v.push_back(42);
auto end = std::chrono::high_resolution_clock::now();
auto duration1 = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
 
// O(n) операция
start = std::chrono::high_resolution_clock::now();
v.insert(v.begin(), 42);
end = std::chrono::high_resolution_clock::now();
auto duration2 = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
 
// duration2 будет значительно больше duration1

// Исследование стратегии роста вектора
std::vector<int> v;
std::cout << "Initial capacity: " << v.capacity() << std::endl;
 
for (int i = 0; i < 100; ++i) {
    v.push_back(i);
    if (v.capacity() > v.size() - 1) {
        std::cout << "Size: " << v.size() 
                  << ", Capacity: " << v.capacity() << std::endl;
    }
}

struct BadAlign {
    char c;       // 1 байт
    double d;     // 8 байт (обычно требует выравнивания по 8 байт)
    int i;        // 4 байта
}; // Размер: не 13 байт, а 24 из-за выравнивания
 
struct BetterAlign {
    double d;     // 8 байт
    int i;        // 4 байта
    char c;       // 1 байт
}; // Размер: около 16 байт, меньше паддинга

// Измерение времени вставки для демонстрации проблемы амортизации
struct ExpensiveToCopy {
    std::array<double, 10000> data;
    ExpensiveToCopy() { 
        std::fill(data.begin(), data.end(), 1.0); 
    }
    ExpensiveToCopy(const ExpensiveToCopy&) = default; // Дорогая операция копирования
};
 
std::vector<ExpensiveToCopy> v;
for (int i = 0; i < 100; ++i) {
    auto start = std::chrono::high_resolution_clock::now();
    v.push_back(ExpensiveToCopy());
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    if (duration.count() > 1000) { // Ищем скачки времени выполнения
        std::cout << "Spike at size " << v.size() 
                  << ": " << duration.count() << " microseconds" << std::endl;
    }
}

// Избегаем ненужных временных объектов
std::vector<std::string> names;
names.reserve(3);
names.emplace_back("Alice");   // Строка конструируется прямо на месте
names.emplace_back("Bob");
names.emplace_back("Charlie");

// Демонстрация разницы в производительности для разных паттернов вставки
std::vector<int> v1, v2;
v1.reserve(10000);
v2.reserve(10000);
 
// Вставка в конец - быстро
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < 10000; ++i) {
    v1.push_back(i);
}
auto end = std::chrono::high_resolution_clock::now();
auto append_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
 
// Вставка в начало - медленно
start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < 10000; ++i) {
    v2.insert(v2.begin(), i);
}
end = std::chrono::high_resolution_clock::now();
auto prepend_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
 
// prepend_time будет на порядки больше append_time

// Плохо: многократное перевыделение памяти
std::vector<MyClass> v;
for (int i = 0; i < 10000; ++i) {
    v.push_back(MyClass(i)); // Частые перевыделения
}
 
// Хорошо: предварительное резервирование
std::vector<MyClass> v;
v.reserve(10000);
for (int i = 0; i < 10000; ++i) {
    v.emplace_back(i); // Без перевыделений, без копирований
}
 
// Иногда лучше: создание с заданным размером
std::vector<int> v(10000); // Создаёт 10000 элементов со значением 0
// Работа с предварительно созданными элементами
for (int i = 0; i < v.size(); ++i) {
    v[i] = compute(i); // Модификация существующих элементов
}

// reserve() vs resize() демонстрация
std::vector<std::string> v1, v2;
 
// С reserve()
v1.reserve(5);
std::cout << "After reserve(5): size=" << v1.size() 
          << ", capacity=" << v1.capacity() << std::endl;
// Выведет: size=0, capacity=5
 
// С resize()
v2.resize(5);
std::cout << "After resize(5): size=" << v2.size() 
          << ", capacity=" << v2.capacity() << std::endl;
// Выведет: size=5, capacity=5

std::vector<int> v(10000);
v.resize(100); // Размер уменьшился, но ёмкость не изменилась
std::cout << "After resize: size=" << v.size() 
          << ", capacity=" << v.capacity() << std::endl;
// Размер 100, ёмкость 10000
 
v.shrink_to_fit(); // Высвобождаем неиспользуемую память
std::cout << "After shrink_to_fit: size=" << v.size() 
          << ", capacity=" << v.capacity() << std::endl;
// Теперь и размер, и ёмкость около 100

struct Complex {
    Complex(double r, double i) : real(r), imag(i) {}
    double real, imag;
};
 
std::vector<Complex> v;
v.reserve(3);
 
// Неоптимально: создаёт временный объект
v.push_back(Complex(1.0, 2.0));
 
// Оптимально: конструирует объект прямо в памяти вектора
v.emplace_back(3.0, 4.0);

// Подход 1: Использование перемещения (C++11 и новее)
std::vector<std::unique_ptr<HeavyObject>> v;
auto obj = std::make_unique<HeavyObject>();
v.push_back(std::move(obj)); // Перемещение вместо копирования
 
// Подход 2: Хранение указателей вместо самих объектов
std::vector<HeavyObject*> pointers;

std::vector<float> data(1000000);
// Заполняем вектор
 
// Получаем прямой доступ к памяти для быстрых операций
float* raw = data.data();
// Можно передать в C API или использовать для оптимизированных вычислений
for (size_t i = 0; i < data.size(); ++i) {
    raw[i] = std::sin(raw[i]); // Обход проверок границ и других служебных операций
}

// Удаление всех отрицательных чисел
std::vector<int> v = {1, -2, 3, -4, 5};
v.erase(std::remove_if(v.begin(), v.end(), 
         [](int x) { return x < 0; }), v.end());
// Теперь v содержит {1, 3, 5}

template<typename T>
void quick_remove_at(std::vector<T>& v, std::size_t idx) {
    if (idx < v.size()) {
        v[idx] = std::move(v.back());
        v.pop_back();
    }
}
 
std::vector<int> v = {1, 2, 3, 4, 5};
quick_remove_at(v, 2); // Удаляем элемент с индексом 2 (значение 3)
// Теперь v содержит {1, 2, 5, 4} - порядок нарушен, но удаление выполнено за O(1)

std::vector<Item> items;
std::vector<bool> deleted(items.size(), false);
 
// Помечаем элементы как удалённые вместо фактического удаления
void mark_deleted(size_t index) {
    deleted[index] = true;
}
 
// Позже выполняем фактическое удаление за одну операцию
void cleanup() {
    items.erase(
        std::remove_if(items.begin(), items.end(),
            [&](const Item& item) {
                return deleted[&item - &items[0]];
            }),
        items.end()
    );
    // Обновляем массив меток
    deleted.resize(items.size());
    std::fill(deleted.begin(), deleted.end(), false);
}

// Пример пользовательского аллокатора, использующего выровненную память
template <typename T, size_t Alignment = 64>
class AlignedAllocator {
public:
    using value_type = T;
    
    AlignedAllocator() noexcept {}
    
    template <class U>
    AlignedAllocator(const AlignedAllocator<U, Alignment>&) noexcept {}
    
    T* allocate(std::size_t n) {
        void* ptr = nullptr;
#ifdef _MSC_VER
        ptr = _aligned_malloc(n * sizeof(T), Alignment);
#else
        if (posix_memalign(&ptr, Alignment, n * sizeof(T))) {
            ptr = nullptr;
        }
#endif
        if (!ptr) throw std::bad_alloc();
        return static_cast<T*>(ptr);
    }
    
    void deallocate(T* p, std::size_t) noexcept {
#ifdef _MSC_VER
        _aligned_free(p);
#else
        free(p);
#endif
    }
};
 
// Использование пользовательского аллокатора
std::vector<float, AlignedAllocator<float>> aligned_vector(1000);

template <typename T, size_t BlockSize = 4096>
class PoolAllocator {
    // Реализация пула памяти с фиксированным размером блоков
public:
    using value_type = T;
    // ...прочие методы аллокатора...
};
 
// Вектор, использующий пул памяти
std::vector<small_object, PoolAllocator<small_object>> pool_vector;

template <typename T>
class TrackingAllocator {
    static size_t total_allocated;
public:
    using value_type = T;
    
    T* allocate(std::size_t n) {
        size_t bytes = n * sizeof(T);
        total_allocated += bytes;
        std::cout << "Allocating " << bytes << " bytes (total: " << total_allocated << ")\n";
        return std::allocator<T>().allocate(n);
    }
    
    void deallocate(T* p, std::size_t n) noexcept {
        size_t bytes = n * sizeof(T);
        total_allocated -= bytes;
        std::cout << "Deallocating " << bytes << " bytes (total: " << total_allocated << ")\n";
        std::allocator<T>().deallocate(p, n);
    }
};

#include <immintrin.h> // Intel intrinsics
 
void simd_transform(std::vector<float>& data) {
    // Убедимся, что данные выровнены должным образом
    assert(reinterpret_cast<uintptr_t>(data.data()) % 32 == 0);
    
    const size_t size = data.size();
    const size_t simd_size = size - (size % 8); // Обрабатываем по 8 float за раз
    
    for (size_t i = 0; i < simd_size; i += 8) {
        // Загружаем 8 float в 256-битный регистр
        __m256 values = _mm256_load_ps(&data[i]);
        // Выполняем операцию (например, умножение на 2.0)
        __m256 results = _mm256_mul_ps(values, _mm256_set1_ps(2.0f));
        // Сохраняем результат обратно в вектор
        _mm256_store_ps(&data[i], results);
    }
    
    // Обрабатываем оставшиеся элементы обычным способом
    for (size_t i = simd_size; i < size; ++i) {
        data[i] *= 2.0f;
    }
}

// Нивный алгоритм, ведущий к множеству кэш-промахов при работе с большой матрицей
void naive_matrix_operation(std::vector<float>& matrix, int width, int height) {
    for (int col = 0; col < width; ++col) {
        for (int row = 0; row < height; ++row) {
            matrix[row * width + col] *= 2.0f; // Неэффективный доступ по столбцам
        }
    }
}
 
// Кэш-дружественный вариант: обрабатываем данные в порядке их размещения в памяти
void cache_friendly_matrix_operation(std::vector<float>& matrix, int width, int height) {
    for (int row = 0; row < height; ++row) {
        for (int col = 0; col < width; ++col) {
            matrix[row * width + col] *= 2.0f; // Последовательный доступ
        }
    }
}

// Блочное умножение матриц для лучшей кэш-локальности
void block_matrix_multiply(const std::vector<float>& a, const std::vector<float>& b,
                         std::vector<float>& c, int n, int block_size = 32) {
    for (int i = 0; i < n; i += block_size) {
        for (int j = 0; j < n; j += block_size) {
            for (int k = 0; k < n; k += block_size) {
                // Умножение блоков
                for (int ii = i; ii < std::min(i + block_size, n); ++ii) {
                    for (int jj = j; jj < std::min(j + block_size, n); ++jj) {
                        float sum = 0.0f;
                        for (int kk = k; kk < std::min(k + block_size, n); ++kk) {
                            sum += a[ii * n + kk] * b[kk * n + jj];
                        }
                        c[ii * n + jj] += sum;
                    }
                }
            }
        }
    }
}

#include <execution>
#include <algorithm>
 
std::vector<double> data(1000000);
// Заполнение данными...
 
// Последовательная обработка
std::transform(data.begin(), data.end(), data.begin(),
             [](double x) { return std::sqrt(x); });
 
// Параллельная обработка (C++17)
std::transform(std::execution::par, data.begin(), data.end(), data.begin(),
             [](double x) { return std::sqrt(x); });
 
// Параллельная векторизованная обработка (C++17)
std::transform(std::execution::par_unseq, data.begin(), data.end(), data.begin(),
             [](double x) { return std::sqrt(x); });

std::vector<int> v(10000000);
// Заполнение данными...
 
void process_chunk(std::vector<int>::iterator begin, std::vector<int>::iterator end) {
    std::transform(begin, end, begin, [](int x) { 
        // Сложная обработка
        return compute_expensive_function(x); 
    });
}
 
// Разделение вектора на части и обработка их параллельно
void parallel_process(std::vector<int>& data, size_t num_threads = 4) {
    std::vector<std::future<void>> futures;
    
    const size_t chunk_size = data.size() / num_threads;
    auto it = data.begin();
    
    for (size_t i = 0; i < num_threads - 1; ++i) {
        auto chunk_end = it + chunk_size;
        futures.push_back(std::async(std::launch::async, process_chunk, it, chunk_end));
        it = chunk_end;
    }
    
    // Обработка последнего куска (может быть немного больше)
    futures.push_back(std::async(std::launch::async, process_chunk, it, data.end()));
    
    // Ждём завершения всех задач
    for (auto& future : futures) {
        future.wait();
    }
}

#include <omp.h>
 
void parallel_process_with_openmp(std::vector<int>& data) {
    // Устанавливаем количество нитей
    omp_set_num_threads(4);
    
    // Параллельный цикл с OpenMP
    #pragma omp parallel for
    for (size_t i = 0; i < data.size(); ++i) {
        data[i] = compute_expensive_function(data[i]);
    }
}

#include <tbb/parallel_for.h>
#include <tbb/blocked_range.h>
 
void process_with_tbb(std::vector<int>& data) {
    tbb::parallel_for(tbb::blocked_range<size_t>(0, data.size()),
        [&](const tbb::blocked_range<size_t>& range) {
            for (size_t i = range.begin(); i < range.end(); ++i) {
                data[i] = compute_expensive_function(data[i]);
            }
        }
    );
}

#include <vector>
#include <chrono>
#include <iostream>
#include <execution>
#include <algorithm>
#include <numeric>
 
// Класс, моделирующий частицу в физической симуляции
struct Particle {
    float x, y, z;      // Позиция
    float vx, vy, vz;   // Скорость
    float mass;         // Масса
    
    // Конструктор с параметрами для emplace_back
    Particle(float x, float y, float z, float mass)
        : x(x), y(y), z(z), vx(0), vy(0), vz(0), mass(mass) {}
        
    // Обновляем позицию частицы на основе её скорости
    void update(float dt) {
        x += vx * dt;
        y += vy * dt;
        z += vz * dt;
    }
};
 
// Симуляция гравитационного взаимодействия между частицами
void simulate_gravity(std::vector<Particle>& particles, float dt) {
    const float G = 6.67430e-11f; // Гравитационная постоянная
    
    // Предварительно вычисляем силы, действующие на каждую частицу
    std::vector<std::tuple<float, float, float>> forces(particles.size(), {0, 0, 0});
    
    // Параллельное вычисление сил между всеми парами частиц
    #pragma omp parallel for
    for (size_t i = 0; i < particles.size(); ++i) {
        auto& p1 = particles[i];
        auto& [fx, fy, fz] = forces[i];
        
        for (size_t j = 0; j < particles.size(); ++j) {
            if (i == j) continue;
            
            auto& p2 = particles[j];
            
            // Вектор от p1 к p2
            float dx = p2.x - p1.x;
            float dy = p2.y - p1.y;
            float dz = p2.z - p1.z;
            
            // Квадрат расстояния (с малым смещением для избежания деления на ноль)
            float r2 = dx*dx + dy*dy + dz*dz + 1e-10f;
            
            // Сила по закону Ньютона
            float f = G * p1.mass * p2.mass / r2;
            
            // Нормализация вектора направления
            float r = std::sqrt(r2);
            float factor = f / r;
            
            // Накапливаем силы
            fx += dx * factor;
            fy += dy * factor;
            fz += dz * factor;
        }
    }
    
    // Применяем вычисленные силы и обновляем позиции
    for (size_t i = 0; i < particles.size(); ++i) {
        auto& p = particles[i];
        auto& [fx, fy, fz] = forces[i];
        
        // F = ma => a = F/m
        float ax = fx / p.mass;
        float ay = fy / p.mass;
        float az = fz / p.mass;
        
        // Обновляем скорость (v = v0 + a*dt)
        p.vx += ax * dt;
        p.vy += ay * dt;
        p.vz += az * dt;
        
        // Обновляем позицию
        p.update(dt);
    }
}
 
int main() {
    // Количество частиц в симуляции
    const size_t num_particles = 1000;
    
    // Инициализация с предварительным резервированием памяти
    std::vector<Particle> particles;
    particles.reserve(num_particles);
    
    // Создаём частицы непосредственно в векторе
    for (size_t i = 0; i < num_particles; ++i) {
        // Используем emplace_back для создания объекта на месте, без копирований
        particles.emplace_back(
            (float)rand() / RAND_MAX * 1000.0f - 500.0f,  // x
            (float)rand() / RAND_MAX * 1000.0f - 500.0f,  // y
            (float)rand() / RAND_MAX * 1000.0f - 500.0f,  // z
            (float)rand() / RAND_MAX * 100.0f + 1.0f      // масса
        );
    }
    
    // Временная дельта для симуляции
    const float dt = 0.01f;
    
    // Измеряем время выполнения
    auto start = std::chrono::high_resolution_clock::now();
    
    // Запускаем симуляцию на 100 шагов
    for (int step = 0; step < 100; ++step) {
        simulate_gravity(particles, dt);
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    
    std::cout << "Симуляция " << num_particles << " частиц за 100 шагов заняла " 
              << duration << " мс" << std::endl;
              
    return 0;
}

std::vector<int> v = {1, 2, 3};
auto it = v.begin() + 1; // it указывает на 2
v.push_back(4);  // Может вызвать перевыделение
// *it = 5; — опасно! it может быть недействительным

std::vector<int> v = {1, 2, 3, 4, 5};
auto mid = v.begin() + 2; // Указывает на 3
auto end = v.end() - 1;   // Указывает на 5
 
v.erase(mid);  // Удаляем элемент 3
// Теперь и mid, и end недействительны!

// Переприсваиваем итераторы после модификации
auto it = v.begin() + index;
v.insert(it, value);
it = v.begin() + index; // Обновляем итератор
 
// При удалении используем возвращаемое значение erase
auto next_it = v.erase(it); // erase возвращает итератор на следующий элемент

std::vector<int> v = {1, 2, 3};
// v[5] = 10; // Неопределённое поведение, вероятно сбой
try {
    v.at(5) = 10; // Генерирует std::out_of_range
} catch (const std::out_of_range& e) {
    std::cerr << "Ошибка доступа: " << e.what() << std::endl;
}

std::vector<std::string> v;
// std::string& first = v.front(); // Неопределённое поведение!
 
// Безопасный вариант
if (!v.empty()) {
    std::string& first = v.front();
    // работаем с first
}

std::vector<int>& getVector() {
    std::vector<int> temp = {1, 2, 3}; // Локальная переменная
    return temp; // ОШИБКА! Возврат ссылки на временный объект
}

class BadClass {
private:
    int* data;
public:
    BadClass(int value) : data(new int(value)) {}
    ~BadClass() { delete data; }
    // Отсутствуют конструкторы копирования/перемещения!
};
 
std::vector<BadClass> v;
v.push_back(BadClass(5)); // После перевыделения возникают проблемы
// Двойное удаление при очистке вектора

class GoodClass {
private:
    int* data;
public:
    GoodClass(int value) : data(new int(value)) {}
    GoodClass(const GoodClass& other) : data(new int(*other.data)) {}
    GoodClass(GoodClass&& other) noexcept : data(other.data) {
        other.data = nullptr;
    }
    GoodClass& operator=(const GoodClass& other) {
        if (this != &other) {
            delete data;
            data = new int(*other.data);
        }
        return *this;
    }
    GoodClass& operator=(GoodClass&& other) noexcept {
        if (this != &other) {
            delete data;
            data = other.data;
            other.data = nullptr;
        }
        return *this;
    }
    ~GoodClass() { delete data; }
};

// При нехватке памяти для перевыделения некоторые объекты могут 
// оказаться в неопределённом состоянии, если исключение возникнет 
// в середине операции перемещения

std::vector<Widget*> widgets;
for (int i = 0; i < 10; ++i) {
    widgets.push_back(new Widget());
}
// При удалении вектора указатели удаляются, но не объекты!
 
// Корректно:
for (auto* widget : widgets) {
    delete widget;
}
widgets.clear();
 
// Ещё лучше - использовать std::unique_ptr
std::vector<std::unique_ptr<Widget>> smart_widgets;
for (int i = 0; i < 10; ++i) {
    smart_widgets.push_back(std::make_unique<Widget>());
}
// Память освободится автоматически

void risky_operation() {
    std::vector<Resource*> resources;
    try {
        resources.push_back(new Resource());
        // Код, который может выбросить исключение
        resources.push_back(new Resource());
    } catch (...) {
        // Если забыть очистить ресурсы здесь, произойдёт утечка
        for (auto* res : resources) {
            delete res;
        }
        throw; // Перебрасываем исключение
    }
    
    // Обработка ресурсов
    
    // Очистка
    for (auto* res : resources) {
        delete res;
    }
}
 
// Лучший подход - использовать RAII и умные указатели
void safe_operation() {
    std::vector<std::unique_ptr<Resource>> resources;
    resources.push_back(std::make_unique<Resource>());
    // Код, который может выбросить исключение
    resources.push_back(std::make_unique<Resource>());
    // Даже при исключении ресурсы будут освобождены
}

// Компиляция с флагами -D_GLIBCXX_DEBUG для libstdc++ или
// -D_LIBCPP_DEBUG=1 для libc++ включает дополнительные проверки

// Инструментирование класса для подсчёта операций
class Instrumented {
    static int created, copied, moved, destroyed;
public:
    Instrumented() { ++created; }
    Instrumented(const Instrumented&) { ++copied; }
    Instrumented(Instrumented&&) noexcept { ++moved; }
    ~Instrumented() { ++destroyed; }
    
    static void report() {
        std::cout << "Created: " << created
                  << ", Copied: " << copied
                  << ", Moved: " << moved
                  << ", Destroyed: " << destroyed << std::endl;
    }
};

// Компиляция с -fsanitize=address выявляет ошибки доступа к памяти
// Компиляция с -fsanitize=undefined обнаруживает неопределённое поведение
g++ -fsanitize=address -g program.cpp

// Переопределение глобальных операторов new/delete
void* operator new(std::size_t size) {
static std::atomic<std::size_t> totalAllocated{0};
std::size_t currentlyAllocated = totalAllocated += size;
std::cout << "Выделено " << size << " байт (всего: " << currentlyAllocated << ")\n";
return malloc(size);
}
 
void operator delete(void* ptr, std::size_t size) noexcept {
static std::atomic<std::size_t> totalFreed{0};
std::size_t currentlyFreed = totalFreed += size;
std::cout << "Освобождено " << size << " байт (всего: " << currentlyFreed << ")\n";
free(ptr);
}

// Если ожидаете роста, резервируйте с запасом
size_t estimated_final_size = initial_size * 1.5;
v.reserve(estimated_final_size);

std::vector<int> v = {1, 2, 3, 4, 5};
 
// v.clear() - удаляет все элементы, но сохраняет ёмкость
// v.resize(0) - то же самое, что clear()
// v = {} - очищает и может уменьшить ёмкость (зависит от реализации)
// v = std::vector<int>() - создаёт новый пустой вектор, старый удаляется
 
// Если нужно также освободить память:
v.clear();
v.shrink_to_fit(); // Запрашивает уменьшение ёмкости до текущего размера

class Base { 
public:
    virtual void process() { std::cout << "Base\n"; }
    virtual ~Base() = default;
};
 
class Derived : public Base {
public:
    void process() override { std::cout << "Derived\n"; }
};
 
// Неправильно - теряется полиморфизм из-за срезки объектов
std::vector<Base> objects;
objects.push_back(Derived()); // Объект "срезается" до Base
objects[0].process(); // Выведет "Base", а не "Derived"
 
// Правильно - использование указателей/ссылок для сохранения полиморфизма
std::vector<std::unique_ptr<Base>> smart_objects;
smart_objects.push_back(std::make_unique<Derived>());
smart_objects[0]->process(); // Выведет "Derived"

// std::vector<bool> специализирован для экономии памяти и может вести себя неожиданно
std::vector<bool> flags(100, false);
 
// Ошибка: нельзя получить адрес элемента
// bool* ptr = &flags[0]; // Не скомпилируется!
 
// Ошибка: ссылки на элементы не являются настоящими ссылками
// bool& ref = flags[0]; // Компилируется, но ref не настоящая ссылка
 
// Решение: использовать std::deque<bool> или std::vector<char> для обычного поведения
std::vector<char> better_flags(100, 0);
char* ptr = &better_flags[0]; // Работает корректно
char& ref = better_flags[0];  // Настоящая ссылка

std::vector<int> v = {1, 2, 3};
std::cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << "\n";
 
v.reserve(100); // Увеличивает ёмкость до 100
// v.size() всё ещё 3, но capacity() стало 100
 
v.resize(50);  // Размер увеличивается до 50, добавляются элементы по умолчанию
// Теперь size() = 50, capacity() = 100
 
v.resize(10);  // Размер уменьшается до 10, "лишние" элементы удаляются
// Теперь size() = 10, но capacity() всё ещё 100
 
// resize() изменяет размер и создаёт/удаляет элементы
// reserve() только меняет ёмкость без изменения размера

std::vector<int> v;
for (int i = 0; i < 1000000; i++) {
    v.push_back(i);
}
 
// Опасно: potentialDataLoss преобразует большое беззнаковое число в int
int size = v.size(); 
// На 64-разрядных системах v.size() имеет тип size_t (unsigned long long)
// Если размер превышает INT_MAX, произойдет переполнение
 
// Безопасно: используем правильный тип
std::vector<int>::size_type safe_size = v.size();
// или C++11 и новее:
auto better_size = v.size();

std::vector<HeavyObject> objects;
HeavyObject obj = createHeavyObject();
 
// Вместо копирования:
// objects.push_back(obj);
 
// Используйте перемещение:
objects.push_back(std::move(obj));
// Теперь obj находится в "перемещенном" состоянии и его не стоит использовать

// Плохо - каждое добавление может вызвать перевыделение
std::vector<int> v;
for (int i = 0; i < 10000; ++i) {
    v.push_back(i);
}
 
// Хорошо - одно перевыделение вместо потенциальных log(n)
std::vector<int> v2;
v2.reserve(10000);
for (int i = 0; i < 10000; ++i) {
    v2.push_back(i);
}

// Может привести к множеству мелких выделений памяти
std::vector<std::vector<int>> matrix(1000, std::vector<int>(1000));
 
// Альтернатива: одномерный вектор с ручной индексацией
std::vector<int> flat_matrix(1000 * 1000);
int get(int row, int col) { return flat_matrix[row * 1000 + col]; }
void set(int row, int col, int value) { flat_matrix[row * 1000 + col] = value; }

// Архитектура хранения компонентов в ECS (Entity Component System)
class ComponentManager {
private:
    // Хранилище компонентов по типам
    std::unordered_map<ComponentType, 
                       std::vector<ComponentData>> componentArrays;
    
    // Маппинг сущность -> индекс компонента в соответствующем векторе
    std::unordered_map<EntityID, 
                       std::unordered_map<ComponentType, size_t>> entityToIndexMap;
 
public:
    template<typename T>
    void addComponent(EntityID entity, T component) {
        // Получаем тип компонента
        ComponentType type = getComponentType<T>();
        
        // Добавляем компонент в конец соответствующего вектора
        componentArrays[type].push_back(std::move(component));
        
        // Сохраняем индекс компонента для быстрого доступа
        entityToIndexMap[entity][type] = componentArrays[type].size() - 1;
    }
    
    // Другие методы для работы с компонентами...
};

template<typename T>
class BlockVector {
private:
    std::vector<std::vector<T>> blocks;
    size_t blockSize;
    size_t totalSize;
    
public:
    BlockVector(size_t blockSize = 4096) 
        : blockSize(blockSize), totalSize(0) {}
    
    void push_back(const T& value) {
        if (totalSize % blockSize == 0) {
            // Нужен новый блок
            blocks.emplace_back();
            blocks.back().reserve(blockSize);
        }
        
        // Добавляем элемент в последний блок
        blocks.back().push_back(value);
        totalSize++;
    }
    
    // Итератор и другие методы...
};

// Класс для обработки сенсорных данных в системе реального времени
class SensorDataProcessor {
private:
    // Предвыделенный буфер с запасом в 2 раза больше ожидаемого максимума
    std::vector<SensorReading> sensorBuffer;
    std::mutex bufferMutex;
    
public:
    SensorDataProcessor(size_t expectedMaxReadings) {
        // Выделяем память с двукратным запасом
        sensorBuffer.reserve(expectedMaxReadings * 2);
    }
    
    void addReading(const SensorReading& reading) {
        std::lock_guard<std::mutex> lock(bufferMutex);
        // В критических секциях не должно быть перевыделений памяти
        assert(sensorBuffer.size() < sensorBuffer.capacity());
        sensorBuffer.push_back(reading);
    }
    
    // Обработка данных...
};

// Утилита для проверки возможности безопасного добавления элементов
template <typename T>
bool canSafelyPushBack(const std::vector<T>& vec, size_t count = 1) {
    return vec.size() + count <= vec.capacity();
}
 
// Использование в критической секции
if (canSafelyPushBack(criticalVector)) {
    criticalVector.push_back(newData);
} else {
    // Обработка ситуации, когда нельзя безопасно добавить элемент
    handleCapacityError();
}

#include <benchmark/benchmark.h>
 
static void BM_VectorPushBack(benchmark::State& state) {
    for (auto _ : state) {
        std::vector<int> v;
        for (int i = 0; i < state.range(0); ++i) {
            v.push_back(i);
        }
    }
}
BENCHMARK(BM_VectorPushBack)->Range(8, 8<<10);
 
static void BM_VectorPushBackReserve(benchmark::State& state) {
    for (auto _ : state) {
        std::vector<int> v;
        v.reserve(state.range(0));
        for (int i = 0; i < state.range(0); ++i) {
            v.push_back(i);
        }
    }
}
BENCHMARK(BM_VectorPushBackReserve)->Range(8, 8<<10);

template <typename T>
class ObjectPool {
private:
    std::vector<T> objects;
    std::vector<size_t> freeIndices;
    std::mutex poolMutex;
    
public:
    ObjectPool(size_t initialSize = 1000) {
        objects.resize(initialSize);
        freeIndices.reserve(initialSize);
        
        // Изначально все объекты свободны
        for (size_t i = 0; i < initialSize; ++i) {
            freeIndices.push_back(i);
        }
    }
    
    // Получение объекта из пула
    T* acquire() {
        std::lock_guard<std::mutex> lock(poolMutex);
        
        if (freeIndices.empty()) {
            // Расширяем пул при необходимости
            size_t oldSize = objects.size();
            objects.resize(oldSize * 2);
            
            for (size_t i = oldSize; i < objects.size(); ++i) {
                freeIndices.push_back(i);
            }
        }
        
        size_t index = freeIndices.back();
        freeIndices.pop_back();
        return &objects[index];
    }
    
    // Возврат объекта в пул
    void release(T* object) {
        std::lock_guard<std::mutex> lock(poolMutex);
        size_t index = object - objects.data();
        freeIndices.push_back(index);
    }
};

struct NetworkRequest {
    int64_t clientId;
    uint32_t requestType;
    std::array<char, 256> payload; // Фиксированный размер буфера
    
    // При необходимости больших данных - только ссылка
    std::shared_ptr<std::vector<uint8_t>> largePayload;
};
 
// Эффективное хранение для обработки пакетами
using RequestBatch = std::vector<NetworkRequest>;

// Сравнение std::vector с boost::container::vector
#include <vector>
#include <boost/container/vector.hpp>
#include <chrono>
 
template<typename Vector>
void benchmark_vector_operations(const std::string& name) {
    auto start = std::chrono::high_resolution_clock::now();
    
    Vector v;
    for (int i = 0; i < 1000000; ++i) {
        v.push_back(i);
    }
    
    auto mid = std::chrono::high_resolution_clock::now();
    
    for (int i = 0; i < 10000; ++i) {
        v.insert(v.begin() + (v.size() / 2), i);
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    
    std::cout << name << " push_back: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(mid - start).count() << " ms\n";
    std::cout << name << " insert: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - mid).count() << " ms\n";
}

// Пример использования folly::small_vector
folly::small_vector<int, 16> sv; // Первые 16 элементов не требуют выделения памяти
 
// Идеально для ситуаций, когда обычно имеется несколько элементов,
// но иногда может быть больше

absl::inlined_vector<int, 8> iv; // Первые 8 элементов хранятся на стеке
 
// Эффективный компромисс между std::vector и std::array