Лекция 7. Контейнеры. std::vector и std::list. Приоритет операций

1. ООП 2021 Лекция 7 Контейнеры. std::vector и std::list. Приоритет операций. [email protected]

1

2. vector

представляют собой контейнеры последовательностей,
представляющие массивы, которые могут меняться по размеру.
Подобно массивам, векторы используют смежные места хранения
для своих элементов, что означает, что их элементы также могут быть
доступны с помощью смещений на обычных указателях к его элементам и
так же эффективно, как и в массивах. Но в отличие от массивов их размер
может изменяться динамически, при этом хранилище автоматически
обрабатывается контейнером.
Внутри векторы используют динамически выделенный массив для
хранения своих элементов. Этот массив, возможно, потребуется
перераспределить для увеличения размера при вставке новых элементов,
что подразумевает выделение нового массива и перемещение в него всех
элементов. Это относительно дорогостоящая задача с точки зрения
времени обработки, и, следовательно, векторы не перераспределяются
каждый раз, когда элемент добавляется в контейнер.
2

3. vector

Вместо этого векторные контейнеры могут выделять некоторое
дополнительное хранилище для размещения для возможного роста, и, таким
образом, контейнер может иметь реальную емкость, большую, чем
хранилище, строго необходимое для содержания его элементов (то есть его
размера).
Библиотеки могут реализовывать различные стратегии роста для баланса
между использованием памяти и перераспределением, но в любом случае
перераспределение должно происходить только при логарифмически
растущих интервалах размера, так что вставка отдельных элементов в конце
вектора может быть обеспечена амортизированным постоянным временем
сложности ( push_back).
Поэтому, по сравнению с массивами, векторы потребляют больше памяти
в обмен на способность управлять хранилищем и динамически развиваться
эффективным образом.
По сравнению с другими контейнерами динамической последовательности
(deque, list и forward_list), векторы очень эффективно получают доступ к своим
элементам (подобно массивам) и относительно эффективному добавлению
или удалению элементов с его конца. Для операций, связанных с вставкой или
удалением элементов в позициях, отличных от конца, они выполняют хуже
других и имеют менее согласованные итераторы и ссылки, чем списки и
3
forward_lists.

4. Свойства класса vector

Sequence
Элементы в контейнерах последовательностей упорядочены в
строгой линейной последовательности. Доступ к отдельным элементам
осуществляется по их положению в этой последовательности.
Dynamic array
Позволяет осуществлять прямой доступ к любому элементу в
последовательности, даже через арифметику указателя, и обеспечивает
относительно быстрое добавление / удаление элементов в конце
последовательности.
Allocator-aware
Контейнер использует объект-распределитель, чтобы динамически
обрабатывать его потребности в памяти
4

5. Шаблонные аргументы класса vector

template<class _Ty,
class _Alloc = allocator<_Ty> >
class vector
Template parameters
_Ty
Тип элементов.
Выделяется как вектор типа элемента :: value_type.
_Alloc
Тип объекта-распределителя, используемый для определения модели
распределения хранилища. По умолчанию используется шаблон класса
распределителя, который определяет простейшую модель распределения
памяти.
Выделяется как вектор типа элемента :: allocator_type.
5

6. Конструкторы

C++98:
explicit vector (const allocator_type& alloc = allocator_type());
explicit vector (size_type n, const value_type& val = value_type(),
const allocator_type& alloc = allocator_type());
template <class InputIterator>
vector (InputIterator first, InputIterator last,
const allocator_type& alloc = allocator_type());
vector (const vector& x);
6

7.

C++14:
(1) vector(); // Создает пустой контейнер без элементов
explicit vector (const allocator_type& alloc); // с распределителем памяти
(2) explicit vector (size_type n, const allocator_type& alloc = allocator_type());
vector (size_type n, const value_type& val,
const allocator_type& alloc = allocator_type());
// Создает контейнер из n элементов. Каждый элемент является копией val
// (если она предоставлена).
(3)
template <class InputIterator>
vector (InputIterator first, InputIterator last,
const allocator_type& alloc = allocator_type());
// конструктор диапазона
// Создает контейнер с таким количеством элементов,как диапазон [первый,
// последний), при этом каждый элемент создается из соответствующего
// элемента в этом диапазоне в том же порядке
(4) vector (const vector& x);
vector (const vector& x, const allocator_type& alloc);
// конструктор копирования (и копирование с помощью распределителя)
// Создает контейнер с копией каждого из элементов в xв том же порядке
(5) vector (vector&& x); // конструктор перемещения
(6) vector (initializer_list<value_type> il, const allocator_type& alloc =
allocator_type());
7
Эти объекты автоматически создаются из деклараторов списка
инициализаторов.

8. Пример

#include <iostream>
#include <vector>
int main (){ // constructors used in the same order as described above:
std::vector<int> first;
// empty vector of ints
std::vector<int> second (4,100);
// four ints with value 100
std::vector<int> third (second.begin(),second.end()); // iterating through second
std::vector<int> fourth (third);
// a copy of third
// the iterator constructor can also be used to construct from arrays:
int myints[ ] = {16,2,77,29};
std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );
std::cout << "The contents of fifth are:";
for (std::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Output:
The contents of fifth are: 16 2 77 29
8

9. vector::operator =

C++11:
Копирование элементов:
vector& operator= (const vector& x);
Перемещение элементов:
vector& operator= (vector&& x);
Инициализация списком
vector& operator= (initializer_list<value_type> il);
9

10. Пример

#include <iostream>
#include <vector>
int main ()
{
std::vector<int> foo (3,0);
std::vector<int> bar (5,0);
bar = foo;
foo = std::vector<int>();
std::cout << "Size of foo: " << int(foo.size()) << '\n';
std::cout << "Size of bar: " << int(bar.size()) << '\n';
return 0;
}
Output:
Size of foo: 0
Size of bar: 3
10

11. vector::assign

C++11:
Назначает новое содержимое вектору, заменяет его текущее
содержимое и соответственно изменяет его размер.
Заполнение через диапазон:
template <class InputIterator>
void assign (InputIterator first, InputIterator last);
Заполнение одним числом:
void assign (size_type n, const value_type& val);
Инициализация списком
void assign (initializer_list<value_type template <class InputIterator>)
11

12. Пример

#include <iostream>
#include <vector>
int main (){
std::vector<int> first;
std::vector<int> second;
std::vector<int> third;
first.assign (7,100);
// 7 ints with a value of 100
std::vector<int>::iterator it;
it=first.begin()+1;
second.assign (it,first.end()-1); // the 5 central values of first
int myints[ ] = {1776,7,4};
third.assign (myints,myints+3); // assigning from array.
std::cout << "Size of first: " << int (first.size()) << '\n';
std::cout << "Size of second: " << int (second.size()) << '\n';
std::cout << "Size of third: " << int (third.size()) << '\n';
return 0;
}
Output:
Size of first: 7
Size of second: 5
Size of third: 3
12

13. vector::resize

Изменяет размер вектора.
C++11:
void resize (size_type n);
void resize (size_type n, const value_type& val);
Если n меньше текущего размера контейнера, содержимое сводится к
его первым n элементам, удаляя их за пределы (и уничтожая их).
Если n больше текущего размера контейнера, содержимое
расширяется, вставляя в конец столько элементов, сколько необходимо
для достижения размера n. Если значение val указано, новые элементы
инициализируются как копии val, иначе они инициализируются каким-то
значением.
Если n больше, чем текущая емкость контейнера, происходит
автоматическое перераспределение выделенного пространства для
хранения.
Обратите внимание, что эта функция изменяет фактическое
содержимое контейнера, вставляя или стирая элементы из него.
13

14. Пример

#include <iostream>
#include <vector>
int main () {
std::vector<int> myvector;
// set some initial content:
for (int i=1;i<10;i++) myvector.push_back(i);
myvector.resize(5);
myvector.resize(8,100);
myvector.resize(12);
std::cout << "myvector contains: << endl;
for (int i=0;i<myvector.size();i++)
std::cout << ' ' << myvector[i];
std::cout << '\n';
Output:
myvector contains:
return 0; }
1 2 3 4 5 100 100 100 0 0 0 0
14

15. vector::size, vector::capacity(), vector::max_size()

size - возвращает размер вектора
capacity - возвращает размер выделенной емкости.
max_size - возвращает максимально возможный размер вектора
#include <iostream>
#include <vector>
int main () {
std::vector<int> myvector;
// set some content in the vector:
for (int i=0; i<100; i++) myvector.push_back(i);
std::cout << "size: " << (int) myvector.size() << '\n';
std::cout << "capacity: " << (int) myvector.capacity() << '\n';
std::cout << "max_size: " << (int) myvector.max_size() << '\n';
return 0;
Output:
}
size: 100
capacity: 128
max_size: 1073741823
15

16. push_back и pop_back

#include <iostream>
#include <vector>
int main () {
std::vector<int> myvector;
int sum (0);
myvector.push_back (100);
myvector.push_back (200);
myvector.push_back (300);
while ( ! myvector.empty())
{
sum+=myvector.back();
myvector.pop_back();
}
std::cout << "The elements of myvector add up to " << sum << '\n';
return 0;
}
Output: The elements of myvector add up to 600
16

17. insert

#include <iostream>
#include <vector>
int main () {
std::vector<int> myvector (3,100);
std::vector<int>::iterator it;
it = myvector.begin();
it = myvector.insert ( it , 200 );
myvector.insert (it,2,300);
it = myvector.begin(); // "it" более недействителен, получите новый
std::vector<int> anothervector (2,400);
myvector.insert (it+2,anothervector.begin(),anothervector.end());
int myarray [ ] = { 501,502,503 };
myvector.insert (myvector.begin(), myarray, myarray+3);
std::cout << "myvector contains<< std:: endl:;
for (it=myvector.begin(); it<myvector.end(); it++)
std::cout << ' ' << *it;
std::cout << '\n';
return 0; }
Output: myvector contains:
501 502 503 300 300 400 400 200 100 100 100
17

18. erase

#include <iostream>
#include <vector>
int main (){
std::vector<int> myvector;
// set some values (from 1 to 10)
for (int i=1; i<=10; i++) myvector.push_back(i);
myvector.erase (myvector.begin()+5); // erase the 6th element
// erase the first 3 elements:
myvector.erase (myvector.begin(),myvector.begin()+3);
std::cout << "myvector contains:";
for (unsigned i=0; i<myvector.size(); ++i)
std::cout << ' ' << myvector[i];
std::cout << '\n';
return 0;
}
Output: myvector contains: 4 5 7 8 9 10
18

19. vector::operator [ ] и vector::at

Возвращает ссылку на элемент в позиции n в векторном контейнере.
Аналогичная функция-член, vector :: at, имеет то же поведение, что и
эта операторная функция, за исключением того, что vector :: at проверен
на границах и сигнализирует, если запрошенная позиция вне допустимого
диапазона, выбрасывая исключение out_of_range.
reference operator [ ] (size_type n);
const_reference operator [ ] (size_type n) const;
reference at (size_type n);
const_reference at (size_type n) const;
19

20. Пример

#include <iostream>
#include <vector>
int main () {
std::vector<int> myvector (10); // 10 zero-initialized elements
std::vector<int>::size_type sz = myvector.size();
for (unsigned i=0; i<sz; i++) myvector[i]=i; // assign some values:
// reverse vector using operator [ ]:
for (unsigned i=0; i<sz/2; i++) {
int temp;
temp = myvector[sz-1-i];
myvector[sz-1-i] = myvector[i];
myvector [i] = temp;
}
std::cout << "myvector contains:"<< '\n';
for (unsigned i=0; i<sz; i++)
std::cout << ' ' << myvector[i];
std::cout << '\n';
return 0; }
Output:
myvector contains:
9876543210
20

21. vector::reserve

void reserve (size_type n);
изменяет емкость – capacity
Требует чтобы векторная емкость была по крайней мере достаточной,
чтобы содержать n элементов.
Если n больше текущей емкости вектора, функция заставляет
контейнер перераспределять его хранилище, увеличивая его емкость до n
(или больше).
Во всех других случаях вызов функции не вызывает
перераспределения, и емкость вектора не изменяется.
Эта функция не влияет на размер вектора и не может изменять ее
элементы.
21

22. Пример

#include <iostream>
#include <vector>
int main () {
std::vector<int>::size_type sz;
std::vector<int> foo;
sz = foo.capacity();
std::cout << "making foo grow:\n";
for (int i=0; i<100; ++i) {
foo.push_back(i);
if (sz!=foo.capacity()) {
sz = foo.capacity();
std::cout << "capacity changed: "
<< sz << '\n';
}
}
std::vector<int> bar;
sz = bar.capacity();
// единственное отличие от foo
bar.reserve(100);
std::cout << "making bar grow:\n";
for (int i=0; i<100; ++i) {
bar.push_back(i);
if (sz!=bar.capacity()) {
sz = bar.capacity();
std::cout << "capacity changed: "
<< sz << '\n';
}
}
return 0;
}
22

23.

making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128
making bar grow:
capacity changed: 100
23

24. vector::begin() и vector::end()

iterator begin();
const_iterator begin() const;
Возвращает итератор произвольного доступа, указывающий на
первый элемент в векторе.
Если контейнер пуст, возвращаемое значение итератора не должно
быть разыменовано, потому что возвращаемый итератор = end
……………………………………………..
iterator end();
const_iterator end() const;
Возвращает итератор, ссылающийся на элемент, следующий за
последним элементом в векторном контейнере.
24

25. Пример

#include <iostream>
#include <vector>
int main ()
{
std::vector<int> myvector;
for (int i=1; i<=5; i++) myvector.push_back(i);
std::cout << "myvector contains:";
for (std::vector<int>::iterator it = myvector.begin() ; it != myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Output:
myvector contains: 1 2 3 4 5
25

26. vector::data()

value_type* data() noexcept;
const value_type* data() const noexcept
Возвращает прямой указатель на массив памяти, используемый
внутренне вектором для хранения принадлежащих ему элементов.
Поскольку элементы в векторе гарантированно сохраняются в
смежных местах хранения в том же порядке, что и представленный
вектором, извлеченный указатель может быть смещен для доступа к
любому элементу массива.;
26

27. Пример

#include <iostream>
#include <vector>
int main (){
std::vector<int> myvector (5);
int* p = myvector.data();
int *p1= &myvector[0];
*p = 10;
++p;
*p = 20;
p[2] = 100;
std::cout << "myvector contains:"
<< std::endl;
for (unsigned i=0; i<myvector.size(); ++i)
std::cout << ' ' << myvector[i];
std::cout << '\n';
return 0;
}
27

28. vector::swap

void swap (vector& x);
Обменивает содержимое контейнера содержимым x, которое является
другим векторным объектом того же типа. Размеры могут отличаться.
После вызова этой функции-члена элементами в этом контейнере
являются те, которые были в x перед вызовом, а элементы x - это те,
которые были в этом. Все итераторы, ссылки и указатели остаются
действительными для обмениваемых объектов.
Обратите внимание, что существует функция, не являющаяся членом,
с тем же именем, swap, перегрузка этого алгоритма с оптимизацией,
которая ведет себя как эта функция-член.
28

29. Пример

#include <clocale>
#include <iostream>
#include <vector>
int main (){
setlocale(LC_ALL,"Rus");
std::vector<int> foo (3,100); // three ints with a value of 100
std::vector<int> bar (5,200); // five ints with a value of 200
std::vector<int>::iterator it= foo.begin();
std::cout<< "значение итератора, укзаывающего на начало вектора foo: "
<< *it<< std::endl;
foo.swap(bar);
std::cout<< "значение итератора, укзаывающего на начало вектора, после swap: "
<< *it<< std::endl;
it=foo.begin();
std::cout<< "значение вновь определенного итератора на начало foo: "
<< *it<< std::endl;
29

30.

std::cout << "foo contains:";
for (unsigned i=0; i<foo.size(); i++)
std::cout << ' ' << foo[i];
std::cout << '\n';
std::cout << "bar contains:";
for (unsigned i=0; i<bar.size(); i++)
std::cout << ' ' << bar[i];
std::cout << '\n';
return 0;
}
30

31. std::list

template < class T, class Alloc = allocator<T> > class list;
Списки представляют собой контейнеры последовательностей, которые
позволяют выполнять операции вставки и удаления с постоянным временем в
любом месте последовательности и итерации в обоих направлениях.
Список контейнеров реализуется как двусвязные списки;
Сопоставленные списки могут хранить каждый из элементов, которые они
содержат, в разных и не связанных друг с другом местах хранения. Они очень
похожи на forward_list: Основное различие заключается в том, что объекты
forward_list являются односвязными списками, и поэтому их можно
перебирать только вперед, но при том они несколько меньше и эффективнее.
31

32.

По сравнению с другими базовыми стандартными контейнерами
последовательности (array, vector и deque) list действуют лучше при вставке,
извлечении и перемещении элементов в любом положении внутри
контейнера, для которого уже был получен итератор.
Основным недостатком list и forward_lists по сравнению с этими
другими контейнерами последовательности является то, что они не имеют
прямого доступа к элементам по их положению.
Например, чтобы получить доступ к шестому элементу в списке, нужно
выполнить итерацию из известной позиции (например, начало или конец) в
эту позицию, которая занимает линейное время на расстоянии между ними.
Они также потребляют некоторую дополнительную память, чтобы
связать информацию привязки к каждому элементу (что может быть важным
фактором для больших списков малогабаритных элементов).
32

33.

begin - Возвращает итератор на начало list
end - Возвращает итератор на конец контейнера
rbegin - Указывает на первый элемент последовательности, записанной в
обратном порядке
rend - Указывает на элемент, следующий за последним элементом
последовательности, записанной в обратном порядке
cbegin - Возвращает const_iterator на начало list
cend - Возвращает const_iterator на конец контейнера
crbegin - Возвращает const_reverse_iterator на первый элемент
последовательности, записанной в обратном порядке
crend - Возвращает const_reverse_iterator на элемент, следующий за последним
элементом последовательности, записанной в обратном порядке
empty - Проверяет, пуст ли контейнер
size - Возвращает размер контейнера
max_size – Возвращает максимально возможный размер контейнера
assign – Передать новое содержание контейнеру
emplace_front - Создать и вставить элемент в начало
push_front - Вставить элемент в начале
pop_front - Удалить первый элемент
33
emplace_back - Построить и вставить элемент в конец

34.

push_back- Добавить элемент в конец
pop_back - Удалить последний элемент
emplace - Построить и вставить элемент
insert - Вставить элементы
erase - Элементы стирания
swap – Переменить контент
resize - Изменить размер
clear – Стереть содержание контейнера
34

35. Операции

splice
Перенос элементов из одного списка в другой
remove
Удалить элементы со специальным значением
remove_if
Удаление элементов по условию
unique
Удалить повторяющиеся значения
merge
Объединить отсортированные списки
sort
Сортировка
reverse
Изменить порядок элементов на обратный
35

36. Пример

#include <iostream>
#include <list>
first.merge(second);
// second становиться пустым!
bool mycomparison
(double first, double second)
{ return ( int(first)<int(second) ); }
second.push_back (2.1);
first.merge(second,mycomparison);
int main (){
std::list<double> first, second;
first.push_back (3.1);
first.push_back (2.2);
first.push_back (2.9);
second.push_back (3.7);
second.push_back (7.1);
second.push_back (1.4);
first.sort();
second.sort();
std::cout << "first contains:";
for (std::list<double>::iterator it=first.begin();
it!=first.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Output:
first contains: 1.4 2.2 2.9 2.1 3.1 3.7 7.1
36

37. Пример

#include <iostream>
#include <list>
int main (){
std::list< std::pair<int,char> > mylist;
mylist.emplace_back(10,'a');
mylist.emplace_back(20,'b');
mylist.emplace_back(30,'c');
std::cout << "mylist contains:";
for (auto& x: mylist)
std::cout << " (" << x.first << "," << x.second << ")";
std::cout << std::endl;
return 0;
}
Output:
mylist contains: (10,a) (20,b) (30,c)
37

38. Типы – производные из имеющихся

Исходя из основных (и определенных пользователем) типов, можно с
помощью следующих операций :
*
указатель
& ссылка
[ ] массив
() функция
а также с помощью определения структур, задать другие, производные
типы. Например:
int* a;
float v[10];
char* p[20]; // массив из 20 символьных указателей
void f(int);
struct str { short length; char* p; };
Ключевая идея состоит в том, что описание объекта производного типа
должно отражать его использование, например:
int v[10]; // объявление вектора
i = v[3]; // использование элемента вектора
int* p; // объявление указателя
38
i = *p; // использование указателя

39.

Обозначения, используемые для производных типов, достаточно трудны
для понимания лишь потому, что операции * и & являются префиксными, а [ ] и
() - постфиксными. Поэтому в задании типов, если приоритеты операций не
отвечают цели, надо ставить скобки. Например, приоритет операции [ ] выше,
чем у *, и мы имеем:
int* v[10];
// массив указателей
int (*p)[10]; // указатель массива
Большинство людей просто запоминает, как выглядят наиболее часто
употребляемые типы. Можно описать сразу несколько имен в одном описании.
Тогда оно содержит вместо одного имени список отделяемых друг от друга
запятыми имен. Например, можно так описать две переменные целого типа:
int x, y; // int x; int y;
Когда мы описываем производные типы, не надо забывать, что операции
описаний применяются только к данному имени (а вовсе не ко всем остальным
именам того же описания). Например:
int* p, y; // int* p; int y; но не int* y;
int x, *p; // int x; int* p;
int v[10], *p; // int v[10]; int* p;
Но такие описания запутывают программу, и, возможно, их следует
избегать.
39

40. Приоритет операций и скобки

Синтаксис языка С++ перегружен скобками, и разнообразие их применений
способно сбить с толку. Они выделяют фактические параметры при вызове
функций, имена типов, задающих функции, а также служат для разрешения
конфликтов между операциями с одинаковым приоритетом. К счастью,
последнее встречается не слишком часто, поскольку приоритеты и порядок
применения операций определены так, чтобы выражения вычислялись
"естественным образом" (т.е. наиболее распространенным образом).
Например, выражение
if (i<=0 || max<i) // ...
означает следующее: "Если i меньше или равно нулю, или если max
меньше i". То есть, оно эквивалентно
if ( (i<=0) || (max<i) ) // ...
но не эквивалентно допустимому, хотя и бессмысленному выражению
if (i <= (0 || max) < i) // ...
Но лучше использовать скобки для надежности, хоть и придется писать
более длинные и менее элегантные выражения, как:
if ( (i<=0) || (max<i) ) // ...
Если появится ощущение, что в выражении нужны скобки, лучше разбить
его на части и ввести дополнительную переменную.
40

41. Домашнее задание на неделю

Проект 31.
Создать абстрактный базовый класс именем своей фамилии,
записанной латиницей.
Создать 3 производных друг от друга класса (а первый – от базового)
с именами измененного имени базового класса с суффиксами типа
«_1» или «child_1», «child_2», «child_3».
Создать в производных классах приватные члены-данных типов int* в первом, float – во втором, char[10] и double* – в третьем и
инициализировать их произвольно.
Реализовать отдельный от иерархии класс базы данных DB, в который в
приватную область поместить хранилище типа list <Ваse* >.
В функции main создать два объекта типа DB: db1 и db2 (добавьте, что
нужно).
Скопировать данные только типов child_2 и child_3 из первого объекта
во второй:
db2 = db1; (dynamic_cast и typeid не использовать ! )
Распечатать данные из db2 (сообразить как это сделать).
Исключить утечку памяти.
41

42. Контрольная работа 7

Пусть имеется полиморфная иерархия из классов – One, Two и Three,
наследуемых друг от друга.
Внутри класса Two помещается член-данных типа list <int*> , а в классе
Three – член-данных типа list <int> *.
Все остальное внутри классов есть, кроме операторов присваивания
копированием.
Задание:
Реализовать только operator = для классов One, Two и Three.
42