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;

}


 

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

37434. Разработка замкнутой (бессбросной) системы производственного водообеспечения техногенного комплекса 1.13 MB
  Результатом выполнения курсового проекта является составление замкнутой схемы производственного водообеспечения техногенного комплекса. В этой схеме исключён сброс сточных вод в водный объект и значительно уменьшен расход воды, забираемой из источника водоснабжения.
37435. Організація обліку готової сільськогосподарської продукції 239.83 KB
  Визначити, класифікувати та описати порядок оцінки готової сільськогосподарської продукції; визначити основні завдання організації обліку готової сільськогосподарської продукції; визначити нормативно-правове регулювання обліку готової сільськогосподарської продукцції; визначити особливості документування господарсьих операцій повʼязаних з випуском готової сілльськогосподарської продукції...
37436. Управління пасажирським судном 233.5 KB
  Старший бортпровідник безпосередньо підкоряється помічникові капітана по пасажирській частині, керує роботою бортпровідників, днювальних, що обслуговують пасажирські приміщення, і забезпечує стан пасажирських приміщень у належному порядку.
37437. История России. Шпаргалка 228.68 KB
  Империя – это конгломерат народов, которые образуют экономическую, политическую и в зачатке культурную систему, где ведущая определяющая, объединяющая роль принадлежит одному или нескольким народам, в то время как остальные народы находятся в состоянии зависимости и подчинения, хотя и извлекают определенные выгоды из своего положения в рамках данного конгломерата.
37438. Икемділік ұғымы. Сұраныс пен ұсыныс икемділігі 154 KB
  Рыноктық экономика – бұл сұраныс пен ұсыныстың үздіксіз арақатынасы. Мұндай қарым-қатынасты қарапайым моделінің тууы, экономикалық ғылым тарихында үлкен маңызды дәуір болып саналады. Сол мезеттен бері екі ғасырдан астам уақыт өтсе де, рыноктық экономикамен теориялық танысу осыдан басталады. Өйткені осы модель арқылы барлық экономикалық процестер ашылып көрсетіледі.
37439. Финансовый мененджмент 212.87 KB
  Финансовый менеджмент– это управление финансово-хозяйственной деятельностью фирмы на основе использования современных методов. Основным лицом ответственным за достижение цели финансового менеджмента, является вице-президент по финансовым вопросам (заместитель директора по финансовым вопросам).
37440. Обеспечение единства измерений в стране. Государственный метрологический надзор. Цели надзора, сфера распространения. Виды метрологического надзора 19.86 KB
  Проверки проводят должностные лица Госстандарта России - главные государственные инспекторы и государственные инспекторы по обеспечению единства измерений, действующие на соответствующих территориях и аттестованные в установленном порядке.
37441. Виды и средства измерений. Виды эталонов. Стандартные образцы 19.55 KB
  Прямые измерения — это непосредственное сравнение физической величины с ее единицей. Например, при определении длины предмета с помощью линейки происходит сравнение искомой величины (количественного выражения значения длины) с мерой, т. е. единицей измерения.
37442. Факторы, сохраняющие качество товаров 16.91 KB
  Режим хранения - это совокупность условий, при которых товар сохраняет свое качество. Для каждого товара необходим определенный режим хранения, зависящий от его состава и свойств. При правильном режиме не только сохраняется качество, но и снижаются потери товаров.