Мюррей Хилл - C++ Страница 8

1.11 Вектора

Встроенное в С++ понятие вектора было разработано так, чтобы обеспечить максимальную эффективность выполнения при минимальном расходе памяти. Оно также (особенно когда используется совместно с указателями) является весьма универсальным инструментом для построения средств более высокого уровня. Вы могли бы, конечно, возразить, что размер вектора должен задаваться как константа, что нет проверки выхода за границы вектора и т.д. Ответ на подобные возражения таков: «Вы можете запрограммировать это сами.» Давайте посмотрим, действительно ли оправдан такой ответ. Другими словами, проверим средства абстракции языка С++, попытавшись реализовать эти возможности для векторных типов, которые мы создадим сами, и посмотрим, какие с этим связаны трудности, каких это требует затрат, и насколько получившиеся векторные типы удобны в обращении. class vector (* int* v; int sz; public: vector(int); // конструктор ~vector(); // деструктор int size() (* return sz; *) void set_size(int); int amp; operator[](int); int amp; elem(int i) (* return v[i]; *) *); Функция size возвращает число элементов вектора, таким образом индексы должны лежать в диапазоне 0 ... size()-1. Функция set_size сделана для изменения этого размера, elem обеспечивает доступ к элементам без проверки индекса, а operator[] дает доступ с проверкой границ.

Идея состоит в том, чтобы класс сам был структурой фиксированного размера, управляющей доступом к фактической памяти вектора, которая выделяется конструктором вектора с помощью распределителя свободной памяти new:

vector::vector(int s) (* if (s«=0) error(„bad vector size“); // плохой размер вектора sz = s; v = new int[s]; *)

Теперь вы можете описывать вектора типа vector почти столь же элегантно, как и вектора, встроенные в сам язык:

vector v1(100); vector v2(nelem*2-4);

Операцию доступа можно определить как

int amp; vector::operator[](int i) (* if(i«0 !! sz„=i) error(«vector index out of range“); // индекс выходит за границы вектора return v[i]; *)

Операция !! (ИЛИИЛИ) – это логическая операция ИЛИ. Ее правый операнд вычисляется только тогда, когда это необходимо, то есть если вычисление левого операнда дало ноль. Возращение ссылки обеспечивает то, что запись [] может использоваться с любой стороны операции присваивания:

v1[x] = v2[y];

Функция со странным именем ~vector – это деструктор, то есть функция, описанная для того, чтобы она неявно вызывалась, когда объект класса выходит из области видимости. Деструктор класса C имеет имя ~C. Если его определить как

vector::~vector() (* delete v; *)

то он будет, с помощью операции delete, освобождать пространство, выделенное конструктором, поэтому когда vector выходит из области видимости, все его пространство возвращается обратно в память для дальнейшего использования.

1.12 Inline-подстановка

Если часто повторяется обращение к очень маленькой функции, то вы можете начать беспокоиться о стоимости вызова функции. Обращение к функции члену не дороже обращения к функции не члену с тем же числом параметров (надо помнить, что функция член всегда имеет хотя бы один параметр), и вызовы в функций в С++ примерно столь же эффективны, сколь и в любом языке. Однако для слишком маленьких функций может встать вопрос о накладных расходах на обращение. В этом случае можно рассмотреть возможность спецификации функции как inline-подставляемой. Если вы поступите таким образом, то компилятор сгенерирует для функции соответствующий код в мете ее вызова. Семантика вызова не изменяется. Если, например, size и elem inline-подставляемые, то

vector s(100); //... i = s.size(); x = elem(i-1);

порождает код, эквивалентный

//... i = 100; x = s.v[i-1];

С++ компилятор обычно достаточно разумен, чтобы генерировать настолько хороший код, насколько вы можете получить в результате прямого макрорасширения. Разумеется, компилятор иногда вынужден использовать временные переменные и другие уловки, чтобы сохранить семантику.

Вы можете указать, что вы хотите, чтобы функция была inline-подставляемой, поставив ключевое слово inline, или, для функции члена, просто включив определение функции в описание класса, как это сделано в предыдущем примере для size() и elem().

При хорошем использовании inline-функции резко повышают скорость выполнения и уменьшают размер объектного кода. Однако, inline функции запутывают описания и могут замедлить компиляцию, поэтому, если они не необходимы, то их желательно избегать. Чтобы inline функция давала существенный выигрыш по сравнению с обычной функцией, она должна быть очень маленькой.

1.13 Производные классы

Теперь давайте определим вектор, для которого пользователь может задавать границы изменения индекса.

class vec: public vector (* int low, high; public: vec(int,int);

int amp; elem(int); int amp; operator[](int); *);

Определение vec как :public vector

означает, в первую очередь, что vec – это vector. То есть, тип vec имеет (наследует) все свойства типа vector дополнительно к тем, что описаны специально для него. Говорят, что vector является базовым классом для vec, а о vec говорится, что он производный класс от vector. Класс vec модифицирует класс vector тем, что в нем задается другой конструктор, который требует от пользователя указывать две границы изменения индекса, а не длину, и имеются свои собственные функции доступа elem(int) и operator[](int). Функция elem() класса vec легко выражается через elem() класса vector: int amp; vec::elem(int i) (* return vector::elem(i-low); *)

Операция разрешения области видимости :: используется для того, чтобы не было бесконечной рекурсии обращения к vec::elem() из нее самой. с помощью унарной операции :: можно ссылаться на нелокальные имена. Было бы разумно описать vec:: elem() как inline, поскольку, скорее всего, эффективность существенна, но необязательно, неразумно и невозможно написать ее так, чтобы она непосредственно использовала закрытый член v класса vector. Функции производного класса не имеют специального доступа к закрытым членам его базового класса.

Конструктор можно написать так:

vec::vec(int lb, int hb) : (hb-lb+1) (* if (hb-lb«0) hb = lb; low = lb; high = hb; *)

Запись: (hb-lb+1) используется для определения списка параметров конструктора базового класса vector::vector(). Этот конструктор вызывается перед телом vec::vec(). Вот небольшой пример, который можно запустить, если скомпилировать его вместе с остальными описаниями vector:

#include «streams.h»

void error(char* p) (* cerr «„ p «« «\n“; // cerr – выходной поток сообщений об ошибках exit(1); *)

void vector::set_size(int) (* /* пустышка */ *)

int amp; vec::operator[](int i) (* if (i«low !! high„i) error(«vec index out of range“); // индекс vec за границами return elem(i); *)

main() (* vector a(10); for (int i=0; i«a.size(); i++) (* a[i] = i; cout „„ a[i] «« " "; *) cout «« «\n“; vec b(10,19); for (i=0; i«b.size(); i++) b[i+10] = a[i]; for (i=0; i«b.size(); i++) cout «« b[i+10] «« " "; cout «« «\n“; *)

Он выдает 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

Это направление развития векторного типа можно разрабатывать дальше. Довольно просто сделать многомерные массивы, массивы, в которых число размерностей задается как параметр конструктора, массивы в стиле Фортрана, к которым можно одновременно обращаться и как к имеющим две размерности, и как к имеющим три, и т.д.

Так класс управляет доступом к некоторым данным. Поскольку весь доступ осуществляется через интерфейс, обеспеченный открытой частью класса, то можно использовать представление данных в соответствие с нуждами разработчика. Например, тривиально можно было бы поменять представление вектора на связанный список. Другая сторона этого состоит в том, что при заданной реализации можно обеспечить любой удобный интерфейс.

1.14 Еще об операциях

Другое направление развития – снабдить вектора операциями:

class Vec : public vector (* public: Vec(int s) : (s) (**) Vec(Vec amp;); ~Vec() (**) void operator=(Vec amp;); void operator*=(Vec amp;); void operator*=(int); //... *);

Обратите внимание на способ определения конструктора производного класса, Vec::Vec(), когда он передает свой параметр конструктору базового класса vector::vector() и больше не делает ничего. Это полезная парадигма. Операция присваивания перегружена, ее можно определить так:

void Vec::operator=(Vec amp; a) (* int s = size(); if (s!=a.size()) error(«bad vector size for =»); // плохой размер вектора для = for (int i = 0; i«s; i++) elem(i) = a.elem(i); *)

Присваивание объектов класса Vec теперь действительно копирует элементы, в то время как присваивание объектов

vector просто копирует структуру, управляющую доступом к элментам. Последнее, однако, происходит и тогда, когда vector копируется без явного использования операции присваивания: (1) когда vector передается как параметр и (3) когда vector передается как значение, возвращаемое функцией. Чтобы обрабатывать эти случаи для векторов Vec, вы определяете конструктор Vec(Vec amp;): Vec::Vec(Vec amp; a) : (a.size()) (* int sz = a.size(); for (int i = 0; i«sz; i++) elem(i) = a.elem(i); *) Этот конструктор инициализирует Vec как копию другого Vec, и будет вызываться в отмеченных выше случаях. Выражение в левой части таких операций, как = и +=, безусловно определено, поэтому кажется вполне естественным реализовать их как операции над объектом, который обозначается (денотируется) этим выражением. В частности, тогда они смогут изменять значение своего первого операнда. Левый операнд таких операций, как + и – не требует особого внимания. Вы могли бы, например, передавать оба аргумента по значению и все рано получить правильную реализацию векторного сложения. Однако вектора могут оказаться большими, поэтому чтобы избежать ненужного копирования операнды операции + передаются в operator +() по ссылке: