Технология программирования. Понятие технологии программирования. Методология процедурно-ориентированного программирования. Абстракция и декомпозиция.

Технология программирования. Понятие технологии программирования. Методология процедурно-ориентированного программирования. Абстракция и декомпозиция.

Технология программирования – набор правил, методик и инструментов предопределяющих процесс разработки программного продукта, процесс разработки включает 5 этапов:

1) Анализ требований к программе.

2) Проектирование.

3) Кодирование.

4) Тестирование.

5) Документирование.

Все 5 этапов тесно связаны между собой, и их реализация напрямую зависит от выбранной методологии программирования.

Методология программирования

С момента появления 1-х программ (нач.60-х – сер.70-х) не существует каких-либо определенных подходов к процессу разработки ПО. Этот этап называется Rou Your Own.

1. Методология процедурно-ориентированного программирования ПОП.

В середине 70-х Дейкстра (галланд.ученый) предложил идею структурного программирования. Далее идею развили Николас Мирт и Демарто.

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

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

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

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

Basic Fortran

Pascal Pl/1

C

Преимущества:

1. Возможность повторного использования одного и того же кода из нескольких мест программы, без его копирования.

2. Легче отследить порядок выполнения программы, чем в случае использования инструкции go to или jump.

3. Возможность поддержки модульности и структурированности.

 

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

int func()

{

int a;

if (a= =10) {

a=a+1;

}

a=a-1;

}

 

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

 

Абстракция и декомпозиция

 

Абстракция – уход от деталей реализации конкретного множества функций.

 

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

Процесс декомпозиции напрямую связан с используемой методологией программирования

 

Декомпозиция в ПОП – это разбиение всей задачи на совокупность процедур и функций.

 

Декомпозиция в ООП – разбиение всей задачи на совокупность классов и объектов, с соответствующими свойствами и методами.

Декомпозиция в системном анализе и системном моделировании – это разбиение всей задачи на совокупность подсистем.

 

2. Технология программирования. Методология объектно-ориентированного программирования. Основные принципы ООП: наследование, инкапсуляция, полиморфизм.

Технология программирования – набор правил, методик и инструментов, предопределяющих процесс разработки программного продукта, процесс разработки включает 5 этапов:

6) Анализ требований к программе.

7) Проектирование.

8) Кодирование.

9) Тестирование.

10) Документирование.

Все 5 этапов тесно связаны между собой, и их реализация напрямую зависит от выбранной методологии программирования.

2. Методология объектно-ориентированного программирования.

В середине 70-х появились ПК. ПК стали повсеместно использоваться компаниями мелкого и среднего бизнеса. Это привело к изменению ПО, акцент сместился от крупных предприятий к мелким. Вычислительные и расчетно-алгоритмические задачи заняли 2-е место, на первый план вышли задачи обработки и управления данными, появились базы данных. В результате революция ПК и ПО привела к следующему:

1. Значительно возросли размеры и сложность программ.

2. Повысились требования к надежности программ.

3. Повысились требования к интерфейсу с пользователем.

В рез-те к сер.70-х стало очевидно, что ПОП не способно справиться с множеством ситуаций, возникла потребность в новой методологии, которой стало ООП.

ООП - это совокупность принципов технологий и инструментальных средств, для создания программных систем на основе архитектуры взаимодействия объектов.

В процедурном программировании данные и подпрограммы формально не связаны. В ООП данная связь выходит на первое место.

C++ C# MC

Java Delphi

Obi Basic

ООП лидирует в части прикладного ПО, в части системного ПО остается лидером процедурные языки, в 1-ю очередь - язык С.

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

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

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

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

Основные принципы ООП:

1. Наследование.

2. Инкапсуляция.

3. Полиморфизм.

 

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

 

2. Инкапсуляция – сокрытие отдельных деталей внутреннего устройства классов от внешних по отношению к нему объектов или пользователей, взаимодействующему с классом пользователю не надо знать каким образом реализован тот или иной метод классов, который он использует. Конкретная реализация свойств и методов класса определяет поведение этого класса и является собственным делом данного класса, более того отдельные свойства и методы могут быть невидимы за пределами этого класса, что является базовой идеей введения различных категорий видимости.

Инкапсуляция ведет свое происхождение от деления модулей на 2 части:

1) интерфейс

2) реализация

В интерфейсной секции описываются все процедуры функций, которые доступны за пределами данного модуля, в секции реализации содержится программный код.

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

 

3. Технология программирования. Методология объектно-ориентированного анализа и проектирования.

Технология программирования – набор правил, методик и инструментов предопределяющих процесс разработки программного продукта, процесс разработки включает 5 этапов:

11) Анализ требований к программе.

12) Проектирование.

13) Кодирование.

14) Тестирование.

15) Документирование.

Все 5 этапов тесно связаны между собой, и их реализация напрямую зависит от выбранной методологии программирования.

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

1. сколько и какие классы нужны для поставленной задачи

2. какие свойства и методы необходимы для придания классу требуемого поведения

3. какие взаимосвязи должны быть установлены между классами

Эти задачи связаны с общим анализом требования к программе и анализом предметной области. Данные обстоятельства и привели к методологии ООАиП.

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

ООА – методология, при которой требования к системе воспринимаются с точки зрения классов и объектов выявленных предметной областью.

ООП(проектирование) – это методология проектирования, соединяющая в себе процесс объектной декомпозиции и приемы представления логической и физической, а так же статической и динамической моделей проектирования системы.

2 важные вещи:

1. ООП основывается на объектно-ориентированной декомпозиции.

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

Кейс-технология (кейссредство): пример диаграммы.

Технология ООАиП привела к появлению соответствующих специалистов - аналитиков (архитекторов), которые разработали специальные приложения; появление этих специалистов привело к созданию CASE средств.

 

4. Технология программирования. Методология системного анализа и системного моделирования.

Технология программирования – набор правил, методик и инструментов предопределяющих процесс разработки программного продукта, процесс разработки включает 5 этапов:

1) Анализ требований к программе.

2) Проектирование.

3) Кодирование.

4) Тестирование.

5) Документирование.

Все 5 этапов тесно связаны между собой, и их реализация напрямую зависит от выбранной методологии программирования.

4. Методология системного анализа и системного моделирования. В р езультате развития ООАиП явилось осознание необходимости построения предварительной модели программной системы, в результате появилась следующая методология.

Системный анализ, как научное направление, самое старое направление. Центральное понятие системный анализа - понятие системы, под которой понимается совокупность объектов, компонентов или элементов произвольной природы, образующих некоторую целостность, определяющей предпосылкой выделения некоторых компонентов как системы, является возникновение у нее новых свойств, которых не имеют составляющие ее элементы.

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

Процесс функционирования системы – изменение свойств или поведения системы во времени. При этом важной характеристикой является ее состояние.

Состояние – это совокупность свойств или признаков, которые в каждый момент времени отражают наиболее существенные особенности поведения системы.

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

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

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

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

«Модель черного ящика»

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

5. Методы проектирования программ. Метод нисходящего проектирования программ. Метод восходящего проектирования программ. Метод смешанного проектирования. Метод объектно-ориентированного проектирования.

1. Метод нисходящего проектирования

2. Метод восходящего проектирования «

3. Метод смешанного проектирования

4. Метод объектно-ориентированного проектирования.

В методологии ПОП развитие получили 2 первых метода. А в ООП развитие получили 3 и 4 методы.

1. Метод нисходящего проектирования «метод сверху вниз».

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

Реализация программы в случае нисходящего проектирования начинается с наиболее абстрактного описания функции, выполненной системой, т.е. с самых крупных подзадач. На данном этапе все более мелкие подзадачи заменяются «функциями-заглушками». Затем последовательными шагами детализируется каждая подзадача, т.е. реализуется одна из функций – заглушек, при этом более мелкие подзадачи заменяются функциями – заглушками, и так до тех пор, пока не будет реализована вся программа. Метод используется в настоящее время.

2. Метод восходящего проектирования «метод снизу вверх».

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

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

3. Метод смешанного проектирования.

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

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

1. сколько и какие классы нужны для поставленной задачи

2. какие свойства и методы необходимы для придания классу требуемого поведения

3. какие взаимосвязи должны быть установлены между классами

Эти задачи связаны с общим анализом требования к программе и анализом предметной области. Данные обстоятельства и привели к методологии ООАиП.

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

ООА – методология, при которой требования к системе воспринимаются с точки зрения классов и объектов выявленных предметной областью.

ООП(проектирование) – это методология проектирования, соединяющая в себе процесс объектной декомпозиции и приемы представления логической и физической, а так же статической и динамической моделей проектирования системы.

2 важные вещи:

1. ООП основывается на объектно-ориентированной декомпозиции.

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

Кейс-технология (кейссредство): пример диаграммы.

Технология ООАиП привела к появлению соответствующих специалистов - аналитиков (архитекторов), которые разработали специальные приложения; появление этих специалистов привело к созданию CASE средств.

 

 

6 Документирование ПО. ЕСКД, ЕСТД, ЕСПД. Основные документы. Техническое задание.

Документирование ПО – это процесс написания технической документации. Техническая документация – это набор документов, используемых при проектировании и эксплуатации ПО. Она включает в себя следующие виды документаций: 1)Проектная документация. 2)технологическая документация. 3)Эксплуатационная документация. Стандарты: ЕСКД – единая система конструкторской документации. ЕСТД – единая система технической документации. ЕСПД – единая система программной документации. ЕСКД – это комплекс государственных стандартов, устанавливающих взаимосвязанные правила, требования и нормы по разработке, оформлению и обращению конструкторской документации, разрабатываемой и применяемой на всех стадиях жизненного цикла ПО. Основное назначение стандартов ЕСКД состоит в установлении единых оптимальных правил, требований и норм. ЕСТД – это комплекс государственных стандартов и рекомендаций, устанавливающих единые правила по порядку и разработке, комплектации, оформления и обращения технической документации, применяемый при изготовлении и изменении ПО. ЕСПД – это комплекс государственных стандартов, устанавливающих взаимосвязанные правила разработки, оформления и обращения программы и программной документации. В стандартах ЕСПД устанавливаются требования, регламентирующие разработку, сопровождение, изготовление и эксплуатацию ПО. Применение ЕСПД обеспечивает: 1)Унификацию ПО. 2)Снижение трудоемкости и повышение эффективности разработки и эксплуатации. 3)Автоматизацию составления и хранения программной документации. К ЕСПД относят следующие документы: 1)Техническое задание. 2)Программа и методика испытаний 3)Руководство пользователя. 4)Руководство системного программиста. 5)Руководство программиста. Техническое задание. Появляется на этапе анализа требований. Техническое задание является исходным документом для проектирования ПО. Техническое задание содержит: 1) Основание для разработки (организация-заказчик, наименования и др.) 2)Назначение ПО. 3)Требования к ПО (технические и особые требования) 4)Требования к программной документации. 5)Технико-экономические показатели (бизнес-оценка) 6)Стадии, этапы разработки (сроки, исполнители). 7)Порядок контроля и приемки. 8)Приложения. Техническое задание должно быть составлено таким образом, чтобы исключить возможные разночтения.

Шаблоны (template).

Шаблон – конструкция языка, которая предназначена для реализации обобщенного программирования.

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

В языке C++ шаблоны реализованы с использованием ключевого слова template.

Шаблон позволяет создавать параметризованные классы и параметризованные функции.

Параметризованные функции.

Синтаксис: template<список параметров> функция

Список параметров может задаваться двумя способами:

1) сlass идентификатор [=имя типа]

2) typename идентификатор [=имя типа]

При объявлении списка параметров ключевые слова class и typename эквивалентны и могут заменять друг друга.

Пример объявления функции:

template<typename Type>

void sort(Type array[], int size)

{

Type n; // Type - какой-то реальный тип

……….

}

Type используется как имя типа.

 

template <typename Type, int size>

Type* read()

{

Type* sort = new Type [size];

………………………………

return sort;

}

 

 

void main()

{

int a[10];

double* p;

sort<int>(a,10);

p=read<double,100>();

}

 

Реализация функции sort (функция сортировки).

template<typename Type>

void sort (Type array[], int size)

{

int c1;

int c2;

for(c1=0;c1<size;c1++)

{

for(c2=c1+1;c2<size;c2++)

{

if((1)array[c1]<array[c2])

{

(2)Type v = array[c1];

(3) array[c1]=array[c2];

array[c2]=v;

}

}

}

}

 

Поскольку параметрические функции можно использовать не только для фундаментальных типов(int, char, short и т.д.), но и для производных типов данных (классы, структуры и т.д.).

В этом случае следует выделить 3 важных момента:

1. Сравнение двух элементов массива.

2.Присвоение переменной значения элемента массива(в классе должен быть реализован присваивающий конструктор).

3.Присвоение элементу массива значения другого элемента массива или переменной.

Смотрите внимательно за операторами!!!!!!!

bool operator <(const A&);

A(const A&); // конструктор копирования.

A& operator = (const A&).

Параметризованные классы.

Синтаксис:

template<список параметров>

class объявление класса;

Список параметров может задаваться двумя способами:

3) сlass идентификатор [=имя типа]

4) typename идентификатор [=имя типа]

Реализация стека.

template <class Type> class stack

{

public:

stack(int size);

void push (Type data);

Type pop (void);

private:

Type* mass;

int index;

Type* p;

Type perem;

};

 

template <class Type>

stack<Type>::stack(int size)

{

mass=new Type[size];

index=0;

}

 

template <class Type>

void stack<Type>::push(Type data)

{

mass[index]=data;

index++;

}

 

template <class Type>

Type stack<Type>::pop()

{

index--;

perem=mass[index];

p=new Type[index];

for(int i=0;i<index;i++)

{

p[i]=mass[i];

}

delete [] mass;

mass=new Type[index];

for(int i=0;i<index;i++)

{

mass[i]=p[i];

}

delete [] p;

return perem;

}

 

void main(int argc, char* argv[])

{

stack<int> s(10); // создание стека

s.push(10);

s.push(20);

printf("%d",s.pop()); //20

printf("%d",s.pop()); //10

getch();

}

 

Контейнеры.

Контейнеры обеспечивают размещение в динамической памяти коллекций данных различных типов.

Типы контейнеров:

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

vector - динамический массив;

list – двусвязный динамический список;

deque – двусторонняя очередь или очередь с двусторонним доступом.

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

set – множество, в котором каждый элемент уникален;

multiset – множество с дубликатами (каждый элемент необязательно уникален);

map – словарь (отображение). Хранит пары “ключ-значение”, в котором каждый ключ связан только с одним значением;

multimap – словарь с дубликатами (мультиотображение). Хранит пары “ключ-значение”, в которых каждый ключ может быть связан с двумя или более значениями;

hash_set – хеш-множество (хешированный ассоциативный контейнер) (не применимо отношение порядка) (хранит объекты типа “ключ”) (знакомая нам структура, которая позволяет добавлять, удалять и проверять наличие элемента во множестве) (Для быстрого доступа используются хеш-функции, также используется бинарный предикат, для проверки ключей на равенство);

hash_multiset – (хешированный ассоциативный контейнер) хеш-множество с дубликатами (в отличие от hash_set, может иметь несколько одинаковых элементов);

hash_map – (хешированный ассоциативный контейнер) хеш-отображение(реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. Для быстрого доступа к элементу по ключу используется специальная хеш-функция. Также используется бинарный предикат для проверки двух ключей на равенство);

hash_multimap – (хешированный ассоциативный контейнер) хеш-отображение с дубликатами (в отличие от hash_map, некоторые элементы hash_multimap могут иметь один и тот же ключ).

3)Адаптеры контейнеров:

stack – стек;

queue – очередь;

priority_queue – очередь с приоритетом.

 

Vector

Vector – шаблон (параметризованный класс), который реализует функционал динамического массива. Класс поддерживает динамическое изменение размера массива и обеспечивает быстрый доступ к любому элементу массива.

Пример:

 

#include <vector>

using namespace std;

void main()

{
vector<int> m;

int v;

m.push_back(10); //m[0]=10

m.push_back(20); //m[1]=20

v=m[0]; //v=10

v=m[1]; //v=20

}

Внутри класса vector перегружены следующие операторы:

1) все операторы сравнения (= =,!=, <, >, <=, >=);

2) [] – доступ к элементу по индексу.

Основные функции:

push_back – добавление элемента в конец (увеличивает размер массива);

pop_back – удаление элемента с конца (уменьшает размер массива);

insert – вставка элемента в указанную позицию;

clear – очистка массива (удаление всех элементов);

size – определение количества элементов в динамическом массиве;

swap – меняет два элемента в массиве местами.

 

List

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

Класс не поддерживает быстрый доступ к элементам списка.

Пример:

 

#include <list>

using namespace std;

void main ()

{

list <int> m;

int v;

m.push_back(10);

m.push_back(20);

m.push_front(1);

……

}

 

Основные функции.

push_back(front) – добавление элемента в конец (начало) списка (увеличивается размер списка);

pop_back(front) – выталкивание элемента с конца (начала) списка (уменьшается размер списка);

insert – вставка элемента в список;

clear – очистка списка;

size – получение сведений о количестве элементов;

swap – замена двух элементов местами (по указателям).

 

Deque

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

 

Пример:

 

#include <deque>

using namespace std;

void main()

{

deque<int> m;

int v;

m.push_back(10);

m.push_front(20);

m.push_back(30);

v=m[0]; //20

v=m[1]; //10

v=m[2]; //30

}

 

Основные функции.

Функционал такой же как у list.

 

Множество(set)

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

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

Класс не позволяет хранить одинаковые ключи.

Пример:

#include <set>;

using namespace std;

void main()

{

set <int> m;

m.insert(20);

m.insert(10);

m.insert(30);

m.insert(30); //error

}

Ключи=данные!!!!!!!!!!!!

Основные функции.

insert – вставка элемента с указанным ключом;

clear – очистка множества;

size – определение количества элементов;

find – поиск элемента по ключу (получаем указатель на элемент(итератор), либо итератор эквивалентен итератору, полученному в результате использования операции end()).

 

Map(словарь)

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

Реализует принцип хеш-таблицы.

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

Класс не позволяет хранить одинаковые ключи, но позволяет хранить одинаковые значения для разных ключей.

Map – расширение set.

Ключ1	Ключ2	Ключ3	Ключ4	Ключ5
Значение1	Значение2	Значение1	Значение3	Значение4

Пример:

#include <map>

using namespace std;

void main()

{

map <int,double> m; //<тип ключа, тип значения>

m.insert(pair <int,double> (30,10.2));

m.insert(pair <int,double> (10,15.5));

m.insert(pair <int,double> (30,10.2));//error

}

Основные функции.

Функционал такой же как у set.

Также следует отметить, что в данном контейнере реализован operator [].

Также важно помнить, что operator [] при обращении к несуществующему элементу в map создаст его. Новый элемент при этом будет инициализирован нулём (либо конструктором по умолчанию, если это не тривиальный тип данных). Данная особенность map может быть удобной, потому как выполнять операции с элементами можно не задумываясь об их присутствии в map.

 

Алгоритмы

 

Алгоритмы – наборы готовых функций, которые могут быть применены к контейнерам.

Условно можно поделить на 3 группы:

1)Алгоритмы для перебора элементов контейнера и выполнения определенных действий над каждым из элементов.

count – подсчет элементов;

find – поиск;

for_each – применение заданной функции к заданному диапазону элементов;

equal – сравнение двух элементов на равенство;

swap – меняет местами заданные два значения;

fill – заполняет диапазон заданными значениями;

remove – удаление элементов из заданного диапазона.

2)Алгоритмы для сортировки элементов контейнера.

sort – сортировка заданного диапазона;

binary_search - просматривает элементы от start до end в поисках значения val. Просматриваемые элементы между start и end должны быть упорядочены по возрастанию, что определено оператором <. (start, end – итераторы).

merge – объединение двух упорядоченных последовательностей, помещая результат в третью последовательность.

3)Алгоритмы для выполнения определенных арифметических действий над элементами контейнера.

accumulate – нахождение суммы элементов контейнера или подконтейнера;

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

partial_sum – вычисляет частичную сумму элементов, расположенных в диапазоне [start,end) и располагает результат в result. (start, end, result – итераторы).

Пример:

#include <algorithm>

#include <numeric>

 

void main()

{

list<int> m;

list<int>::iterator it;

m.push_back(3);

m.push_back(2);

it = find (m.begin(), m.end(), 2); // получаем указатель на элемент с значением 2.

}

 

Реализация сортировки.

Не все контейнеры поддерживают sort. Например, list не поддерживает, а vector поддерживает.

Пример:

#include <algorithm>

#include <numeric>

#include <vector>

using namespace std;

void main()

{

vector<int> m;

m.push_back(2);

m.push_back(1);

m.push_back(5);

sort(m.begin(), m.end(), greater<int>());

// сортировка по возрастанию (greater)

// сортировка по убыванию (less)

}

 

Функция суммирования accumulate – сумма всех элементов контейнера.

int v = accumulate(m.begin(), m.end(), 2);

//значение 2 будет прибавлено к полученной сумме.

 

 

Аллокаторы.

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

Библиотека STL позволяет использовать стандартные аллокаторы, которые реализованы в библиотеке, и собственные аллокаторы, которые реализованы пользователем.

Пример (выделение и освобождение элементов массива):

 

#include <memory>

using namespace std;

 

void main()

{

allocator <int> a;

allocator <int>::pointer p;//указывает на выделенную память под элементы (тип элементов как в скобках)

p=a.allocate(10);//выделяет память под 10 элементов типа int

for(int i=0; i<10; i++)

{

p[i]=i;//заполнение памяти

}

a.deallocate(p,10); // 10 объектов в области, указываемой p, должны быть уничтожены до этого запроса.

}

Все контейнеры STL обладают стандартными аллокаторами, но можно создать и свой аллокатор со своим размещением в памяти.

 

Функциональные объекты.

Функциональные объекты – объекты классов, в которых выполнена перегрузка оператора “вызов функции” (operator ()).

Функциональные объекты используются как функции, вызываемые для различных типов данных.

Код, выполняемый при вызове, определяется пользователем.

Функциональные объекты реализуют указатель на функцию, но применительно к объектам шаблонных классов.

Пример (функциональный объект сравнения двух элементов):

 

class Functor

{

public:

 

bool operator() (int a, int b)

{

return a<b;

}

};

 

void main()

{

Functor f;

bool res;

res=f(5,7); //true

res=f(8,5); //false

}

 

Основное назначение функциональных объектов – использование их в различных алгоритмах.

Например: алгоритм for_each – переборка всех элементов контейнера и вызов определенного пользователем функционального объекта для каждого элемента контейнера.