4972
Стандартная библиотека шаблонов STL
Лекция
Информатика, кибернетика и программирование
Стандартная библиотека шаблонов STL Практическая деятельность программистов в течение нескольких десятков лет привела широкому распространению ряда способов организации структур данных, например, массив, список, очередь и т.д. Эти структуры данных с...
Русский
2012-11-30
25.77 KB
20 чел.
Практическая деятельность программистов в течение нескольких десятков лет привела широкому распространению ряда способов организации структур данных, например, массив, список, очередь и т.д. Эти структуры данных стали стандартными. Для использования стандартных структур данных при решении различных задач была разработана стандартная библиотека шаблонов, предназначенных для формирования контейнерных классов
Контейнер это объект, содержащий набор других объектов, организованный определенным образом.
Назначение контейнеров управление наборами (коллекциями) объектов определенного типа.
Примеры контейнеров: массив, список.
Работа с контейнерами поддерживается с помощью контейнерных классов.
Для каждого типа контейнера в соответствующем контейнерном классе определены методы для работы с его элементами.
Свойства контейнеров:
- для каждого типа контейнера в контейнерном классе определены методы для работы с его элементами независимо от типа элементов
Достинства:
- повышение надежности, переносимости и универсльности
- уменьшение сроков и стоимости разработки программ
Недостатки:
- снижение быстродействия
- трудность изучения
Классификация контейнеров:
последовательные
ассоциативные
Последовательные контейнеры
векторы (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 | |
Сортировочные станции СС предназначены главным образом для массовой сортировки вагонов по назначениям плана формирования и организации новых составов сквозных участковых сборных вывозных передаточных и других поездов. Основные операции которые выполняются на СС: операции по формированиюрасформированию поездов передаче вагонов на подъездные пути предприятий промышленного транспорта и приему вагонов с подъездных путей подборке группировке вагонов передач на грузовые станции узла и поездов на портовые и паромные станции а... | |||