Операции с последовательными контейнерами. (Лекция 2)

Содержание

Слайд 2

Свойства трех последовательных контейнеров Для данного типа Т типы vector ,


Свойства трех последовательных контейнеров

Для данного типа Т типы vector, deque

и list называются последовательными контейнерами. К этой группе относится также массив.
Слайд 3

Наборы операций с последов. контейнерами Галочка (۷) означает, что функции insert

Наборы операций с последов. контейнерами


Галочка (۷) означает, что функции insert

и erase выполняются гораздо медленнее, чем для списков.
Слайд 4

Замечания Говорят, что выполнение функций insert и erase занимает линейное время

Замечания

Говорят, что выполнение функций insert и erase занимает линейное время

для векторов и двусторонних очередей, а это означает: время их выполнения пропорционально длине последовательности, хранящейся в контейнере. В противоположность этому
все операции, помеченные галочкой ۷ (без скобок), выполняются за постоянное время, то есть время, необходимое для их выполнения, не зависит от длины последовательности.
Рассмотрим программу использования всех функции для вставки и удаления (push_back, pop_ back, push_front, pop_front, insert и erase).
Слайд 5

// insdel.cpp: Вставка и удаление элементов из // списка. #include #include

// insdel.cpp: Вставка и удаление элементов из // списка.
#include
#include


using namespace std;
void showlist(const char *str, const list &L)
{ // печать содержимого списка
list::const_iterator i;
cout << str << endl << " ";
for (i=L.begin(); i != L.end(); ++i)
cout << *i << " "; cout << endl;
}
int list_insdel()
{ list L; int x;
cout << "Enter positive integers, followed by 0:\n";
while (cin >> x, x != 0)
L.push_back(x);
showlist("Initial list:", L);
Слайд 6

Посмотрим результат: Enter positive integers, followed by 0: 10 20 30

Посмотрим результат:
Enter positive integers, followed by 0:
10 20 30 0
Initial

list:
10 20 30
Слайд 7

L.push_front(123); showlist("After inserting 123 at the beginning:", L); list ::iterator i

L.push_front(123);
showlist("After inserting 123 at the beginning:", L);
list::iterator i = L.begin();


L.insert(++i, 456);
showlist("After inserting 456 at the second position:", L);
i = L.end();
L.insert(--i, 999);
showlist("After inserting 999 just before the end:", L);
i = L.begin();
x = *i;
L.pop_front();
cout << "Deleted at the beginning: " << x << endl;
showlist("After this deletion:", L);
Слайд 8

Посмотрим результат: After inserting 123 at the beginning: 123 10 20

Посмотрим результат:
After inserting 123 at the beginning:
123 10 20 30
After

inserting 456 at the second position:
123 456 10 20 30
After inserting 999 just before the end:
123 456 10 20 999 30
Deleted at the beginning: 123
After this deletion:
456 10 20 999 30
Слайд 9

i = L.end(); x = *--i; L.pop_back(); cout showlist("After this deletion:",

i = L.end();
x = *--i;
L.pop_back();
cout << "Deleted at the end:

" << x << endl;
showlist("After this deletion:", L);
i = L.begin() ;
x = *++i;
cout << "To be deleted: " << x << endl;
L.erase (i);
showlist("After this deletion (of second element):", L);
return 0;
}
Функции для вставки и удаления здесь применяются к списку, поскольку это единственный контейнерный тип, для которого все эти функции определены и выполняются эффективно (см. вышеприведенную таблицу).
Слайд 10

Посмотрим результат: Deleted at the end: 30 After this deletion: 456

Посмотрим результат:
Deleted at the end: 30
After this deletion:
456 10

20 999
То be deleted: 10
After this deletion (of second element):
456 20 999
Приращение итератора можно выполнять с помощь функции advance (i, n).
Например, advance (i, 3)
Для сортировки списка используется метод sort() самого класса list. Например, L.sort();
Слайд 11

Замечания Рассмотрим употребление const в первых двух строчках функции showlist :

Замечания

Рассмотрим употребление const в первых двух строчках функции showlist :
void

showlist(const char *str, const list &L)
{ list::const_iterator i; …
Добавление приставки const к параметрам типа указатель или ссылка, как это сделано выше, является хорошей практикой, если такие параметры не используются для модификации объектов, на которые они указывают. Поскольку функция showlist не модифицирует ни строку str, ни список L, отсюда происходят два употребления слова const на первой из этих двух строчек.
Слайд 12

Замечания На второй строчке мы должны объявить переменную i типа const_iterator,

Замечания

На второй строчке мы должны объявить переменную i типа const_iterator,

чтобы иметь возможность использовать ее вместе с L. Это похоже на применение модификатора const к указателям: если хотим присвоить вышеобъявленный параметр str указателю р, мы сможем сделать это, только использовав const при объявлении этого указателя:
const char *p; // const необходим, поскольку str
р = str; // описан как const char *str
// типа const char *
Слайд 13

Стирание подпоследовательности Если [i1,i2) является действительным диапазоном для вектора v, мы

Стирание подпоследовательности

Если [i1,i2) является действительным диапазоном для вектора v, мы

можем стереть подпоследовательность в v, заданную этим диапазоном, следующим образом:
v.erase(i1, i2);
То же самое относится и к остальным контейнерам.
Слайд 14

Сортировка вектора #include #include #include using namespace std; int vector_sort1() {

Сортировка вектора

#include
#include
#include
using namespace std;
int vector_sort1()
{

vector v; int x;
cout << "Enter positive integers, followed by 0:\n";
while (cin >> x, x != 0) v.push_back(x);
sort (v.begin(), v.end());
cout << "After sorting: \n" ;
vector::iterator i;
for (i=v.begin();i != v.end(); ++i)
cout << *i << " " ;
cout << endl;
return 0;
}
Слайд 15

Замечания Вывод этой программы содержит введенные пользователем целые числа, отсортированные в

Замечания

Вывод этой программы содержит введенные пользователем целые числа, отсортированные в

восходящем порядке.
Вышеприведенный вызов функции sort отличается от вызовов push back, insert, begin и др. Поскольку мы пишем не v.sort(...), а просто sort(...), видно, что sort является не функцией-членом класса vector, а шаблонной функцией, которая не является членом класса. Технический термин, обозначающий такую шаблонную функцию в STL,- обобщенный (generic) алгоритм, или просто алгоритм. Строчка
#include
необходима, поскольку мы используем алгоритм sort.
Слайд 16

Сортировка массива #include #include using namespace std; int sort2() { int

Сортировка массива

#include
#include
using namespace std;
int sort2()
{ int a[10],

x, n = 0, *p;
cout << "Enter at most 10 positive integers, followed by 0:\n";
while (cin >> x, x != 0 && n < 10) a[n++] = x;
sort(a, a+n);
cout << "After sorting: \n";
for (p=a; p != a+n; p++) cout << *p << " ";
cout << endl; return 0; }
Важно заметить сходство между вызовами:
sort(v.begin(), v.end()); // в программе sort1.cpp и
sort(a, a+n); // в программе sort2.cpp.
Второй аргумент ссылается на позицию, находящуюся непосредственно после последнего элемента.
Слайд 17

Сортировка подпоследовательности массива Например, мы можем отсортировать только элементы а[3], a[4],

Сортировка подпоследовательности массива

Например, мы можем отсортировать только элементы а[3], a[4],

а[5] и а[6], написав: sort(a+З, а+7); или, что эквивалентно, sort([&a[3], &а[7]);
Слайд 18

Сортировка подпоследовательности вектора В программе sort1.cpp в векторе v также отсортируем

Сортировка подпоследовательности вектора

В программе sort1.cpp в векторе v также отсортируем

v[3], v[4], v[5] и v[6], написав:
vector v;
vector::iterator i, j;
i = v.begin() + 3;
j = v.begin() + 7;
sort (i, j); или
sort (v.begin() + 3, v.begin() + 7);
Доступ по индексу возможен, т.к. вектор является контейнером произвольного доступа, для которого определен operator[] доступа по индексу. Но, мы не можем заменить v[3] на
*(v + 3), потому что тип переменной v является классом, для которого не определен ни бинарный оператор +, ни унарный оператор *.
Слайд 19

Алгоритм STL sort Алгоритм sort требует произвольного доступа. Такой доступ обеспечивают

Алгоритм STL sort

Алгоритм sort требует произвольного доступа. Такой доступ

обеспечивают векторы, массивы и двусторонние очереди, поэтому мы могли использовать этот алгоритм в программах sort1.cpp и sort2.cpp.
Вызов sort (v.begin () , v.end());
будет работать, если мы в программ заменим всюду vector на deque, но не на list.
Список не обеспечивает произвольного доступа, поэтому с нему не применим алгоритм sort. Для сортировки списка используется метод sort() самого класса list. Например, L.sort();
Слайд 20

Инициализация контейнеров int a[3] = {10, 5, 7}; // инициализация массива

Инициализация контейнеров

int a[3] = {10, 5, 7}; // инициализация массива
int b[

] = {8, 13}; // эквивалентно int b[2] = {8, 13};
int c[3] = {4}; // эквивалентно int c[3] = {4, 0, 0};
Инициализация также возможна и для трех других типов последовательных контейнеров:
vector v(a, a+3); // int a[3] = {10, 5, 7};
deque w(a, a+3);
list x(a, a+3);
Но не только массив, а также vector, deque и list могут служить основой для инициализации контейнера того же типа:
vector v1(v.begin(), v.end());
вектор v1 станет идентичен вектору v, оба будут состоять из трех элементов типа int: 10, 5 и 7.
Слайд 21

Инициализация контейнеров Однако, мы не можем использовать значения списка х для

Инициализация контейнеров

Однако, мы не можем использовать значения списка х для

инициализации вектора v1.
vector v1(x.begin(), x.end()); // не откомпилируется
Способ инициализации обеспечивается конструкторами контейнерных классов. Существуют конструкторы, у которых первый параметр указывает размер и второй (необязательный) – значения всех элементов; можно написать:
vector v(5,8); // Пять элементов, все = равны 8.
vector v(5);
В последнем случае вектор v будет содержать пять элементов, присваивать значения элементам будем позже.
Слайд 22

Алгоритм find #include #include using namespace std; int find1() { vector

Алгоритм find

#include
#include
using namespace std;
int find1()
{

vector v; int x;
cout << "Enter positive integers, followed by 0:\n";
while (cin >> x, x != 0)
v.push_back(x);
cout << "Value to be searched for: "; cin >> x;
vector::iterator i = find(v.begin() , v.end(), x);
if (i == v.end()) cout << "Not found\n";
else
{ cout << "Found";
if (i == v.begin()) cout << " as the first element";
else cout << " after " << *--i;
} // Алгоритм find применим к вектору,
cout << endl; // двуст-й очереди, списку и массиву
return 0;
}
Слайд 23

Алгоритм find для массива #include #include using namespace std; int find2()

Алгоритм find для массива

#include
#include
using namespace

std;
int find2()
{
int a[10] , x, n = 0;
cout << "Enter at most 10 integers, followed by 0:\n";
while (cin >> x, x != 0 && n < 10) a[n++] = x;
cout << "Value to be searched for: "; cin >> x;
int *p = find (a, a+n, x) ;
if (p == a+n) cout << "Not found\n";
else
{ cout << "Found";
if (p== a) cout << " as the first element";
else cout << " after " << *--p;
}
cout << endl;
return 0;
}
Слайд 24

Алгоритм copy // copy1.cpp: Копируем вектор в список. // Первая версия:

Алгоритм copy

// copy1.cpp: Копируем вектор в список.
// Первая версия: режим замещения.
#include


#include
int copy_vector_list1()
{
int a[4] = {10, 20, 30, 40};
vector v(a, a+4);
list L(4); // Список из 4 элементов
copy(v.begin(), v.end(), L.begin());
list::iterator i;
for (i=L.begin(); i != L.end(); ++i)
cout << *i << " "; // Результат: 10 20 30 40
cout << endl;
return 0;
}
Слайд 25

Алгоритм copy и итератор вставки Рассмотрим режим вставки. list L; //

Алгоритм copy и итератор вставки

Рассмотрим режим вставки.
list L; // Пустой список.
Заменим

вызов алгоритма сору на следующий:
copy(v.begin(), v.end(), inserter(L, L.begin()));
inserter(…) называется итератором вставки.
// сору2.срр: Вторая версия: режим вставки.
int copy_vector_list2()
{ int a[4] = {10, 20, 30, 40};
vector v(a, a+4);
list L(5, 123); // 5 элементов, каждый =123
list:: iterator i = L.begin(); // ++i; ++i;
advance (i, 3); // приращение итератора
copy(v.begin(), v.end(), inserter(L, i));
for (i=L.begin(); i != L.end(); ++i)
cout << *i << " "; cout << endl; return 0;
} // Результат: 123 123 10 20 30 40 123 123 123
Слайд 26

Краткие выводы Были рассмотрены операции с последовательными контейнерами (push_back, pop_ back,

Краткие выводы

Были рассмотрены операции с последовательными контейнерами (push_back, pop_ back, push_front,

pop_front, insert и erase).
Были рассмотнрены алгоритмы (#include ):
- сортировки (векторы, массивы, двуст. очереди), для списка этот алгоритм не применим, используется метод метод sort() самого класса list.
sort (v.begin(), v.end());
sort([&a[3], &а[7]);
Но L.sort();
- поиска (векторы, массивы, двуст. очереди, списки)
i = find(v.begin() , v.end(), x);
int *p = find (a, a+n, x) ; - для массива
- Предыдущая
Географический турнир в 9-х классах
Следующая -
Здоровий спосіб життя

Похожие презентации

Основные понятия теории графов
Шпиндельные узлы
Основы моделирования вычислительных систем
Жан-Жак Руссо́
Информационно-правовая система КонсультантПлюс
мир музыкальных образов
Расчет на сейсмические воздействия по акселерограммам (во временной области) с учетом демпферов
Власть
Деловая игра «Различные аспекты и методы управления организацией»
Тема_1.1 claid.ppt
Древняя Греция III–II тыс. до н.э
Презентация МХК по программе Даниловой Г.И. 10 класс. Из опыта работы учителя изобразительного искусства Москаль Т.А. МОУ «СОШ №83»
Презентация Нептуна
Урок 8 Тема Художественная культура
Проектная деятельность как способ формирования творческих способностей на уроках русского языка Е.С. Ванзитлер учитель русско
Перспективы реформирования бюджетной сети в свете принятия Федерального закона от 8 мая 2010 г. № 83-ФЗ о совершенствовании правов
Презентация "Музыка, застывшая в камне" - скачать презентации по МХК
Капитальное строительство в ядерной энергетике Генеральный план АЭС
Способ крепления балки штырем для фиксации балки в креплении
ЛІНГВІСТИЧНА ЕКСПЕРТИЗА ТЕКСТУ
Солнце и растения
Формы работы классного руководителя с семьёй Автор: учитель начальных классов МОУ "СОШ с. Ездочное" Лягуша И.В.
Регистрация на курсах повышения квалификации «Гармония»
Динамика систем с конечным числом степеней свободы масс
Культура раннего Возрождения в Италии: Сандро Боттичелли
Языковая ситуация в Эльзасе
Распределение обработки данных
Презентация на тему "Повреждения органа зрения" - скачать презентации по Медицине
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть