Работа с Visual Studio.Net
Использование STL
В подобных ситуациях владение стандартными динамическими структурами данных и алгоритмами может сэкономить массу усилий, так как их разработчики уже выполнили большую часть неблагодарной черновой работы, тщательно отладили динамику жизни структур данных и все ветви алгоритмов. Кроме того, они провели анализ эффективности алгоритмов и привели их оценки. Сравним для примера две реализации алгоритма сортировки. Все знают, что рекурсивный алгоритм быстрой сортировки 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-функции стр
() и преобразования типов указателей.
- Универсальность второго
подхода реализуется за счет настройки шаблона на конкретный тип переменных,
что происходит на этапе компиляции.
|