«Время — это единственная вещь, которую все хотят иметь, но которую нельзя купить или продлить» — Харви Маккей
Будет 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 в позицию, указываемую итератором it3) Лист с итераторами - 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);