🤔 В чем разница vector и list?

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

🚩std::vector

Это динамический массив, который обеспечивает быстрый доступ к элементам по индексу. Вектор хранит свои элементы в непрерывном блоке памяти, что делает возможным обращение к элементам за константное время O(1). Однако, такое хранение делает вставку и удаление элементов в начало или середину вектора менее эффективными (в среднем O(n), где n — количество элементов), так как может потребоваться перемещение большого количества элементов для освобождения места или заполнения пробела.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    vec.push_back(6); // Добавление элемента в конец вектора
    std::cout << "Элемент по индексу 3: " << vec[3] << std::endl; // Быстрый доступ к элементам

    return 0;
}

🚩std::list

В отличие от std::vector, представляет собой двусвязный список. Каждый элемент содержит данные и указатели на предыдущий и следующий элементы в списке. Это обеспечивает быструю вставку и удаление элементов в любом месте списка, так как требуется только изменение нескольких указателей (O(1)), независимо от размера списка. Однако, доступ к элементам в std::list осуществляется за линейное время O(n), так как для доступа к элементу нужно пройти через указатели от начала или конца списка.

#include <list>
#include <iostream>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    lst.push_front(0); // Быстрая вставка в начало списка
    lst.push_back(6);  // Быстрая вставка в конец списка

    for (auto it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

Ставь 👍 и забирай 📚 Базу знаний