C++ для начинающих

#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 );

6. Абстрактные контейнерные типы

В этой главе мы продолжим рассмотрение типов данных, начатое в главе 3, представим дополнительную информацию о классах vector и string и познакомимся с другими контейнерными типами, входящими в состав стандартной библиотеки С++. Мы также расскажем об операторах и выражениях, упомянутых в главе 4, сосредоточив внимание на тех операциях, которые поддерживаются объектами контейнерных типов.

Последовательный контейнер содержит упорядоченный набор элементов одного типа. Можно выделить два основных типа контейнеров – вектор (vector) и список (list). (Третий последовательный контейнер – двусторонняя очередь (deque) – обеспечивает ту же функциональность, что и vector, но особенно эффективно реализует операции вставки и удаления первого элемента. deque следует применять, например, при реализации очереди, из которой извлекается только первый элемент. Все сказанное ниже относительно вектора применимо также и к deque.)

Ассоциативный контейнер эффективно реализует операции проверки существования и извлечения элемента. Два основных ассоциативных контейнера – это отображение (map) и множество (set). map состоит из пар ключ/значение, причем ключ используется для поиска элемента, а значение содержит хранимую информацию. Телефонный справочник хорошо иллюстрирует понятие отображения: ключом является фамилия и имя абонента, а значением – его телефонный номер.