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

Часть III

Данные и алгоритмы

Глава 17

Векторы и свободная память

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

.

17.1. Введение

 

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

 

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

В этой и следующих двух главах мы покажем, как построить класс

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

Разобравшись в вопросах проектирования, реализации и использования класса

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

 

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

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

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

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

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

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

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

 

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