Глава     

Пример: STL

Разделы

Содержание

Богатая коллекция структур данных, основанная на использовании шаблонов, недавно была добавлена к стандартной библиотеке языка C++. Эти структуры содержат классы для векторов, списков, множеств, карт (словарей), стеков, очередей, очередей с приоритетами. Когда этот стандарт станет распространен повсеместно, программисты на языке C++ будут освобождены от необходимости постоянно переопределять и повторно реализовывать один и тот же набор классов для структур данных. Более подробная информация о библиотеке STL (STL ≈ Standard Template Library, стандартная библиотека шаблонов) может быть найдена в работах [Musser═1996, Glass═1996].

Создание STL является результатом многолетних исследований под руководством Александра Степанова и Менга Ли из компании Hewlett-Packard и Дэвида Мюссера из Rensselaer Polytechnic Institute. Создание STL вдохновлялось не только предшествующими объектно-ориентированными библиотеками, но и многолетним опытом работы ее создателей в области функциональных и директивных языков программирования (Scheme и Ada).

Одна из наиболее необычных идей в STL═≈ это обобщенные алгоритмы. Она заслуживает отдельного рассмотрения, поскольку выглядит вызовом объектно-ориентированным принципам, которые мы обсуждали до сих пор, и в то же время является источником огромной мощи библиотеки STL. Обобщенные алгоритмы в STL напоминают классы-шаблоны. Идея шаблонов применяется к отдельным функциям. Чтобы понять концепцию обобщенных алгоритмов, мы сперва должны описать использование инкапсуляции в большинстве объектных библиотек.

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

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

Отделяя функционирование алгоритмов от контейнерных классов, библиотека STL много выигрывает в размере═≈ как в объеме самой библиотеки, так и в генерируемом коде. Вместо того чтобы дублировать алгоритмы для дюжины или около того контейнерных классов, одно-единственное описание библиотечной функции может использоваться с любым контейнером. Более того, описание этих функций является настолько общим, что они могут применяться с обычными массивами и указателями (в смысле языка C), и с другими типами данных.

Наш пример проиллюстрирует некоторые основные свойства стандартной библиотеки шаблонов. Обобщенный алгоритм find находит первое вхождение заданного значения в коллекцию. Итераторы стандартной библиотеки состоят из пар значений, отмечающих начало и конец структуры. Алгоритм find использует пару итераторов и ищет первое вхождение заданного значения. Он определен следующим образом: 

template<class InputIterator, class T>
InputIterator find (InputIterator first,
                     InputIterator last,
                      const T& value)
{
  while (first != last && *first != value)
   {
    ++first;
   };
  return first;
}

Алгоритм будет работать со структурой любого типа, в том числе и с обычными массивами языка C. Чтобы найти первое вхождение числа═7 в массив целых, пользователь выполняет следующий код: 

int data[100];
...
int *where;
where = find(data, data+100,═7);

Поиск первого значения в целочисленном списке ничуть не сложнее: 

list<int> aList;
...
list<int>::iterator where;
where = find(aList.begin(), aList.end(),═7);

В этой главе мы можем описать только основные свойства STL. Следующие два раздела посвящены базовым концепциям, используемым в библиотеке, а именно итераторам и объектам-функциям. Затем три примера проиллюстрируют в действии контейнеры и обобщенные алгоритмы библиотеки STL.

16.1. Итераторы

Разделы

Итераторы═≈ это фундамент, на котором основано использование контейнерных классов и соответствующих алгоритмов из стандартной библиотеки. Абстрактно итератор═≈ это просто объект типа указателя, который применяется для прохода по всем элементам в контейнере.

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

Традиционные указатели иногда принимают значение null═≈ то есть не указывают ни на что. Итераторы аналогичным образом могут не определять какое-либо конкретное значение. Подобно тому, как логической ошибкой является разыменование и использование указателя со значением null, нельзя разыменовывать и применять итератор, который не определяет никакого значения.

Когда в языке C++ используются два указателя, которые ограничивают область памяти, по соглашению второй указатель не рассматривается как часть области. Например, массив с именем x и длиной═10 иногда описывается как занимающий область от x до x+10, хотя элемент x+10 не является частью массива. На самом деле указатель x+10 ссылается на запредельный элемент, то есть элемент, следующий за последним элементом описываемого диапазона. Итераторы определяют диапазон аналогичным образом. Второе значение рассматривается не как часть определяемого диапазона, но как запредельный элемент, описывающий значение, следующее в последовательности за последним значением из заданного диапазона.

Подобно традиционным указателям, основное действие, которое модифицирует итератор, это инкрементация (оператор ++). Когда инкрементация применяется к итератору, который указывает на последнее значение в последовательности, итератор принимает описанное выше запредельное значение. Оператор разыменования (*) осуществляет доступ к данным, определяемым итератором.

Диапазон может описывать весь контейнер при задании итератора, указывающего на первый элемент, и итератора, имеющего специальное ╚последнее╩ значение. Диапазоны могут описывать подпоследовательности, входящие в контейнер (двум итераторам присваиваются конкретные значения). В стандартных контейнерах итератор начала контейнера возвращается функцией begin(), а итератор, обозначающий конец контейнера,═≈ функцией end().

16.2. Объекты-функции

Разделы

Ряд обобщенных алгоритмов из библиотеки STL требует функций в качестве аргументов. Простым примером служит обобщенный алгоритм for_each(), который вызывает функцию, переданную в качестве аргумента, для каждого значения в контейнере. Следующий код используется для того, чтобы вывести полный набор значений в целочисленном списке: 

void printElement(int value)
{
  cout << "The list contains " << value << endl;
}

main ()
{
  list<int> aList;
  ...
  for_each(aList.begin(), aList.end(), printElement);
}

Понятие функции было обобщено до понятия объекта-функции. Объект-функция═≈ это экземпляр класса, в котором определен метод ╚круглые скобки╩ (). В ряде случаев удобно заменить функции на объекты-функции. Когда объект-функция используется в качестве функции, то при ее вызове используется оператор ╚круглые скобки╩.

Чтобы проиллюстрировать это, рассмотрим следующее определение класса: 

class biggerThanThree
{
public:

    bool operator () (int v)
     {
      return V >═3 ;
     }
};

Если мы создадим экземпляр класса biggerThanThree, то каждый раз, когда мы будем ссылаться на него с использованием синтаксиса вызова функции, будет вызываться метод, соответствующий оператору ╚круглые скобки╩. Следующий шаг═≈ обобщить этот класс, добавив к нему конструктор и неизменяемое поле данных, которое устанавливается конструктором: 

class biggerThan
{
public:

     biggerThan (int x) : testValue(x) { }
 
     const int testValue;

     bool operator () (int val)
      {  return val > testValue;  }
};

Результатом является функция общего вида, выполняющая целочисленное сравнение ╚больше чем X╩, где значение X определяется при создании экземпляра класса. Это может быть сделано, например, при передачи одной из обобщенных функций аргумента═≈ логической функции. Мы ищем в списке первое значение, большее═12, с помощью кода 

list<int>::iterator firstBig =
  find_if( aList.begin(), aList.end(), biggerThan(12));

16.3. Пример программы: инвентаризация

Разделы

Наш первый пример иллюстрирует создание и обработку объектов в библиотеке STL. Допустим, фирме WorldWideWidgetWorks потребовалась программа учета виджетов. Виджеты═≈ это простые устройства, различаемые по идентификационным номерам: 

class Widget
{
public:

    Widget(int a) : id(a) { }
    Widget() : id(0) { }
    int id;
};

ostream & operator << (osteam & out, Widget & w)
{
  return out << "Widget " << w.id;
}

bool operator == (const Widget & lhs, const Widget & rhs)
{
  return lhs.id == rhs.id;
}

bool operator < (const Widget & lhs, const Widget & rhs) 
{
  return lhs.id < rhs.id;
}

Инвентарь описывается двумя списками. Один представляет собой виджеты, имеющиеся в данный момент на складе. Второй список содержит типы виджетов, которые были заказаны покупателями. Первый список содержит собственно виджеты, а второй═≈ идентификационные типы виджетов. Чтобы управлять инвентарем, требуются две команды: 

class inventory
{
public:

    void order (int wid);

    // обработка заказа виджета типа wid
    void receive (int wid);

    // получение виджета типа wid

private:

    list<Widget> on_hand;
    list<int>    on_order;
};

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

void inventory::receive(int wid)
{
  cout << "Пришла партия виджетов типа" << wid << endl;

  list<int>::iterator weNeed = 
    find(on_order.begin(), on_order_end(), wid);

  if ( weNeed != on_order.end() )
   {
    cout << "Поставить " << Widget(wid)
         << " чтобы пополнить запас" << endl;

    on_order.erase(weNeed);
   }
  else
   {
    on_hand.push_front(Widget(wid));
   };
}

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

class WidgetTester
{
public:

    WidgetTester(int t) : testid(t) { }
    const int testid;
    bool operator () (const Widget & wid)
     {  return wid.id == testid; }
};

Функция, обслуживающая заказы виджетов, выглядит так: 

void inventory::order(int wid)
{
  cout << "Получен заказ на виджеты типа " 
       << wid << endl;

list<Widget>>::iterator weHave = 
  find_if(on_hand.begin(), on_hand.end(), WidgetTester(wid));

  if ( weHave != on_hand.end() )
   {
    cout << "Поставить " << *weHave << endl;
    on_hand.erase(weHave);
   }
  else
   {
    cout << "Заказать виджет типа " < wid << endl;
    on_order.push_front(wid);
   };
}

16.4. Пример программы: графы

Разделы

Второй и третий примеры используют тип данных ╚карта╩. Карта map═≈ это индексированный словарь, то есть набор пар ключ-значение.

Карта, в которой элементами тоже являются карты, служит естественным представлением направленного графа. Предположим, к примеру, что мы используем текстовые строки для кодирования названий городов и хотим сконструировать карту, где значения ребер графа═≈ это расстояние между двумя соответствующими городами. Такой граф показан на рис.═16.1.


Рис.═16.1. Взвешенный граф

Листинг═16.1.
Операторы инициализации графа 
typedef map<string, int> stringVector;
typedef map<string, stringVector> graph;

string pendleton("Pendleton");
string pensacola("Pensacola");
string peoria("Peoria");
string phoenix("Phoenix");
string pierre("Pierre");
string pittsburg("Pittsburg");
string princeton("Princeton");
string pueblo("Pueblo");

graph cityMap;

cityMap[pendleton][phoenix] =═4;
cityMap[pendleton][pueblo] =═8;
cityMap[pensacola][phoenix] =═5;
cityMap[peoria][pittsburgh] =═5;
cityMap[peoria][pueblo] =═3;
cityMap[phoenix][peoria] =═4;
cityMap[phoenix][pittsburg] =═10;
cityMap[phoenix][pueblo] =═3;
cityMap[pierre][pendleton] =═2;
cityMap[pittsburg][pensacola] =═4;
cityMap[princeton][pittsburg] =═2;
cityMap[pueblo][pierre] =═3;

Тип данных stringVector═≈ это вектор целых чисел, индексированный строками. Тип данных graph═≈ это двумерный разреженный массив, индексированный строками и содержащий целые числа. Последовательность операторов присваивания инициализирует граф. Граф, показанный на рис.═16.1, реализован в листинге═16.1.

Можно использовать набор классических алгоритмов для обработки таких графов. Одним из примеров является алгоритм Дейкстры поиска кратчайшего пути. Требуется указать город, с которого начинается путь. При этом создается приоритетная очередь для пар расстояние/город. Она инициализируется нулем для начального города. Приоритетная очередь содержит города в порядке от ближайшего до самого дальнего. Определение типа данных DistancePair выглядит следующим образом: 

struct DistancePair
{
  unsigned int first;
  string  second;
  DistancePair() : first(0) { }
  DistancePair(unsigned int f, string & s)
    : first(f), second(s) { }
};

bool operator < (DistancePair & lhs, DistancePair & rhs)
{ return lhs.first < rhs.first; }

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

void shortestDistance(const graph & cityMap,
           const string & start,
           stringVector & distances)
{
  // обработать приоритетную очередь расстояний до городов
  priority_queue< DistancePair, Vector<DistancePair>, greater<DistancePair> > que;

  que.push(DistancePair(0, start));
  while (! que.empty() )  
   {
    // выбрать ближайший город из очереди
    int distance = que.top().first;
    string city = que.top().second;
    que.pop();

    // если мы еще не встречали такой город, обработать его
    if (0 == distances.count(city))
     {
      // затем добавить его к карте
      // кратчайших расстояний
      distances[city] = distance;

      // и занести в очередь новые значения
      stringVector::iterator start, stop;
      start = cityMap[city].begin();
      stop = cityMap[city].end();

      for (; start != stop; ++start)
       {
        que.push(DistancePair(distance + (*start).second, 
                 (*start).first) );
       }  
     }//if
   }//while
}

16.5. Пример программы: алфавитный указатель

Разделы

Последним примером является алфавитный указатель. Программа использует связные списки и тип данных multimap. multimap═≈ это разновидность карт, которая позволяет индексировать одним ключом несколько данных.

Алфавитный указатель представляет собой список упорядоченных по алфавиту слов, который показывает номера строк, где встречается то или иное слово. Эти значения хранятся в алфавитном указателе в виде мультикарты multimap, индексированной словами (тип данных string). Ее содержимое═≈ целые числа (номера строк в тексте). Мультикарта используется потому, что одно и то же слово встречается в нескольких местах. На самом деле обнаружение таких повторений═≈ главное предназначение алфавитного указателя.

Тип данных для алфавитного указателя задается следующим образом: 

class concordance // алфавитный указатель
{
typedef multimap<string, int> wordDictType;

public:
    concordance() : wordMap() { }
    void addWord (string, int);
    void readText(istream &);
    void printConcordance(ostream &);

private:
    wordDictType wordmap;
};

Создание алфавитного указателя разбивается на два шага. Сперва он генерируется программой (строки текста считываются из входного потока), а затем результат печатается в выходной файл. Эти два шага реализуются в функциях-членах readText() и printConcordance(). Первая из них записывается следующим образом: 

void concordance::readText(istream & in)
// считать текст из входного потока,
// занося слова в алфавитный указатель
{
string line;

  // читать строки входного потока
  for (int i=1; getline(in, line); i++)
   {
    //преобразовать в нижний регистр
    allLower(line); 

    //разбить строку на слова
    list<string> words;
    split(line, " ,.;:", words); 

    //внести слова в коллекцию
    list<string>::iterator wptr; 

    for (wptr = words.begin(); wptr != words.end(); ++wptr)
     { addWord(*wprt, i); }
   }
}

Строки текста считываются из входного потока одна за другой. Их текст прежде всего преобразуется к нижнему регистру. Затем строка разбивается на слова с помощью функции split(). Набор литер-разделителей и исходный текст передаются как аргументы. Эта функция иллюстрирует некоторые из возможностей обработки текстовых строк, заложенных в библиотеку STL: 

void split(string & text, string & separators, list<string> & words)
{
  int n = text.length();
  int start, stop;

  // найти первую букву, не разделитель
  start = text.find_first_not_of(separator);

  while ( (start >=═0) && (start < n) )
   {
    // найти конец текущего слова
    stop = text_find_first_of(separators, start);
    if ( (stop <═0) || (stop > n) ) stop = n;

    // добавить слово к списку слов
    words.push_back(text.substr(start, stop-start));

    // найти начало следующего слова
    start = text.find_first_not_of(separators,stop+1);
   }
}

Вслед за вызовом функции split() каждое найденное слово добавляется в алфавитный указатель с помощью следующего метода: 

void concordance::addWord(string word, int line)
{
  // проверить, не встречается ли слово в списке
  // сначала найти диапазон вхождений с нужным ключом
  wordDictType::iterator low =
    wordMap.lower_bound(word);

  wordDictType::iterator high = 
    wordMap.upper_bound(word);

  // цикл по вхождениям, соответствуют ли они строке
  for (; low != high; ++low)
   { if ( (*low).second == line ) return; }

  // не встретилась, добавим
  wordMap.insert(make_pair(word, line));
}

Метод addWord() гарантирует, что значения в карте слов не дублируются, если какое-либо слово встречается в одной строке дважды. Это достигается благодаря проверке записей, которые соответствуют ключу поиска. Каждая запись проверяется на совпадение номеров строк, и в случае совпадения запись в указатель не добавляется. Только если цикл проверки завершается без обнаружения записи с тем же номером строки, новая пара слово/номер строки добавляется в карту.

Последний шаг═≈ распечатать алфавитный указатель. Это делается следующим образом: 

void concordance::printConcordance(ostream & out)
{
  string lastword("");
  wordDictType::iterator pairPtr;
  wordDictType::iterator stop = wordMap.end();

  for(pairPtr = wordMap.begin(); pairPtr != stop; ++pairPtr)
   {
    // если слово такое же, что и предыдущее,
    // просто напечатать номер строки
    if ( lastword == (*pairPtr).first)
     {
      out << " " << (*pairPtr).second;
     }
    else // первое вхождение слова
     {
      lastword = (*pairPtr).first;
      out << endl << lastword << ": " << 
        (*pairPtr).second;
     }
   } 

  // завершить последнюю строку вывода
  cout << endl; 
}

Итератор циклически проходит по всем элементам, содержащимся в списке слов. Каждое новое слово порождает новую строку вывода; следующие за словом номера строк разделяются пробелами. Если, к примеру, на входе задан текст 

It was the best of times,
it was the worst of times.

то на выходе будут напечатаны слова от ╚best╩ до ╚worst╩: 

best:═ 1
it:═   1═2
of:═   1═2
the:═  1═2
times:═1═2
was:═  1═2
worst:═1

16.6. Будущее ООП

Разделы

Мы отмечали, что во многих отношениях библиотека STL не является объектно-ориентированной. Скорее, она написана под воздействием функционального программирования. Означает ли включение STL в список стандартных библиотек C++, что объектно-ориентированное программирование выходит из моды?

Безусловно, нет. Объектно-ориентированные техники проектирования и программирования не имеют себе равных при разработке больших сложных систем. В большинстве задач программирования ООП будет оставаться главенствующим. Однако разработка STL (и не только) показывает желанные признаки того, что сообщество объектно-ориентированных программистов признает, что не все идеи должны иметь выражение в объектно-ориентированном стиле, равно как и не все проблемы обязаны решаться с помощью объектно-ориентированной техники.

Упражнения

Разделы

  1. Предположите, что имеется непосредственная реализация класса линейной структуры данных (например, класса связных списков из главы═15). Опишите основные свойства класса-итератора для этой структуры. За какой информацией должен следить ваш итератор?
  2. Теперь рассмотрите нелинейную структуру данных (например, двоичное дерево). Какую информацию должен поддерживать итератор для того, чтобы выдавать элементы, содержащиеся в контейнере?

Пример: STL