Это мой первый опыт написания статьи, так что не судите строго.
Рассказать я хочу о использовании языка C++, и в частности о библиотеке STL.
Основное предназначение библиотеки STL заключается в предоставлении програмисту необходимых контейнеров и функций для работы с ними, что избавляет программиста от лишней головной боли
Библиотеку можно условно разбить на несколько частей:
* контейнеры - объекты отвечающие за хранение других объектов (обычно данных пользователя)
* итераторы - абстракция указателя на элемент контейнера
* алгоритмы - функции для работы с контейнерами (поиск, сортировка, поиск медианы, и т.д.)
* функторы - объекты играющие роль функций
* адаптеры - объекты преобразующие интерфейс объекта к интерфейсу нужному для работы алгоритма (обычно используются в случае применения алгоритмов не к стандартным контейнерам, а на пример к входному или выходному потоку)
Контейнеры:
Контейнер может хранить объекты определенного типа, какого именно выбирать вам. Все контейнеры динамически изменяют свой размер и следят за используемой ими памятью, то есть при удалении контейнера гарантируется удаление всех объектов в контейнере.
Начнем с примера:
Код:
vector[i] V;
assert( V.size() == 0 );
V.push_back( 23 );
V.push_back( 34.56 );
assert( V.size() == 2 );
assert( V[0] == 23 );
assert( V[1] == 34 );
// эта строка станет понятна позже, пока стоит заметить,
// что тип, которым инстанциируется ostream_iterator
// совпадает с типом элементов контейнера
copy( V.begin(), V.end(), ostream_iterator[i]( cout, "n" ) );
Здесь мы создаем массив целых чисел и добавляем в него два числа, функция push_back добавляет элемент в конец контейнера. Проверяем что массив содержит добавленные числа, и что они действительно целые, функция assert проверяет верность утверждений во время выполнения. И выводим все элементы на экран
В таком виде пример не скомпилируется, для работы программы нужно подключить нужные заголовочные файлы, и написать функцию main
Код:
#include <cassert> // для функции assert
#include <vector>
#include <iostream> // библиотека ввода/вывода
#include <algorithm> // алгоритмы (мы используем copy)
using namespace std;
int main(int argc, char* argv[])
{
// сюда вставляем код примера
return 0;
}
все объекты STL находтся в пространстве имен std, строка "using namespace std;" нужна для того, чтобы не писать std::vector, а просто vector
В результате выполнения программы на экране появится
Код:
23
34
Неполный список контейнеров:
* vector - массив
* list - список
* deque - дек
* stack - стек
* queue - очередь
* set - множество
* map - ассоциативный массив
Стек и очередь релизуются обычно на базе дека. В set и map хранятся только уникальные элементы (для map уникальные ключи), существуют также multiset и multimap, которые позволяют хранить несколько одинаковых элементов, а также hashset и hashmap в которых скорость доступа к элементам увеличена за счет использования хеша
Контейнеры делятся на два типа :
1) Последовательные (массив, список, дек)
2) Ассоциативные (множество, ассоциативный массив)
У последовательных контейнеров элементы линейно упорядочены (пронумерованы)
В ассоциативных же контейнерах элементы могут храниться в произвольном порядке
У всех последовательных контейнеров есть функция push_back для добавления элементов в конец, если необходимо добавить элемент в произвольную позицию можно воспользоваться функцией insert
Код:
vector[i] V;
V.push_back( 1 );
assert( V[0] == 1 );
V.insert( V.begin(), 2 );
assert( V[0] == 2 && V[1] == 1 );
В ассоциативные контейнеры элементы добавляются функцией insert
Код:
set[i] S;
S.insert( 1 );
Контейнер map хранит в себе пары ключ-значение, поэтому перед добавлением необходимо создать пару
Код:
map[i] M;
M.insert( make_pair( 1, "Test" ) );
Вывести на экран элементы контейнера можно так
Код:
set[i] S;
// добавляем элементы
copy( S.begin(), S.end(), ostream_iterator[i]( cout, "n" ) );
Осталась проблема c map, т.к. для пары в отличие от встроенных типов нет функций вывода в поток, нам придется написать ее самостоятельно
Код:
// Это функтор выводящий значения пары на экран
template <class Key, class Value>
struct print_pair
{
void operator()(const pair<Key, Value>& p)
{
cout << p.first << " -> " << p.second << endl;
}
};
т.к. мы используем в примере с map строки, необходимо подключить заголовочный файл с описанием строк
Код:
#include <string>
теперь можно выводить значения из map на экран
Код:
map[i] M;
.. // добавляем элементы
for_each( M.begin(), M.end(), print_pair[i]() );
алгоритм for_each к каждому элементу из диапазона применяет указанный функтор, который выводит их на экран
Вот что у нас получилось в примере с map
Код:
#include <map>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
template <class Key, class Value>
struct print_pair
{
void operator()(const pair<Key, Value>& p)
{
cout << p.first << " -> " << p.second << endl;
}
};
int main(int argc, char* argv[])
{
map[i] M;
M.insert( make_pair( 1, "One" ) );
M.insert( make_pair( 2, "Two" ) );
M.insert( make_pair( 3, "Three" ) );
for_each( M.begin(), M.end(), print_pair[i]() );
return 0;
}
В результате выполнения программы на экране появится
Код:
1 -> One
2 -> Two
3 -> Three
Алгоритмы и итераторы:
Итератор - это объект который инкапсулиует указатель на текущий элемент и способ обхода контейнера
Для начала общие свойства итераторов
1) Наличие конструктора по умолчанию
Код:
vector[i]::iterator i;
2) Возможность разыменовывания
Код:
int n = *i;
3) Возможность присваивания если итератор изменяемый (mutable)
Код:
*i = 2;
4) Доступ к членам с помощью -> если итератор указывает на сложный тип
Код:
map[i]::iterator i = M.begin();
cout << i->first;
5) Возможность сравнения двух итераторов
Код:
while( begin != end ) ++begin;
Итераторы бывают нескольких видов:
1) Однонаправленный итератор (forward iterator) - по последовательности элементов возможно перемещатся только вперед - есть operator++(обе формы)
2) Двунаправленный итератор (bidirectional iterator) - поддерживает также перемещение обратно - есть operator--(обе формы)
3) Итератор произвольного доступа (random access iterator) - позволяет за раз перемещаться на несколько элементов (+=, -=, operator[])
Каждый следующий тип итератора дополняет предыдущий, т.е. итератор произвольного доступа является также и двунаправленным итератором, т.к. имеет такой же интерфейс; такой полиморфизм без общего базового класса называется polymorphism ad hoc (полиморфизм в конкретном случае)
Существуют также итераторы для потоков ввода/вывода
Данные итераторы являются адаптерами, которые преобразуют интерфейс потоков ввода/вывода (<<, >>) к интерфейсу однонаправленного итератора
1) Итератор входного потока (input iterator) - позволяет перемещаться вперед и считывать значение текущего элемента
2) Итератор выходного потока (output iterator) - позволяет перемещаться вперед и записывать в текущий элемент
все алгоритмы работают с диапазаном элементов, представленым начальным и конечным итераторами, поэтому один и тотже алгоритм можно применять к разным контейнерам
у каждого контейнера есть функции begin и end, которые возвращают итераторы указывающие на первый элемент и на фиктивный элемент находящийся после последнего, их удобно использовать когда мы хотим обработать контейнер целиком
обратите внимание что элемент на который указывает конечный итератор не обрабатывается, т.е. алгоритмы работают в диапазоне [i, j)
не всякий алгоритм работает с любым итератором, большинству алгоритмов подойдут однонаправленные итераторы, и итераторы входного или выходного потока (в зависимости от того, пишет алгоритм или читает), reverse уже требует двунаправленных итераторов, а sort потребуются итераторы произвольного доступа
какой тип итератора необходим алгоритму можно узнать из сигнатуры, обычно все достаточно ясно
если алгоритм не возможно применить к какому-нибудь контейнеру, то либо контейнер сам реализует этот алгоритм в виде функции члена (к примеру у списка своя функция sort), либо этот алгоритм не применим вообще (например map или set нет смысла сортировать)
Для работы с итераторами существуют две функции:
distance - вычисляет расстояние(количество элементов) между итераторами
advance - перемещает итератор на заданное количество элементов
Они работают со всеми типами итераторов кроме output iterator, и если итератор не двунаправленный, то перемещаться возможно только вперед
Код:
list[i] L;
for( int i = 0; i < 10; i++ )
{
L.push_front( i );
}
// sort( L.begin(), L.end() );
// не выйдет, list предоставляет двунаправленные итераторы
L.sort();
assert( L.size() == distance( L.begin(), L.end() ) );
list[i]::iterator i = L.begin();
advance( i, L.size()/2 ); // перемещаем итератор на серидину списка
copy( L.begin(), i, ostream_iterator[i]( cout, "n" ) );
cout << "i указывает на " << *i << endl;
// Элемент, на который указывает конечный итератор не
// обрабатывается алгоритмами
В результате выполнения программы на экране появится
Код:
0
1
2
3
4
i указывает на 5
Пару слов об адаптерах
адаптеры это объекты, которые изменяют интерфейс адаптируемого объекта, не добавляя при этом функциональности
в наших примерах часто используется адаптер выходного потока ostream_iterator, так же существует адаптер и для входного потока
Код:
vector[i] V;
copy( istream_iterator[i]( cin ), istream_iterator[i](),
back_inserter( V ) );
sort( V.begin(), V.end() );
copy( V.begin(), V.end(), ostream_iterator[i]( cout, " " ) );
Алгоритм copy будет читать из входного потока до тех пор, пока не будет окончен ввод(ctrl+d), и добавлять элементы в конец вектора
Помимо back_inserter существуют также front_inserter и inserter
Код:
list[i] L;
copy( istream_iterator[i]( cin ), istream_iterator[i](),
front_inserter( L ) );
copy( L.begin(), L.end(), ostream_iterator[i]( cout, " " ) );
cout << endl;
set[i] S;
copy( L.begin(), L.end(), inserter( S, S.begin() ) );
copy( S.begin(), S.end(), ostream_iterator[i]( cout, " " ) );
Функторы:
Функторы это объекты, выступающие в роли функций
Код:
struct TestFunctor
{
template <class T>
void operator()(const T& value)
{
cout << value << endl;
}
};
TestFunctor print;
print( 1 );
print( "Test" );
Функтор принимающий один аргумент называется унарным, два - бинарным
В STL существует понятие адаптированного функтора, это функтор с обявлеными типами параметров и возвращаемого значения
Код:
struct adapted_unary_minus
{
typedef int argument_type;
typedef int result_type;
result_type operator()( const argument_type& left )
{
return -left;
}
};
struct adapted_binary_minus
{
typedef int first_argument_type;
typedef int second_argument_type;
typedef int result_type;
result_type operator()( const first_argument_type& left,
const second_argument_type& right )
{
return left - right;
}
};
Обьявления типов параметров и результата используются алгоритмами
Для удобства в библиотеке обьявлены вспомогатеьные классы unary_function и binary_function, которые добавляют необходимые typedef
Код:
struct adapted_unary_minus : public unary_function[i]
{
result_type operator()( const argument_type& left )
{
return -left;
}
}
struct adapted_equal : public binary_function[i]
{
result_type operator()( const first_argument_type& left,
const second_argument_type& right )
{
return left == right;
}
}
Обычно функторы используются для сравнения элементов в алгоритмах поиска, сортировки или подсчета, а также в алгоритмах вроде transform для изменения значений в контейнере, функторы использующиеся для настройки работы алгоритма называются предикатами
Код:
vector[i] V;
for( int i = 0; i < 20; i++ )
{
V.push_back( rand()%10 );
}
copy( V.begin(), V.end(), ostream_iterator[i]( cout, " " ) );
int num = count_if( V.begin(), V.end(), bind2nd( equal_to[i](), 5 ) );
cout << endl << "В массиве " << num<< " пятерок" << endl;
equal_to - это стандартный функтор для проверки равенства значений, он приниает два аргумента и возвращает результат их сравнения, алгоритм count_if подсчитывает количество элементов для которых верен предикат
в данном случае конечно можно записать более просто
Код:
int num = count( V.begin(), V.end(), 5 );
но count_if более гибкий, например
Код:
int num = count_if( V.begin(), V.end(), bind2nd( less[i](), 5 ) );
cout << endl << "В массиве " << num<< " элементов меньше пяти" << endl;
Поэкспериментируйте, вот список функторов, выполняющих сравнение:
Код:
equal_to, not_equal_to, less, greater, less_equal, greater_equal
Теперь давайте разберемся чтоже такое bind2nd, для начала взглянем как работает count_if, код примерно такой
Код:
int count_if(iterator begin, iterator end, predicate pred)
{
int _count = 0;
for(; begin != end; ++begin )
{
if( pred( *begin ) ) ++_count;
}
return _count;
}
как видно из примера предикат это унарная функция (должен иметь один аргумент), а функции сравнения все бинарные (получают два аргумента), поэтому нам необходимо сначала преобразовывать функцию к унарной
bind1st и bind2nd это адаптеры бинарных функций, преобразующие их к интерфейсу унарных, они фиксируют первый или второй параметры бинарной функции, например
Код:
cout << boolalpha << bind1st( less[i](), 5 ) ( 6 ) << endl; // 5 < 6 == true
cout << boolalpha << bind1st( less[i](), 5 ) ( 4 ) << endl; // 5 < 4 == false
Не обращайте внимания пока на boolalpha, этот объект просто говорит потоку что значения типа bool надо выводить в виде строки, он называется манипулятором и является частью стандартной библиотеки ввода/вывода (о ней я надеюсь еще напишу), для использования нужно подключить заголовочный файл:
Код:
#include <iomanip>
А теперь давайте разберемся что произошло. bind1st из бинарной функции less сделал унарную функцию, и зафиксировал первый аргумент, вот примерный код, как это реализуется
Код:
template <class BinaryFunction>
class binder1st : public unary_function[B]
{
BinaryFunction::first_argument_type left;
BinaryFunction function;
public:
binder1st(const BinaryFunction& func,
const BinaryFunction::first_argument_type& arg) :
function(func), left(arg) {}
result_type operator() (const argument_type& right)
{
return function( left, right );
}
}
template <class BinaryFunction>
binder1st[B] bind1st(const BinaryFunction& func,
const BinaryFunction::first_argument_type& left)
{
return binder1st[B]( func, left );
}
т.е. после вызова bind1st( less[i](), 5 ) мы имеем объек типа binder1st, который является унарным функтором, значит к нему можно применить operator(), что мы и делаем
Ну что же, вроде предварительный вариант есть, наверняка что-то упустил, или обьяснил не удачно, первый блин, как говорится, комом
Напоследок напишу еще немножко о шаблонах, для тех кто не знает что это такое
Небольшое введение в шаблоны
Код:
template <class T>
class Vector
{
...
void push_back(const T& addValue);
T get_at(int position);
...
};
это шаблонный класс который хранит в себе элементы как массив
чтобы создать объект шаблонный класс необходимо инстанциировать, т.е. указать параметр шаблона
Код:
Vector[i] vec;
в данном случае мы говорим компилятору что хотим создать вектор для хранения целых чисел и работаем с ним примерно так
Код:
vec.push_back(1);
vec.push_back(2);
int i = vec.get_at(1); // i == 2
существуют так же шаблонные функции
Код:
tempalte <class T>
T sum(T value1, T value 2)
{
return value1 + value2;
}
при вызове такой функции можно не инстанциировать шаблон явно
Код:
sum( 1.5, 2.5 ); // == 4.0
в данном случае компилятор сам определит что параметром шаблона является double потому что типы аргументов совпадают
Код:
sum( 1, 2.5 ); // ошибка
в данном случае параметр шаблона никак не оределить из аргументов функции, поэтому придется его указывать явно
Код:
sum[i]( 1, 2.5 ) // == 3
шаблонные функции могут быть как внешними так и членами классов
Код:
struct Test
{
template <class T>
void print(T value)
{
cout << value << endl;
}
};
Test test;
test.print( 1 );
test.print( "Test" );
и еще кое-что о typedef, этот оператор не определяет новых типов, он просто создает новое имя для существующего типа, класса (старое никуда не пропадает =)
интересно то, что typedef можно включать в определение класса, тем самым ограничивая область видимости
Код:
struct Test
{
typedef int TestType;
};
Test::TestType i; // эквиваленто int i
также typedef может использоватся с шаблонными параметрами
Код:
template <class T>
struct Test2
{
typedef T TestType;
};
Test2[i]::TestType i; // эквиваленто int i
достаточно часто бывают и более сложные кострукции
Код:
template <class T>
struct Test3
{
typedef typename T::TestType TestType;
// оператор typename указывает что T::TestType это тип
};
Test3<Test> i; // эквиваленто int i
// Test3[i] i; // а вот так не выйдет
Наверное надо побольше рассказать о шаблонах, так что задавайте вопросы