Хорошо, вот мы познакомились со списком и узнали, что у него есть какие-то методы. Но когда же он нужен на практике? Например, когда нужно удалять элементы из середины. Давайте продемонстрируем следующий пример. Он будет непростым, но отчасти вам близким. А именно, давайте мы захотим делать следующее: мы захотим складывать числа в контейнер, назовем его Numbers. С помощью метода Add просто принимаем число "икс" и как-то добавляем его. Мы хотим не только добавлять числа, но и удалять. Удалять по некоторому условию. Как мы решали похожую проблему в финальном проекте второго курса? Мы писали шаблонный метод, который принимал в качестве шаблонного параметра Predicate, то есть условия, по которым надо удалять элементы. Соответственно, мы напишем метод Remove, который будет принимать условие, по которому нужно удалять элементы. Он будет шаблонным. Шаблонным параметром Predicate, условие. И будет принимать функциональный объект. Например, функцию или Лямбда-функцию, которая должна возвращать "bl". И если она возвращает "true", то этот элемент надо удалить. Как можно реализовывать такой класс? Можно реализовать его с помощью вектора. Давайте я назову его NumbersOnVector. У меня будет private vector data. И методы я реализую следующим образом: это я просто сделаю push_ back, а Remove будет чуточку интереснее. А именно: как мне удалить элементы из вектора по условиям? Мне нужно вызвать функцию remove_if от начала вектора, конца вектора, и условия. А условия у нас уже есть. Однако вы, наверное, помните? Что remove_if физически не удаляет элементы, он их просто перемещает в конец и после этого нужно вызвать erase. Давайте его вызовем. data.erase от итератора,который вернул remove_if и конца вектора. Хорошо. Мы написали и реализовали этот контейнер с помощью вектора. Давайте попробуем реализовать его еще и с помощью списка. Все-таки нам здесь нужно удалять что-то из нашего контейнера. Возможно, список будет эффективнее. По крайней мере, иногда. Давайте я скопирую этот класс и реализую его с помощью списка. push_ back остается как есть. Внутри у нас теперь list. А здесь у нас будет код чуть проще, мы просто напишем data.remove_if(predicate). Вот так легко можно удалить элементы по условию из списка. И теперь нам можно подключить библиотеку list. Какая удача, она уже подключена. Хорошо. Вот у нас есть два класса с одинаковой функциональностью, но один реализован на векторе, а другой на списке. Давайте же напишем какой-нибудь benchmark, который позволит замерять, что же эффективней. Давайте benchmark будет следующим: мы сложим сколько-то чисел. Это количество положим в переменную SIZE. Но давайте там будет для начала миллион чисел. Давайте начнем писать сначала с вектором. Вкладываем SIZE элементов. Cначала объявив NumbersOnVector numbers. Складываем теперь туда с помощью цикла for SIZE чисел, вызывая метод Add. А теперь, ну давайте это скопируем для списка, и теперь давайте поудаляем оттуда элементы. Давайте будем удалять порциями, а именно: мы сделаем некоторое количество удалений. Давайте для начала у нас будет переменная REMOVAL_COUNT, количество удалений. И давайте для начала мы сделаем десять удалений. И как же они будут устроены? Давайте мы удалим сначала все элементы, все числа, у которых остаток от деления на десять равен нулю. Затем все числа, у которых остаток от деления на десять равен единице и так далее. В итоге мы за десять вызовов метода remove удалим все числа, при этом на каждом шаге на каждую из десяти итераций мы будем удалять какие-то элементы, лежащие вообще говоря не подряд, а где-то с каким-то шагом в контейнере. Как я это реализую? Я напишу здесь цикл for от нуля до REMOVAL_COUNT. И вот здесь нам нужно удалить все элементы, у которых остаток от деления на REMOVAL_COUNT равен i. Для этого мы у нашего контейнера numbers вызовем метод Remove и передадим сюда Лямбда функцию. Она должна захватить по значению переменную i и затем для очередного числа Икс возвращать тру. И если остаток от деления Икс на REMOVAL_COUNT равен i. И теперь мы то же самое, я прошу прощения, здесь нам нужно вместо Remove написать, конечно же, return. У меня сразу среда разработки это подчеркнула. И теперь я ту же самую серию удаления проворачиваю на списке. Добавляем еще точку с запятой в конец и получаем, кажется, неплохой benchmark. Давайте попробуем запустить этот код. Итак, еще раз: мы добавляем count элементов, а затем удаляем их в десять заходов. Точнее, добавили миллион элементов, затем удалили в десять заходов кусками. Итак, в том случае, когда мы добавили миллион элементов и затем удаляли в десять заходов, вектор получился эффективнее. Вектор отработал за 200 миллисекунд, список почти в два раза дольше работал. Возможно, здесь сказывается то, что по списку тяжелее итерироваться. Все-таки мы удалили элементы большими пачками и вектор их просто все скинул в конец, а потом удалил. Мы удаляли помногу элементов за раз. А давайте попробуем удалять понемногу элементов за раз. Давайте у нас будет десять тысяч элементов, и мы их удалим за тысячу шагов, то есть тысячу раз будем удалять по десять, получается, элементов. Что же покажет наш benchmark в этом случае? Давайте посмотрим. И теперь список оказался в полтора раза эффективнее, чем вектор. Почему так происходит? Потому что мы удаляем понемногу элементов, и теперь срабатывает тот факт, что в списке удобно быстро удалять из середины. Поэтому получилась следующая интересная картина: казалось бы, код один и тот же, контейнер одинаковый, но в зависимости от разной конфигурации входных параметров мы получаем, что эффективнее либо вектор, либо список, что лишний раз доказывает важность измерений на конкретных входных конфигурациях. Итак, мы познакомились с контейнером "список", узнали что он эффективен, если нужно часто удалять из середины. Или добавлять в середину, например. Кстати говоря, итераторы из списка имеют категорию bidirectional итераторы.То есть это двунаправленные итераторы, не обладающие возможностью, не позволяющие к себе прибавлять числа. То есть это не итераторы произвольного доступа, а двунаправленные итераторы. На практике списки, вообще говоря, нужны довольно редко. Мы показали один пример, еще примеры вы увидите в задачах. А также, если вдруг вас огорчает, что у вас с каждым элементом хранится указатель и на следующий элемент и на предыдущий, а вам нужен только указатель на следующий, вы всего лишь хотите интегрироваться вперед, но не назад, сэкономив память, в этом случае, возможно, вас заинтересует контейнер forward_list, который, однако, на практике нужен еще реже, чем просто список.
