Программирование. Принципы и практика использования C++ Исправленное издание

Страуструп Бьерн

Мы будем приближаться к стандартному библиотечному классу vector через ряд постепенно усложняющихся вариантов реализации. Сначала мы создадим очень простой класс vector. Затем выявим его недостатки и исправим их. Сделав это несколько раз, мы придем к реализации класса vector, который почти эквивалентен стандартному библиотечному классу vector, поставляемому вместе с компиляторами языка C++. Этот процесс постепенного уточнения точно отражает обычный подход к решению программистской задачи. Попутно мы выявим и исследуем многие классические задачи, связанные с использованием памяти и структур данных. Наш основной план приведен ниже.

• Глава 17. Как работать с разными

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

• Глава 18. Как скопировать вектор? Как реализовать оператор доступа к элементам по индексу? Кроме того, мы введем в рассмотрение массивы и исследуем их связь с указателями.

• Глава 19. Как создать векторы с разными типами хранящихся в них элементов? Как обрабатывать ошибку выхода за пределы допустимого диапазона? Для ответа на этот вопрос мы изучим шаблоны языка С++ и исключения.

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

Итак, все упирается в прямой доступ к памяти. Зачем нам это нужно? Наши классы

vector

и

string

чрезвычайно полезны и удобны; их можно просто использовать. В конце концов, контейнеры, такие как

vector

и

string

, разработаны именно для того, чтобы освободить нас от неприятных аспектов работы с реальной памятью. Однако, если мы не верим в волшебство, то должны освоить самый низкий уровень управления памятью. А почему бы нам не поверить в волшебство, т.е. почему бы не поверить, что разработчики класса vector знали, что делают? В конце концов, мы же не разбираем физические устройства, обеспечивающие работу памяти компьютера.

Дело в том, что все мы — программисты (специалисты по компьютерным наукам, разработчики программного обеспечения и т.д.), а не физики. Если бы мы изучали физику, то были бы обязаны разбираться в деталях устройства и функционирования памяти компьютера. Но поскольку мы изучаем программирование, то должны вникать в детали устройства программ. С теоретической точки зрения мы могли бы рассматривать низкоуровневый доступ к памяти и средства управления деталями реализации так же, как и физические устройства. Однако в этом случае мы не только вынуждены были бы верить в волшебство, но и не смогли бы разрабатывать новые контейнеры (которые нужны только нам и которых нет в стандартной библиотеке). Кроме того, мы не смогли бы разобраться в огромном количестве программного кода, написанного на языках С и С++, для непосредственного использования памяти. Как будет показано в следующих главах, указатели (низкоуровневый и прямой способ ссылки на объекты) полезны не только для управления памятью. Невозможно овладеть языком С++, не зная, как работают указатели.

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

17.2. Основы

Начнем нашу поступательную разработку класса

vector

с очень простого примера.

vector<double> age(4); // вектор с четырьмя элементами типа double

age[0]=0.33;

age[1]=22.0;

age[2]=27.2;

age[3]=54.2;

Очевидно,

что этот код создает объект класса

vector

с четырьмя элементами типа

double

и присваивает им значения

0.33

,

22.0

,

27.2

и

54.2

. Эти четыре элемента имеют номера 0, 1, 2 и 3. Нумерация элементов в стандартных контейнерах языка С++ всегда начинается с нуля. Нумерация с нуля используется часто и является универсальным соглашением, которого придерживаются все программисты, пишущие программы на языке С++. Количество элементов в объекте класса

vector

называется его размером. Итак, размер вектора

age

равен четырем. Элементы вектора нумеруются (индексируются) от

0

до

size-1

. Например, элементы вектора

age

нумеруются от

0

до

age.size–1

. Вектор age можно изобразить следующим образом:

Как реализовать эту схему в компьютерной памяти? Как хранить значения и обеспечивать к ним доступ? Очевидно, что мы должны определить класс и назвать его

vector

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

vector

, но в данном контексте это было бы мошенничеством: мы же как раз этот класс и разрабатываем.

Итак, как представить стрелку, изображенную на рисунке? Представим себе, что ее нет. Мы можем определить структуру данных фиксированного размера.

class vector {

int size,age0,age1,age2,age3;

// ...

};

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

Это просто и красиво, но как только мы попробуем добавить элемент с помощью функции

push_back

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

vector

, такие как

push_back

, невозможно реализовать, если в классе

vector

количество элементов фиксировано. По существу, нам нужен член класса, ссылающийся на множество элементов так, чтобы при расширении памяти он мог ссылаться на другое множество элементов. Нам нужен адрес первого элемента. В языке C++ тип данных, способный хранить адрес, называют указателем (pointer). Синтаксически он выделяется суффиксом

*

, так что

double*

означает указатель на объект типа

double

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

vector

.

// очень упрощенный вектор элементов типа double (вроде vector<double>)

class vector {

int sz; // размер

double* elem; // указатель на первый элемент (типа double)

public:

vector(int s); // конструктор: размещает в памяти s чисел

// типа double,

// устанавливает на них указатель elem,

// хранит число s в члене sz