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;

}


 

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

79353. Відомий і невідомий український меценат Петро Яцик 27 KB
  Мета: ознайомити учнів школи з відомим меценатом Петром Яциком; практична формування вміння розуміти що українська мова -– це скарб народу який учні повинні здобувати із задоволенням і досягати успіхів у навчанні завдяки плідній творчій праці; виховна прищеплювати любов до української мови...
79354. Гра-подорож «Мандри зайки-морквоїда» 55 KB
  Молодші школярі разом з героєм подорожі та своїми старшими друзями мандрують видатними датами календаря знайомляться з історією рідної країни здійснюють екскурсії по місцях славетного минулого вивчають історію козацтва рідного краю.
79356. Сценарий школьного праздника «Последний звонок» 81.5 KB
  Звучит музыка выходят одиннадцатиклассники. Так пусть начнет сегодня торжество Своим свободным голосом держава Звучит Гимн Украины Вед: Сегодня наш праздник мы назвали не совсем традиционно – Школьная моя семья. Звучит музыка выходят выпускники читают слова о первом учителе.