Базовый набор для решения задач на LeetCode/Codeforces, ч.1

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

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

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

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

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

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

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

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

1) VECTOR
2) LIST
3) DEQUE

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

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

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

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

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

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

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

at(index) — возвращает элемент на указанной позиции.
Небольшая аннотация: Замечание от читателя: «На самом деле при использовании оператора [] программа просто упадет с segfault-ом, а метод at() выбросит гарантированное исключение, что не убьет программу. И также стоит отметить, что вызов [] быстрее, так как нет дополнительных проверок.»
Аналог: 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 — да, в принципе сойдет для общего понимания контейнера.

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

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

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

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);