Контейнеры (Коллекции). Stl бибилиотеки. Линейные контейнеры array

Выражение	Возвращаемый тип	Сложность
Примечание
C::value_type	T	Время компиляции
C::reference	T	Время компиляции
C::const_reference		Время компиляции
C::pointer	Тип указателя, указывающего на C::reference	Время компиляции	Указатель на Т
C::iterator	Тип итератора, указывающего на C::reference	Время компиляции	Итератор любого типа, кроме итератора вывода
C::const_iterator	Тип итератора, указывающего на C::const_reference	Время компиляции	Итератор любого типа, кроме итератора вывода
C::size_type	Беззнаковый целочисленный тип	Время компиляции
C obj;		Постоянная	После: obj.size() == 0
C obj1; obj1 = obj2;		Линейная	После: obj1 == obj2
C obj; (&obj)->~C();	Результат не используется	Линейная	После: a.size() == 0.
obj.begin()		Постоянная
obj.end()		Постоянная
obj1 == obj2	Обратимый в bool	Линейная
obj1 != obj2	Обратимый в bool	Линейная
obj.size()	size_type	Зависит от типа	Не рекомендуется применять для проверки, пуст ли контейнер
obj.empty()	Обратимый в bool	Постоянная
obj1 < obj2	Обратимый в bool	Линейная
obj1 > obj2	Обратимый в bool	Линейная
obj1 <= obj2	Обратимый в bool	Линейная
obj1 >= obj2	Обратимый в bool	Линейная
obj.swap(obj2)	void	Постоянная

3. Итераторы

В библиотеке STL для доступа к элементам в качестве посредника используется обобщённая абстракция, именуемая итератором. Каждый контейнер поддерживает «свой» вид итератора, который представляет собой «модернизированный» интеллектуальный указатель, «знающий» как получить доступ к элементам конкретного контейнера. Стандарт C++ определяет пять категорий итераторов, описанных в следующей таблице:

Категория	Поддерживаемые операции	Примечание
Входные	operator++, operator*, operator->, конструктор копии, operator=, operator==, operator!=	Обеспечивают доступ для чтения в одном направлении. Позволяют выполнить присваивание или копирование с помощью оператора присваиваивания и конструктора копии
Выходные	operator++, operator*, конструктор копии	Обеспечивают доступ для записи в одном направлении. Их нельзя сравнивать на равенство.
Однонаправленные	operator++, operator*, operator->, конструктор копии, конструктор по умолчанию, operator=, operator==, operator!=	Обеспечивают доступ для чтения и записи в одном направлении. Позволяют выполнить присваивание или копирование с помощью оператора присваиваивания и конструктора копии. Их можно сравнивать на равенство.
Двунаправленные	operator++, operator--, operator*, operator->, конструктор копии, конструктор по умолчанию, operator=, operator==, operator!=	Поддерживают все функции, описанные для однонаправленных итераторов (см. выше). Кроме того, они позволяют переходить к предыдущему элементу.
Произвольного доступа	operator++, operator--, operator*, operator->, конструктор копии, конструктор по умолчанию, operator=, operator==, operator!=, operator+, operator-, operator+=, operator-=, operator<, operator>, operator<=, operator>=, operator[]	Эквивалентны обычным указателям: поддерживают арифметику указателей, синтаксис индексации массивов и все формы сравнения.

assign(n,x)присваивание контейнеру n копий элементов х (не для ассоциативных контейнеров)
assign(first,last) присваивание элементов из диапазона [first:last]
Ассоциативные операции
operator[](k) – доступ к элементу с ключом k
find (k) – находит элемент с ключом k
lower _ bound (k) – находит первый элемент с ключом k
upper_bound(k) – находит первый элемент с ключом, большим k equal_range(k) – находит lower_bound(нижнюю границу)и upper_bound (верхнююграницу) элементов с ключом k
Итераторы (iterators) – указатели на элементы контейнера. Они позволяют получить доступ к содержимому контейнера примерно так же, как указатели используются для доступа к элементам массива. С итераторами можно работать также, как с указателями. К ним применимы операции *, ++, --. Итератор имеет тип iterator.
Классы итераторов и функции, предназначенные для работы с ними, находятся в библиотечном файле <iterator>. Примеры итераторов
begin() указывает на первый элемент
end() указывает на элемент, следующий за последним
rbegin() указывает на первый элемент в обратной последователь-ности
rend() указывает на элемент,следующий за последним в обрат-ной последовательности
Итераторы (iterators) – указатели на элементы контейнера. Они позволяют получить доступ к содержимому контейнера примерно так же, как указатели используются для доступа к элементам массива.
Классы итераторов и функции, предназначенные для работы с ними, находятся в библиотечном файле <iterator>. Каждый контейнер содержит ряд ключевых методов, позволяющих найти концы последовательности элементов в виде соответствующих значений итераторов:
- iterator begin() – возвращает итератор, который указывает на первый элемент последовательности.
const_iterator begin() const
- iterator end() – возвращает итератор, который указывает на элемент, следующий за последним элементом последовательности (используется при оформлении циклов).
const_iterator end () const
- reverse_iterator rbegin() - возвращает итератор, указывающий напервый элемент в обратной последовательности (используетсядля работы с элементами последовательности в обратном порядке).
const_reverse_iterator rbegin() const .
Существует пять типов итераторов:
1. Итераторы ввода (input_iterator) поддерживают операции равенства, разыменования и инкремента. ==, !=, *i, ++i, i++, *i++ . Специальным случаем итератора ввода является istream_iterator.
2. Итераторы вывода (output_iterator) поддерживают операции разыменования, допустимые только с левой стороны присваивания, и инкремента. ++i, i++, *i=t, *i++=t
Специальным случаем итератора вывода является ostream_iterator.
3. Однонаправленные итераторы (forward_iterator) поддерживают все операции итераторов ввода/вывода и, кроме того, позволяют без ограничения применять присваивание. ==, !=, =, *i, ++i, i++, *i++
4. Двунаправленные итераторы (biderectional_iterator) обладают всеми свойствами forward-итераторов, а также имеют дополнительную операцию декремента (--i, i--, *i--), что позволяет им проходить контейнер в обоих направлениях.
5. Итераторы произвольного доступа (random_access_iterator) обладают всеми свойствами biderectional-итераторов, а также поддерживают операции сравнения и адресной арифметики, то есть непосредственный доступ по индексу. i+=n, i+n, i-=n, i-n, i1-i2, i[n], i1i2, i1>=i2.
Пример1. Написать функцию g() с тремя параметрами:
- непустой и неизменяемый контейнер-вектор типа vector;
- непустой контейнер-список типа list;
- целое число – шаг по первому контейнеру.
Функция должна сравнить элементы списка, перебираемые в обратном порядке с шагом 1, с соответствующими элементами вектора, выбираемыми с шагом, равным третьему параметру. Если обнаруживаются пары элементов разных знаков, то у текущего элемента списка должен меняться знак. После окончания сравнения контейнеров функция должна вывести на устройство вывода изменённый список. Функция возвращает общее количество неотрицательных элементов списка.
# include < iostream >
# include < Vector >
# include < List >
using namespace std; // средства стандартной библиотеки, и, в //частности, STL, определены в пространстве имен std.
typedef vector V;
typedef list L;
int g(const V& vect, L& lst, int step){
V:: const_iterator vp = vect.begin();
L:: reverse_iterator lp = lst.rbegin();
int t = 0;
do{ if (*lp * *vp < 0) *lp = -*lp;
if (vect.end() - vp <= step) break;
++ lp;
vp += step;
} while (lp != lst.rend());
L::iterator rp = lst.begin();
while (rp != lst.end()){
cout << *rp << ' ';
if (*rp >= 0) t++;
++rp;
};
cout << endl;
return t ;
}
int main (){
/*определение тестовых объектов размером по 15 элементов с начальным заполнением нулями*/
V vect 1(15,0.0); // вектор чисел типа float
L list 1(15,0.0); //список чисел типа float
int i;
i = g(vect1,list1,1);
cout<< '\n' << "positive elements: " << i << '\n';
return 0;
}
Пример 2.Доступ к вектору через итератор.
#include
#include
using namespace std;
int main(){
vector v;
int i;
for(i=0;i<10;i++)
v.push_back(i);
cout<< " size= " <
vector::iterator p=v.begin();
while(p!=v.end()){
cout<<*p<< ' ' ;
p ++;
}
}
Пример 3. Вставка и удаление элементов в вектор.
#include
#include
using namespace std;
int main(){
vector v(5,1);
int i;
//вывод
for(i=0;i<5;i++)cout<
cout<
vector::iterator p=v.begin();
p +=2;
//вставить 10 элементов со значением 9
v.insert(p,10,9);
//вывод
p=v.begin();
while(p!=v.end()){
cout<<*p<<' ';
p ++;
}
//удалить вставленные элементы
p = v . begin ();
p+=2;
v.erase(p,p+10);
//вывод
p=v.begin();
while(p!=v.end()){
cout<<*p<<' ';
p++;
}
}
Пример 4. Программа для сортировки с использованием алгоритма sort .
// сортирует массив целых чисел
# include < iostream >
#include
using namespace std;
int arr[] = {45, 2, 22, -17, 0, -30, 25, 55};
int main (){
sort (arr, arr+8); // сортировка
for ( intj =0; j <8; j ++) // вывести отсортированный массив
cout<< arr[j]<< ' ';
cout << endl ;
return 0;
}
Пример 5. Программа для поиска вхождения подпоследовательности в последовательность с использованием алгоритма
// search . cpp
//Ищем последовательность, заданную одним контейнером, в другом //контейнере
#include
#include
using namespace std;
int source[] = {11, 44, 33, 11, 22, 33, 11, 22, 44};
int pattern[] = {11, 22, 33};
int main (){
int* ptr;
ptr=search(source,source+9,pattern, pattern+3);
if ( ptr == source +9)
cout <<”Совпадения не найдено\ n ”;
else
cout<<” Совпадение в позиции ” <<(ptr –source)<< endl;
return 0;
}
Пример 6. Поиск первого четного элемента в списке.
#include
#include
#include
int main(){
using namespace std;
// оздается список из целых чисел.
list numbers;
numbers.push_back(13); numbers.push_back(17);
numbers.push_back(42); numbers.push_back(46);
numbers . push _ back (99);
// Используется функция find _ if и лямбда-выражение.
const list::const_iterator result =
find_if(numbers.begin(), numbers.end(),[](int n) { return (n % 2) == 0; });
// Print the result.
if (result != numbers.end()) {
cout << "The first even number in the list is " << *result << "." << endl;
} else {
cout << "The list contains no even numbers." << endl;
}
}
Литература


1. STL для программистов на с++ Афтер Леен Аммерааъл


2. Monster-book.com цайти


3. С++ книги