4. Объекты-функции
Некоторые алгоритмы из библиотеки STL требуют функций в качестве параметров. Примером служит алгоритм for_each(), который вызывает функцию, переданную в качестве параметра, для каждого значения в контейнере. В программе 9.3 показано, как с помощью алгоритма for_each() можно вывести все элементы связного списка на экран.
#include
#include
#include
using namespace std;
void PrintElement( int value )
{
cout << "Список содержит значение " << value << '\n';
}
void main()
{
list intList;
for ( int i = 0; i < 100; i++ )
intList.push_back( i );
for_each( intList.begin(), intList.end(), PrintElement );
}
Программа 9.3. Применение алгоритма for_each с параметром-функцией PrintElement.
Понятие функции в STL было обобщено до понятия объекта-функции. Объект-функция – это объект класса, в котором перегружен оператор вызова функции "круглые скобки" (). В ряде случаев удобно заменить функции на объекты-функции. Когда объект-функция используется в качестве функции, то при ее вызове используется оператор "круглые скобки".
Рассмотрим следующее определение класса:
class СBiggerThanThree {
public:
bool operator () (int v)
{ return v > 3; }
};
Если мы создадим объект класса CBiggerThanThree, то каждый раз, когда мы будем ссылаться на него с использованием синтаксиса вызова функции, то будет вызываться перегруженный оператор "круглые скобки". Следующий шаг – обобщить этот класс, добавив к нему конструктор и неизменяемое поле данных, которое устанавливается конструктором:
class CBiggerThan {
public:
CBiggerThan( int x ) : testValue(x) {;}
bool operator () (int val)
{ return val>testValue; }
const int testValue;
};
В результате мы получили функцию общего вида, которая выполняет целочисленное сравнение "больше чем X", где значение X определяется при создании объекта класса. Подобную функцию можно использовать в качестве параметра при вызове некоторых алгоритмов STL, например, алгоритма логического поиска find_if. Ниже приведен пример вызова этого алгоритма для поиска в целочисленном списке первого элемента со значением больше 12:
list::iterator firstBig = find_if( intList.begin(),
intList.end(),
CBiggerThan(12) );
5. Пример программы: инвентаризация
Рассмотрим пример, иллюстрирующий создание и обработку объектов в библиотеке STL. Допустим, что требуется написать складскую программу для учета некоторых приспособлений – виджетов. Это какие-то устройства, различаемые по идентификационным номерам:
class CWidget
{
public:
CWidget(int a) : id(a) {}
CWidget() : id(0) {}
int id;
};
Для упорядочения и сравнения объектов-виджетов предназначены несколько перегруженных операторов:
bool operator== ( const CWidget& lhs, const CWidget& rhs )
{
return lhs.id == rhs.id;
}
bool operator!= ( const CWidget& lhs, const CWidget& rhs )
{
return lhs.id != rhs.id;
}
bool operator< ( const CWidget& lhs, const CWidget& rhs )
{
return lhs.id < rhs.id;
}
bool operator> ( const CWidget& lhs, const CWidget& rhs )
{
return lhs.id > rhs.id;
}
Виджеты в программе описываются двумя списками. В одном хранятся виджеты, имеющиеся в данный момент на складе. Второй список содержит типы виджетов, которые были заказаны покупателями. Первый список содержит собственно виджеты, а второй – идентификационные типы виджетов. Для работы со складом требуются две функции-члена:
-
Order() – обслуживание заказа;
-
Receive() – отслеживание поставок новых виджетов на склад.
class CInventory
{
public:
void Order( int wid ); // обработка заказа виджета типа wid
void Receive( int wid ); // получение виджета типа wid
private:
list on_hand;
list on_order;
};
Когда поступает новый виджет, надо сравнить его идентификационный номер со списком заказанных виджетов. С помощью алгоритма find() можно найти виджет в списке заказов. Если виджет был заказан, то его надо немедленно переслать покупателю. В противном случае он добавляется к списку виджетов на складе.
void CInventory::Receive( int wid )
{
cout << "Пришла партия виджетов типа " << wid << endl;
list::iterator weNeed = find( on_order.begin(),
on_order.end(), wid );
if ( weNeed != on_order.end() )
{
cout << "Отправить " << wid << " покупателю \n";
on_order.erase(weNeed);
}
else
on_hand.push_front( CWidget(wid) );
}
Когда покупатель заказывает новый виджет, мы просматриваем с помощью функции find_if() список имеющихся на складе виджетов, чтобы определить, нельзя ли обслужить заказ немедленно. Для этого определена унарная функция, которая берет в качестве аргумента виджет и определяет, соответствует ли он требуемому типу. Эта функция записывается следующим образом:
class CWidgetTester {
public:
CWidgetTester( int t ) : testid(t) { }
bool operator() ( const CWidget& wid )
{ return wid.id == testid; }
const int testid;
};
Функция, обслуживающая заказы виджетов, выглядит так:
void CInventory::Order( int wid )
{
cout << "Получен заказ на виджеты типа " << wid << endl;
list::iterator weHave = find_if( on_hand.begin(),
on_hand.end(), CWidgetTester(wid) );
if ( weHave != on_hand.end() )
{
cout << "Отправить покупателю виджет " << weHave->id << endl;
on_hand.erase(weHave);
}
else
{
cout << "Заказать виджет типа " << wid << endl;
on_order.push_front(wid);
};
}
Главная функция для тестирования класса CInventory, описывающего состояние склада и заказы, может выглядеть следующим образом:
void main()
{
CInventory inv;
inv.Receive( 5 );
inv.Order( 10 );
inv.Order( 5 );
inv.Receive( 10 );
inv.Receive( 10 );
}
6. Ассоциативные списки
В библиотеке STL реализованы различные АТД. Более сложным по сравнению со связным списком является ассоциативный список map, в котором каждому значению соответствует уникальный ключ. Частным случаем ассоциативного списка является обычный массив, в нем ключом является целочисленный индекс. В ассоциативном списке ключ может быть любого типа, и в общем можно сказать, что ассоциативный список представляет собой список пар ключ/значение. Важное достоинство ассоциативных списков – возможность получения значения по данному ключу. Например, в ассоциативном списке можно хранить имена телефонных абонентов в качестве ключей, а номера телефонов – в качестве значений.
В ассоциативном списке можно хранить только уникальные ключи. Дублирования ключей не допускается. Для создания ассоциативного списка с неуникальными ключами предназначен отдельный класс-контейнер multimap.
Пары ключ/значения в ассоциативном списке хранятся в виде объектов класса pair. Он имеет следующее описание:
template struct pair {
Ktype first; // Ключ
Vtype second; // Значение
// Конструкторы
pair();
pair( const Ktype& k, const Vtype& v );
}
В программе 9.4 приведен пример ассоциативного списка, предназначенного для хранения десяти пар ключ/значения следующего вида:
A 0
B 1
C 2
...
J 9
Пользователь может набрать на клавиатуре ключ (одну из букв от A до J) и программа выведет на экран соответствующее этому ключу значение.
Поиск нужного значения по заданному ключу выполняется с помощью алгоритма find(). Эта функция возвращает итератор, указывающий на соответствующий ключу элемент или на итератор конца списка, если указанный ключ не найден.
#include
#include
|