Реализация задания в виде класса, используя для хранения информации контейнер стандартной библиотеки шаблонов (STL) языка С++

КУРСОВАЯ РАБОТА

по дисциплине Языки программирования

тема реализация задания в виде класса, используя для хранения информации контейнер стандартной библиотеки шаблонов (STL) языка С++.

Расчетно-пояснительная записка

Содержание

ВВЕДЕНИЕ.

1.Общая характеристика работы…….………………………...……………….6

1.1. Актуальность темы……………………………………………………………6

1.2. Цель работы…………………………………………………….......………….6

1.3. Задачи работы………………………...………………………………………..6

2 Основное содержание……………………………………………………………7

2.1 Теоретическое введение…….………..………..………………………….........7

2.1.1 Введение в STL……….…………………………………………………..7

2.1.2. Контейнеры………….………………………………………………...…8

2.1.3.Контейнерные классы…………………………………………………..12

2.1.4. Итераторы ………………………………………………………………13

2.1.5Алгоритмы……………………………………………………………..…15

2.1.6 Списки и их методы ………………………………………………….....16

2.1.7 Вектор. Его методы и преимущества. ……………………………...….17

2.2.Практичесая часть……………….………………………………………...…18

2.2.1 Блок-схема алгоритма….………………………………………………..18

2.2.2 Блок-схема удаления тура…………...…………………………………..19

2.2.3 Листинг программы…………………………………………………...…20

2.2.4 Пример выполнения …………………………………………………….24

3. Заключение……………………………………………...………………...........26

4.Список использованной литературы……………………..…….. ………….27

ВВЕДЕНИЕ

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

Являясь одним из самых популярных языков программирования, C++ широко используется для разработки программного обеспечения. Область его применения включает создание операционных систем, разнообразных прикладных программ, драйверов устройств, приложений для встраиваемых систем, высокопроизводительных серверов, а также развлекательных приложений (игр). Существует множество реализаций языка C++, как бесплатных, так и коммерческих и для различных платформ. Например, на платформе x86 это GCC, Visual C++, Intel C++ Compiler, Embarcadero (Borland) C++ Builder и другие. C++ оказал огромное влияние на другие языки программирования, в первую очередь на Java и C#.

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

1 Общая характеристика работы

1. Актуальность темы

Язык программирования С++ является одним из самых употребляемых в настоящее время. Достаточно часто возникает задача ведения базы данных при минимальных затратах памяти. В этом случае применяется объектно-ориентированный подход с использованием стандартной библиотеки шаблонов (STL). В своей работе я использовала класс контейнера – вектор.

1. Цель работы

Целью данной работы является изучение стандартной библиотеки шаблонов (STL) языка С++ и создание собственной базы данных.

1. Задачи работы

Для достижения цели следует решить поставленные задачи:

1. создание собственной базы данных;
2. реализовать возможности добавления новых элементов;
3. реализовать возможность замены одного из элементов;
4. реализовать возможность поиска по заданным критериям;
5. реализовать возможность удаления одного из элементовж
6. реализовать возможность вывода всех данных;

1. Общая характеристика

2.1 Теоретическое введение

2.1.1 Введение в STL

В STL содержится несколько основных сущностей. Три наиболее важные из них — это контейнеры, алгоритмы и итераторы. Контейнер — это способ организации хранения данных (стек, связный список, очередь). Еще один контейнер — это массив, но он настолько тривиален и популярен, что встроен в C++ и большинство других языков программирования. Контейнеры бывают самые разнообразные, и в STL включены наиболее полезные из них. Контейнеры STL подключаются к программе с помощью шаблонных классов, а значит, можно легко изменить тип хранимых в них данных. Под алгоритмами в STL подразумевают процедуры, применяемые к контейнерам для обработки их данных различными способами. Например, есть алгоритмы сортировки, копирования, поиска и объединения. Алгоритмы представлены в STL в виде шаблонных функций. Однако они не являются методами классов-контейнеров. Наоборот, это совершенно независимые функции. На самом деле, одной из самых привлекательных черт STL является универсальность ее алгоритмов. Их можно использовать не только в объектах классов-контейнеров, но и в обычных массивах и даже в собственных контейнерах. (Контейнеры, тем не менее, содержат методы для выполнения некоторых специфических задач.) Итераторы — это обобщение концепции указателей: они ссылаются на элементы контейнера. Их можно инкрементировать, как обычные указатели, и они будут ссылаться последовательно на все элементы контейнера. Итераторы — ключевая часть всего STL, поскольку они связывают алгоритмы с контейнерами. Их можно представить себе в виде кабеля, связывающего колонки вашей стереосистемы или компьютер с его периферией.

2.1.2 Контейнеры

Контейнер — это объект, который может содержать в себе другие объекты. Существует несколько разных типов контейнеров(см.рис.1). Например, класс vector определяет динамический массив, deque создает двунаправленную очередь, а list представляет связный список. Эти контейнеры называются последовательными контейнерами (sequence containers), потому что в терминологии STL последовательность -это линейный список. STL также определяет ассоциативные контейнеры (associative containers), которые обеспечивают эффективное извлечение значений на основе ключей.

Таким образом, ассоциативные контейнеры хранят пары “ключ/значение”. Примером может служить map. Этот контейнер хранит пары “ключ/значение”, в которых каждый ключ является уникальным. Это облегчает извлечение значения по заданному ключу.

Рис.1-Разновидность контейнеров

Последовательные контейнеры

В последовательных контейнерах данные хранятся подобно тому, как дома стоят на улице — в ряд. Каждый элемент связывается с другими посредством номера своей позиции в ряду. Все элементы, кроме конечных, имеют по одному соседу с каждой стороны. Примером последовательного контейнера является обычный массив. Проблема с массивами заключается в том, что их размеры нужно указывать при компиляции, то есть в исходном коде. К сожалению, во время написания программы обычно не бывает известно, сколько элементов потребуется записать в массив. Поэтому, как правило, рассчитывают на худший вариант, и размер массива указывают «с запасом». В итоге при работе программы выясняется, что либо в массиве остается очень много свободного места, либо все-таки не хватает ячеек, а это может привести к чему угодно, вплоть до зависания программы. В STL для борьбы с такими трудностями существует контейнер vector. Но с массивами есть еще одна проблема. Допустим, в массиве хранятся данные о работниках, и вы отсортировали их по алфавиту в соответствии с фамилиями. Теперь, если нужно будет добавить сотрудника, фамилия которого начинается с буквы Л, то придется сдвинуть всех работников с фамилиями на М - Я, чтобы освободить место для вставки нового значения. Все это может занимать довольно много времени. В STL имеется контейнер список, который основан на идее связного списка и который решает данный вопрос. Третьим представителем последовательных контейнеров является очередь с двусторонним доступом. Это комбинация стека и обычной очереди. Стек, как вы помните, работает по принципу LIFO (последний вошел — первый вышел). То есть и ввод, и вывод данных в стеке производится «сверху». В очереди же, напротив, используется принцип FIFO (первый вошел — первый вышел): данные поступают «сверху», а выходят «снизу». Очередь с двусторонним доступом, надо полагать, использует комбинированный порядок обмена данных. И вносить значения в очередь с двусторонним доступом, и выводить из нее можно с обеих сторон. Это довольно гибкий инструмент, он ценен не только сам по себе, но может служить базой для стеков очередей, в чем мы вскоре сможем убедиться.

Ассоциативные контейнеры

Ассоциативный контейнер — это уже несколько иная организация

данных. Данные располагаются не последовательно, доступ к ним осуществляется посредством ключей. Ключи — это просто номера строк, они обычно используются для выстраивания хранящихся элементов в определенном порядке и модифицируются контейнерами автоматически. Примером может служить обычный орфографический словарь, где слова сортируются по алфавиту. Вы просто вводите нужное слово (значение ключа), например «арбуз», а контейнер конвертирует его в адрес этого элемента в памяти. Если известен ключ, доступ к данным осуществляется очень просто. В STL имеется два типа ассоциативных контейнеров: множества и отображения. И те и другие контейнеры хранят данные в виде дерева, что позволяет осуществлять быструю вставку, удаление и поиск данных. Множества и отображения являются очень удобными и при этом достаточно универсальными инструментами, которые могут применяться в очень многих ситуациях. Но осуществлять сортировку и выполнять другие операции, требующие случайного доступа к данным, неудобно. Множества проще и, возможно, из-за этого более популярны, чем отображения. Множество хранит набор элементов, содержащих ключи — атрибуты, используемые для упорядочивания данных. Например, множество может хранить объекты класса person, которые упорядочиваются в алфавитном порядке. В качестве ключа при этом используется значение name. При такой организации данных можно очень быстро найти нужный объект, осуществляя поиск по имени объекта (ищем объект класса person по атрибуту name). Если в множестве хранятся значения одного из базовых типов, таких, как int, ключом является сам элемент. Некоторые авторы называют ключом весь объект, хранящийся в множестве, но мы будем употреблять термин ключевой объект, чтобы подчеркнуть, что атрибут, используемый для упорядочивания (ключ), — это не обязательно весь элемент данных. Отображение хранит пары объектов. Один кортеж в такой «базе данных» состоит из двух «атрибутов»: ключевой объект и целевой (ассоциированный) объект. Этот инструмент часто используется в качестве контейнера, несколько напоминающего массив. Разница лишь в том, что доступ к данным осуществляется не по номеру элемента, а по специальному индексу, который сам по себе может быть произвольного типа. То есть ключевой объект служит индексом, а целевой — значением этого индекса. Контейнеры отображение и множество разрешают сопоставлять только один ключ данному значению. Это имеет смысл в таких, например, случаях, как хранение списка работников, где каждому имени сопоставляется уникальный идентификационный номер. С другой стороны, мулътиотображения и мультимножества позволяют хранить несколько ключей для одного значения Например, слову «ключ» в толковом словаре может быть сопоставлено несколько статей.

2.1.3 Контейнерные классы

Каждый контейнер имеет определенный для него аллокатор (allocator). Аллокатор управляет выделением памяти для контейнера. Аллокатором по умолчанию является объект класса allocator, но вы можете определять свои собственные аллокаторы, если это необходимо для специализированных приложений. Для большинства применений аллокатора по умолчанию вполне достаточно.

Контейнеры реализованы посредством шаблонных классов. Например, ниже показа- на спецификация шаблона контейнера deque. Все контейнеры используют схожие спе- цификации: template <class T, class Allocator = allocator<T> > class deque Здесь обобщенный тип T специфицирует тип объектов, хранящихся в deque. Аллокатор, используемый deque, специфицирован Allocator; по умолчанию это стан- дартный класс для аллокаторов. Для подавляющего большинства приложений вы будете просто применять аллокатор по умолчанию, то же касается всего кода этой главы. Однако вы можете определять собственные типы аллокаторов, когда требуется специальная схема выделения памяти.

2.1.4 Итераторы

Итераторы — это объекты, которые ведут себя более или менее подобно указателям. Они предоставляют возможность выполнять циклическую обработку элементов контейнера — подобно тому, как вы используете указатель для организации цикла по массиву. Существует пять типов итераторов(см.рис.2)

Рис.2-Типы итераторов

Вообще итератор, имеющий более широкие возможности доступа, может применяться вместо итератора с меньшими возможностями. Например, прямой итератор может быть использован вместо входного итератора. Итераторы обрабатываются подобно указателям. Обратные итераторы либо двунаправлены, либо произвольного доступа, которые перемещаются по последовательности в обратном направлении. Таким образом, если обратный итератор указывает на конец последовательности, то увеличение этого итератора на единицу переместит его на элемент, предшествующий конечному. Все итераторы должны поддерживать типы операций с указателями, допустимые для их категории. Например, класс входного итератора должен поддерживать операции ->, ++, *, == и !=. Более того, операция * не может использоваться для присваивания значения. В отличие от входного, итератор произвольного доступа должен поддерживать операции ->, +, ++, -, --, *, <, >, <=, >=, -=, +=, ==, != и []. Вдобавок операция * должна позволять присваивание. Операции, поддерживаемые каждым типом итераторов, перечислены ниже(см.рис.3).

Рис.3-Операии итераторов

При ссылках на различные типы итераторов в описаниях шаблонов будут использованы следующие термины(см.рис.4).

Рис.4-Термины итераторов

2.1.5 Алгоритмы

Алгоритмы выполняют действия над контейнерами. Их возможности включают инициализацию, сортировку, поиск, слияние, замену и трансформацию содержимого контейнера. Многие алгоритмы оперируют диапазонами элементов в контейнере.

Алгоритмы:

find ()- этот алгоритм ищет первый элемент в контейнере, значение которого равно указанному.

count()-подсчитывает, сколько элементов в контейнере имеют данное значение.

sort()-алгоритм сортировки.

search()-ищет целую последовательность значений, заданную одним контейнером, в другом контейнере.

merge()-этот алгоритм работает с тремя контейнерами, объединяя элементы двух из них в третий, целевой контейнер.

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

transform()-этот алгоритм тоже делает что-то с каждым элементом контейнера, но еще и помещает результат в другой контейнер (или в тот же). Опять же, пользовательcкая функция определяет, что именно делать с данными, причем тип возвращаемого ею результата должен соответствовать типу целевого контейнера.

2.1.6 Списки и их методы

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

Методы.

push_front(), front() и pop_front() аналогичны методам pop_back() из векторов.

2.1.7 Вектор. Его методы и преимущества.

Векторы — это, так сказать, умные массивы. Они занимаются автоматическим размещением себя в памяти, расширением и сужением своего размера по мере вставки или удаления данных. Векторы можно использовать в какой-то мере как массивы, обращаясь к элементам с помощью привычного оператора []. Случайный доступ выполняется очень быстро в векторах. Также довольно быстро осуществляется добавление (или проталкивание) новых данных в конец вектора. Когда это происходит, размер вектора автоматически увеличивается для того, чтобы было, куда положить новое значение.

Так же существует достаточно большое количество полезных методов для вектора:

push_back() - вставляет значение своего аргумента в конец вектора

size() - возвращает текущее число элементов, содержащихся в контейнере.

swap() - обменивает данные одного вектора на данные другого, при этом порядок следования элементов не изменяется

back() - возвращает значение последнего элемента вектора

insert - имеет два параметра: будущее расположение нового элемента в контейнере и значение элемента.

erase() - удаляет элемент из указанной позиции

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

2.2 Практическая часть

2.2.1 Блок-схема алгоритма