Из жизни студентов


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

Важно помнить, что рекурсия сама по себе стоит дорого, поэтому важны детали реализации конкретного алгоритма. Над деталями реализации алгоритмов библиотеки STL потрудились специалисты, и результатом их труда является достаточно высокая эффективность, которую отмечают многие разработчики. К сожалению, возможности STL очень скудно описаны в MSDN, хотя в мире существуют книги, где библиотека и технология ее использования для решения конкретных задач описаны достаточно подробно. Среди доступных нам книг на русском языке, конечно, следует отметить последнюю книгу Б. Страуструпа «Язык программирования C++», 3-е изд. — СПб: «Невский Диалект», 1999. Но она описывает библиотеку концептуально. В ней почти нет текстов программ, готовых к употреблению в среде Visual Studio. Поэтому мне захотелось дать быстрый путь к овладению некоторыми возможностями библиотеки тем читателям, которые обладают хорошим алгоритмическим мышлением, имеют некоторый опыт работы с динамическими структурами данных, но не знакомы с особенностями структуры и использования STL. Ниже будут приведены примеры практического использования контейнеров и алгоритмов STL, но не будет подробного описания заложенных в них принципов.
  
Шаблоны
STL — это библиотека шаблонов. Прежде всего вспомним, что такое шаблон. Различают шаблоны функций и шаблоны классов. Шаблон функций (function template) является средством языка C++, позволяющим избежать рутинного переписывания кодов функций, которые имеют сходный алгоритм, но разные типы параметров. Классическим примером, иллюстрирующим выгоды шаблона, является множество реализаций функции max (a, b) . При отсутствии механизма шаблонов для придания функции max () универсального характера следует создать несколько функций, разделяющих одно и то же имя. Например:
long max (long a, long b);
double max (double a, double b);
MyType max (mytype a, mytype b);
Vectors max (Vectors a, Vectors b);
Очевидно, что тела всех функций могут выглядеть совершенно одинаково для многих типов параметров. Например, коды функции max могут иметь вид:
return (a>b) ? а : b;
В таких случаях удобно использовать шаблон функции. Шаблон задается ключевым словом template:
template <class Т> Т max(Т х, Т у)
{
return (х>у) ? х : у;
};
Описатель <class т> — это аргумент шаблона. Символ т (type) означает произвольный тип данных т, который будет задан при использовании шаблона, т выполняет роль формального параметра, поэтому сам символ (т) может быть и другим, но везде одинаковым. При фактическом использовании шаблона место т заменяет какой-то уже описанный тип. Им может быть как стандартный, встроенный тип языка, так и новый тип, определенный пользователем. В том числе он может быть именем класса, определенного ранее. Важно, чтобы для типа был определен смысл операции > (больше). Если т заменяется классом, то в классе должна быть предварительно реализована операция operator> ().
Примечание
Не идите на поводу у ложного друга — переводчика термина operator. В английском языке он имеет смысл операции (например, операция + или операция <, операция логического или |, и т. д.). То, что мы называем оператором языка (например, оператор while, оператор for, условный оператор if, и т. д.), имеет английский аналог — statement (например, conditional statement if).
Если задан шаблон, то компилятор генерирует подходящие коды функции max () в соответствии с конкретными типами фактических параметров, использованных при вызове функции. Например, встретив во внешней функции коды:
Man a("Alex Black", 54), b("Galina Black", 44), с;
с = max (a, b);
cout « "\n Старший: " « с;
компилятор в сгенерированной по шаблону копии функции max при сравнении объектов класса Man использует функцию operator > (), которая должна быть определена внутри класса Man. Например, так:
int operator >(Man& m) { return m__Age > m. m_Age; }
Если в той же внешней функции встретится оператор:
cout « "\n max (10,011) = " « max (10,011);
то компилятор в другой копии функции max, сгенерированной по тому же шаблону, использует операцию >, определенную для стандартного типа данных int. Один раз написав шаблон функции max, мы можем вызывать ее для всех типов данных, для которых определена операция operator> (). Если для какого-то типа данных тело функции max не годится, то можно отменить (override) действие шаблона функции для этого типа. Например, определив функцию:
char* max (char* s, char *t)
{
return (strcmp (s, t) >0) ?s : t;
}
мы отменяем действие шаблона для символьных строк, так как функция, скроенная по шаблону, осуществляла бы ничего не значащее сравнение указателей s и t. При использовании шаблона следует строго соблюдать типы параметров и не надеяться на стандартные преобразования типов, по умолчанию осуществляемые компилятором при вызове обычных функций. Например, явно заданную функцию, скрывающую (отменяющую) шаблон:
double max (double, double);
можно вызывать с аргументами (int, double) или (float, long). Компилятор при этом автоматически преобразует параметры к типу double. Однако если явная декларация функции, скрывающей шаблон, отсутствует, то шаблон
template <class T> T max(Т х, Т у)
не позволит смешивать типы при вызове функции max. Таким образом, обращение int i=max (9, 8.); вызывает сообщение об ошибке: "Could not find a match for max (int, double) ", которое означает, что не найдена функция max () для пары аргументов типа (int, double).
  
Шаблон функции быстрой сортировки
Приведем пример реализации вышеупомянутого рекурсивного алгоритма сортировки массива переменных Quicksort. Его идея состоит в том, что меняются местами элементы массива, стоящие слева и справа от выбранного «центрального» (mid) элемента массива, если они нарушают порядок последовательности. Интервал, в котором выбирается центральный элемент, постепенно сжимается, «расправляясь» сначала с левой половиной массива, затем с правой. Функция Quicksort, приведенная ниже, реализует рекурсивный алгоритм быстрой сортировки. Далее следует код, который позволяет протестировать работу функции. Сортируется массив вещественных чисел, элементы которого заданы случайным образом:
void Quicksort (double *ar, int 1, int r)
{
//========== Рабочие переменные
double mid, temp;
//========== Левая и правая границы интервала
int i = 1, j = r;
//========== Центральный элемент
mid = ar[ (1 + г) /2];
//========== Цикл, сжимающий интервал
do
//== Поиск индексов элементов, нарушающих порядок
while (ar[i] < mid)
i++; // слева
while (mid < ar[j])
j--; // и справа
//== Если последовательность нарушена,
if (i <= j)
{
//===== то производим обмен
temp = ar[i];
ar[i++] = ar[j];
ar[j-—] = temp;
}
}
//========= Цикл do-while повторяется, пока
//========= есть нарушения последовательности
while (i <= j);
//========= Если левая часть не упорядочена,
if (I < j)
Quicksort (ar, 1, j); // то занимаемся ею
// Если правая часть не упорядочена,
if (i < r)
Quicksort (ar, i, r); // то занимаемся ею }
//========== Тестируем алгоритм
void main()
{
//========= Размер массива сортируемых чисел
const int N = 21;
double ar[N]; // Сам массив
puts("\n\nArray before Sorting\n");
for (int i=0; i<N; i++)
{
ar[i] = rand()%20;
if (i%3==0)
printf ("\n");
printf ("ar[%d]=%2.0f\t",i,ar[ij);
}
Quicksort(ar,0,N-1); // Сортировка
puts("\n\nAfter SortingNn");
for (i=0; i<N; i++)
{
if (i%3==0)
printf ("\n");
printf ("ar[%d]=%2.0f\t",i,ar[i]);
}
puts ("\n");
}
Для того чтобы сортировать массивы любого типа, целесообразно на основе данной функции создать шаблон. Оказывается, что для этого нужно приложить совсем немного усилий. В уже существующий код внесите следующие изменения:
template <class T>
void Quicksort (Т *ar, int 1, int r)
{
//======= Рабочие переменные
Т mid, temp;
//======= Далее следует тот же код, который приведен
//======= в оригинальной версии функции Quicksort
}
Проверьте функционирование, вставив в функцию main вызовы функции с другими типами параметров. Например:
void main()
{
//======= Размер массива сортируемых чисел
const int N = 21;
// double ar[N];
int ar[N];
puts("\n\nArray before SortingXn");
for (int i=0; i<N; i++)
{
ar[i] = rand()%20; if (i%3==0)
printf ("\n"); // printf ("ar[%d]=%2.0f\t",i,ar[i]);
printf ("%d\t",ar[i]);
}
Quicksort(ar,0,N-1);
puts("\n\nAfter SortingXn");
for (i=0; i<N; i + + ) ;
{
if (i%3==0)
printf ("\n"); // printf ("ar[%d]=%2.0f\t",i,ar[i]);
printf ("%d\t",ar[i]);
}
puts("\n");
}
В данный момент функция main настроена на сортировку массива целых. Внесите приведенные изменения и проверьте работу шаблона для массива целых. Уберите комментарии там, где они есть, но вставьте комментарии в строки программы, следующие ниже. После этой процедуры функция main будет настроена на проверку шаблона функции сортировки для массива вещественных. Проверьте и этот случай. Шаблон должен справиться с обоими.
Примечание
Перед запуском консольных приложений настройте консольное окно так, чтобы его размеры вмещали весь выходной текст. Для этого вызовите контекстное меню на заголовке консольного окна и дайте команду Properties. Откройте страницу на вкладке Layout и подстройте размеры окна в полях Width и Height группы Window Size.
  
Шаблоны классов
Шаблон классов (class template) в руководствах программиста иногда называется generic class или class generator. Шаблон действительно помогает компилятору сгенерировать определение конкретного класса по образу и подобию заданной схемы. Разработчики компилятора C++ различают два термина: class template и template class. Первый означает абстрактный шаблон классов, а второй — одно из его конкретных воплощений. Пользователь может сам создать template class для какого-то типа данных. В этом случае созданный класс отменяет (overrides) автоматическую генерацию класса по шаблону для этого типа данных. Рассмотрим стандартный пример, иллюстрирующий использование шаблона для автоматического создания классов, которые реализуют функционирование абстрактного типа данных «Вектор линейного пространства». Элементами вектора могут быть объекты различной природы. В примере создаются векторы целых, вещественных, объектов некоторого класса circle (вектор окружностей) и указателей на функции. Для вектора из элементов любого типа тела методов шаблона одинаковы, поэтому и есть смысл объединить их в шаблоне:
#include <iostream>
#include <string>
#include <math.h>
//====== Шаблон классов "Вектор линейного пространства"
template <class T> class Vector
{

//====== Данные класса
private:
Т *data; // Указатель начала массива компонентов
int size; // Размер массива
//====== Методы класса
public:
Vector(int);
~Vector()
{
delete[] data;
}
int Size()
{
return size;
}
T& operator [](int i)
{
return data[i];
}
};
//====== Внешняя реализация тела конструктора
template <class T> Vector<T>::Vector(int n)
{
data = new Т[n];
size = n; };
//====== Вспомогательный класс"Круг"
class Circle
{
private:
//====== Данные класса
int х, у; // Координаты центра
int r; // Радиус
public:
//====== Два конструктора
Circle ()
{
х = у = r = 0; }
Circle (int a, int b, int с) {
x = a;
У = b;
r = с;
}
//====== Метод для вычисления площади круга
double area ()
{
return 3.14159*r*r;
}
};
//====== Глобальное определение нового типа
//====== указателя на функцию
typedef double (*Tfunc) (double);
//====== Тестирование ч
void main ()
{
//===== Генерируется вектор целых
Vector <int> x(5) ;
for ( int i=0; i < x.SizeO; ++i)
{
x[i] = i; // Инициализация
cout « x[i] « ' ' ; // Вывод
}
cout « ' \n ' ;
//===== Генерируется вектор вещественных Vector <float> y(10);
for (i=0; i < y.SizeO; ++i)
{
y[i] = float (i); // Инициализация cout « y[i] « ' ' ; // Вывод
}
cout « ' \n' ;
//==== Генерируется вектор объектов класса Circle
Vector <Circle> z(4);
for (i=0; i< z.SizeO; ++i) // Инициализация
z[i] = Circle(i+100,i + 100,i+20) ;
cout « z[i].area() « " "; // Вывод
}
cout « ' \n' ;
//==== Генерируется вектор указателей на функции
Vector <Tfunc> f(3);
cout«"\nVector of function pointers: " ;
f[0] = sqrt; // Инициализация
f[l] = sin;
f[2] = tan;
for (i=0; i< f.Size(); ++i)
cout « f[i](3.) « ' '; // Вывод cout « "\n\n";
}
Обратите внимание на синтаксис внешней реализации тела конструктора шаблона классов. Vector<T> — это имя шаблона, a Vector (int n) — имя метода шаблона (конструктор). При использовании шаблона для генерации конкретного вектора объектов необходимо задать в угловых скобках тип данных, известный к этому моменту и видимый в этой области программы. Использование шаблона всегда предполагает наличие описателя типа при имени класса (Vector <type>). Имя Vector теперь не может быть использовано без указания конкретного типа элементов.
В рассмотренном примере операция [ ] определена в шаблоне как общая для всех типов Т, однако метоД area () определен только для объектов класса Circle и он применяется к объекту z [i] класса circle, вектор из четырех элементов которого автоматически создается компилятором при объявлении Vector <circle> z (4);. Работая с вектором указателей на функции, мы в цикле по переменой i вызываем i-ю функцию и посылаем ей в качестве аргумента вещественное число 3 (см. вызов f [i] (3.) ).
Если для какого-то типа переменных автоматически сгенерированный по шаблону класс не подходит, то его следует описать явно. Созданный таким образом класс (template class) отменяет автоматическое создание класса по шаблону только для этого типа. Например, предположим, что создан новый класс Man:
class Man
{
private:
string m_Name;
int m_Age;
public:
//======= Конструкторы
Man{}
{
m_Name = "Dummy";
m_Age = 0; }
Man (char* n, int a)
{
m_Name = string(n); m_Age = a;
}
Man (strings n, int a)
{
m_Name = n;
m_Age = a;
}
Man& operator=(const Man& m)
{
m_Name = m.m_Name;
m_Age = m.m_Age;
return *this;
}
Man(const Man& m)
{
*this = m;
}
//======== Деструктор
~Man()
{
cout « "\n+ + " « m_Name « " is leaving";
m_Name.erase (); }
bool operator==(const Man& m)
{
return m_Name == m.m_Name;
}
bool operator<(const Mans m)
{
//======= Упорядочиваем по имени
return m_Name < m.m_Name;
}
friend ostreams operator«(ostreams os, const Mans m);
};
//========= Внешняя реализация операции вывода
ostream& operator«(ostreams os, const Mans m)
{
return os « m.m_Name « ", Age: " « m.m_Age;
}
Для класса Man мы не хотим использовать class template Vector, но хотим со здать вектор объектов класса, работающий несколько иначе. С этой целью явн описываем новое конкретное воплощение (template class) класса Vector дл. типа Man.
class Vector <Man>
{
Т *data;
int size;
public:
Vector (int n, T* m);
~Vector 0 { delete [] data;
}
int Size()
{
return size;
}
T& operator [] (int i)
{
return data[i];
}
};
Vector <Man> : : Vector (int n, T* m)
{
size = n;
data = new Man [n] ;
for (int i=0; i<size; i++)
data [i] = m[i] ;
}
Отличие от шаблона состоит в том, что конструктор класса vector <Man> имеет теперь два параметра, а не один, как было в шаблоне. Теперь массив указателей data инициализируется данными массива объектов, поданного на вход конструктора. Цель этого нововведения — показать технику частного воплощения шаблона. Для проверки функционирования вектора из элементов типа Man следует создать какой-то тестовый массив, например:
Man miles ("Miles Davis", 60); // Отдельный Man
//====== Массив объектов класса Man
Man some [ ] =
{
Man("Count Basis", 70),
Man ("Duke Ellingtcnton", 90) ,
miles,
Man("Winton Marsales", 50) ,
};
а в функцию main ( ) добавить манипуляции с реальным вектором типа Man. В коде, который приведен ниже, обратите внимание на то, что при создании вектора men из четырех объектов класса Man вторым параметром передается адрес обычного массива объектов, инициализирующий все элементы (внутреннего для шаблона) массива data:
//====== Конструируем вектор объектов
//====== на основе массива объектов
Vector <Man> men (sizeof (some) /sizeof (Man) , some);
cout«"\nVector of Man: ";
//====== Вывод вектора
for (i=0; i< men. Size (); ++i)
cout « men[i] « "; ";
В шаблоне классов могут быть объявлены static данные и функции. При этом следует иметь в виду, что каждый конкретный класс, образованный по шаблону,
будет иметь свои собственные копии static членов. Эти члены будут общими для всех объектов конкретного класса, но различными для всех классов — реализаций шаблона.
Параметры шаблона
При описании шаблона можно задать более одного параметра. Например:
template <class T, int size=256> class Stack {...};
Теперь при создании конкретной реализации класса можно задать размер стека
Stack <int, 2048>;
или
Stack <double, 8*N>;
Важно запомнить, что числовой параметр должен быть константой. В примере переменная N могла быть описана как const int N=1024; но не могла быть переменной int N=1024;. При создании конкретного класса по шаблону возможно вложенное определение класса, например, если был описан частный случай класса — шаблон структур вида:
template <class T> struct Buffer {...};
то после этого можно создать конкретную структуру, в качестве типа которой задать структуру, созданную по этому же шаблону, например:
Buffer <Buffer <int> > buf;
Между двумя закрывающими угловыми скобками » надо вставить символ пробела, так как в языке C++ операция >> имеет самостоятельный смысл, и не один. Существует возможность генерировать по шаблону классы, которые являются производными от какого-то базового класса. Например, если описать базовый класс TList, в котором не определен тип элементов хранения, то есть используется тип void, то целесообразно ввести описание шаблона производных классов:
class TList
//======== Начало списка
void *First;:
public:
void insert (void*);
int order (void*, void*, int);
//======== Другие методы

};
template <class T> class List :
public TList T *First;
public:
void insert (T *t)
{
TList::insert(t);
}
int order (T *pl, T *p2, int n)
{
return TList::order(pi, p2, n);
}
//======= Другие методы
};
В этих условиях становится возможным декларация списка, состоящего из элементов одного определенного типа, например List <int> intList;, или гетерогенного списка, состоящего из элементов различных типов, образованных от какого-то одного базового класса. Например, объявление List <Device> DevList; генерирует класс для работы со списком приборов, из иерархии классов Device, то есть в списке могут быть объекты классов, производных от Device. Аналогичный результат даст объявление List <Man> ManList; и т. д. Вспомните, что работать с объектами производных классов можно с помощью указателей на базовый класс.
  
Контейнеры библиотеки STL
Теперь, когда вы вспомнили, что такое шаблоны функций и шаблоны классов, мы можем исследовать возможности стандартной библиотеки шаблонов STL. В июле 1994 года специальный комитет Международной организации по принятию стандартов (ANSI/ISO C++) проголосовал за то, чтобы принять STL в качестве части стандарта языка C++. Предложение было основано на исследовании обобщенного (generic) программирования и концепции библиотеки (generic software library), которое проводили Alex Stepanov, Meng Lee и David Musser. Главной целью при разработке библиотеки было достижение общности (generality) подхода к различным структурам данных и алгоритмам их обработки без ущерба эффективности кода.
В STL определены два типа контейнеров — последовательности (sequence containers) и ассоциативные контейнеры. Все контейнеры предназначены для хранения данных любого типа. Последовательности предполагают последовательный доступ к своим элементам, а ассоциативные контейнеры работают по принципу ассоциации ключа (key) с его значением (value). Можно считать, что ассоциативные контейнеры хранят пары произвольных элементов и производят поиск по ключу, используя технику hash-таблиц. В STL существует три типа последовательных контейнеров: vector, deque И list.
  
Последовательности типа vector
Для их использования необходимо подключить файл заголовков <vector> и сделать доступным (видимым) стандартное (std) пространство имен:
#include <vector> using namespace std;
Обратите внимание на отсутствие расширения .h в директиве подключения файла заголовков. Дело в том, что STL используется на множестве различных платформ с применением разных компиляторов. Файлы заголовков в разных условиях имеют разные расширения. Они могут иметь расширение Н, НРР или НХХ. Для того чтобы одинаково запутать всех разработчиков, было решено вовсе не использовать расширение для файлов заголовков библиотеки STL. Пространство имен std позволяет избежать конфликта имен. Если вы назовете какой-то свой класс тем же именем, что и класс из STL (например, string), то обращение вида std: : string однозначно определит принадлежность класса стандартной библиотеке. Директива using позволяет не указывать (многократно) операцию разрешения области видимости std: :, поэтому можно расслабиться и не писать std: : string, a писать просто — string.
Вектор является шаблоном класса, который настраивается с помощью двух параметров:
vector<class T, allocator<class T> >
Объект, который управляет динамическим выделением и освобождением памяти типа т, называется allocator. Для большинства типов контейнеров он обычно объявляется по умолчанию в конструкторе. Для «хитрых» данных, например требующих памяти в глобальном heap, видимо, можно изобрести индивидуальный распределитель памяти. Но в большинстве случаев работает вариант по умолчанию. Кроме того, с типом vector обычно связаны.4 типа сущностей:

  • Pointer — ведет себя как указатель на тип т;
  • const pointer — не позволяет изменить данные типа т, на которые он указывает;
  • reference — ссылки на данные типа т;
  • const reference— не позволяет изменить данные типа т, на которые она ссылается.

Обычно эти сущности являются тем, чем и должны являться, но это не гарантируется. Они могут быть более сложными объектами.
Итак, vector является аналогом обычного массива в языке С, за исключением того, что он может автоматически изменять память по мере надобности. Доступ к данным обеспечивается с помощью операции выбора [ ]. Вставка новых элементов эффективна только в конец контейнера (push_back). Удаление — тоже. Данные операции в начале или середине влекут сдвиги всего массива данных, что резко снижает эффективность работы контейнера. Такие операции называются линейными, имея в виду тот факт, что время их выполнения линейно зависит от количества элементов в контейнере. Вставка или удаление в конце называются константными операциями, так как время их выполнения является константой для данной реализации и не зависит от количества элементов. Вот простая программа, иллюстрирующая использование вектора. Так как в приложениях консольного типа обычно возникают проблемы с русификацией, то для вывода текста мы используем английский язык:
#include <vector>
#include <algorithm>
#include <iostream> using namespace std;
//======= Вводим тип для сокращения текста (места)
typedef unsigned int uint;
void main ()
{
//======== Вектор целых
vector<int> v(4);
cout « "\nlnt Vector:\n";
for (uint i=0; i<v.size(); i++)
{
v[i] = rand()%10 + 1;
cout « v[i] « "; ";
}
//======= Сортировка по умолчанию sort (v.begin (), v.end());
cout « "\n\nAfter default sort\n";
for (i=0; i<v.size(); i++) cout « v[i] « "; ";
//======== Удаление элементов
v.erase(v.begin());
cout « "\n\nAfter first element erasure\n";
for (i=0; i<v.size(); i++) cout « v[i] « "; ";
v. erase (v. end ()-2, v.endO);
cout « "\n\nAfter last 2 elements erasure\n";
for (i=0; i<v.size(); i++)
cout « v[i] « "; ";
//======== Изменение размеров
int size = 2; v.resize(size);
cout « "\n\nAfter resize, the new size: " « v.size()
« endl; for (i=0; i<v.size(); i++)
cout « v[i] « "; ";
v.resize(6,-1);
cout « "\n\nAfter resize, the new size: " « v.size()« endl;
for (i=0; i<v.size(); i++)
cout « v[i] « "; ";
//======== Статистика .
cout « "\n\nVector's maximum size: " « v.max_size() « "XnVector's capacity: " « v.capacity() « endl
//======== Резервирование
v.reserve (100);
cout « "\nAfter reserving storage for 100 elements:\n"
« "Size: " « v.sizeO « endl :
« "Maximum size: " « v.max_size() « endl
« "Capacity: " « v.capacity() « endl;
v.resize(2000);
cout « "\nAfter resizing storage to 2000 elements:\n"
« "Size: " « v.size() « end1
« "Maximum size: " « v.max_size() « end1
« "Capacity: " « v.capacity() « endl; cout « "\n\n";
}
Для того чтобы лучше уяснить смысл и различие методов size, resize, max_size и capacity, мы несколько раз повторяем вызовы этих методов. Если вы читаете книгу вдалеке от компьютера, то вам, возможно, будет интересно узнать, что программа выведет в окно консольного приложения:
Int Vector:
2; 8; 5; 1;
After default sort
1; 2; 5; 8;
After first element erasure
2; 5; 8;
After last 2 elements erasure 2;
After resize, the new size: 2,
Vector capacity: 4 2; 0 ;
After resize, the new size:
6 2; 0; -1; -1; -1; -1;
Vector's maximum size: 1073741823
Vector's capacity: 6 After reserving storage for 100 elements:
Vector's size: 6
Vector's maximum size: 1073741823
Vector's capacity: 100
After resizing storage to 2000 elements:
Vector's size: 2000
Vector's maximum size: 1073741823
Vector's capacity: 2000

 

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г. Яндекс.Метрика