и того же типа. Мы можем обращаться к элементу вектора по индексу, расширять вектор с помощью функции push_back(), запрашивать у вектора количество его элементов, используя функцию size(), а также предотвращать выход за пределы допустимого диапазона. Стандартный вектор — удобный, гибкий, эффективный (по времени и объему памяти) и безопасный контейнер с точки зрения статических типов. Стандартный класс string обладает как этими, так и другими полезными свойствами стандартных контейнерных типов, таких как list и map, которые будут описаны в главе 20.
Однако память компьютера не обеспечивает непосредственной поддержки таких полезных типов. Аппаратное обеспечение способно непосредственно поддерживать только последовательности битов. Например, в классе vector<double> операция v.push_back(2.3) добавляет число 2.3 в последовательность чисел типа double и увеличивает на единицу счетчик элементов вектора v (с помощью функции v.size()). На самом нижнем уровне компьютер ничего не знает о таких сложных функциях, как push_back(); все, что он знает, — как прочитать и записать несколько байтов за раз.
В этой и следующих двух главах мы покажем, как построить класс vector, используя основные языковые возможности, доступные любому программисту. Это сделано для того, чтобы проиллюстрировать полезные концепции и методы программирования и показать, как их можно выразить с помощью средств языка С++. Языковые возможности и методы программирования, использованные при реализации класса vector, весьма полезны и очень широко используются.
Разобравшись в вопросах проектирования, реализации и использования класса vector, мы сможем понять устройство других стандартных контейнеров, таких как map, и испытать элементные и эффективные методы их использования, обеспечиваемые стандартной библиотекой языка C++ (подробнее об этом речь пойдет в главах 20 и 21). Эти методы, называемые алгоритмами, позволяют решать типичные задачи программирования обработки данных. Вместо самостоятельной разработки кустарных инструментов мы можем облегчить написание и тестирование программ с помощью библиотеки языка C++. Мы уже видели и использовали один из наиболее полезных алгоритмов из стандартной библиотеки — sort().
Мы будем приближаться к стандартному библиотечному классу 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. Например, элементы вектора