4972

Стандартная библиотека шаблонов STL

Лекция

Информатика, кибернетика и программирование

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

Русский

2012-11-30

25.77 KB

20 чел.

Стандартная библиотека шаблонов STL

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

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

Назначение контейнеров – управление наборами (коллекциями) объектов определенного типа.

Примеры контейнеров: массив, список.

Работа с контейнерами поддерживается с помощью контейнерных классов.

Для каждого типа контейнера в соответствующем контейнерном классе определены методы для работы с его элементами.

Свойства контейнеров:

- для каждого типа контейнера в контейнерном классе определены методы для работы с его элементами независимо от типа элементов

Достинства:

- повышение надежности, переносимости и универсльности

- уменьшение сроков и стоимости разработки программ

Недостатки:

- снижение быстродействия

- трудность изучения

Классификация контейнеров:

последовательные

ассоциативные

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

векторы (vector)

двусторонние очереди (deque);

списки (list)

стеки (stack)

очереди (queue)

очереди с приоритетами (priority queue)

В последовательном контейнере элемент занимает определенную позицию, которая зависит только от времени и места вставки.

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

словари (map)

словари с дубликатами (multimap);

множества (set);

множества с дубликатами (multiset)

битовые множества (bitset)

Позиция элемента зависит от его значения по определенному критерию сортировки. Это ускоряет поиск нужного элемента

Требования к контейнерам

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

2. Расположение элементов в контейнера в определенном порядке

3. Необходимость отслеживания операций

Общие операции и методы

begin() 

end()

rbegin()

rend()

size()

max_size()

empty( )

сравнение < >

присваивание =

swap()

clear( )

Операция

Метод

Вид последовательного контейнера

vector

deque

list

Вставка в начало

push_front()

-

+

+

Удаление из начала

pop_front()

-

+

+

Вставка в конец

push_back()

+

+

+

Удаление из конца

pop_back()

+

+

+

Вставка в произвольное место

insert()

+

Удаление из произвольного места

erase ()

+

Произвольный доступ к элементу

[] или at()

+

+

-

Выводы:

1. Вектор эффективно реализует произвольный доступ, добавление и удаление элемента из конца

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

3. Список эффективно реализует вставку и удаление элементов в произвольное место, но не имеет произвольного доступа к элементам.

Массивы и двусторонние очереди – на самостоятельную проработку

Списки

Свойства и возможности списков

- Список не предоставляет произвольного доступа к своим элементам

- Вставка и удаление элементов в любое место списка выполняется за одно и то же время

- Нет операций, связанных с емкостью и перераспределением памяти

- Много специальных методов для перемещения элементов.

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

Пример работы со списком.

include "stdafx.h"

#include<list>//включение заголовочного файла шаблонного класса списка

#include<algorithm>

using namespace std;//стандартное пространство имен

int _tmain()

{

   // TODO: Please replace the sample code below with your own.

   //Console::WriteLine(S"Hello World");

   

 list <int> L1, L2, L3;//определение 3-х пустых списков

 //Заполнение списков значениями

 for(unsigned i=0; i<5; i++)

 L1.push_front(i);

 for(unsigned i=0; i<3; i++)

 L2.push_back(i+10);

L3=L2;

list <int>::iterator it;

printf("L1: ");

 for(it=L1.begin(); it !=L1.end(); it++)

 {

  printf(“%d ”,*it);

 }

printf(“L1.size %d”, L1.size());

printf("L2: ");

for(it=L2.begin(); it !=L2.end(); it++)

 {

  printf(“%d ”,*it);

 }

printf(“L2 size %d”, L2.size());

printf("L3: ");

 for(it=L3.begin(); it !=L3.end(); it++)

 {

  printf(“%d ”,*it);

 }

printf ("L3 size %d ", L3.size());

 it = L1.begin(); it++; it++;

L1.splice(it,L2);

printf("L1: ");

 for(it=L1.begin(); it !=L1.end(); it++)

 {

  printf(“%d ”,*it);

 }

printf(“L1.size %d”, L1.size());

L1.sort();

printf("L1: ");

 for(it=L1.begin(); it !=L1.end(); it++)

 {

  printf(“%d ”,*it);

 }

 

 L1.merge(L3);

printf("L1: ");

 for(it=L1.begin(); it !=L1.end(); it++)

 {

  printf(“%d ”,*it);

 }

 

printf("Смена порядка следования элементов списка L1 на обратный");

 L1.reverse();

 for(it=L1.begin(); it !=L1.end(); it++)

 {

  printf(“%d ”,*it);

 }

printf("Удаление дубликатов");

 L1.unique();

 for(it=L1.begin(); it !=L1.end(); it++)

 {

  printf(“%d ”,*it);

 }

}

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

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

Типы ассоциативных контейнеров:

- словарь (map)$;

- словарь с дубликатами (multimap);

- множество (set);

- множество с дубликатами (multiset);

- битовые множества (bitset);

Словарь – набор пар «ключ/значение». Каждый ключ в одном экземпляре.

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

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

Множество с дубликатами – множество, в котором могут быть элементы с одинаковыми значениями.

Битовые множества – массивы битов фиксированного размера.

Достоинства битовых множеств:

- произвольный фиксированный размер битового поля

- поддержка присваивания значениям отдельным битам.

- запись битовых полей в виде последовательностей нулей и единиц.

Пример работы со словарями (телефонная книга)

/ generated using an Application Wizard.

#include "stdafx.h"

#include <fstream>

#include <iostream>

#include <string>

#include <map>

using namespace std;

typedef map <string, long, less <string> > map_dic;

int _tmain()

{

   // TODO: Please replace the sample code below with your own.

map_dic dic1;

 

ifstream in("phonebook.txt");

   string fam;

 long num;

 

 for (unsigned k=0; k<3; k++)

 {

 in>> num;

 in.get();

 getline(in, fam);

 dic1[fam]=num;

 cout<<num<<" "<<fam<<endl;

}

dic1["Николаев Николай Николаевич"]=1234567;

dic1["Сергеев Сергей Сергеевич"]=4444444;

map_dic::iterator it;

 for(it = dic1.begin(); it != dic1.end(); it++)

 cout << it->first << " " << it->second << endl;

   getline (in, fam);

 if(dic1.find(fam) !=dic1.end())

 cout<<"Found!!!"<<endl;

fam="Petrov;

dic1.insert(make_pair(fam, 6666666));

dic1.erase(fam);

in.close();

   

 return 0;

}


 

А также другие работы, которые могут Вас заинтересовать

22388. Сжатые и растянутые элементы. Конструктивные особенности. Расчет прочности центрально И Внецентренно растянутых элементов. Расчет внецентренно сжатых элементов таврового и двутаврового сечений 1.23 MB
  Расчет прочности центрально И Внецентренно растянутых элементов. Расчет внецентренно сжатых элементов таврового и двутаврового сечений. НАПРЯЖЕННОЕ СОСТОЯНИЕ РАСТЯНУТЫХ И СЖАТЫХ ЖЕЛЕЗОБЕТОННЫХ ЭЛЕМЕНТОВ Сжатые элементы. Конструктивные особенности сжатых элементов К центральносжатым элементам условно относят: промежуточные колонны в зданиях и сооружениях; верхние пояса ферм загруженных по узлам; восходящие раскосы и стойки ферменной решетки.
22389. ТРЕЩИНОСТОЙКОСТЬ И ПЕРЕМЕЩЕНИЯ ЖЕЛЕЗОБЕТОННЫХ ЭЛЕМЕНТОВ. СОПРОТИВЛЕНИЕ ОБРАЗОВАНИЮ ТРЕЩИН ЦЕНТРАЛЬНО РАСТЯНУТЫХ, ИЗГИБАЕМЫХ, ВНЕЦЕНТРЕННО СЖАТЫХ И РАСТЯНУТЫХ ЭЛЕМЕНТОВ. ТРЕЩИНОСТОЙКОСТЬ И ПЕРЕМЕЩЕНИЯ ЖЕЛЕЗОБЕТОННЫХ ЭЛЕМЕНТОВ 101.52 KB
  ТРЕЩИНОСТОЙКОСТЬ И ПЕРЕМЕЩЕНИЯ ЖЕЛЕЗОБЕТОННЫХ ЭЛЕМЕНТОВ. СОПРОТИВЛЕНИЕ ОБРАЗОВАНИЮ ТРЕЩИН ЦЕНТРАЛЬНО РАСТЯНУТЫХ ИЗГИБАЕМЫХ ВНЕЦЕНТРЕННО СЖАТЫХ И РАСТЯНУТЫХ ЭЛЕМЕНТОВ. ТРЕЩИНОСТОЙКОСТЬ И ПЕРЕМЕЩЕНИЯ ЖЕЛЕЗОБЕТОННЫХ ЭЛЕМЕНТОВ. Общие положения Трещиностойкость элементов как условлено ранее это сопротивление образованию трещин в стадии I или сопротивление раскрытию трещин в стадии II.
22390. РАСЧЕТ ПО ОБРАЗОВАНИЮ ТРЕЩИН, НОРМАЛЬНЫХ И НАКЛОННЫХ К ПРОДОЛЬНОЙ ОСИ ЭЛЕМЕНТА. СОПРОТИВЛЕНИЕ РАСКРЫТИЮ ТРЕЩИН. ОПРЕДЕЛЕНИЕ РАССТОЯНИЯ МЕЖДУ ТРЕЩИНАМИ 235.22 KB
  РАСЧЕТ ПО ОБРАЗОВАНИЮ ТРЕЩИН НОРМАЛЬНЫХ И НАКЛОННЫХ К ПРОДОЛЬНОЙ ОСИ ЭЛЕМЕНТА. СОПРОТИВЛЕНИЕ РАСКРЫТИЮ ТРЕЩИН. ОПРЕДЕЛЕНИЕ РАССТОЯНИЯ МЕЖДУ ТРЕЩИНАМИ. Расчет по образованию трещин нормальных к продольной оси элемента Этот расчет заключается в проверке условия что трещины в сечениях нормальных к продольной оси элемента не образуются если момент внешних сил М не превосходит момента внутренних усилий в сечении перед образованием трещин Мcrcт.
22391. КРИВИЗНА ОСИ ПРИ ИЗГИБЕ, ЖЕСТКОСТЬ И ПЕРЕМЕЩЕНИЯ ЖЕЛЕЗОБЕТОННЫХ ЭЛЕМЕНТОВ. ОБЩИЕ ПОЛОЖЕНИЯ РАСЧЕТА 161.5 KB
  КРИВИЗНА ОСИ ПРИ ИЗГИБЕ ЖЕСТКОСТЬ И ПЕРЕМЕЩЕНИЯ ЖЕЛЕЗОБЕТОННЫХ ЭЛЕМЕНТОВ. ОБЩИЕ ПОЛОЖЕНИЯ РАСЧЕТА Расчет перемещений железобетонных элементов прогибов и углов поворота связан с определением кривизны оси при изгибе или с определением жесткости элементов. Считается что элементы или участки элементов не имеют трещин в растянутой зоне если при действии постоянных длительных и кратковременных нагрузок с коэффициентом надежности по нагрузке γf= 1 трещины не образуются. Кривизна оси при изгибе и жесткость железобетонных элементов на участках...
22392. БЕТОН. СТРУКТУРА БЕТОНА. ПРОЧНОСТЬ И ДЕФОРМАТИВНОСТЬ. КЛАССЫ И МАРКИ БЕТОНА. АРМАТУРА. НАЗНАЧЕНИЕ И КЛАССИФИКАЦИЯ. МЕХАНИЧЕСКИЕ СВОЙСТВА. АРМАТУРНЫЕ СВАРНЫЕ ИЗДЕЛИЯ 130.03 KB
  СТРУКТУРА БЕТОНА. КЛАССЫ И МАРКИ БЕТОНА. В связи с этим в бетоне со временем прочность нарастает несколько изменяется объем в зависимости от соотношения состава бетона и химического состава цемента происходит усадка или при использовании специальных цементов расширение. По этим полостям и частично капиллярам возможно перемещение влаги и газа в толще бетона.
22393. ЖЕЛЕЗОБЕТОН. ОСОБЕННОСТИ ЗАВОДСКОГО ПРОИЗВОДСТВА. ПРЕДВАРИТЕЛЬНО-НАПРЯЖЕННЫЙ ЖЕЛЕЗОБЕТОН. АНКЕРОВКА АРМАТУРЫ В БЕТОНЕ. СЦЕПЛЕНИЕ АРМАТУРЫ С БЕТОНОМ. УСАДКА И ПОЛЗУЧЕСТЬ ЖЕЛЕЗОБЕТОНА 435.32 KB
  УСАДКА И ПОЛЗУЧЕСТЬ ЖЕЛЕЗОБЕТОНА. СПЕЦИАЛЬНЫЕ ВИДЫ ЖЕЛЕЗОБЕТОНА. Железобетон состоит из бетона и стальной арматуры. В изгибаемых элементах высокое сопротивление бетона сжатию используется в сжатой зоне а высокое сопротивление арматуры растяжению в растянутой зоне где бетон слабо сопротивляется растяжению и в нем образуются трещины рисунок 2.
22394. КЛАССИФИКАЦИЯ ЗДАНИЙ И СООРУЖЕНИЙ. КОНСТРУКТИВНЫЕ ЭЛЕМЕНТЫ НАДЗЕМНОЙ ЧАСТИ ПРОМЫШЛЕННЫХ ЗДАНИЙ 213.84 KB
  Различные строительные объекты здания и сооружения в зависимости от их назначения можно подразделить на четыре основные группы: жилые и общественные здания которые объединяются общим названием гражданские здания; к общественным зданиям относятся общежития клубы больницы школы.различные административные здания учебные театральнозрелищные торговые здания и т.; промышленные здания здания фабрик заводов и других производственных помещений здания гаражей электростанций котельных и т. сельскохозяйственные здания здания...
22395. Системный (структурный) уровень компьютерного проектирования сложных объектов 230 KB
  Системный подход к задаче автоматизированного проектирования технологического процесса; 2. Системный анализ сложных процессов 3 Этапы проектирования сложных систем 1. Системный подход к задаче автоматизированного проектирования технологического процесса Системный подход к задачам автоматизированного проектирования требует реализации совместного проектирования технологического процесса ТП и автоматизированной системы управления этим процессом АСУТП.
22396. Системный уровень компьютерного проектирования сложных объектов 110.5 KB
  Системный подход направление методологии научного познания и социальной практики в основе которого лежит рассмотрение объектов как системы; ориентирует исследователя на раскрытие целостности объекта на выявление многообразных типов связей в нем и сведения их в единую теоретическую картину. Основная процедура – построение обобщающей модели отражающие взаимосвязи реальной ситуации; техническая основа системного анализа – ЭВМ и информационные системы. Основной общий принцип системного подхода заключается в рассмотрении частей явления или...