У третій частині уроків про контейнери STL, ми закінчили розгляд векторів, скажем, типу vector<float> як еквівалента масиву дійсних чисел. Для таких «масивів» дуже швидко здійснюються операції доступу до елементу (читання-запис) за індексом і вставка-видалення елемента в кінець вектора. Набагато гірше (по ефективності) виконуються операції вставки-видалення елемента десь в середині вектора, або переміщення елемента з однієї позиції в іншу.
Наприклад, в векторі розміром 15 операція переміщення 10-го елемента в позицію 2 зажадає:
запам'ятати в проміжній змінній 10-й елемент;
для всіх елементів з 9-го по 2-й (в зворотньому напрямку, можливо використовуючи реверсний итератор) скопіювати в наступну позицію (8 операцій копіювання);
збережений раніше в проміжній змінній елемент скопіювати в позицію 2;
Разом, для цієї простої операції нам потрібно 10 операцій копіювання. Кожен елемент вектора, як вже обговорювалося раніше, може представляти збій складно-складову структуру. І його копіювання - це досить трудомістка дію.
для “колекцій”, в яких плануються активні додавання, видалення і переміщення елементів, бібліотека STL пропонує інший вид контейнера - двусвязний список, list. Для такого контейнера доступ до елементів (читання, запись) послідовний, і не такий ефективний. Зате операції додавання, видалення або зміни порядку елементів дуже швидкі.
итератор list не є ітератором прямого доступу. Тому для нього незастосовні операції +, –, +=, -=, а для контейнера недопустима операція індексація. Ітератори для цього контейнера переміщаються послідовно операціями++ і — .
Для ілюстрації роботи з таким контейнером запишемо все ту ж задачу знаходження всіх простих чисел, що не перевищують N (для одноманітності і порівняння з попередніми варіантами):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include <iostream> #include <list> #include <string> using namespace std; inline ostream& operator <<(ostream& out, const list<int>& obj) { const int line = 10; int k = 0; for (auto j = obj.begin(); j != obj.end(); j++) { cout << *j << "\t"; if (0 == ++k % line) cout << endl; } if (k % line != 0) cout << endl; return out; } int main(int argc, char **argv) { int n = stoi(argv[1]); // верхняя граница list<int> a; for (int i = 2; i < n; i++) a.push_back(i); list<int>::iterator k = a.begin(); while (*k * *k <= n) { int div = *k++; auto j = k; while (j != a.end()) { auto i = j++; if (0 == *i % div) a.erase(i); } } cout << a; } |
Тут перша половина коду (оператор << для списку) тільки декоративна реалізація для діагностики та зручності, а в іншій частині проробляється наступне:
формується список list<int> натуральних чисел діапазону [2…N] – строки 19 – 22;
Для кожного (залишився) числа з усієї подальшої списку видаляються кратні йому елементи – рядок 31;
І так до тих пір, поки чергове перевіряється число не перевищить квадратний корінь з N – рядок 26 (в теорії чисел показано, що подільність можна перевіряти не до N-1, а до числа, перевищує корінь квадратний N);
З особливостей коду, і контейнерів list взагалі, потрібно звернути увагу на те, що після видалення елемента, зазначених вище поточним значенням ітератора, значення ітератора стає невизначеним. Якщо нам потрібно продовжувати ітерацію, то ми повинні працювати з копією итератор (i в показаному коді).
Виконанням коду ми можемо перевірити, що результати його в точності аналогічні попереднім варіантам. Перед запуском програми, не забудьте визначити аргумент команди рівний 300, як ми це робили в попередньому уроці.
ніхрена не зрозуміло… стаття написана кострубато і поверхнево не очікував від purecode такого ставлення.
Це одна з тем для гейм діва, а до неї так некрасиво поставилися, мало того неясно нічого після прочитання.
Если “ніхрена не зрозуміло”, то потрібно взяти і перечитати по 2-му разу, 3 Його … для кращого засвоєння.
А якщо “стаття написана кострубато і поверхнево” – то візьміть і напишіть від себе авторську статтю краще.
згоден. Стаття мало зрозуміла, особливо молодої аудиторії. І перечитування по кілька разів тут не допоможе.