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;

}


 

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

79077. Вербальные договоры. Стипуляция. Порядок заключения и содержание 25.9 KB
  Открытые в 1933 году новые фрагменты из Институций Гая доказывают что договор стипуляции был известен уже законам XII таблиц.Несмотря однако на все смягчения необходимых формальностей в классическом римском праве всетаки прочно охранялись некоторые черты стипуляции как формального контракта: присутствие договаривающхся сторон в одном месте устный вопрос кредитора и такой же устный ответ должника совпадающий по смыслу с вопросом. Обязательство возникшее из стипуляции было обязательством строгого права и потому подлежало строго...
79078. Виды деликтов и обязательства из них. Личная обида. Кража. Неправомерное повреждение имущества. Другие виды частных деликтов 26.1 KB
  Наиболее подходящий русский термин соответствующий furtum кража. Однако furtum не совпадало полностью с современным понятием кражи. Во-первых к категории furtum в Риме относились и те деликты которые в современном праве именуются кражей и те которые теперь называются присвоением растратой и т.
79079. Владение и право собственности. Владение и держание. Виды. Установление и прекращение владения. Преторские интердикты. Защита добросовестного владения 33.21 KB
  Факты с наступлением которых лицо приобретает право собственности называются способами приобретения права собственности modus cquirendi а те юридические факты в особенности сделки которые служат основанием для приобретения права собственности называются титулом приобретения titulus cquirendi.Способы приобретения права собственности делятся на первоначальные и производные. При первоначальном приобретении права собственности нет праводателя ограниченность правомочий которого могла отразиться на содержании права приобретателя.
79080. Деятельность римских юристов. Формы их деятельности. Значение римской юриспруденции для формирования и развития права. Сабиньянская и прокулянская школы юристов 21.39 KB
  Сабиньянская и прокулянская школы юристов. В произведениях Цицерона формы деятельности римских юристов характеризуются терминами respondere cvere gere а также scribere. Термином respondere обозначается консультационная работа римских юристов дача гражданам обращавшимся к юристам советов по возбуждавшим сомнение вопросам: cvere ограждение интересов данного гражданина при совершении сделок также путем совета не включать какоелибо невыгодное условие и т.
79081. Договор имущественного найма и его виды. Договор найма вещи Поднаем. Прекращение договора найма вещи. Наем услуг. Договор подряда 31.33 KB
  Классическое римское право знало три вида договора locatio-conductio: 1) наем вещей (locatio-conductio rerum); 2) наем услуг (locatio-conductio operarum); 3) наем работы или подряд (locatio-conductio opens или opens faciendi).
79082. Договор поручения. Содержание. Особенности правоотношений, возникающих из договора поручения. Прекращение договора поручения 25.5 KB
  Особенности правоотношений возникающих из договора поручения. Прекращение договора поручения. Договор поручения состоял в том что одно лицо дозритель мандант поручало а другое лицо мандатарий поверенный принимало на себя исполнение безвозмездно какихлибо действий.
79083. Договор товарищества. Виды товарищества. Права и обязанности товарищей в отношении друг друга и в отношении третьих лиц. Вклады. Участие в прибылях и убытках. Прекращение товарищества 26.64 KB
  Виды товарищества. Прекращение товарищества. Договором товарищества societs назывался договор по которому два лица или несколько лиц объединялись для достижения какойто общей хозяйственной цели разумеется не противоречащей праву.
79084. Зарождение юридических лиц. Статус корпораций, муниципий, фиска, благотворительных учреждений. Порядок возникновения юридических лиц. Основания прекращения юридических лиц 22.12 KB
  В древнереспубликанском праве еще не было имущества корпорации это была общая собственность членов корпорации но только неделимая пока существовала корпорация. В случае прекращения корпорации имущество делилось между последним составом ее членов. Наконец третий юрист Ульпиан3 говорил что в корпоративном объединении universits не имеет значения для бытия объединения остаются ли в нем все время одни и те же члены или только часть прежних или все заменены новыми; долги объединения не являются долгами отдельных его членов и права...
79085. Защита права собственности. Иски. Ответственность добросовестного и недобросовестного владельца перед собственником. Прекращение права собственности 20.82 KB
  Этот иск представлялся собственнику для истребования вещи владение которой им утрачено. Таким образом сторонами в виндикационном процессе являлись: в качестве истца собственник не имеющий фактического владения вещью; в качестве ответчика фактический обладатель вещи как держатель так и владелец ее притом владелец как недобросовестный так и добросовестный. Добросовестный владелец отвечал за состояние вещи со времени предъявления иска. вещи регулярно получаемые от другой плодоприносящей вещи при нормальном хозяйственном ее...