Гибкая сортировка таблиц с использованием списков типов

Описывается применение идиомы обобщенного программирования к работе с табличной информацией в памяти компьютера. Демонстрируется возможность использования шаблонных конструкций языка С++ для порождения таблиц произвольной структуры с возможностью их сортировки на основе заданных критериев. У статт...

Full description

Saved in:
Bibliographic Details
Date:2006
Main Author: Марьянович, О.Т.
Format: Article
Language:Russian
Published: Інститут програмних систем НАН України 2006
Subjects:
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/2316
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:Гибкая сортировка таблиц с использованием списков типов / О.Т. Марьянович// Проблеми програмування. — 2006. — N 1. — С. 93-98. — Бібліогр.: 1 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1859547580076130304
author Марьянович, О.Т.
author_facet Марьянович, О.Т.
citation_txt Гибкая сортировка таблиц с использованием списков типов / О.Т. Марьянович// Проблеми програмування. — 2006. — N 1. — С. 93-98. — Бібліогр.: 1 назв. — рос.
collection DSpace DC
description Описывается применение идиомы обобщенного программирования к работе с табличной информацией в памяти компьютера. Демонстрируется возможность использования шаблонных конструкций языка С++ для порождения таблиц произвольной структуры с возможностью их сортировки на основе заданных критериев. У статті описується застосування ідіоми узагальненого програмування для роботи з табличною інформацією у пам’яті комп’ютера. Демонструється можливість використання шаблонних конструкцій мови С++ для генерування таблиць довільної структури з можливістю їх сортування згідно заданих критеріїв. The article describes application of generic programming paradigm to processing tabular information in computer memory. The use of C++ templates for compile-time generation of arbitrary structured tables with possibility of their sorting according to specified criteia is demonstrated.
first_indexed 2025-11-26T02:44:47Z
format Article
fulltext Прикладне програмне забезпечення © О.Т. Марьянович, 2006 ISSN 1727-4907. Проблеми програмування. 2006. № 1 93 УДК 681.3 О. Т. Марьянович ГИБКАЯ СОРТИРОВКА ТАБЛИЦ С ИСПОЛЬЗОВАНИЕМ СПИСКОВ ТИПОВ Описывается применение идиомы обобщенного программирования к работе с табличной информацией в памяти компьютера. Демонстрируется возможность использования шаблонных конструкций языка С++ для порождения таблиц произвольной структуры с возможностью их сортировки на основе задан- ных критериев. Введение В практике программирования не- редко возникают задачи, подобные тем, ко- торые решает язык SQL, однако в силу раз- личных ограничений (одним из них явля- ется требование переносимости на разные платформы) реализацию таких задач прихо- дится осуществлять в памяти компьютера без использования сторонних библиотек. Речь идет о задачах анализа информации, организованной в виде связанных таблиц. При этом источником информации может быть не реляционная база данных, а нечто иное, например данные могут поступать по сети на основе определенного протокола. Характерными примерами рассмат- риваемых задач является поиск количества записей по определенному критерию, свя- зывание записей из нескольких таблиц, аг- регирование информации из различных таб- лиц и т.п. Для эффективного решения таких задач ключевым моментом является воз- можность сортировки таблиц на основе раз- личных критериев. Реализация подобных задач на ос- нове традиционного С++ программирования сводится, по сути, к следующему: а) для каждой таблицы вводится класс (TableRow), члены данных которого представляют поля строки таблицы; б) каждая таблица представляется специальным классом (Table), содержащим член данных, хранящий коллекцию объек- тов класса TableRow; в) предоставляется возможность сор- тировать записи таблицы – реализуется ме- тод sort. Существует множество подходов к реализации алгоритмов сортировки, одним из который является создание массива ука- зателей на строки таблицы (индекса) и сор- тировки данного массива с использованием стандартной функции qsort. При этом для каждого из необходимых критериев сорти- ровки нужно реализовать функцию compare сравнения строк таблицы в соответствии с данным критерием; г) в классе Table реализуются раз- личные прикладные методы, обеспечиваю- щие решение задач анализа данных. Выполнение пунктов (а–в) не пред- ставляет сложности, однако, если таблиц много, возникает желание избавиться от не- обходимости ручного тиражирования одно- типного кода, возложив данную задачу на компилятор C++. Данная заметка посвящена описанию реализации такого подхода с использова- нием шаблонных конструкций языка С++ и технических приемов, изложенных в [1]. Использование шаблонных таблиц с сортировкой Прежде чем перейти к деталям реа- лизации, покажем, каким образом можно использовать шаблонные таблицы с сорти- ровкой в программах на C++. Основным классом является шаб- лонный класс Table, объявленный как template <class TList, class TIndexList = Loki::NullType> class Table. Первый аргумент шаблона - список типов (класс Typelist библиотеки Loki, см. [1]), задающий структуру таблицы (каждый тип из списка соответствует типу данных колонки таблицы). Второй аргумент - список типов, ка- ждый элемент которого в свою очередь яв- ляется списком типов. Такие вложенные списки типов содержат определения крите- риев сортировки, которые могут быть при- Прикладне програмне забезпечення 94 менены к данной таблице. Критерий сорти- ровки представляет собой последователь- ность пар колонка/порядок сортировки в форме шаблонного класса SortSpec, объяв- ленного как template <int COL, int ORDER = 0> struct SortSpec {enum {column = COL }; enum {order = ORDER };}. Данный класс содержит номер ко- лонки, по которой следует выполнять сор- тировку, и порядок сортировки (возрастаю- щий/убывающий). Конструктор таблицы содержит ар- гумент, задающий ее размер (количество строк). Доступ к ячейкам таблицы осущест- вляется при помощи методов template <un- signed int COL, typename VAL> inline void SetCell(unsigned int row_, const VAL val) и template <unsigned int COL, typename VAL> inline VAL GetCell(unsigned int row_) const. Кроме того, имеются методы template <int INDEX> void sort(), inline void unsort(), inline void dump() и template < class TList > void dump(), позволяющие выпол- нять сортировку по заданному критерию, отменять сортировку (возвращаться к есте- ственному порядку строк таблицы) и выво- дить таблицу на стандартное устройство по- строчно в соответствии с ее текущей сорти- ровкой. При этом есть возможность избира- тельного вывода колонок посредством шаб- лонного варианта функции dump, где в ка- честве параметра передается список коло- нок, которые следует выводить. В качестве типов колонок таблицы могут служить элементарные С++ типы, а также классы, удовлетворяющие неслож- ным требованиям, среди которых реализа- ция операторов присваивания и сравнения, а также функции dump для вывода объекта на стандартное устройство. В частности, в та- ком качестве для хранения текстовых строк используется специально разработанный класс template <unsigned int INIT_BUF_SIZE = 16 > class StringField. Поясним сказанное следующим при- мером. Пусть необходимо работать со спи- ском людей, содержащим следующую ин- формацию: фамилия, год рождения, место рождения, заработная плата. При этом тре- буется выводить данный список, отсортиро- ванный по любой из колонок в возрастаю- щем порядке, и фамилии всегда должны следовать в алфавитном порядке. Кроме того, нужно иметь возможность выводить таблицу, отсортированную по последней колонке в убывающем порядке. Для этого достаточно объявить таб- лицу следующим образом: enum { name, year, place, wage }; typedef SortSpec<name, asc> ByName; typedef SortSpec<year, asc> ByYear; typedef SortSpec<place, asc> ByPlace; typedef SortSpec<wage, asc> ByWage; typedef SortSpec<wage, desc> By WageDesc; typedef Table< TYPELIST_4(StringField<>, int, StringField<>, int), TYPELIST_5( TYPELIST_1( ByName ), TYPELIST_2( ByYear, ByName ), TYPELIST_2( ByPlace, ByName ), TYPELIST_2(ByWage, ByName ), TYPELIST_2( ByWageDesc, ByName )) > PeopleData. Перечислимый тип введен для удоб- ства ссылки на порядковый номер столбца таблицы. Первый параметр шаблона инструк- тирует компилятор, что колонками таблицы являются строка, целое число, строка и це- лое число, следующие в указанном порядке. Второй параметр шаблона говорит о том, что таблица должна поддерживать сор- тировку по пяти различным критериям. При этом список типов, соответствующий, ска- жем, пятому критерию сортировки, говорит о том, что сортировать следует вначале по четвертой колонке в убывающем порядке, а затем – по первой колонке в возрастающем порядке. Пример использования таким обра- зом объявленной таблицы приводится ниже. Вначале объявляются типы, опреде- ляющие колонки таблицы: typedef Loki::Int2Type<name> Name; typedef Loki::Int2Type<year> Year; typedef Loki::Int2Type<place> Place; typedef Loki::Int2Type<wage> Wage;. Затем объявляется макрос, упро- щающий заполнение таблицы: #define SET_ROW(ROW, NAME, YEAR, PLACE, WAGE) \ table.SetCell<0, const char* >(ROW, NAME);\ Прикладне програмне забезпечення 95 table.SetCell<1, int >(ROW, YEAR); \ table.SetCell<2, const char*>(ROW, PLACE);\ table.SetCell<3, int >(ROW, WAGE); В главной функции вначале созда- ется таблица из четырех записей: PeopleData table(4). Данная таблица заполняется инфор- мацией: SET_ROW(0, "Smith", 1960, "USA", 1000); SET_ROW(1, "Armstrong", 1975, "USA", 1200); SET_ROW(2, "Lee", 1956, "China", 800); SET_ROW(3, "Petroff", 1982, "Russia", 300);. Теперь, чтобы вывести таблицу в первоначальном порядке следования запи- сей, достаточно выполнить table.dump(), чтобы вывести только имя и место рожде- ния, достаточно выполнить table.dump<TY- PELIST_2(Name, Place)>(), чтобы вывести целиком таблицу, отсортированную по году/имени, достаточно выполнить table.sort<1>(); table.dump(), чтобы вывести таблицу, отсортированную по убыванию заработной платы, включив в нее только заработную плату и имя, достаточно выполнить table.sort<4>(); table.dump<TY- PELIST_2(Wage, Name)>(), и т.д. В последующих разделах приводятся краткие пояснения реализации данной функциональности. Хранение данных в таблице Основой для хранения данных в таб- лице служит кортеж, реализованный в классе Loki::Tuple. Указанный класс служит базовым для класса Row, объекты которого используются для хранения строк таблицы: template <class TList> class Row : public Loki::Tuple<TList>. Список типов, передаваемый в шаб- лонном параметре, определяет типы дан- ных, хранимых в строке таблицы. Необходимость в таком классе вме- сто непосредственного использования Loki::Tuple вызвана потребностью вывода элементов кортежа, что не реализовано в Loki::Tuple. Класс Table хранит строки в динами- чески выделяемом массиве Row<TList>* _rows. Конкретизация класса Row опреде- ляется первым аргументом шаблона класса Table. Доступ к отдельным ячейкам таб- лицы осуществляется через методы класса Loki::Tuple, обернутые в методы класса Table, дополнительно задающие номер строки, в которой расположена рассматри- ваемая ячейка. Порядок сортировки в соответствии с различными критериями, задаваемыми вторым шаблонным аргументом класса Table, хранится в массиве индексов. Каж- дый индекс представлен экземпляром класса TableIndex. Индекс - это целочислен- ный массив, элементы которого указывают на строки таблицы, соответствующие пози- циям индекса. Массив индексов объявлен следую- щим образом: TableIndex_indexes[Loki::TL::Length <TIndexList>:: value]. Таблица хранит номер текущего ак- тивного индекса, и при доступе к строке на основе ее порядкового номера такая строка выбирается с использованием ссылки, хра- нимой в указанной позиции активного ин- декса, Активный индекс устанавливается при помощи шаблонной функции template <int INDEX> void sort() с целочисленным параметром, определяющим критерий сор- тировки (номер индекса в массиве индек- сов). При этом индекс может перестраи- ваться, если он устарел, или использоваться как есть, если после очередной перестройки индекса не было изменений, делающих его неправильным. Для построения индекса использу- ется специальная адаптация функции быст- рой сортировки qsort – функция qsortex. Смысл адаптации сводится к введению в функцию compare дополнительного аргу- мента, позволяющего передавать указатель this, тем самым давая возможность ее ис- пользования для сортировки нестатических данных класса. Сигнатура функции qsort модифицирована соответствующим обра- зом, при этом никаких изменений в алго- ритм сортировки не введено. Вывод таблицы с избирательным выбором колонок Вывод таблицы осуществляется функцией template < class T > void dump(). Прикладне програмне забезпечення 96 Шаблонным аргументом данной функции является список типов, элемен- тами которого являются представленные в виде типов целые числа, соответствующие колонкам, которые следует выводить. Нешаблонный вариант функции, осуществляющий вывод всех колонок, всего лишь вызывает шаблонную функцию dump, конкретизированную списком типов, полу- ченным на основе первого шаблонного па- раметра класса Table: inline void dump() { dump <IndexList<TList>::Result >(); }. Класс IndexList используется для преобразования произвольного списка ти- пов в список вида TYPELIST_N(Loki::Int2Type<0>, Loki::Int2Type<1>, … Loki::Int2Type<N>), где N – число элементов в списке TList. Функция dump проходит по строкам таблицы и для каждой строки вызывает ме- тод dump класса Row. В свою очередь функция Row::dump использует для вывода шаблонный класс Dumper: template <class TListTuple, class TListCols> class Dumper. Этот класс реализует единственную статическую функцию DoDump, аргумен- том которой является указатель на строку (объект класса Row). Шаблонными аргу- ментами класса являются: список типов, определяющий структуру строки, и список выводимых колонок в форме Int2Type-ти- пов. При этом используется стандартный прием рекурсивного порождения кода на основе частичной специализации шаблонов, описанный в [1]. По сути, для каждого эле- мента из списка TListCols строится и вызы- вается код, осуществляющий вывод соот- ветствующего элемента строки. При этом используется шаблонная функция DumpHelper, реализующая вывод элемента в зависимости от его типа. Сортировка таблицы Для сортировки таблицы вводится массив индексов. Размер массива равен числу элементов шаблонного параметра TIndexList класса Table. Каждый элемент такого массива представлен экземпляром класса TableIndex. В свою очередь класс TableIndex включает целочисленный массив с элементами, указывающими на номер строки таблицы в соответствии с заданной сортировкой. Для сортировки таблицы использу- ется метод sort с шаблонным аргументом, указывающим на критерий сортировки, ко- торый следует к ней применить. При этом строки таблицы не перемещаются, пере- страивается только соответствующий ин- декс. Кроме того, данный индекс запомина- ется как активный для использования при выводе таблицы и выполнении других зави- сящих от текущей сортировки действий. Замечание. Индекс перестраивается только в том случае, если в этом есть необ- ходимость. Детали соответствующей реали- зации будут рассмотрены в следующем раз- деле. Для сортировки применяется алго- ритм qsort. Непосредственное использова- ние функции qsort оказывается невозмож- ным в связи с тем, что в функцию сравнения не удается передать указатель на класс, элементы которого сортируются. По этой причине сигнатура данной функции была изменена введением аргумента data. Резуль- тирующая функция qsortex была написана на основе исходного текста функции qsort путем внесения указанных выше изменений. Наибольший интерес в связи с сор- тировкой представляет функция сравнения. В данном случае она реализована как шаб- лонная функция compare, которой в каче- стве шаблонного параметра передается спи- сок типов, определяющий критерий сорти- ровки: template <class TList1> inline static int compare (const void * elem1, const void * elem2, const void* data) { Row<TList>& row1 = ((Table<TList, TIndexList>*)data)->_rows[*(unsigned nt*)elem1]; Row<TList>& row2 = ((Table<TList, TIndexList>*)data)->_rows[*(unsigned int*)elem2]; return Compare<TList, List1> ::DoCompare (row1, row2); }. При вызове этой функции из qsortex в качестве elem1 и elem2 передаются указа- тели на элементы индекса, которые следует сравнить, а в качестве data – указатель на таблицу, строки которой должны использо- ваться для сравнения. Прикладне програмне забезпечення 97 Сравнение как таковое обеспечива- ется шаблонным классом Compare: template <class TListTuple, class TListCols> class Compare. Первым шаблонным аргументом яв- ляется список типов, определяющий струк- туру объектов класса Tuple, которые сле- дует сравнить. Второй шаблонный аргумент задает колонки (элементы из Tuple), кото- рые должны участвовать в сравнении в за- данном порядке. С использованием частичной спе- циализации шаблонов класс Compare обес- печивает рекурсивное построение кода, ко- торый сравнивает элементы строк, которые представленые в списке TListCols (функция DoCompare). При этом для сравнения от- дельных элементов используется шаблонная функция CompareGeneral. В настоящей пуб- ликации данная функция реализована только для сравнения целых чисел и объек- тов классов (в последнем случае классы должны содержать реализацию метода compare). Идея реализации функции DoCompare заключается в том, что она вы- полняет сравнение по элементу кортежа, определяемому головой списка сравнивае- мых элементов. Если они не равны, резуль- тат возвращается немедленно. При их ра- венстве вызывается функция DoCompare класса Compare, конкретизированного хво- стом списка типов. Рекурсия продолжается до тех пор, пока в хвосте списка не ока- жется NullType. Избирательная перестройка индексов При выполнении функции sort нет необходимости всякий раз перестраивать индекс. Это необходимо делать лишь в слу- чае, если после очередной перестройки ин- декса изменились данные в колонках таб- лицы, входящих в критерий сортировки для данного индекса. Иными словами, это озна- чает, что необходимо добиться того, чтобы функция, меняющая значение в ячейке таб- лицы, выполняла также пометку нужных индексов как “грязных”. Тогда функция sort может перестраивать индекс только в слу- чае, когда он помечен как “грязный”. Данная задача решается следующим образом. Создается класс ChangedSortIndexes, назначение которого состоит в том, чтобы по списку критериев сортировки и номеру колонки построить список из номеров ин- дексов в виде Int2Type, которые следует пе- рестроить в связи с изменением значения в указанной колонкt. Класс имеет следующее объявление: template <class TSortIndexList, typename TChangedCol, int Mode = -1, int ColCount = -1> struct ChangedSortIndexes. При реализации ChangedSortIndexes используются вспомогательный класс Has- Col, объявленный как template <class TList, typename T> struct HasCol. Предполагается, что шаблонный ар- гумент TList данного класса содержит спи- сок из классов SortSpec, а T является номе- ром колонки в виде Int2Type. Константа value данного класса оказывается равной 1, если в списке TList содержится SortIndex с константой column, равной номеру колонки, пердставленной параметром T. В противном случае значение константы оказывается равным 0. Для того чтобы в классе HasCol можно было воспользоваться классом Loki::IndexOf, список из SortIndex вначале преобразуется в список из Int2Type, для чего используется класс ColNumbers. Идея реализации класса ChangedSortIndexes состоит в следующем: а) вводятся технические шаблонные аргументы Mode и ColCount.; б) строятся три частичные специали- зации шаблона относительно аргумента Mode. Специализация для Mode = -1 выпол- няет роль модератора, а именно проверяет, содержит ли список, представленный пара- метром Head, колонку, заданную TChangedCol, в зависимости от чего приме- няет частичную специализацию для Mode = 0 или Mode = 1 соответственно. Кроме того, если данная специализация применяется впервые (ColCount = -1), запоминается пер- воначальная длина списка TSortIndexList, которая в дальнейшем передается после- дующим специализациям шаблона. Таким образом появляется возможность опреде- лить порядковый номер элемента Head от- носительно первоначального списка как ColCount - Loki::TL::Length<Tail>::value – 1; в) Частичная специализация для Mode = 0 только применяет частичную спе- Прикладне програмне забезпечення 98 циализацию для Mode = -1 относительно хвоста списка, тем самым обеспечивая ре- курсию до исчерпания списка критериев сортировки; г) Частичная специализация для Mode = 1, в дополнение к в), добавляет нужный элемент Int2Type в результирую- щий список типов. Таким образом, резуль- тирующий список типов содержит только элементы, добавленные данной частичной специализацией. Получив возможность строить спи- сок изменившихся колонок, остается лишь применить данный список к пометке “гряз- ных” индексов. Для этого используется класс RecurseAction, объявленный как template <class TList> struct RecurseAction. Данный класс обеспечивает выпол- нение функции Do абстрактного класса Action для каждого элемента списка TList. При этом функции Do передается целое число, соответствующее очередному эле- менту TList (напомним, что элементами TList являются классы Int2Type). Для пометки “грязных” индексов из класса Action наследуется класс ClearIndex, замещающий виртуальную функцию Do. Функция Do класса ClearIndex как раз и вы- полняет пометку соответствующего индекса как “грязного”. Заключение Основная цель данной статьи – из- ложить общие идеи возможности использо- вания списков типов для реализации раз- личной функциональности, относящейся к работе с таблицами, на примере вывода на печать и сортировки строк таблицы. Пред- ложенный подход можно распространить и на другие задачи, в частности фильтрацию, группировку и связывание строк. Текущая реализация работы со строками таблицы носит, главным образом, иллюстративный характер. Как следствие, она весьма ограни- чена для практического использования, тем не менее, не представляет особой сложно- сти применить более развитые механизмы работы со строками, тем самым расширить область приложений данного подхода. 1. Александреску А. Обобщенное программирование и прикладные шаблоны проектирования. - Москва: изд. дом ‘Вильямс’, 2002. –245 с. Получено 05.12.05 Об авторе Марьянович Олег Тадеушевич канд. физ.-мат. наук Место работы Институт кибернетики им. В. М. Глушкова НАН Украины. 03680, МСП, Киев-187, просп. Акад. Глушкова, 40, отд. 145. Тел. 526 3603, Факс 526 1558. Еmail OMarianovich@miratech.ua.
id nasplib_isofts_kiev_ua-123456789-2316
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn 1727-4907
language Russian
last_indexed 2025-11-26T02:44:47Z
publishDate 2006
publisher Інститут програмних систем НАН України
record_format dspace
spelling Марьянович, О.Т.
2008-09-17T13:54:42Z
2008-09-17T13:54:42Z
2006
Гибкая сортировка таблиц с использованием списков типов / О.Т. Марьянович// Проблеми програмування. — 2006. — N 1. — С. 93-98. — Бібліогр.: 1 назв. — рос.
1727-4907
https://nasplib.isofts.kiev.ua/handle/123456789/2316
681.3
Описывается применение идиомы обобщенного программирования к работе с табличной информацией в памяти компьютера. Демонстрируется возможность использования шаблонных конструкций языка С++ для порождения таблиц произвольной структуры с возможностью их сортировки на основе заданных критериев.
У статті описується застосування ідіоми узагальненого програмування для роботи з табличною інформацією у пам’яті комп’ютера. Демонструється можливість використання шаблонних конструкцій мови С++ для генерування таблиць довільної структури з можливістю їх сортування згідно заданих критеріїв.
The article describes application of generic programming paradigm to processing tabular information in computer memory. The use of C++ templates for compile-time generation of arbitrary structured tables with possibility of their sorting according to specified criteia is demonstrated.
ru
Інститут програмних систем НАН України
Прикладне програмне забезпечення
Гибкая сортировка таблиц с использованием списков типов
Гнучке сортування таблиць з використанням списків типів
Flexible tables sorting using type lists
Article
published earlier
spellingShingle Гибкая сортировка таблиц с использованием списков типов
Марьянович, О.Т.
Прикладне програмне забезпечення
title Гибкая сортировка таблиц с использованием списков типов
title_alt Гнучке сортування таблиць з використанням списків типів
Flexible tables sorting using type lists
title_full Гибкая сортировка таблиц с использованием списков типов
title_fullStr Гибкая сортировка таблиц с использованием списков типов
title_full_unstemmed Гибкая сортировка таблиц с использованием списков типов
title_short Гибкая сортировка таблиц с использованием списков типов
title_sort гибкая сортировка таблиц с использованием списков типов
topic Прикладне програмне забезпечення
topic_facet Прикладне програмне забезпечення
url https://nasplib.isofts.kiev.ua/handle/123456789/2316
work_keys_str_mv AT marʹânovičot gibkaâsortirovkatablicsispolʹzovaniemspiskovtipov
AT marʹânovičot gnučkesortuvannâtablicʹzvikoristannâmspiskívtipív
AT marʹânovičot flexibletablessortingusingtypelists