STL List поверхностное знакомство

Опубликовано 01.10.2014 | Автор: admin

Что такое list в STL? Это такой контейнер (хранилище элементов одинакового типа), который представляет собой двусвязный список. Двусвязный список являет собой сущность, где каждый отдельный внутренний элемент имеет прямую связь со своими соседствующими элементами, при этом любые не соседствующие элементы друг с другом никаких связей не имеют и ничего друг о друге не знают.

На анимированном рисунке очень ограничено показана приблизительная архитектура списка. Для нас этот рисунок может быть сложен и трудно понимаем. Просто, должны же мы приблизительно понимать, о чем говорим.

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

   list<int> l1;
   l1.push_back(1);
   l1.push_back(2);
   l1.insert(l1.begin()+1,100); //Так нельзя

list<int> l1;

l1.push_back(1);

l1.push_back(2);

l1.insert(l1.begin()+1,100); //Так нельзя

Дело в том, что чтобы вставить элемент в середину списка, нужно до этой середины дойти. Список не обладает произвольными итераторами, а те итераторы, которыми он обладает, не поддерживают операций + и —. Т. е. нельзя написать l1.begin + 1;, только потому что итераторы у списка двунаправленные. Зато можно установить независимый итератор на любую позицию списка и уже используя его вставлять элемент.

list<int> l1;
    for (int i=0;i<20;i++) l1.push_back(i+1);

    list<int>::iterator it=l1.begin();
    advance(it,5);
    l1.insert(it,100);

list<int> l1;

for (int i=0;i<20;i++) l1.push_back(i+1);

list<int>::iterator it=l1.begin();

advance(it,5);

l1.insert(it,100);

В этом примере использовалась функция advance(). Это такая функция, которая наделяет возможностью смещения любого итератора. Это полезно, потому что для некоторых итераторов не определено операций += и -=. В том случае, если используется двунаправленный итератор или итератор произвольного доступа, смещение со знаком — означает отодвинуть итератор назад, а со знаком + (или без знака вообще), означает отодвинуть итератор вперед.

advanced(iter,-8); //отодвинули итератор на 8 позиций назад
advansed(iter,8); //отодвинули итератор на 8 позиций вперед

1 2	advanced(iter,-8); //отодвинули итератор на 8 позиций назад advansed(iter,8); //отодвинули итератор на 8 позиций вперед

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

Список отличий списка(list) от вектора и дека:

Отсутствие произвольного доступа. Быстрый доступ существует только к первому и последнему элементу списка. Оттакливаясь от первого или последнего элемента списка, можно получить доступ к любому элементу внутри. Такой обход выполняется по существующей цепочке связей внутри списка. Обход можно делать и с первого, и с последнего элемента.

Вставка и удаление элементов выполняется одинаково быстро (при условии, что итератор уже установлен в эту позицию). И вставка, и удаление выполняются за константное время. При вставке или удалении не требуется смещать элементы, поэтому и вставка, и удаление происходит очень быстро, а все операции сводятся к манипулированию указателями.

Вставка в список никогда не делает недействительными никакие итераторы, а операция удаления из списка делает невалидными только итераторы, указывающие на удаленный элемент.

Список поддерживает обработку исключений таким образом, что почти каждая операция либо выполняется успешно, либо не выполняется вообще. Таким образом список не может оказаться в промежуточном положении из-за незавершенной операции.

Списки содержат такие функции, как front(),push_front(),pop_front() и back(),push_back(),pop_back().

У списков нельзя получить доступ к элементу подобно массиву, используя [] и нельзя с помощью .at(), потому как списки не поддерживают произвольный доступ.

Списки не поддерживают операции изменения ёмкости и перераспределения памяти, потому как такие операции спискам не требуются. Каждый объект внутри списка занимает свою собственную ячейку в памяти, и та ячейка будет оставаться корректной вплоть до того момента, пока объект не будет удалён.

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

vector делает упор на быстрый произвольный доступ, a list — на быструю вставку и удаление элементов.

К спискам следует прибегать, когда по ходу работы программы требуется большое количество вставок и/или удалений во внутренних позициях и практически не требуется переходить из одной позиции в другую, весьма удаленную. Такие связные структуры часто используются вместо массивов, просто потому, что они в состоянии динамически увеличиваться;

Важно

При работе со списком вызвающая сторона должна гарантировать, что в списке есть хотя бы 1 элемент. Если список пуст, то любой обход списка приводит к неопределенному поведению (UB).

Вообще, со списком во многих случаях можно работать как с вектором. Например, начальный ввод данных ничем не отличается. Мой пример просто пример немного другого способа ввода данных, на самом деле можно использовать push_back() в цикле как у вектора, и наоборот: приводимый мой пример может работать и с вектором. Это Не особенность списка.

Пример заполнения списка с клавиатуры и вывода на экран (ввод в список прекращается после ввода любого значения не соответствующего типу данных, хранимых в списке)

#include <iostream>
#include <list>   //Обязательно если используем список
#include <iterator>

using namespace std;

int main(){
    list<int> l1;  //Объявили список, хранящий целые числа
    copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(l1));  //Ввод с клавиатуры, можно в строчку вводить через пробел
    copy(l1.begin(),l1.end(),ostream_iterator<int>(cout," "));  //Вывод на экран

return 0;
}

#include <iostream>

#include <list> //Обязательно если используем список

#include <iterator>

using namespace std;

int main(){

list<int> l1; //Объявили список, хранящий целые числа

copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(l1)); //Ввод с клавиатуры, можно в строчку вводить через пробел

copy(l1.begin(),l1.end(),ostream_iterator<int>(cout," ")); //Вывод на экран

return 0;

}

Пример удаления из list всех элементов равных 10

#include <iostream>
#include <list>
#include <iterator>

using namespace std;

int main(){

    list<int> l1;
    copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(l1));

      l1.remove(10);  //Все 10 будут удалены из списка

    copy(l1.begin(),l1.end(),ostream_iterator<int>(cout," "));

return 0;
}

#include <iostream>

#include <list>

#include <iterator>

using namespace std;

int main(){

list<int> l1;

copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(l1));

l1.remove(10); //Все 10 будут удалены из списка

copy(l1.begin(),l1.end(),ostream_iterator<int>(cout," "));

return 0;

}

Если нужно удалить только одно значение, то нужно узнать место этого значения внутри списка. Для этого используются итераторы (итераторы это наш посредник между STL и нами), так вот нужно использовать итераторы и обобщенный алгоритм find. find нам вернет итератор, который указывает на адрес такого элемента.

#include <iostream>
#include <list> //использование list
#include <iterator>
#include <algorithm> //для использования обобщенного алгоритма find

using namespace std;

int main(){

    list<int> l1;
    copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(l1));

    list<int>::iterator it=find(l1.begin(),l1.end(),10);
     if (it!=l1.end()){
         l1.erase(it); //Удаляем первое вхождение 10 внутри списка, остальные числа == 10 не затрагиваем
     }
    copy(l1.begin(),l1.end(),ostream_iterator<int>(cout," "));

return 0;
}

#include <iostream>

#include <list> //использование list

#include <iterator>

#include <algorithm> //для использования обобщенного алгоритма find

using namespace std;

int main(){

list<int> l1;

copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(l1));

list<int>::iterator it=find(l1.begin(),l1.end(),10);

if (it!=l1.end()){

l1.erase(it); //Удаляем первое вхождение 10 внутри списка, остальные числа == 10 не затрагиваем

}

copy(l1.begin(),l1.end(),ostream_iterator<int>(cout," "));

return 0;

}

Если для списка list есть какой-то алгоритм, который работает эффективнее, чем обобщенный алгоритм к этому списку, то для списка определена специальная функция (например, список MyList, MyList.sort(),MyList.remove()). Если нет алгоритма, который работает эффективнее, чем аналогичный обобщенный алгоритм, то тогда для списка нет специальной функции, и если в алгоритме не требуются итераторы с произвольным доступом, то тогда такой обобщенный алгоритм применяется к списку. Такие алгоритмы, как правило, работают одинаково эффективно для разного вида контейнеров. Сейчас и был приведен пример с find. find одинакого быстр и для списка и для вектора, быстрее чем этот алгоритм для списка нету, поэтому у списка отсутствует такая функция поиска как find или search и заменяется она обычным обобщенным алгоритмом. Аналогично для всех других ситуаций. Поэтому если у списка есть какая-то одноименная функция, схожая с обобщенным алгоритмом, то лучше для списка применять именно её, а не обобщенный алгоритм, потому что она учитывает структуру списка и работает эффективнее, а вот если нету такой специальной функции, то нужно использовать либо обобщенный алгоритм, либо использовать алгоритм нельзя в силу ограничений из-за, например, итераторов, не имеющих произвольного доступа.

Ну и предлагаю решить простую задачку. Нужно создать список из 20 элементов. Заполнить этот список любыми значениями. Вставить в каждую позицию списка, кратную 3, цифру 100. Использовать цикл while

Пример:

Список: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20

тут ваш код

Вывод 1,2,100,3,4,100,5,6,100,7,8,100,9,10,100,11,12,100,13,14,100,15,16,100,17,18,100,19,20