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;

}


 

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

32604. Учет долгосрочных и краткосрочных кредитов и займов 48.5 KB
  Операции связанные с получением и погашением банковских кредитов и займов отражаются в бухгалтерском учете на счетах 66 Расчеты по краткосрочным кредитам и займам и 67 Расчеты по долгосрочным кредитам и займам . Причитающиеся по полученным кредитам и займам проценты к уплате отражают по кредиту счета 66 67 в корреспонденции с дебетом счета 91. Суммы полученных организацией краткосрочных кредитов и займов отражаются по кредиту счета 66 Расчеты по краткосрочным кредитам и займам и дебету счетов 50 Касса 51 Расчетные счета 52...
32605. Калькулирование себестоимости продукции животноводства 52.5 KB
  Данные первичных документов по учёту приплода и прироста живой массы систематизируются в отчёте о движении скота и птицы на фермах форма №223АПК. Если мы приходуем приплод и прирост живой массы то Д11 К 20 2 Если мы приходуем молоко шерсть яйца то Д 43 2 К 20 2. Калькулирование себестоимости продукции животноводства Порядок исчисления себестоимости продукции КРС молочного направления В молочном скотоводстве по основному стаду выделяют два объекта калькулирования приплод и молоко по животным на выращивании прирост живой массы и...
32606. Вспомогательными производства 42 KB
  Учёт затрет во вспомогательных производствах ведется на счете 23 Вспомогательные производства. Он имеет следующие субсчета: 23 1 Ремонтные мастерские; 23 2 Ремонт зданий и сооружений; 23 3 Машиннотракторный парк; 23 4 Автомобильный транспорт; 23 5 Энергетические производства хозяйства; 23 6 Водоснабжение; 23 7 Гужевой транспорт; 23 8 Прочие вспомогательные производства. Аналитический учёт по счёту 23 ведут в производственных отчётах по вспомогательным производствам форма № 83АПК который открывается на...
32607. Особенности организации учёта и исчисления себестоимости продукции основных видов промышленных производств 52 KB
  Для первичных документов по учету сырья и выхода готовой продукции предусмотрен отчёт о переработке продукции форма № 180АПК. В первом разделе отчёта учитывается количество израсходованного сырья во втором количество полученной продукции. Схема учета затрат на производство и выхода продукции животноводства представлена на рисунке 6. По дебету счета собираются затраты а по кредиту учитывается выход продукции в течении года по плановой себестоимости с доведением в конце года или месяца до фактической в зависимости от вида производств.
32609. Докладно описати вантажні станції, розташовані на під’їзних коліях, виділивши: 1) умови розміщення станцій; 2) характеристика портових станцій і станцій паромних переправ; 3) характеристика перевантажувальних станцій 146 KB
  Докладно описати вантажні станції розташовані на підїзних коліях виділивши: 1 умови розміщення станцій; 2 характеристика портових станцій і станцій паромних переправ; 3 характеристика перевантажувальних станцій. 1 В пунктах стикування залізниць різної колії залізничних доріг з іншими видами транспорту і на п к підприємств споруджуються спеціальні вантажні станції. На основній станції виконується передача вагонів від УЗ на п к розформування поїздів і підбір вагонів по окремим пунктам подавання вагонів на вантажні станції або...
32610. Основні норми проектування плану і поздовжнього профілю дільничних станцій 311.5 KB
  Розміщення колій на горизонтальному майданчику полегшує умови рушення поїздів в обох напрямках знижує небезпеку уходу вагонів від товчка при маневрах або під впливом вітру. Станція окремі парки і витяжні колії повинні розташовуватися в плані на прямих дільницях що поліпшує умови видимості під час руху поїзда і маневрової роботи рушенні поїздів з місця. Головні колії на підходах до станції слід проектувати на прямих або кривих можливо більшого радіусу що створює умови для забезпечення безпечності і плавності руху поїздів....
32612. Докладно описати такі питання: – призначення і класифікація сортувальних станцій; – класифікація сортувальних станцій; – основні операції, що виконуються на сортувальних станціях; - основні пристрої, які проектуються на сортувальних станціях 841 KB
  Сортировочные станции СС предназначены главным образом для массовой сортировки вагонов по назначениям плана формирования и организации новых составов сквозных участковых сборных вывозных передаточных и других поездов. Основные операции которые выполняются на СС: операции по формированиюрасформированию поездов передаче вагонов на подъездные пути предприятий промышленного транспорта и приему вагонов с подъездных путей подборке группировке вагонов передач на грузовые станции узла и поездов на портовые и паромные станции а...