Контейнери STL: list. Частина 4

У третій частині уроків про контейнери STL,  ми закінчили розгляд векторів, скажем, типу vector<float> як еквівалента масиву дійсних чисел. Для таких «масивів» дуже швидко здійснюються операції доступу до елементу (читання-запис) за індексом і вставка-видалення елемента в кінець вектора. Набагато гірше (по ефективності) виконуються операції вставки-видалення елемента десь в середині вектора, або переміщення елемента з однієї позиції в іншу.

Наприклад, в векторі розміром 15 операція переміщення 10-го елемента в позицію 2 зажадає:

• запам'ятати в проміжній змінній 10-й елемент;

• для всіх елементів з 9-го по 2-й (в зворотньому напрямку, можливо використовуючи реверсний итератор) скопіювати в наступну позицію (8 операцій копіювання);

• збережений раніше в проміжній змінній елемент скопіювати в позицію 2;

Разом, для цієї простої операції нам потрібно 10 операцій копіювання. Кожен елемент вектора, як вже обговорювалося раніше, може представляти збій складно-складову структуру. І його копіювання - це досить трудомістка дію.

для “колекцій”, в яких плануються активні додавання, видалення і переміщення елементів, бібліотека STL пропонує інший вид контейнера - двусвязний список, list. Для такого контейнера доступ до елементів (читання, запись) послідовний, і не такий ефективний. Зате операції додавання, видалення або зміни порядку елементів дуже швидкі.

итератор list не є ітератором прямого доступу. Тому для нього незастосовні операції +,  –,  +=,  -=, а для контейнера недопустима операція індексація. Ітератори для цього контейнера переміщаються послідовно операціями++  і  — .

Для ілюстрації роботи з таким контейнером запишемо все ту ж задачу знаходження всіх простих чисел, що не перевищують N (для одноманітності і порівняння з попередніми варіантами):

Тут перша половина коду (оператор << для списку) тільки декоративна реалізація для діагностики та зручності, а в іншій частині проробляється наступне:

• формується список list<int>  натуральних чисел діапазону [2…N] – строки 19 – 22;

• Для кожного (залишився) числа з усієї подальшої списку видаляються кратні йому елементи – рядок 31;

• І так до тих пір, поки чергове перевіряється число не перевищить квадратний корінь з N – рядок 26 (в теорії чисел показано, що подільність можна перевіряти не до N-1, а до числа, перевищує корінь квадратний N);

З особливостей коду, і контейнерів list взагалі, потрібно звернути увагу на те, що після видалення елемента, зазначених вище поточним значенням ітератора, значення ітератора стає невизначеним. Якщо нам потрібно продовжувати ітерацію, то ми повинні працювати з копією итератор (i в показаному коді).

Виконанням коду ми можемо перевірити, що результати його в точності аналогічні попереднім варіантам. Перед запуском програми, не забудьте визначити аргумент команди рівний 300, як ми це робили в попередньому уроці.