Сечения массива

Проблемы оптимизации работы с матрицами давно волнуют создателей компиляторов. В то далекое время, когда решения задач электродинамики и вообще краевых задач матфизики еще интересовали влиятельных людей нашей страны (скорее, научные авторитеты убеждали их, что такие задачи следует решать), мы, используя язык PL/I или FORTRAN, конечно же, хранили и обрабатывали матрицы в одномерных массивах. Дело в том, что выбор одного элемента из более естественного для матриц двухмерного массива обходился дорого. Выработалась особая техника работы с одномерными массивами, хранящими матрицы (обычно разреженные). В языке C++ операция выбора элемента из двухмерного динамического массива не намного дороже, чем из одномерного (да и скорости изменились), поэтому острота проблемы спала. Тем не менее проблема экономии времени при решения сложных краевых задач не ушла в прошлое.

STL имеет пару вспомогательных классов: slice и gslice, которые созданы для того, чтобы было удобно работать со срезами (сечениями) одномерных массивов. Если вы храните двухмерную матрицу в последовательности типа valarray, то элементы одной строки матрицы или одного ее столбца можно представить в виде сечения, то есть определенной части всей последовательности. Конструктор класса slice определяет закономерность, в соответствии с которой будут выбираться элементы последовательности, чтобы образовать срез. Например, объект slice s(0, n , 2); представляет собой сечение из п элементов последовательности. Элементы выбираются начиная с нулевого, через один, то есть с шагом 2. Если вы храните матрицу пхп в последовательности типа valarray и при этом она упорядочена по строкам (сначала первая строка, затем вторая, и т. д.), то третью строку матрицы можно выбрать с помощью сечения:

slice s (2*n, n , 1);

Действительно, параметры указывают, что надо пропустить 2*n элементов, затем выбрать n элементов с шагом по одному. Если матрица хранится a la FORTRAN, то есть по столбцам, то для выбора той же строки надо определить сечение:

slice s (2, n , n);

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

int n = 5, // Размерность матрицы n (размером пхп) пп = п*п;

// Размерность valarray

//=== Создаем матрицу (одномерную последовательность)

valarray<double> a (nn);

//=== Генерируем ее элементы по закону f (Пока его нет)

generate (&a[0], &a[nn], f) ;

//====== Создаем сечение

slice s (0, n , 1);

//====== Выделяем сечение (первую строку,

//====== если матрица хранится по строкам)

valarray<double> v = a[s];

Вы видите, что объект s класса slice помещается в то место, куда мы обычно помещаем целочисленный индекс массива или последовательности. Такая интерпретация операции [ ] непривычна. Вы, вероятно, догадались, что роль объекта s в приведенном фрагменте является чисто эпизодической. Можно обойтись и без него, заменив его временным безымянным объектом, который создаст компилятор. При этом конструкция выражения будет более эффективной, но и более головоломной. Последние две строки фрагмента можно заменить одной строкой:

valarray<double> v = afslice (0, n , 1);

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

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

Содержание раздела