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;

}


 

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

76737. Передние мышцы и фасции бедра 182.5 KB
  В передней области бедра широкая фасция формирует влагалище для четырехглавой мышцы портняжной и тонкой. Подкожная щель овальная ямка формируемая широкой фасцией на передней поверхности бедра лежит на 56 см ниже паховой связки в бедренном треугольнике. Передние мышцы бедра Портняжная мышца с началом от передней верхней подвздошной ости и прикреплением к большеберцовой бугристости и фасции голени где сухожилие ее перекрещивается с сухожилиями тонкой и полусухожильной мышц образуя треугольную фиброзную пластинку с синовиальной сумкой.
76738. Предмет и содержание анатомии 183.43 KB
  Анатомия изучает внешние формы и внутреннее строение вплоть до микроскопического как всего человеческого организма так и отдельных его органов и тканей. Основными методами анатомического исследования являются вскрытие рассечение препарирование мертвого тела с осмотром измерениями описанием взвешиванием органов микроскопическим изучением отдельных органов группы органов или системы всего организма. Общая задача при изучении современной анатомии состоит в том чтобы системно рассмотреть внешние формы и внутренние структуры положение...
76739. Современные подходы к анатомическому исследованию 183.79 KB
  Они дополняются инъекцией сосудов полостей органов бальзамирующими растворами цветными контрастными наполнителями; просветлением и мумификацией коррозией изготовлением распилов замороженного тела по Н. Для ритуального бальзамирования древнеегипетских фараонов после вскрытия тела и извлечения внутренностей использовалось промывание пальмовым вином просаливание наполнение благовониями с последующим обматыванием трупа материей пропитанной воском благовониями и смолами и погружением в серию гробов саркофаги и пирамиды. Но существует и...
76740. Анатомия и медицина 183.07 KB
  Систематическая анатомия описывает строение нормального здорового человека по системам: костной суставной мышечной и т. она изучает методом системного подхода строение здорового нормального человека; в связи с этим полезно знать определение здоровья и нормы. Здоровье полное физическое психическое и социальное благополучие человека находящееся в равновесии с окружающей средой определение Всемирной организации здравоохранения ВОЗ.
76741. Основные методологические принципы анатомии 182.27 KB
  Из одной клетки создавать ткань орган системы органов и в целом весь организм пересаживать клетки и ткани человеку и животным. У человека различают следующие основные ткани: Эпителиальная покровная ткань т. Соединительная ткань собственная хрящевая костная состоящая из клеток коллагеновых и эластических волокон и основного гелеобразного вещества. Собственная соединительная ткань рыхлая и плотная имеет много разновидностей ретикулярная жировая пигментная волокнистая кровь и лимфа.
76742. Анатомия и медицина древней Греции и Рима 183.8 KB
  были обобщены все достижения современной ему анатомии. Гиппократ свел в единое руководство достижения современной ему анатомии используя первые рукописи в виде Анатомии Диоклесса трудов Алкмеона и своих собственных. Древнегреческая Александрийская медицинская школа в изучении анатомии стояла на передовых позициях.
76743. Анатомия эпохи Возрождения 183.2 KB
  В методику исследования органов вводятся новые способы: инъекции сосудов и полостей распилы костей консервация органов и тканей новые химические методы бальзамирования измерения и зарисовки органов с подробным описанием. Великий итальянский художник и ученый Леонардо да Винчи вскрывая трупы производил подробное и тщательное описание анатомических структур сразу же все зарисовывал дополнял измерениями; производил инъекции сосудов желудочков мозга; создавал модели органов чтобы понять их функцию. Позиции европейских университетов в...
76744. Первые русские анатомы XVIII века 183.81 KB
  В становление анатомии и физиологии в Петровской Академии наук внесли вклад Д. Протасов ставший тоже академиком читавшим университетский курс анатомии. В лекциях впервые использовал данные микроскопической анатомии.
76745. Отечественная анатомия Древней Руси 183.52 KB
  Анатомические знания получали при вскрытиях трупов животных и людей оказании помощи раненым и больным. С развитием иконографии анатомические знания о пропорциях тела его пластике потребовались художникам иконописцам. Некоторые анатомические сведения излагались в Люцидарии Вepтограде переводных рекомендациях древнегреческих и древнеримских ученых и врачей.