«Время — это единственная вещь, которую все хотят иметь, но которую нельзя купить или продлить» — Харви Маккей

Будет 5 статей по темам:

• Последовательные контейнеры(ВЫ ТУТ)

• Ассоциативные контейнеры

• Стеки и очереди - они же адаптеры

• Функциональные объекты

• Основные алгоритмы - последние будут иногда проскакивать во всех статьях выше

Наполнение статьи про последовательные контейнеры:

1) VECTOR
2) LIST
3) DEQUE

1) Великий и самый простой - std::vector

Краткое описание: динамический массив с кучей различных функций для упрощения работы с ним

Памятка по функциям:
size() - возвращает текущий размер вектора.

push_back(something) - добавляет новый элемент в конец вектора.

pop_back() - удаляет последний элемент вектора.

clear() - удаляет все элементы из вектора.
Небольшая аннотация: если вектор пустой и вы вызвали clear(), то ничего не произойдет, так как внутри идет проверка на !empty(), про которую написано ниже.

empty() - проверяет, является ли вектор пустым.

at(index) - возвращает элемент на указанной позиции.
Небольшая аннотация: к сожалению она не защитит вас от ситуации с обращением к несуществующему индексу
Аналог: vec[ваш_итератор]

front() - Возвращает первый элемент вектора.
Небольшая аннотация: к сожалению она не защитит вас от ситуации с обращением к несуществующему индексу [0]

back() - Возвращает последний элемент вектора.
Небольшая аннотация: к сожалению она не защитит вас от ситуации с обращением к несуществующему индексу [vector.size() - 1]

Небольшой пример кода:

    vector<int> vec = {1, 2, 3, 4, 5};//первый вариант заполнения массива
    
    vec.push_back(1);// добавление элемента в вектор {1, 2, 3, 4, 5, 1}
    vec.pop_back();//удаление последнего элемента {1, 2, 3, 4, 5}
    
    vec.front();//первый элемент вектора - 1
    vec.back();//последний элемент вектора - 2
    
    for(auto& elem : vec){//первый вариант вывода элементов массива через foreach, а точнее одной из его вариаций
        cout<<elem<<endl;
    }
    for(auto i = 0; i < (int)vec.size(); i++){//второй вариант вывода
        cout<<vec[i]<<endl;
    }
    
    //тут давайте поговорим про объединение двух векторов, что часто нужно сделать
    // объединение == конкатенация
    vector<int> vec2 = {6, 7, 8, 9, 10};
    
    vec.insert(vec.end(), vec2.begin(), vec2.end()); // имеем первый вариант заполнения массива 
    //ИТОГ: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    vec += vec2;//второй вариант(работает на LEETCODE. но не работает на некоторых компиляторах
    //ИТОГ: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

    /* Обратите внимание*/
    vec = vec2; //данный вызов не произведет конкатенации, а vec будет абсолютно равен vec2
    
    vec.clear();//очистка вектора

Список функций валидных для использования с std::vector и помогающие в решении задач:

*max_element(vec.begin(), vec.end()) - вернет наибольший элемент вектора и обратите внимание на (*) - чистый max_element() возвращает итератор и для получения значения - вы можете разыменовать его при желании.

*min_element(vec.begin(), vec.end()) - вернет наименьший элемент вектора и обратите внимание на (*) - чистый min_element() возвращает итератор и для получения значения - вы можете разыменовать его при желании.

std::sort() - используется для сортировки элементов в нужной последовательности про компараторы мы поговорим в самом конце этой статьи.

reserve() - выделит память для вашего вектора, так если вам нужно найти элемент графа с самым большим количеством узлов, то выделять память придется изначально и в принципе лучше выделять ровно столько памяти, сколько потребуется, чтобы выигрывать по времени
Также reserve очень полезен в задачах, где используются n-мерные вектора и соответственно матрицы - без него вам никуда.

2) Великий и без доступа по индексу — std::list

Честно, ни разу не использовал его при решении задач на LeetCode - я говорю именно про std::list, а так в задачах на linked list - да, в принципе сойдет, но вот при работе с какими-то проектами - я использую Qt Creator/С++ и для получения там списка элементов часто используется QList - более расширенный чем std::list, поэтому про него стоит упомянуть.

Кратко: упорядоченный контейнер состоящий из элементов выбранного типа, в котором доступ к элементам происходит через указатели. Индексы в нем отсутствуют, а соответственно и доступа по индексам там нет - главное преимущество перед вектором - это вставка и удаление элементов в начале и конце за константное время, поскольку сдвигать все элементы вектора засчет указателей не приходится.

Еще более быстрое объяснение: двусвязный список или двусторонняя очередь.

Памятка по функциям:

size() - возвращает текущий размер листа.

push_front() - добавляет новый элемент в начало листа.

push_back(something) - добавляет новый элемент в конец листа.

front() - вернет первый элемент листа.

back() - вернет последний элемент листа.
Если в листе будет находиться один элемент, то оба указателя будут указывать на один элемент.

pop_front() - удаляет первый элемент листа.

pop_back() - удаляет последний элемент листа.

clear() - удаляет все элементы из листа.

empty() - проверяет, является ли лист пустым.

merge(list& x) - объединит наши листы, где элементы будут в порядке по возрастанию

reverse() - развернет наш лист и если до этого была вызвана функция merge() или sort() - чистый, то мы получим вектор по убыванию.

remove(some_int) - удалит все элементы со значением some_int

Из минусов: чтобы получить конкретный элемент листа придется с самого начала пробегать весь лист, что в отличии от вектора, где доступ происходит за константное время по индексу - не очень хорошо.

Конечно можно рассказать, что листы придумали для того чтобы не выделять огромные последовательные куски памяти в векторе, поскольку раньше в компьютерах памяти было не так много и вроде памяти сейчас просто море, тогда зачем их используют - константное время на вставку и удаление элементов отвечу я вам. Но давайте лучше поговорим об объединении листов.

Объединение листов

Тут будет разобрано 3 варианта развития событий с вашими листами, поэтому будьте внимательны:

1 вариант - если итератор лежит в диапазоне вашего листа, куда вы хотите прикрепить другой лист, при этом другой лист останется пустым - чем-то напоминает move-конструкторы
void splice(iterator position, list& x);

2 вариант - если итератор лежит в диапазоне вашего листа, а итератор j находится в диапазоне другого листа, который мы присоединяем, причем эта функция работает даже если вы используете один и тот же лист.
void splice(iterator position, list& x, iterator j);

3 вариант - самый громоздкий.

position итератор - вашего листа, куда вы присоединяете.
first, last - относятся к другому листу, который присоединяем
Результат: элементы в диапазоне от [first, last] удалятся и вставятся [iterator, iterator + last]
Работает даже если лист один и тот же
void splice(iterator position, list& x, iterator first, iterator last);

Пример кода:

    list<int> list1 = {1, 2, 3};
    list<int> list2 = {4, 5, 6};

    list<int>::iterator it = list1.begin() + 2;

    list1.splice(it, list2); // Вставляем все элементы из list2 в позицию, указываемую итератором it

3) Лист с итераторами - std::deque

Кратко: упорядоченный контейнер состоящий из элементов выбранного типа, в котором доступ к элементам происходит через указатели. В нем присутствует доступ по индексам.
Вставка и удаление в начале и конце происходит за константое время. Если вставка и удаление происходят в середине происходит гораздо быстрее чем в векторе, но это не аксиома и нужно смотреть на размер сравниваемого вектора.

size() - возвращает текущий размер листа.

push_front() - добавляет новый элемент в начало листа.

push_back(something) - добавляет новый элемент в конец листа.

front() - вернет первый элемент листа.

back() - вернет последний элемент листа.
Если в листе будет находиться один элемент, то оба указателя будут указывать на один элемент.

pop_front() - удаляет первый элемент листа.

pop_back() - удаляет последний элемент листа.

clear() - удаляет все элементы из листа.

empty() - проверяет, является ли лист пустым.

Функции, которых нету в листе

erase(iterator pos) - удаление элемента по индексу

at(some_int) - доступ к элементу по индексу

Пример кода:

  deque<int>deq;
  // Добавляем элементы в конец дека
  deq.push_back(4);
  deq.push_back(5);
  deq.push_back(6);

  // Добавляем элементы в начало дека 
  deq.push_front(3);
  deq.push_front(2);
  deq.push_front(1);

  // Удаляем первый элемент из дека
  deq.pop_front();

  //Получаем доступ по индексу к элементу дека
  deq.at(0);

   //Удаляем 5-ый элемент дека
  deq.erase(deq.begin() + 4);