Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Информатика, программирование->Контрольная работа
В языке C блоком считается последовательность объявлений, определений и операторов, заключенная в фигурные скобки. Объект языка C может быть объявлен ...полностью>>
Информатика, программирование->Контрольная работа
Препроцессор языка C – это программа, выполняющая обработку исходного кода для передачи его компилятору, в процессе которой происходит подстановка дир...полностью>>
Информатика, программирование->Контрольная работа
Для изменения порядка интерпретации можно использовать круглые скобки. Если при выполнении пункта 2 справа встречается закрывающая круглая скобка, то ...полностью>>
Информатика, программирование->Контрольная работа
Поле имя_типа определяет имя нового перечислимого типа. Поле список_названий определяет имена констант перечислимого типа и их значения. Имена констан...полностью>>

Главная > Лекция >Информатика, программирование

Сохрани ссылку в одной из сетей:

Стандартная библиотека шаблонов 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//включение заголовочного файла шаблонного класса списка

#include

using namespace std;//стандартное пространство имен

int _tmain()

{

// TODO: Please replace the sample code below with your own.

//Console::WriteLine(S"Hello World");

list 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 ::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

#include

#include

#include

using namespace std;

typedef map > 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<

}

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!!!"<

fam="Petrov;

dic1.insert(make_pair(fam, 6666666));

dic1.erase(fam);

in.close();

return 0;

}


Похожие страницы:

  1. Стандартная библиотека шаблонов

    Лабораторная работа >> Информатика, программирование
    Стандартная библиотека шаблонов 1. Цель работы Освоить технологию обобщенного программирования с использованием библиотеки стандартных шаблонов (STL) языка C++. 2. Темы ... памяти, который по умолчанию является стандартным. В классе vector определены ...
  2. Основы объектно-ориентированного программирования. Конспект лекций

    Конспект >> Информатика, программирование
    Основы объектно-ориентированного программирования Введение Язык С++ был создан как объектно-ориентированное продолжение одного из самых популярных в мире языков для разработки коммерческих программ. Язык С был разработан как нечто среднее между языками ...
  3. Языки программирования (6)

    Реферат >> Информатика
    ... Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены ... , Ruby, Tcl и др. Широко используется стандартная библиотека шаблонов STL языка C++. Фундаментальными строительными блоками для ...
  4. Объектно-ориентированное программирование (5)

    Книга >> Информатика, программирование
    ... это сложившиеся к данному моменту шаблоны вычислений и использования вычислительных ресурсов, ... По последнему варианту трактуются шаблоны в С++. 1.3. Причины ... обычно невозможно, поскольку подпрограммы стандартных библиотек и операционной системы находятся ...
  5. Языки программирования. Курс лекций

    Конспект >> Информатика, программирование
    ... быть» диапазон [1..K]. В С++ множество «ушло» в стандартную библиотеку языка(STL: map, set, multiset). Java Также ... Шаблоны-классы и шаблоны- функции. Параметры шаблонов. Вывод параметров шаблонов. Генерация кода по шаблонам. Частичная специализация шаблонов ...

Хочу больше похожих работ...