В предыдущих видео мы узнали о внутреннем устройстве вектора и деко, мы узнали когда эффективен один и когда эффективен другой или узнали, что иногда заранее сказать нельзя и нужно измерять. Заодно мы узнали, что получается есть различные стратегии выделения памяти под линейные контейнеры, а именно вектор выделяет единый блок памяти под все свои элементы, а дек выделяет память чанками или блоками памяти. Конечно, они размер не три имеют в реальности а побольше, но зато выглядят наглядно. Какие же еще есть стратегии выделения памяти. Вот дек выделяет память кусками, эти куски довольно большие, а что если сделать их совсем маленькими. Вот прямо таки каждому элементу свой кусок памяти и вы знаете, что это будет на самом деле, вы уже решали задачу, в которой надо было сдавать свой список. Итак, как же устроен список. Вот вы создаете, есть оказывается контейнер, лист, вы можете создать вот такой контейнер, положив туда, скажем, 6 чисел с помощью того же синтаксис с фигурными скобками и что же будет происходить? Каждому элементу выделим свой кусок памяти, индивидуальной, но когда элементы просто так раскинуты по памяти, вы даже проитерироватся не сможете. И как же проблему решить? Можно научить каждый элемент ходить к следующему, можно просто рядом с ним положить указатель на следующий элемент. Мы, давайте, назовем вот эти вот области памяти, где будут хранится элементы, item, соответственно у нас там будет указатель item*, и теперь можем притерироватся по списку от начала в конец. Но иногда бывает удобно притерироватся в обратную сторону, по этому почему бы нам не положить указатель на предыдущий элемент. Итак вот, так устроен список. У каждого элемента свой индивидуальный блок памяти и вместе с ним лежит указатель на предыдущий элемент, указатель на следующий элемент. Какие же от этого плюшки мы можем получить? Что же мы выиграем от такого способа хранить элементы? Теперь мы можем быстро удалить элементы из середины списка. Давайте представим, что нужно удалить четверку. Как мы можем это сделать? Нам нужно сначала ее найти, а потом удалить, и найти можно с помощью функций find, в которую можно передать два итератора и собственно тот элемент, который мы ищем, она отработает за линейное время. Кстати нельзя ли найти четверку с помощью двоичного поиска? Нет, потому что при таком устройстве контейнера, при таком устройстве списка вы не можете эффективно реализовать двоичный поиск, поэтому четверку мы ищем честно, зато найдя четверку, найдя итератор IT, который указывает на эту четверку, мы можем ее быстро, за констант время взять и удалить из списка. Как мы это делаем? Просто освобождаем память из под четверки и перевешиваем указатели, говорим, что за тройкой теперь следует пятерка и наоборот, перед пятеркой идет тройка и все, удаление закончилось. Мы смогли заотъединиться не трогают другие элементы, разве что указатели, удалить элемент из середины списка. Это его основное преимущество. Мы можем быстро удалить из середины, быстро добавлять в середину и при этом, заметьте, мы не инвалидировали ничего, разве что указатель на четверку огорчаться, когда мы ее удалим, но все остальные указатели и даже итераторы. Все остальные элементы останутся валидними, и это важное преимущество списка. Однако, мы при таком устройстве списка не можем быстро обратиться к элементу по его номеру. Если мы хотим отчитать там третий элемент, мы должны взять первый, после него второй, после него третий. Это явно будет не от единицы [inaudible] и кроме того у нас под каждый элемент выделяется свой кусок памяти вместе с указанием на предыдущий и на следующий. Из-за этого могут случаться некоторые накладные расходы, однако, список, несмотря на то, что он устроен некоторым особенным образом, его основные методы имеют уже известные вам названия, они очень похожи в частности на методы вектор и дека, а именно у нас есть огромная пачка методов, которые работают за константное врем, за отединицы. Методы size, empty, clear, с уже известным вам смыслом, методы добавления в конец, добавления в начало, удаление с конца, удаление из начала, а также методы из insert erase, которые позволяют вставить элемент по итератору или удалить элемент по итератору, и в данном случае они работают за константное время. Кроме того, список устроен довольно интересно, у вас элементы где-то в памяти в разных местах лежат и указывают друг на друга, поэтому некоторые алгоритмы можно реализовать более эффективно. Например, алгоритм reverse, что он делал когда он был функцией reverse, что делает функция реверс, когда ей передаете два итератора, она берет и меняет первый элемент с последним, второй с предпоследним и так далее, физически перекладывает в памяти, первый ставит на место последнего, последний на место первого, но в случае списка вы можете сами элементы в памяти не перекладывать, а просто перевешивать указатели, и поэтому у списка есть метод реверс. Помните, мы говорили о том, что если у вас есть алгоритм, который есть в виде функции внешней и для данного контейнера в виде метода, эффективнее использовать метод, именно потому такой метод и есть, и это верно и для списка в случае с алгоритмами reverse, uniqie, remove и remove_if. Они все делают то, что заявлено то, что нужно, при этом всего лишь перевешивая указатели. Кроме того, алгоритм sort для списка будет работать долго, поэтому у списка есть специально реализованный именно для него метод sort, который выполняет сортировку за время NlogN.
