Основи програмування на С ++ для початківців

Контейнери 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, як ми це робили в попередньому уроці.
Список C ++, лист з ++, Контейнери C ++ STL , Стандартна бібліотека шаблонів, контейнер з ++, двусвязний список

3 думки про "Контейнери STL: list. Частина 4

  1. ніхрена не зрозуміло… стаття написана кострубато і поверхнево не очікував від purecode такого ставлення.
    Це одна з тем для гейм діва, а до неї так некрасиво поставилися, мало того неясно нічого після прочитання.

  2. Если “ніхрена не зрозуміло”, то потрібно взяти і перечитати по 2-му разу, 3 Його … для кращого засвоєння.

    А якщо “стаття написана кострубато і поверхнево” – то візьміть і напишіть від себе авторську статтю краще.

  3. згоден. Стаття мало зрозуміла, особливо молодої аудиторії. І перечитування по кілька разів тут не допоможе.

залишити коментар

Ваша електронна адреса не буде опублікований. Обов'язкові поля позначені * *