Итераторы и алгоритмы

Список

Вектор

Вектор - одномерный массив проиндексированных элементов. Вектор представляет собой пример наиболее полного стандартного контейнера. Для использования вектора стандартной библиотеки необходимо:

#include <vector>
using namespace std;

void main()
{
// double x[100]; //наверное мало
// double* x=new double[10000]; //много, зато c запасом и наверняка
vector<double> x(100, 1.0); //не обязательно так много, ведь при необходимости x.resize(x.size()+100);

double sum=0.0;
for(int i=0; i<x.size(); i++)
{
sum+=x[i]; //доступ по индексу, хотя в данном случае требуется выполнять обработку всех элементов массива
}
}

Размер	a.size()	Возвращает размер контейнера a, то есть, количество элементов находящихся в нём.
Пустой контейнер	a.empty()	Определяет, пуст ли контейнер a. Эквивалентно a.size() == 0.
Доступ к элементам	a[n]	Возвращает n-ый элемент от начала контейнера a.
Втолкнуть в конец	a.push_back(t)	Вставляет копию значения t в конец контейнера.
Очистить	a.clear()	Разрушает все элементы и удаляет их из контейнера a.
Изменение размера	a.resize(n)	Изменяет контейнер так, что он содержит ровно n элементов. Если необходимо дополнить контейнер a, то вставляются значения по умолчанию.
Ёмкость	a.capacity()	Возвращает количество элементов, для которых зарезервирована.память.
Резервирование	a.reserve(n)	Выделяет дополнительную память для последующего размещения новых элементов.

При работе с вектором мы сталкиваемся с такими понятими как размер и емкость. Размер - количество элементов, хранимых в контейнере, можно узнать с помощью функции size(), а изменить с помощью resize(). Операции push_back(), insert(), erase() также изменяют размеры вектора. Когда размеры вектора изменяются, то все его элементы могут быть перемещены в новую область памяти, поэтому хранить указатели на элементы вектора не имеет смысла и может быть опасно. Всегда нужно работать через итераторы.

При работе с вектором можно выделить (зарезервировать) некоторую область памяти для потенциального расширения. Использование функции reserve() обеспечить выделение памяти для новых элементов контейнера. При этом вставка новых элементов или изменение размеров с помощью resize() не потребует перераспределения хранимого вектора в памяти. Определить "емкость" вектора можно с помощью функции capaсity().

С помощью функции empty() можно узнать о наличии элементов в контейнере. Если контейнер действительно пуст, то функция возвращает true.

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

Каждый элемент должен хранить ссылки на последующий и предыдущий элемент. Для того, чтобы отделить хранимые объекты от способа хранения вводится вспомогательный объект УЗЕЛ (Node)

Возможны различные реализации списков:

Простой односвязный список:
Простой двухсвязный список:
Кольцевой двухсвязный список:

Узел - объекты, который содержит ссылки на последующий и предыдущий элементы, а также значение данного элемента списка.

template <class T> class ListNode
{
private:
ListNode* m_next;
TreeNode* m_prev;
T m_value;
};

Cписки в станадртной библиотеке C++ являются двусвязными. Поэтому список поддерживает вставку в начало (push_front) и в конец (push_back). Кроме того новые элементы можно вставить в любое место списка (insert). При этом не потребуется переразмещение всей структуры данных:

list<int> L;
L.push_back(0);
L.push_front(1);

Нет гарантии в том, что элементы контейнера хранятся в каком-либо определенном порядке. Фактически, при каждом обходе контейнера этот порядок может быть различным.

Для обобщения работы с элементами различных контейнеров вводят понятие, общее для всех контейнеров - итератор. Итераторы являются общей концепцией обработки последовательности элементов, хранимых в любых контейнерах. Реализация итератора отличается для разных типов контейнеров, но работа с итератором, набор функций и операторов унифицирован.

Итератор - это объект, который представляет собой обощение понятия указатель. Это обобщённый "указатель" на элемент, хранящийся в контейнере. Применение оператора * приведет к разыменованию и получению доступа к значению элемента. А использование операторов ++ и -- позволит получить указатель на следующий и предыдущий элемент хранимый в контейнере. Все контейнеры должны предоставлять несколько ключевых функций-членов, которые позволяют программисту получить итераторы на первый и последний элемент контейнера, то есть найти "концы" последовательности элемента контейнера.

Итератор -- это механизм, который делает возможным отделение алгоритмов от контейнеров: алгоритмы являются шаблонами, параметризиуемыми типом итератора так, что они не ограничиваются контейнерами одного типа. Например,

list<double> x;
x.insert(x.begin(),1);
list<double>::iterator i;
for(i=x.begin(); i!=x.end(); i++)
{
sum+=(*i); //доступ к элементам по итератору, у некоторых контейнеров альтернативы нет, всегда работают с использованием итераторов
}

i=x.begin();
while(i!=x.end())
{
sum+=(*i); //доступ к элементам по итератору
i++;
}

i=x.end();
while(i!=x.begin())
{
sum+=(*i); //доступ к элементам по итератору
i--;
}

i=x.rbegin();
while(i!=x.rend())
{
sum+=*i; //доступ к элементам по итератору
i++;
}

// но если использовать алгоритмы (вместо 4 строчек кода достаточно записать одну)
sum=accumulate(x.begin(), x.end(), 0.0);

Обобщенные процедуры для обработки элементов любых контейнеров объявлены в файле <algorithm>. Можно выделить несколько групп алгоритмов в зависимости от того, модифицируют они контейнер или только лишь извлекают необходимую информацию:

Алгоритмы не модифицирующие контейнер - это процедуры поиска и сравнения.

list<string> ls;
...
list<string>::const_iterator p=find(ls.begin(), ls.end(), "К8");
if(p!= ls.end())
{
...
}

Алгоритмы модифицирующие значение элементов контейнера, но неизменяющие порядок их следования - выполнение действий над каждым элементом контейнера, поиск и замена.

vector<int> v(100);
...
fill(v.begin(), v.end(), 0);
...
replace(v.begin(), v.end(), -1, 1);

Алгоритмы модифицирующие контейнер, то есть изменяющие порядок следования элементов - это функции копирования, всевозможных перестановок, удаления, тасования и сортировки, двоичного поиска (в процессе поиска последовательность сортируется), разбиения и слияния последовательностей.

vector<int> v(100);
...
sort(v.begin(), v.end());
reverse(v.begin(), v.end());

Функции-помощники (перестановки и сравнения)

Численные алгоритмы объявлены в файле <numeric>:

• accumulate - накапливат результаты выполнения операций над последовательностью (сложение элементов)
• inner_product - накапливат результаты выполнения операций над двумя последовательностями (перемножение)
• partial_sum - позволяет получить последовательность инкрементных изменений (a, a+b, a+b+c, a+b+c+d,...)
• adjacent_difference - позволяет получить последовательность инкрементных изменений (a, b-a, c-b-a, d-c-b-a,...)