Учебник по Visual C++ .Net



             

Использование STL - часть 2


//=== из цикла надо ввести 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, но не будет подробного описания заложенных в них принципов.




    Содержание  Назад  Вперед