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;

}


 

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

32515. ПРОЕКТНАЯ ДЕЯТЕЛЬНОСТЬ ШКОЛЬНИКОВ И ЕЕ ЭТАПЫ 153.5 KB
  Большие возможности в этом отношении открывает метод проектов или метод учебных проектов наряду с другими нетрадиционными методами получающий сейчас всё большее распространение. Метод проектов это совокупность учебнопознавательных приёмов которые позволяют решить ту или иную проблему в результате самостоятельных действий учащихся с обязательной презентацией этих результатов. Метод проектов известный также как метод проблем возник ещё в 1920е годы в США. метод проектов нашёл широкое распространение и приобрёл большую популярность за...
32516. ИТОГОВЫЙ КОНТРОЛЬ В ФОРМЕ УСТНОГО ЭКЗАМЕНА И ТЕСТИРОВАНИЯ 82 KB
  Избранные вопросы методики преподавания информатики ИТОГОВЫЙ КОНТРОЛЬ В ФОРМЕ УСТНОГО ЭКЗАМЕНА И ТЕСТИРОВАНИЯ Итоговый контроль. Перечень экзаменационных материалов по информатике ничем не отличается от перечня материалов по другим предметам вопросы билеты практические задания. Не вдаваясь в глубокий анализ причин по которым это происходит необходимо тем не менее определить в каких границах учитель или методист свободен при составлении билетов: в настоящее время билеты по информатике рекомендованные МО РФ можно взять за основу...
32517. ИТОГОВЫЙ КОНТРОЛЬ В ФОРМЕ ЗАЩИТЫ РЕФЕРАТОВ И ПРОЕКТОВ 107 KB
  Одной из основных целей творческой работы в виде реферата является комплексное исследование проблемы с использованием различных источников информации. Специфической особенностью информатики является ее высокий интегрирующий потенциал: основным объектом информатики является информация соответственно рассматриваются эффективные методы и приемы работы с информацией; осваиваются средства обработки хранения восприятия и передачи информации в том числе универсальное средство компьютер; теоретические знания и знания технологии работы с...
32518. ИНТЕГРИРОВАННЫЕ УРОКИ И МЕТОДИКА ИХ ПРОВЕДЕНИЯ 1.19 MB
  1 Квадратный трехчлен 4 Решение уравнений и запись корней. 1 Решение неравенств и запись ответов. 1 Решение задач и запись корней. 1 Решение заданий.
32519. ЭКСКУРСИИ ПО ИНФОРМАТИКЕ И МЕТОДИКА ИХ ПРОВЕДЕНИЯ 73.5 KB
  Избранные вопросы методики преподавания информатики ЭКСКУРСИИ ПО ИНФОРМАТИКЕ И МЕТОДИКА ИХ ПРОВЕДЕНИЯ УРОКЭКСКУРСИЯ Самый термин экскурсия произошёл от латинского слова excurro экскурро что значит выбегаю. Следовательно само название экскурсии указывает на одну из существенных черт этой формы организации учебной работы а именно выведение учащихся за пределы школы к изучаемому объекту. Таким образом экскурсия характеризуется тремя существенными признаками: вопервых на экскурсии обучение и воспитание проводятся на основе...
32520. ДИСТАНЦИОННОЕ ОБУЧЕНИЕ И ЕГО ПРИНЦИПЫ 97.5 KB
  Термин дистанционное обучение означает конкретную форму обучения которая основана на конкретных технологических и методологических решениях и может дополнять другие традиционные формы обучения например очную классноурочную или в отдельных случаях заменять их например если учащемуся недоступны иные варианты связи с удаленностью места проживания или с проблемами со здоровьем. Название дистанционное образование не следует считать правильным поскольку под термином образование понимается весь процесс обучения и воспитания...
32521. ШКОЛЬНЫЕ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ 312.5 KB
  Избранные вопросы методики преподавания информатики ШКОЛЬНЫЕ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ ПОЛОЖЕНИЕ о школьных и городских предметных олимпиадах школьников. Общие положения Настоящее Положение определяет статус цели и задачи школьных и городских олимпиад порядок их проведения и финансирования. Основными целями и задачами олимпиад являются: пропаганда научных знаний и развитие у учащихся интереса к научной деятельности создание необходимых условий для выявления одаренных детей активизация работы факультативов спецкурсов кружков....
32522. ОСНОВНЫЕ НАПРАВЛЕНИЯ ИСПОЛЬЗОВАНИЯ ПРОГРАММНЫХ СРЕДСТВ В УЧЕБНОМ ПРОЦЕССЕ ОБЩЕОБРАЗОВАТЕЛЬНОЙ ШКОЛЫ. РЕАЛИЗАЦИЯ ЗАДАЧ ИСПОЛЬЗОВАНИЯ ПРОГРАММНЫХ СРЕДСТВ ПРИ ИЗУЧЕНИИ ОБЩЕОБРАЗОВАТЕЛЬНЫХ ДИСЦИПЛИН. ПРОГРАММНЫЕ СРЕДСТВА ДЛЯ ФОРМИРОВАНИЯ РАЗЛИЧНЫХ НАВЫКОВ 60.5 KB
  ПРОГРАММНЫЕ СРЕДСТВА ДЛЯ ФОРМИРОВАНИЯ РАЗЛИЧНЫХ НАВЫКОВ. Выделим среди основных направлений применения ПС в обучении четыре аспекта: философский формирование системноинформационной картины мира; инструментальный знакомство с основами информационных технологий формирование навыков работы с информацией; практический применение умений использования средств ИТ в учебной деятельности; психологический поддержание мотивации использования средств ИТ в учебной деятельности развитие психологических характеристик учащихся. Раскроем в...
32523. СТРУКТУРА ТЕХНОЛОГИИ ПРИМЕНЕНИЯ ПРОГРАММНЫХ СРЕДСТВ В УЧЕБНОМ ПРОЦЕССЕ 49.5 KB
  ППС и методика их использования СТРУКТУРА ТЕХНОЛОГИИ ПРИМЕНЕНИЯ ПРОГРАММНЫХ СРЕДСТВ В УЧЕБНОМ ПРОЦЕССЕ Структура технологии применения программных средств в учебном процессе Технология искусственно организуемый процесс в отличие от природных явлений протекающих естественно с заданными начальными условиями известным результатом и способами достижения этого результата. Под технологией обучения будем понимать системно организованный процесс передачи общественных знаний обучаемым при котором заранее устанавливают объем передачи знаний...