|
В подобных ситуациях владение стандартными
динамическими структурами данных и алгоритмами
может сэкономить массу усилий, так как их
разработчики уже выполнили большую часть
неблагодарной черновой работы, тщательно
отладили динамику жизни структур данных и все
ветви алгоритмов. Кроме того, они провели анализ
эффективности алгоритмов и привели их оценки.
Сравним для примера две реализации алгоритма
сортировки. Все знают, что рекурсивный алгоритм
быстрой сортировки Quicksort, —изобретенный С.
A. R. Ноаге в 1960 году, считается одним из
самых эффективных в смысле количества
необходимых операций для выполнения работы. Так,
для сортировки массива в п элементов этому
алгоритму понадобится всего лишь O(n Iog2 n)
операций.
В библиотеке, подключаемой файлом заголовков
stdlib.h, есть функция qsort, которая использует
алгоритм Quicksort для сортировки массива
элементов произвольного типа. Кроме сортируемого
массива в функцию qsort необходимо передать
адрес функции, которая сравнивает два элемента
между собой. Алгоритм использует это сравнение
для упорядочивания массива. Следующая программа
демонстрирует, как можно воспользоваться
функцией qsort для сортировки массива целых,
вводимого пользователем. Для ее отладки я
воспользовался проектом Console консольного
типа, процедура создания которого была описана
ранее. Из-за ошибок, связанных с использованием
бета-версии Studio.Net, мне пришлось изменить
конфигурацию проекта с Debug на Release. Это
можно сделать,
дав команду
Build > Configuration Manager
и выбрав
Release
в окне
Active Solution Configuration:
#include
<stdlib.h>
#include
<iostream>
using namespace
std;
//=== Внешняя функция сравнения переменных типа
int
inline int
crop (const void *a, const void *b)
{
int
i = *(int *)a, j = *(int *)b;
return
(i < j) ? -1 : (i > j) ? 1 : 0;
}
void
main()
{
int
array [1024],
//
Сортируемый массив
n - 0;
//
Счетчик элементов
cout «"Enter some integers (Press Ctrl+z to
stop)\n";
//=== Вводим по принципу "пока не надоест". Для
выхода
//=== из цикла надо ввести EOF (то
есть Ctrl+z, Enter)
while
(cin » array[n++])
//==== Шаг назад, так как мы сосчитали EOF n—;
qsort (array, n, sizeof(int), cmp) ;
for (int
i = 0; i < n; i++)
cout
« array[i] « endl;
cout
« endl;
}
Теперь сравним этот фрагмент с тем, который
использует стандартный контейнер vector и
алгоритм sort из библиотеки STL (Standard
Template Library):
#include
<algorithm>
#include
<vector>
#include
<iostream>
using namespace
std;
void
main ()
{
vector<int> v; //
Сортируемый контейнер
int
i; // Рабочая переменная
cout «"Enter some
integers (Press Ctrl+z to stop)\n";
while
(cin » i) // Вводим те же числа
v.push_back (i); //
Помещаем в конец контейнера
//======= Сортируем контейнер, используя тип
//======= упорядочения, принятый по умолчанию
sort (v.begin () , v.end());
for
(i =0; i < int(v.size()); i++)
cout
« v[i] « endl;
cout « endl;
}
По умолчанию алгоритм sort использует для
сравнения элементов операцию меньше, то есть
сортирует контейнер по возрастанию.
Сравнительная оценка эффективности двух
реализаций, которую проводили специалисты
(числа, конечно, вводились не вручную),
показывает, что эффективность второй версии выше
в 10-20 раз. Она зависит от размера массива и
степени его упорядоченности. Приведем одну из
причин такого результата.
-
Универсальность первого алгоритма
реализуется на этапе выполнения за счет
вызова generic-функции стр () и
преобразования типов указателей.
-
Универсальность второго подхода реализуется
за счет настройки шаблона на конкретный тип
переменных, что происходит на этапе
компиляции.
Важно помнить, что рекурсия сама по себе стоит
дорого, поэтому важны детали реализации
конкретного алгоритма. Над деталями реализации
алгоритмов библиотеки STL потрудились
специалисты, и результатом их труда является
достаточно высокая эффективность, которую
отмечают многие разработчики. К сожалению,
возможности STL очень скудно описаны в MSDN,
хотя в мире существуют книги, где библиотека и
технология ее использования для решения
конкретных задач описаны достаточно подробно.
Среди доступных нам книг на русском языке,
конечно, следует отметить последнюю книгу Б.
Страуструпа «Язык программирования C++», 3-е
изд. — СПб: «Невский Диалект», 1999. Но она
описывает библиотеку концептуально. В ней почти
нет текстов программ, готовых к употреблению в
среде Visual Studio. Поэтому мне захотелось дать
быстрый путь к овладению некоторыми
возможностями библиотеки тем читателям, которые
обладают хорошим алгоритмическим мышлением,
имеют некоторый опыт работы с динамическими
структурами данных, но не знакомы с
особенностями структуры и использования STL.
Ниже будут приведены примеры практического
использования контейнеров и алгоритмов STL, но
не будет подробного описания заложенных в них
принципов. |
