Робота з зв’язковими списками STL

Наступний важливий компонент STL, який ми збираємося розглянути – клас list (список) Це той самий всім знайомий однозвязний список, який кожен з програмістів або його брат, або сестра повинні були написати для початкового курсу програмування Основна ідея списку в тому, що у вас є стартова точка (зазвичай звана головою, head, списку) і потім серія елементів у списку (називаються вершинами, nodes, списку) Кожне елемент містить покажчик на наступний елемент, так що за списком можна легко переміщатися в одному напрямку

Версія класу list в STL досить багата у своїй реалізації Вона пропонує можливість додавати елементи в кінець списку, в початок списку, і навіть вставляти елементи в середину повязаного списку Якщо ви збираєтеся створити структуру даних, якої потрібно вставка елементів в середину вже існуючих, то використовуйте list, а не vector Вектора вимагають, щоб елементи зберігалися в одному блоці, кожен наступний відразу за попереднім в памяті У списку ж елементи вказують один на одного, а не містяться в сусідніх адресах памяті Так що вставка в список – нескладна операція Додавання в кінець і початок списку є теж досить швидкими операціями

Загалом вам потрібно знати, як додавати елементи в список та як отримати і назад Для того, щоб покласти що-небудь в список, ви використовуєте метод insert (вставити) Це те ж метод, що ми бачили в класі vector, і використовуєте ви його точно так само Наприклад, для створення нового списку, що містить цілі числа, ми могли б написати:

list&ltint, allocator&ltint&gt &gt intList

Тип елементів у списку буде int (від англ Integer, цілий) Аргумент allocator в конструкторі списку додає класу list гнучкості, дозволяючи йому виділяти память під нові цілі числа динамічно STL надає клас allocator для створення нових елементів даного типу, але ви можете, якщо хочете, надавати свою власну схему виділення памяті Зазвичай же ви будете просто використовувати шаблонну посилання на клас allocator Зауваження про класи типу allocator: клас allocator вимагає, щоб ваш обєкт міг бути створений викликом конструктора без параметрів Це означає, що для класу Foo вам потрібно мати опис приблизно в такому вигляді:

class Foo

{

public: Foo(int x) Foo(void)

}

Якщо у вас не буде такого конструктора (void constructor, як вони називаються), то компілятор поскаржиться на якісь загадкові вираження в заголовному файлі класу list і ваше програма не скомпіліруется Якщо таке відбувається, додайте конструктор без параметрів Крім того, якщо ваш клас вимагає особливої ​​роботи з копіями, то не забудьте написати конструктор для копій:

Foo(const Foo&amp aFoo)

Вам потрібно такий конструктор, якщо ваш клас містить інші обєкти або покажчики, які створюються класом Конструктор для копій за замовчуванням створює двійкову копію кожного елемента в класі, що може призвести до проблем на стадії звільнення памяті, займаної обєктом (в деструкції)

У будь-якому випадку для додавання нового елемента в список вам потрібно використовувати метод insert: intListinsert (intListbegin (), 12)

Це вираз помістить значення 12 в початок списку, пропіхав всі інші елементи списку на один назад в ієрархії списку Точно також, наступний вираз

intListinsert (intListend(), 12 )

помістить значення 12 в кінець списку, за всіма елементами у списку Важливо зауважити, що кожен раз, коли ви додаєте елементи на початок або кінець списку, ви змінюєте положення колишнього останнього або першого елементу Тому, коли ви пишете:

intlistinsert (intListbegin(), 11)

intlistinsert (intListbegin(), 12)

intlistinsert (intListbegin(), 13)

то отримуєте список, що містить значення: 13, 12, 11 (саме в цьому порядку) Разом з усім цим, давайте подивимося на деякі доступні методи класу list, а також розберемося, що вони роблять У табл 53 перераховані найважливіші методи класу list і наведений опис того, що кожен з них робить

Таблиця 53 Важливі методу класу list

Вставляє новий елемент в дану позицію в списку

Зазвичай використовується метод, еквівалентний вставці в кінець списку

Зазвичай використовується метод, еквівалентний вставці в початок списку

Один із способів вставити один список (або його частина) у другий список

Обмінює дані між списками ефективним чином

Цей метод видаляє зі списку всі елементи, які підходять під задане значення

Цей метод видаляє зі списку всі елементи c даними значенням, які підходять під заданий предикат

Цей метод видаляє даний елемент у списку

Ця допоміжна операція видалить зі списку всі елементи, крім одного для кожного значення

Повертає кількість елементів у списку

Вказує, чи є (FALSE) чи ні (TRUE) елементів у списку

Змушує список мати задану кількість елементів

Повертає перший елемент у списку

Повертає останній елемент у списку

Сортує список у зростаючому порядку Може використовуватися з функцією порівняння елементів або використовувати порядок сортування за замовчуванням

Повертає позицію першого елемента, що задовольняє заданому критерію

Це метод змінить порядок у списку на протилежний, роблячи перший елемент останнім, а останній – перший і аналогічно переставляючи всі інші елементи

Цей метод застосує задану функцію до всіх елементів списку

Попередні функції можуть бути використані в будь-якому списку Вони надають потужний набір операцій, який дозволяє вам робити практично все, що вам може знадобитися зробити з будь-яким даними списком Давайте подивимося на повний приклад того, як використовувати списки Створіть ще одне консольний додаток в CBuidler і додайте цей код у файл projectcpp:

#include &ltstdioh&gt

#include &ltstringh&gt

#include &ltstdlibh&gt

#include &ltlist&gt

#include &ltstring&gt using namespace std int main(void)

{

list > listStrings listStringsinsert (listStringsend (), Перший) listStringsinsert (listStringsend (), Другий) listStringsinsert (listStringsend (), Третій )

listStringsinsert (listStringsend (), Четвертий) listStringsinsert (listStringsend (), Пятий) listStringsinsert (listStringsend (), Шостий)

list&ltstring, allocator&ltstring&gt &gt::iterator list_iterator list_iterator = listStringsbegin()

while  (list_iterator = listStringsend() )

{

printf (Рядок = <% s> \ n, (* list_iterator) c_str ())

// advance (list_iterator, 1) list_iterator++

}

return 0

}

Цей простий приклад показує кілька важливих особливостей у використанні списку По-перше, ви могли помітити, що відразу за включенням заголовних файлів знаходиться рядок:

using namespace std

Цей рядок важлива при компіляції додатків з STL в CBuilder В системі CBuilder компанія

Borland вирішила все третьесторонніе (third-party) бібліотеки (такі, як STL) загорнути в

«Обкладинку» namespace (іменованої області видимості) Це для вас добре, оскільки означає, що бібліотеки, які ви використовуєте у своїх додатках, що не будуть конфліктувати з іншими бібліотеками, для яких у вас може не бути вихідного коду

Namespace – це просто вищий рівень області видимості (scope) Наприклад, в наступній простій програмі є три елементи, названі foo:

class MyFoo

{

int foo // 1 public: MyFoo()

}

int foo // 2 int main()

{

int foo = 2 // 3

}

int func()

{

foo = 3

}

MyFoo::MyFoo()

{

foo = 4

}

Залежно від того, де в програмі ви знаходитесь, імя foo означає щось зовсім різне Усередині функції main імя foo означає локальну змінну foo Поза функції main, всередині іншої функції func імя foo означає змінну foo на рівні файлу (позначену коментарем / / 2) І нарешті, в методі класу змінна – член класу (member variable) foo бере гору, яка позначена коментарем / / 1 і звернення до неї йде в методі класу MyFoo (в конструкторі)

Namespace дуже схожа на звичайну область видимості, але вона дозволяє укладати в себе тільки виділені частини програми У разі STL компанія Borland вирішила помістити функції в область namespace std Для доступу до членів цієї області std ви використовуєте стандартний оператор видимості «::» (scoping operator) Наприклад, для використання класу list, визначеного в namespace std, ми могли б написати:

std::list&lt int, std::allocator&ltint&gt &gt intList

Фактично, цей код компілюватиметься, запускатися і відмінно працювати в середовищі CBuilder Інакше, якщо ви не любите використовувати оператор видимості std :: усюди, де ви посилаєтеся на один з класів STL, то ви можете використовувати інший метод, який говорить компілятору, що ви безпосередньо звертаєтеся до речей в області namespace std Це робиться виразом using namespace , яке говорить компілятору дивитися всі невпізнані лексеми в області namespace Проблема з таким підходом в тому, що забирається можливість тримати сторонні бібліотеки роздільно Якби у мене була інша область namespace, яка містила б клас list і я хотів би використовувати їх обох, то мені все-таки довелося б повністю здавати імена класів з другого області namespace Коротше кажучи, області видимості namespace – хороша ідея, яка проте може привести до деякої роботи з боку програміста

Джерело: Теллес М – Borland C + + Builder Бібліотека програміста – 1998

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*