Главная » C++, C++ Builder » Работа со связными списками STL

0

Следующий важный компонент STL, который мы собираемся рассмотреть — класс list (список). Это тот самый всем знакомый односвязный список, который каждый из программистов или его брат, или сестра должны были написать для начального курса программирования. Основная идея списка в том, что у вас есть стартовая точка (обычно называемая головой, head, списка) и затем серия элементов в списке (называются вершинами, nodes, списка). Каждое элемент содержит указатель на следующий элемент, так что по списку можно легко перемещаться в одном направлении.

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

В общем вам нужно знать, как добавлять элементы в список и как получить и обратно. Для того, чтобы положить что-нибудь в список, вы используете метод insert (вставить). Это то же метод, что мы видели в классе vector, и используете вы его точно так же. Например, для создания нового списка, содержащего целые числа, мы могли бы написать:

list<int, allocator<int> > intList;

Тип элементов в списке будет int (от англ. integer, целый). Аргумент allocator<int> в конструкторе списка добавляет классу list гибкости, позволяя ему  выделять память под новые целые числа динамически. STL предоставляет класс allocator для создания новых элементов данного типа, но вы можете, если хотите, предоставлять свою собственную схему выделения памяти. Обычно же вы будете просто использовать шаблонную ссылку на класс allocator. Замечание о классах типа allocator: класс allocator  требует, чтобы ваш объект мог быть создан вызовом конструктора без параметров. Это значит, что для класса Foo вам нужно иметь описание примерно в таком виде:

class Foo

{

public: Foo(int x); Foo(void);

}

Если у вас не будет такого конструктора (void constructor, как они называются), то компилятор пожалуется на какие-то загадочные выражения в заголовочном файле  класса  list  и  ваше приложение не скомпилируется. Если такое происходит, добавьте конструктор без параметров. Кроме того, если ваш класс требует особой работы с копиями, то не забудьте написать конструктор для копий:

Foo(const Foo& aFoo);

Вам потребуется такой конструктор, если ваш  класс содержит другие объекты или указатели, которые создаются классом. Конструктор для копий по умолчанию создает двоичную копию каждого элемента в классе, что может привести к проблемам на стадии освобождения памяти, занимаемой объектом (в деструкторе).

В любом случае для добавления нового элемента в список вам нужно использовать метод insert: intList.insert (intList.begin(), 12 );

Это выражение поместит значение 12 в начало списка, пропихав все остальные элементы списка на один назад в иерархии списка. Точно также, следующее выражение

intList.insert (intList.end(), 12 );

поместит значение 12 в конец списка, за всеми элементами в списке. Важно заметить, что каждый раз, когда вы добавляете элементы в начало или конец списка, вы изменяете положение бывшего последнего или первого элемента. Поэтому, когда вы пишете:

intlist.insert (intList.begin(), 11);

intlist.insert (intList.begin(), 12);

intlist.insert (intList.begin(), 13);

то получаете список, содержащий значения: 13, 12, 11 (именно в этом порядке). Вместе со всем этим, давайте посмотрим на некоторые доступные методы класса list, а также разберемся, что они делают. В табл. 5.3 перечислены самые важные методы класса list и приведено описание того, что каждый из них делает.

Таблица 5.3 Важные метода класса list

insert

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

push_back

Обычно используемый метод, эквивалентный вставке в конец списка

push_front

Обычно используемый метод, эквивалентный вставке в начало списка

splice

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

swap

Обменивает данные между списками эффективным образом

remove

Этот метод удаляет из списка все элементы, подходящие под заданное значение

remove_if

Этот метод удаляет из списка все элементы c данным значением, подходящие под заданный предикат

erase

Этот метод удаляет данный элемент в списке

unique

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

size

Возвращает количество элементов в списке

empty

Указывает, есть ли (FALSE) или нет (TRUE) элементов в списке

resize

Заставляет список иметь заданное количество элементов

front

Возвращает первый элемент в списке

back

Возвращает последний элемент в списке

sort

Сортирует список в возрастающем порядке. Может использоваться с функцией сравнения элементов или использовать порядок сортировки по умолчанию

find

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

reverse

Это метод изменит порядок в списке на противоположный, делая первый элемент последним, а последний — первым и аналогично переставляя все остальные элементы

for_each

Этот метод применит заданную функцию ко всем элементам списка

Предыдущие функции могут быть использованы в любом списке. Они предоставляют мощный набор операций, который позволяет вам делать практически все, что вам может  понадобиться сделать с любым данным списком. Давайте посмотрим на полный пример того, как использовать списки. Создайте еще одно консольное приложение в CBuidler и добавьте этот код в файл project.cpp:

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <list>

#include <string> using namespace std; int main(void)

{

list<string, allocator<string> > listStrings; listStrings.insert (listStrings.end(), "Первый" ); listStrings.insert (listStrings.end(), "Второй" ); listStrings.insert (listStrings.end(), "Третий" );

listStrings.insert (listStrings.end(), "Четвертый" ); listStrings.insert (listStrings.end(), "Пятый" ); listStrings.insert (listStrings.end(), "Шестой" );

list<string, allocator<string> >::iterator list_iterator; list_iterator = listStrings.begin();

while  (list_iterator != listStrings.end() )

{

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< int, std::allocator<int> > intList;

Фактически, этот код будет компилироваться, запускаться и отлично работать в среде CBuilder. Иначе, если вы не любите использовать оператор видимости std:: всюду, где вы ссылаетесь на один из классов STL, то вы можете использовать другой метод, который говорит компилятору, что вы непосредственно обращаетесь к вещам в области namespace std. Это делается выражением using namespace <name>, которое говорит компилятору смотреть все неопознанные лексемы в области namespace <name>. Проблема с таким подходом в том, что убирается возможность держать посторонние библиотеки раздельно. Если бы у меня была другая область namespace, которая содержала бы класс list и я хотел бы использовать их обоих, то мне все-таки пришлось бы полностью задавать  имена классов из второй области namespace.  Короче  говоря,  области видимости namespace — хорошая идея, которая тем не менее может привести к некоторой работе со стороны программиста.

Источник: Теллес М. – Borland C++ Builder. Библиотека программиста – 1998

По теме:

  • Комментарии