|
C++ для начинающих |
5.11. Пример связанного списка
Мы завершали главы 3 и 4 примерами
для введения читателя в механизм классов С++. В конце этого раздела мы покажем,
как разработать класс, представляющий собой односвязный список. (В главе
6 мы рассмотрим двусвязный список, являющийся частью стандартной библиотеки.)
Если вы в первый раз читаете эту книгу, то можете пропустить данный раздел и
вернуться к нему после чтения главы 13. (Для усвоения этого материала нужно
представлять себе механизм классов С++, конструкторы, деструкторы и т.д. Если
вы плохо знаете классы, но все же хотите продолжить чтение данного раздела,
мы рекомендуем прочесть пункты 2.3 и 3.15.
Список представляет собой последовательность элементов, каждый из которых содержит
значение некоторого типа и адрес следующего элемента (причем для последнего
из них адрес может быть нулевым). К любой такой последовательности всегда можно
добавить еще один элемент (хотя реальная попытка подобного добавления может
закончиться неудачно, если отведенная программе свободная память исчерпана).
Список, в котором нет ни одного элемента, называется пустым.
Какие операции должен поддерживать список? Добавление (insert), удаление (remove)
и поиск (find) определенных элементов. Кроме того, можно запрашивать размер
списка (size), распечатывать его содержимое (display), проверять равенство двух
списков. Мы покажем также, как инвертировать (reverse) и сцеплять (concatenate)
списки.
Простейшая реализация операции size() перебирает все элементы, подсчитывая их
количество. Более сложная реализация сохраняет размер как член данных; она намного
эффективнее, однако требует некоторого усложнения операций insert() и remove()
для поддержки размера в актуальном состоянии.
Мы выбрали второй вариант реализации функции size() и храним размер списка в
члене данных. Мы предполагаем, что пользователи будут достаточно часто применять
эту операцию, поэтому ее необходимо реализовать как можно более эффективно.
(Одним из преимуществ отделения открытого интерфейса от скрытой реализации является
то, что если наше предположение окажется неверным, мы сможем переписать реализацию,
сохранив открытый интерфейс – в данном случае тип возвращаемого значения и набор
параметров функции size() – и программы, использующие эту функцию, не нужно
будет модифицировать.)
Операция insert() в общем случае принимает два параметра: указатель на один
из элементов списка и новое значение, которое вставляется после указанного элемента.
Например, для списка
1 1 2 3 8
вызов
mylist.insert (pointer_to_3, 5);
изменит наш список так:
1 1 2 3 5 8
Чтобы обеспечить подобную возможность, нам необходимо дать пользователю способ получения адреса определенного элемента. Одним из способов может быть использование функции find() – нахождение элемента с определенным значением:
pointer_to_3 = mylist.find( 3 );
find() принимает в качестве параметра значение из списка. Если элемент с таким
значением найден, то возвращается его адрес, иначе find() возвращает 0.
Может быть два специальных случая вставки элемента: в начало и в конец списка.
Для этого требуется только задание значения:
insert_front( value ); insert_end( value );
Предусмотрим следующие операции удаления элемента с заданным значением, первого элемента и всех элементов списка:
remove( value ); remove_front(); remove_all();
Функция display() распечатывает размер списка и все его элементы. Пустой список можно представить в виде:
(0)( )
а список из семи элементов как:
(7) ( 0 1 1 2 3 5 8 )
reverse() меняет порядок элементов на противоположный. После вызова
mylist.reverse();
предыдущий список выглядит таким образом:
(7) ( 8 5 3 2 1 1 0 )
Конкатенация добавляет элементы второго списка в конец первого. Например, для двух списков:
(4)( 0 1 1 2 ) // listl (4)( 2 3 5 8 ) // list2
операция
listl.concat( list2 );
превращает list1 в
(8) ( 0 1 1 2 2 3 5 8 )
Чтобы сделать из этого списка последовательность чисел Фибоначчи, мы можем
воспользоваться функцией remove():
listl.remove( 2 );
Мы определили поведение нашего списка, теперь можно приступать к реализации.
Пусть список (list) и элемент списка (list_item) будут представлены двумя разными
классами. (Ограничимся теми элементами, которые способны хранить только целые
значения. Отсюда названия наших классов – ilist и ilist_item.)
Наш список содержит следующие члены: _at_front – адрес первого элемента, _at_end
– адрес последнего элемента и _size – количество элементов. При определении
объекта типа ilist все три члена должны быть инициализированы 0. Это обеспечивается
конструктором по умолчанию:
class ilist_item;
class ilist {
public:
// конструктор по умолчанию
ilist() : _at_front( 0 ),
_at_end( 0 ), _size( 0 ) {}
// ...
private:
ilist_item *_at_front;
ilist_item *_at_end;
int _size;
};
Теперь мы можем определять объекты типа ilist, например:
ilist mylist;
но пока ничего больше. Добавим возможность запрашивать размер списка. Включим
объявление функции size() в открытый интерфейс списка и определим эту функцию
так:
inline int ilist::size() { return _size; }
Теперь мы можем использовать:
int size = mylist.size();
Пока не будем позволять присваивать один список другому и инициализировать один
список другим (впоследствии мы реализуем и это, причем такие изменения не потребуют
модификации пользовательских программ). Объявим копирующий конструктор и копирующий
оператор присваивания в закрытой части определения списка без их реализации.
Теперь определение класса ilist выглядит таким образом:
class ilist {
public:
// определения не показаны
ilist();
int size();
// ...
private:
// запрещаем инициализацию
// и присваивание одного списка другому
ilist( const ilist& );
ilist& operator=( const ilist& );
// данные-члены без изменения
};
Обе строки следующей программы вызовут ошибки компиляции, потому что функция main() не может обращаться к закрытым членам класса ilist:
int main()
{
ilist yourlist( mylist ); // ошибка
mylist = mylist; // ошибка
}
Следующий шаг – вставка элемента, для представления которого мы выбрали отдельный класс:
class ilist_item {
public:
// ...
private:
int _value;
ilist_item *_next;
};
Член _value хранит значение, а _next – адрес следующего элемента или 0.
Конструктор ilist_item требует задания значения и необязательного параметра
– адреса существующего объекта ilist_item. Если этот адрес задан, то создаваемый
объект ilist_item будет помещен в список после указанного. Например, для списка
0 1 1 2 5
вызов конструктора
ilist_item ( 3, pointer_to_2 );
модифицирует последовательность так:
0 1 1 2 3 5
Вот реализация ilist_item. (Напомним, что второй параметр конструктора является необязательным. Если пользователь не задал второй аргумент при вызове конструктора, по умолчанию употребляется 0. Значение по умолчанию указывается в объявлении функции, а не в ее определении; это поясняется в главе 7.)
class ilist_item {
public:
ilist_item( int value, ilist_-item *item_to_link_to = 0 );
// ...
};
inline
ilist_item::
ilist_item( int value, ilist_item *item )
: _value( value )
{
if ( item )
_next = 0;
else {
_next = item->_next;
item->_next = this;
}
Операция insert() в общем случае работает с двумя параметрами – значением и адресом элемента, после которого производится вставка. Наш первый вариант реализации имеет два недочета. Сможете ли вы их найти?
inline void
ilist::
insert( ilist_item *ptr, int value )
{
new ilist_item( value, ptr );
++_size;
}
Одна из проблем заключается в том, что указатель не проверяется на нулевое значение. Мы обязаны распознать и обработать такую ситуацию, иначе это приведет к краху программы во время исполнения. Как реагировать на нулевой указатель? Можно аварийно закончить выполнение, вызвав стандартную функцию abort(), объявленную в заголовочном файле cstdlib:
#include <cstdlib> // ... if ( ! ptr ) abort();
Кроме того, можно использовать макрос assert(). Это также приведет к аварийному завершению, но с выводом диагностического сообщения:
#include <cassert> // ... assert( ptr != 0 );
Третья возможность – возбудить исключение:
if ( ! ptr )
throw "Panic: ilist::insert(): ptr == O";
В общем случае желательно избегать аварийного завершения программы: в такой
ситуации мы заставляем пользователя беспомощно сидеть и ждать, пока служба поддержки
обнаружит и исправит ошибку.
Если мы не можем продолжать выполнение там, где обнаружена ошибка, лучшим решением
будет возбуждение исключения: оно передает управление вызвавшей программе в
надежде, что та сумеет выйти из положения.
Мы же поступим совсем другим способом: рассмотрим передачу нулевого указателя
как запрос на вставку элемента перед первым в списке:
if ( ! ptr ) insert_front( value );
Второй изъян в нашей версии можно назвать философским. Мы реализовали size()
и _size как пробный вариант, который может впоследствии измениться. Если мы
преобразуем функции size() таким образом, что она будет просто пересчитывать
элементы списка, член _size перестанет быть нужным. Написав:
++_size;
мы тесно связали реализацию insert() с текущей конструкцией алгоритма пересчета
элементов списка. Если мы изменим алгоритм, нам придется переписывать эту функцию,
как и insert_front(), insert_end() и все операции удаления из списка. Вместо
того чтобы распространять детали текущей реализации на разные функции класса,
лучше инкапсулировать их в паре:
inline void ilist::bump_up_size() { ++_size; }
inline void ilist::bump_down_size() { --_size; }
Поскольку мы объявили эти функции встроенными, эффективность не пострадала. Вот окончательный вариант insert():
inline void
ilist::
insert( ilist_item *ptr, int value )
if ( !ptr )
insert_front( value );
else {
bump_up_size();
new ilist_item( value, ptr );
}
}
Реализация функций insert_front() и insert_end() достаточно очевидна. В каждой из них мы должны предусмотреть случай, когда список пуст.
inline void
ilist::
insert_front( int value )
{
ilist_item *ptr = new ilist_item( value );
if ( !_at_front )
_at_front = _at_end = ptr;
else {
ptr->next( _at_front );
_at_front = ptr;
}
bump_up_size();
}
inl-ine void
ilist::
insert_end( int value )
{
if ( !_at_end )
_at_end = _at_front = new ilist_item( value );
else _at_end = new ilist_item( value, _at_end );
bump_up_s-ize();
}
find() ищет значение в списке. Если элемент с указанным значением найден, возвращается его адрес, иначе find() возвращает 0. Реализация find()выглядит так:
ilist_item*
ilist::
find( int value )
{
ilist_item *ptr = _at_front;
while ( ptr )
{
if ( ptr->value() == value )
break;
ptr = ptr->next();
}
return ptr;
}
Функцию find() можно использовать следующим образом:
ilist_item *ptr = mylist.find( 8 ); mylist.insert( ptr, some_value );
или в более компактной записи:
mylist.insert( mylist.find( 8 ), some_value );
Перед тем как тестировать операции вставки элементов, нам нужно написать функцию
display(), которая поможет нам при отладке. Алгоритм display() достаточно прост:
печатаем все элементы, с первого до последнего. Можете ли вы сказать, где в
данной реализации ошибка?
// не работает правильно!
for ( ilist_item *iter = _at_front; // начнем с первого
iter != _at_end; // пока не последний
++iter ) // возьмем следующий
cout << iter->value() << ' ';
// теперь напечатаем последний
cout << iter->value();
Список – это не массив, его элементы не занимают непрерывную область памяти. Инкремент итератора
++iter;
вовсе не сдвигает его на следующий элемент списка. Вместо этого он указывает на место в памяти, непосредственно следующее за данным элементом, а там может быть все что угодно. Для изменения значения итератора нужно воспользоваться членом _next объекта ilist_item:
iter = iter->_next;
Мы инкапсулировали доступ к членам ilist_item набором встраиваемых функций. Определение класса ilist_item теперь выглядит так:
class ilist_item {
public:
ilist_item( int value, ilist_item *item_to_link_to = 0 );
int value() { return _value; }
iilst_item* next() { return _next; }
void next( ilist_item *link ) { _next = link; }
void value( int new_value ) { _value = new_value; }
private:
int _value;
ilist_item *_next;
};
Вот определение функции display(), использующее последнюю реализацию класса ilist_item:
#include <iostream>
class ilist {
public:
void display( ostream &os = cout );
// ...
};
void ilist::
display( ostream &os )
{
os << "\n( " << _size << " )( ";
ilist_item *ptr = _at_front;
while ( ptr ) {
os << ptr->value() << " ";
ptr = ptr->next();
}
os << ")\n";
}
Тестовую программу для нашего класса ilist в его текущей реализации можно представить таким образом:
#include <iostream> #include "ilist.h" int main()
{
ilist mylist; for ( int ix = 0; ix < 10; ++ix ) {
mylist.insert_front( ix );
mylist.insert_end( ix );
}
cout <<
"Ok: после insert_front() и insert_end()\n";
mylist.display(); ilist_item *it = mylist.find( 8 );
cout << "\n"
<< "Ищем значение 8: нашли?"
<< ( it ? " да!\n" : " нет!\n" ); mylist.insert( it, 1024 );
cout << "\n" <<
"Вставка элемента 1024 после 8\n"; mylist.display();
int elem_cnt = mylist.remove( 8 );
cout << "\n"
<< "Удалено " << elem_cnt
<< " элемент(ов) со значением 8\n"; mylist.display();
cout << "\n" << "Удален первый элемент\n"; mylist.remove_front(); mylist.display(); cout << "\n" << "Удалены все элементы\n";
mylist.remove_all(); mylist.display();
}
Результат работы программы:
Ok: после insert_front() и insert_end() (20)( 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 ) Ищем значение 8: нашли? да! Вставка элемента 1024 после 8 ( 21 )( 9 8 1024 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 ) Удалено 2 элемент(ов) со значением 8 ( 19 )( 9 1024 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 9 ) Удален первый элемент ( 18 )( 1024 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 9 ) Удалены все элементы ( 0 )( )
Помимо вставки элементов, необходима возможность их удаления. Мы реализуем три таких операции:
void remove_front(); void remove_all (); int remove( int value );
Вот как выглядит реализация remove_front():
inline void
i1ist::
remove_front()
{
if ( _at_front ) {
ilist_item *ptr = _at_front;
_at_front = _at_front->next();
bump_down_size() ;
delete ptr;
}
}
remove_all() вызывает remove_front() до тех пор, пока все элементы не будут
удалены:
void ilist::
remove_all()
{
while ( _at_front )
remove_front();
_size = 0;
_at_front = _at_end = 0;
}
Общая функция remove() также использует remove_front() для обработки специального случая, когда удаляемый элемент (элементы) находится в начале списка. Для удаления из середины списка используется итерация. У элемента, предшествующего удаляемому, необходимо модифицировать указатель _next. Вот реализация функции:
int ilist::
remove( int value )
{
ilist_item *plist = _at_front;
int elem_cnt = 0;
while ( plist && plist->value() == value )
{
plist = plist->next();
remove_front();
++elem_cnt;
}
if ( ! plist )
return elem_cnt;
ilist_item *prev = plist;
plist = plist->next();
while ( plist ) {
if ( plist->value() == value ) {
prev->next( plist->next() );
delete plist;
++elem_cnt;
bump_down_size();
plist = prev->next();
if ( ! plist ) {
_at_end = prev;
return elem_cnt;
}
}
else {
prev = plist;
plist = plist->next();
}
return elem_cnt;
}
Следующая программа проверяет работу операций в четырех случаях: когда удаляемые элементы расположены в конце списка, удаляются все элементы, таких элементов нет или они находятся и в начале, и в конце списка.
#include <iostream>
#include "ilist.h"
int main()
{
ilist mylist;
cout << "\n-----------------------------------------------\n"
<< "тест #1: - элементы в конце\n"
<< "-----------------------------------------------\n";
mylist.insert_front( 1 ); mylist.insert_front( 1 );
mylist.insert_front( 1 );
my1ist.insert_front( 2 ); mylist.insert_front( 3 );
my1ist.insert_front( 4 );
mylist.display();
int elem_cnt = mylist.remove( 1 );
cout << "\n" << "Удалено " << elem_cnt
<< " элемент(ов) со значением 1\n";
mylist.display();
mylist.remove_all();
cout << "\n-----------------------------------------------\n"
<< "тест #2: - элементы в начале\n"
<< "-----------------------------------------------\n";
mylist.insert_front( 1 ); mylist.insert_front( 1 );
mylist.insert_front( 1 );
mylist.display();
elem_cnt = mylist.remove( 1 );
cout << "\n" << "Удалено " << elem_cnt
<< " элемент(ов) со значением 1\n";
mylist.display();
mylist.remove_all () ;
cout << "\n-----------------------------------------------\n"
<< "тест #3: - элементов нет в списке\n"
<< "-----------------------------------------------\n";
mylist.insert_front( 0 ); mylist.insert_front( 2 );
mylist.insert_front( 4 );
mylist.display();
elem_cnt = mylist.remove( 1 );
cout << "\n" << "Удалено " << elem_cnt
<< " элемент(ов) со значением 1\n";
mylist.display();
mylist.remove_all () ;
cout << "\n-----------------------------------------------\n"
<< "тест #4: - элементы в конце и в начале\n"
<< "-----------------------------------------------\n";
my1ist.insert_front( 1 ); mylist.insert_front( 1 );
my1ist.insert_front( 1 );
my1ist.insert_front( 0 ); mylist.insert_front( 2 );
my1ist.insert_front( 4 );
mylist.insert_front( 1 ); my1ist.insert_front( 1 );
mylist.insert_front( 1 );
mylist.display() ;
elem_cnt = mylist.remove( 1 );
cout << "\n" << "Удалено " << elem_cnt
<< " элемент(ов) со значением 1\n";
mylist.display();
}
Результат работы программы:
----------------------------------------------- тест #1: - элементы в конце ----------------------------------------------- ( 6 )( 4 3 2 1 1 1 ) Удалено 3 элемент(ов) со значением 1 ( 3 )( 4 3 2 ) ----------------------------------------------- тест #2: - элементы в начале ----------------------------------------------- ( 3 )( 1 1 1 ) Удалено 3 элемент(ов) со значением 1 ( 0 )( ) -----------------------------------------------
тест #3: - элементов нет в списке ----------------------------------------------- ( 3 )( 4 2 0 ) Удалено 0 элемент(ов) со значением 1 ( 3 )( 4 2 0 ) ----------------------------------------------- тест #4: - элементы в конце и в начале ----------------------------------------------- (9 )( 1 1 1 4 2 0 1 1 1 ) Удалено 6 элемент(ов) со значением 1 ( 3 )( 4 2 0 )
Последние две операции, которые мы хотим реализовать, – конкатенация двух списков (добавление одного списка в конец другого) и инверсия (изменение порядка элементов на противоположный). Первый вариант concat() содержит ошибку. Сможете ли вы ее найти?
void ilist::concat( const ilist &i1 ) {
if ( ! _at_end )
_at_front = i1._at_front;
else _at_end->next( i1._at_front );
_at_end = i1._at_end;
}
Проблема состоит в том, что теперь два объекта ilist содержат последовательность
одних и тех же элементов. Изменение одного из списков, например вызов операций
insert() и remove(), отражается на другом, приводя его в рассогласованное состояние.
Простейший способ обойти эту проблему – скопировать каждый элемент второго списка.
Сделаем это при помощи функции insert_end():
void ilist::
concat( const ilist &i1 )
{
i1ist_item *ptr = i1._at_front;
while ( ptr ) {
insert_end( ptr->value() );
ptr = ptr->next();
}
}
Вот реализация функции reverse():
void
ilist::
reverse()
{
ilist_item *ptr = _at_front;
ilist_item *prev = 0;
_at_front = _at_end;
_at_end = ptr;
while ( ptr != _at_front )
{
ilist_item *tmp = ptr->next();
ptr->next( prev );
prev = ptr;
ptr = tmp;
}
_at_front->next( prev );
}
Тестовая программа для проверки этих операций выглядит так:
#include <iostream>
#include "ilist.h"
int main()
{
ilist mylist;
for ( int ix = 0; ix < 10; ++ix )
{ mylist.insert_front( ix ); }
mylist.display();
cout << "\n" << "инвертирование списка\n";
mylist.reverse(); mylist.display();
ilist mylist_too;
mylist_too.insert_end(0); mylist_too.insert_end(1);
mylist_too.insert_end(1); mylist_too.insert_end(2);
mylist_too.insert_end(3); mylist_too.insert_end(5);
cout << "\n" << "mylist_too:\n";
mylist_too.display();
mylist.concat( mylist_too );
cout << "\n"
<< "mylist после concat с mylist_too:\n";
mylist.disp1ay();
}
Результат работы программы:
( 10 ) ( 9 8 7 6 5 4 3 2 1 0 ) инвертирование списка ( 10 ) ( 0 1 2 3 4 5 6 7 8 9 ) mylist_too: ( 6 )( 0 1 1 2 3 5 ) mylist после concat с mylist_too: ( 16 ) ( 0 1 2 3 4 5 6 7 8 9 0 1 1 2 3 5 )
С одной стороны, задачу можно считать выполненной: мы не только реализовали
все запланированные функции, но и проверили их работоспособность. С другой стороны,
мы не обеспечили всех операций, которые необходимы для практического использования
списка.
Одним из главных недостатков является то, что у пользователя нет способа перебирать
элементы списка и он не может обойти это ограничение, поскольку реализация от
него скрыта. Другим недостатком является отсутствие поддержки операций инициализации
одного списка другим и присваивания одного списка другому. Мы сознательно не
стали их реализовывать в первой версии, но теперь начнем улучшать наш класс.
Для реализации первой операции инициализации необходимо определить копирующий
конструктор. Поведение такого конструктора, построенного компилятором по умолчанию,
совершенно неправильно для нашего класса (как, собственно, и для любого класса,
содержащего указатель в качестве члена), именно поэтому мы с самого начала запретили
его использование. Лучше уж полностью лишить пользователя какой-либо операции,
чем допустить возможные ошибки. (В разделе 14.5 объясняется,
почему действия копирующего конструктора по умолчанию в подобных случаях неверны.)
Вот реализация конструктора, использующая функцию insert_end():
ilist::ilist( const ilist &rhs )
{
ilist_item *pt = rhs._at_front;
while ( pt ) {
insert_end( pt->value() );
pt = pt->next();
}
}
Оператор присваивания должен сначала вызвать remove_all(), а затем с помощью
insert_end() вставить все элементы второго списка. Поскольку эта операция повторяется
в обеих функциях, вынесем ее в отдельную функцию insert_all():
void ilist::insert_all ( const ilist &rhs )
{
ilist_item *pt = rhs._at_front;
while ( pt ) {
insert_end( pt->value() );
pt = pt->next();
}
}
после чего копирующий конструктор и оператор присваивания можно реализовать
так:
inline ilist::ilist( const ilist &rhs )
: _at_front( 0 ), _at_end( 0 )
{ insert_all ( rhs ); }
inline ilist&
ilist::operator=( const ilist &rhs ) {
remove_all();
insert_all( rhs );
return *this;
}
Теперь осталось обеспечить пользователя возможностью путешествовать по списку, например с помощью доступа к члену _at_front:
ilist_item *ilist::front() { return _at_front(); }
После этого можно применить ilist_item::next(), как мы делали в функциях-членах:
ilist_item *pt = mylist.front();
while ( pt ) {
do_something( pt->value() );
pt = pt->next();
}
Хотя это решает проблему, лучше поступить иначе: реализовать общую концепцию
прохода по элементам контейнера. В данном разделе мы расскажем об использовании
цикла такого вида:
for ( ilist_item *iter = mylist.init_iter();
iter;
iter = mylist.next_iter() )
do_something( iter->value() );
(В разделе 2.8 мы уже касались понятия итератора. В
главах 6 и 12 будут рассмотрены
итераторы для имеющихся в стандартной библиотеке контейнерных типов и обобщенных
алгоритмов.)
Наш итератор представляет собой несколько больше, чем просто указатель. Он должен
уметь запоминать текущий элемент, возвращать следующий и определять, когда все
элементы кончились. По умолчанию итератор инициализируется значением _at_front,
однако пользователь может задать в качестве начального любой элемент списка.
next_iter() возвращает следующий элемент или 0, если элементов больше нет. Для
реализации пришлось ввести дополнительный член класса:
class ilist {
public:
// ...
init_iter( ilist_item *it = 0 );
private:
//...
ilist_item *_current;
};
init_iter() выглядит так:
inline ilist_item*
ilist::init_iter( i1ist_item *it )
{
return _current = it ? it : _at_front;
}
next_iter() перемещает указатель _current на следующий элемент и возвращает
его адрес, если элементы не кончились. В противном случае он возвращает 0 и
устанавливает _current в 0. Его реализацию можно представить следующим образом:
inline ilist_item*
ilist::
next_iter()
{
ilist_item *next = _current
? _current = _current->next()
: _current;
return next;
}
Если элемент, на который указывает _current, удален, могут возникнуть проблемы. Их преодолевают модификацией кода функций remove() и remove_front(): они должны проверять значение _current. Если он указывает на удаляемый элемент, функции изменят его так, чтобы он адресовал следующий элемент либо был равен 0, когда удаляемый элемент – последний в списке или список стал пустым. Модифицированная remove_front() выглядит так:
inline void
ilist::remove_front()
{
if ( _at_front ) {
ilist_item *ptr = _at_front;
_at_front = _at_front->next();
// _current не должен указывать на удаленный элемент
if ( _current == ptr )
_current = _at_front;
bump_down_size();
delete ptr;
}
}
Вот модифицированный фрагмент кода remove():
while ( plist ) {
if ( plist->value() == value )
{
prev->next( plist->next() );
if ( _current == plist )
_current = prev->next();
Что произойдет, если элемент будет вставлен перед тем, на который указывает
_current? Значение _current не изменяется. Пользователь должен начать проход
по списку с помощью вызова init_iter(), чтобы новый элемент попал в число перебираемых.
При инициализации списка другим и при присваивании значение _current не копируется,
а сбрасывается в 0.
Тестовая программа для проверки работы копирующего конструктора и оператора
присваивания выглядит так::
#include <iostream>
#include "ilist.h"
int main()
{
ilist mylist;
for ( int ix = 0; ix < 10; ++ix ) {
mylist.insert_front( ix );
mylist.insert_end( ix );
}
cout << "\n" << "Применение init_iter() и next_iter()"
<< "для обхода всех элементов списка:\n";
ilist_item *iter;
for ( iter = mylist.init_iter();
iter; iter = mylist.next_iter() )
cout << iter->value() << " ";
cout << "\n" << "Применение копирующего конструктора\n";
ilist mylist2( mylist );
mylist.remove_all();
for ( iter = mylist2.init_iter();
iter; iter = mylist2.next_iter() )
cout << iter->value() << " ";
cout << "\n" << "Применение копирующего оператора присваивания\n";
mylist = mylist2;
for ( iter = mylist.init_iter();
iter; iter = mylist.next_iter() )
cout << iter->value() << " ";
cout << "\n";
}
Результат работы программы:
Применение init_iter() и next_iter() для обхода всех элементов списка: 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 Применение копирующего конструктора 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 Применение копирующего оператора присваивания 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
5.11.1. Обобщенный список
Наш класс ilist имеет серьезный недостаток: он может хранить элементы только
целого типа. Если бы он мог содержать элементы любого типа – как встроенного,
так и определенного пользователем, – то его область применения была бы гораздо
шире. Модифицировать ilist для поддержки произвольных типов данных позволяет
механизм шаблонов (см. главу 16).
При использовании шаблона вместо параметра подставляется реальный тип данных.
Например:
list< string > slist;
создает экземпляр списка, способного содержать объекты типа string, а
list< int > ilist;
создает список, в точности повторяющий наш ilist. С помощью шаблона класса
можно обеспечить поддержку произвольных типов данных одним экземпляром кода.
Рассмотрим последовательность действий, уделив особое внимание классу list_item.
Определение шаблона класса начинается ключевым словом template, затем следует
список параметров в угловых скобках. Параметр представляет собой идентификатор,
перед которым стоит ключевое слово class или typename. Например:
template <class elemType> class list_item;
Эта инструкция объявляет list_item шаблоном класса с единственным параметром-типом. Следующее объявление эквивалентно предыдущему:
template <typename elemType> class list_item;
Ключевые слова class и typename имеют одинаковое значение, можно использовать
любое из них. Более удобное для запоминания typename появилось в стандарте С++
сравнительно недавно и поддерживается еще не всеми компиляторами. Поскольку
наши тексты были написаны до появления этого ключевого слова, в них употребляется
class. Шаблон класса list_item выглядит так:
template <class elemType>
class list_item {
public:
list_item( elemType value, list_item *item = 0 )
: _value( value ) {
if ( !item )
_next = 0;
else {
_next = item->_next;
item->_next = this;
}
}
elemType value() { return _value; }
list_item* next() { return _next; }
void next( list_item *link ) { _next = link; }
void value( elemType new_value ) { _value = new_value; }
private:
elemType _value;
list_item *_next;
};
Все упоминания типа int в определении класса ilist_item заменены на параметр
elemType. Когда мы пишем:
list_item<doub1e> *ptr = new list_item<doub1e>( 3.14 );
компилятор подставляет double вместо elemType и создает экземпляр list_item,
поддерживающий данный тип.
Аналогичным образом модифицируем класс ilist в шаблон класса list:
template <class elemType>
class list {
public:
list()
: _at_front( 0 ), _at_end( 0 ), _current( 0 ),
_size( 0 ) {}
1ist( const list& );
list& operator=( const list& );
~list() { remove_all(); }
void insert ( list_item<elemType> *ptr, elemType value );
void insert_end( elemType value );
void insert_front( elemType value );
void insert_all( const list &rhs );
int remove( elemType value );
void remove_front();
void remove_all();
list_item<elemType> *find( elemType value );
list_item<elemType> *next_iter();
list_item<elemType>* init_iter( list_item<elemType> *it );
void disp1ay( ostream &os = cout );
void concat( const list& );
void reverse ();
int size() { return _size; }
private:
void bump_up_size() { ++_size; }
void bump_down_size() { --_size; }
list_item<elemType> *_at_front;
1ist_item<elemType> *_at_end;
list_item<elemType> *_current;
int _size;
};
Объекты шаблона класса list используются точно так же, как и объекты класса
ilist. Основное преимущество шаблона в том, что он обеспечивает поддержку произвольных
типов данных с помощью единственного определения.
(Шаблоны являются важной составной частью концепции программирования на С++.
В главе 6 мы рассмотрим набор классов контейнерных типов,
предоставляемых стандартной библиотекой С++. Неудивительно, что она содержит
шаблон класса, реализующего операции со списками, равно как и шаблон класса,
поддерживающего векторы; мы рассматривали их в главах 2
и 3.)
Наличие класса списка в стандартной библиотеке представляет некоторую проблему.
Мы выбрали для нашей реализации название list, но, к сожалению, стандартный
класс также носит это название. Теперь мы не можем использовать в программе
одновременно оба класса. Конечно, проблему решит переименование нашего шаблона,
однако во многих случаях эта возможность отсутствует.
Более общее решение состоит в использовании механизма пространства имен, который
позволяет разработчику библиотеки заключить все свои имена в некоторое поименованное
пространство и таким образом избежать конфликта с именами из глобального пространства.
Применяя нотацию квалифицированного доступа, мы можем употреблять эти имена
в программах. Стандартная библиотека С++ помещает свои имена в пространство
std. Мы тоже поместим наш код в собственное пространство:
namespace Primer_Third_Edition
{
template <typename elemType>
class list_item{ ... };
template <typename elemType>
class list{ ... };
// ...
}
Для использования такого класса в пользовательской программе необходимо написать
следующее:
// наш заголовочный файл
#include "list.h"
// сделаем наши определения видимыми в программе
using namespace Primer_Third_Edition;
// теперь можно использовать наш класс list
list< int > ilist;
// ...
(Пространства имен описываются в разделах 8.5 и 8.6.)
Упражнение 5.16
Мы не определили деструктор для ilist_item, хотя класс содержит указатель на
динамическую область памяти. Причина заключается в том, что класс не выделяет
память для объекта, адресуемого указателем _next, и, следовательно, не несет
ответственности за ее освобождение. Начинающий программист мог бы допустить
ошибку, вызвав деструктор для ilist_item:
ilist_item::~ilist_item()
{
delete _next;
}
Посмотрите на функции remove_all() и remove_front() и объясните, почему наличие
такого деструктора является ошибочным.
Упражнение 5.17
Наш класс ilist не поддерживает следующие операции:
void ilist::remove_end();
void ilist::remove( ilist_item* );
Как вы думаете, почему мы их не включили? Реализуйте их.
Упражнение 5.18
Модифицируйте функцию find() так, чтобы вторым параметром она принимала адрес
элемента, с которого нужно начинать поиск. Если этот параметр не задан, поиск
начинается с первого элемента. (Поскольку мы добавляем второй параметр, имеющий
значение по умолчанию, открытый интерфейс данной функции не меняется. Программы,
использующие предыдущую версию find(), будут работать без модификации.)
class ilist {
public:
// ...
ilist_item* find( int value, ilist_item *start_at = 0 );
// ...
};
Упражнение 5.19
Используя новую версию find(), напишите функцию count(), которая подсчитывает количество вхождений элементов с заданным значением. Подготовьте тестовую программу.
Упражнение 5.20
Модифицируйте insert(int value) так, чтобы она возвращала указатель на вставленный объект ilist_item.
Упражнение 5.21
Используя модифицированную версию insert(), напишите функцию:
void ilist::
insert( ilist_item *begin,
int *array_of_value,
int elem_cnt );
где array_of_value указывает на массив значений, который нужно вставить в ilist,
elem_cnt – на размер этого массива, а begin – на элемент, после которого производится
вставка. Например, если есть ilist:
(3)( 0 1 21 )
и массив:
int ia[] = { 1, 2, 3, 5, 8, 13 };
вызов этой новой функции
ilist_item *it = mylist.find( 1 );
mylist.insert( it, ia, 6 );
изменит список таким образом:
(9) ( 0 1 1 2 3 5 8 13 21 )
Упражнение 5.22
Функции concat() и reverse() модифицируют оригинальный список. Это не всегда
желательно. Напишите аналогичную пару функций, которые создают новый объект
ilist:
ilist ilist::reverse_copy();
ilist ilist::concat_copy( const ilist &rhs );