victor79 Dec 27 2021 at 14:54

С++: работа с таблицами

12 min

17K

Хочу предложить к обозрению небольшую коллекцию функций, для удобной работы со списком структур, которые можно использовать как таблицы.

Для примера, пусть будет следующий код:

struct Row {
    int field1 = 0;
    int field2 = 0;
    double qty = 0;
    double sum = 0;
};

std::vector<Row> table1;
...
// сортировка по произвольному перечню колонок
UseCols::sort(table1, COLUMNS(field1));
UseCols::sort(table1, COLUMNS(field1, field2));
// поиск по произвольным колонкам
auto itr1 = UseCols::findSorted(table1, COLUMNS(field1, field2), 1, 2);
auto itr2 = UseCols::findFirst(table1, COLUMNS(field2), 1);
// и разные другие функции обработки таблицы
auto [sumQty, sumSum] = UseCols::sum(table1, COLUMNS(qty, sum));
// хотя предыдущее избыточно, и по KISS'у лучше поштучно
double sumQty2 = UseCols::sum(table1, FIELD(qty));

В результате такие списки структур представляются как таблицы с колонками. При необходимости и желании можно сделать такой шаблонный класс таблиц оберткой над вектором.

В общем про эти, про еще кучку других функций, и вообще про разные свойства С++, я здесь напишу. Исходники можно смотреть здесь: https://github.com/victorprogrammist/useCols

Ниже будет общий обзор функционала, а пока обзор макроса COLUMNS и других вариантов доступа к данным одного элемента списка.

Про COLUMNS и прочие варианты доступа к элементу списка

UPD: В исходниках макросы были заменены на названия UC_COLUMNS && UC_FIELD. В статье пока оставил прежние названия.

UPD: Согласно подсказке @KanuTaH Был добавлен построитель лямбды на шаблонах без макросов: membersAccessor. И другие варианты вообще без лямбды.

COLUMNS создает шаблонную функцию-лямбду для получения значений из элемента списка. В параметры макроса передаются названия полей структуры.

В случае если в COLUMNS передается одно название, то этот вызов эквивалентен вызову FIELD(field1).

Возвращаемое значение этой функции зависит от количества параметров. Если нужно возвращать одно поле из структуры, то возвращается ссылка на значение этого поля.

В остальных случаях возвращается значение типа: std::tuple<const T1&, const T2&,...>

Список может быть не только списком структур, но и списком указателей на структуры - синтаксис использования будет одинаковый.

В качестве списка может использоваться любая коллекция, с которой могут работать std::sort & std::lower_bound.

В простейшем случае разворот этого макроса будет выглядеть так (почти так):

// COLUMNS(field1)
[](const auto& item) -> const auto& {
    return item.field1;
};

Именами полей можно указывать и более сложные структуры, например разворачивать поля вложенных структур:

struct Row2 {
    int val1 = 0;
};
struct Row1 {
    Row2* field1 = nullptr;
    int field2 = 0;
};
std::vector<const Row1*> list;
...
auto &[v1,v2] = COLUMNS(field1->val1, field2)(list.front());

Можно использовать построитель лямбд доступа к полям membersAccessor, вместо COLUMNS, для всех случаев, где применим COLUMNS. Его возможности немного по скромней - в нем не применить получение данных через точку. И запись чуть по длинней.

Но в остальном принцип тот же: если запрашивается один элемент, то результат вычисления лямбды это ссылка на значение. Если несколько, то результат std::tuple. Пример:

UseCols::sort(list, UseCols::membersAccessor(&Row::field1, &Row::field2));

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

Что-то вроде такого для случаев одного значения упорядочивания:

[](const auto& item) -> auto {
    return calcSomeFunction(item.field1, item.field2);
};

Для случаев множественного результата с tuple, по крайней мере на gcc, не обязательно перечислять типы для tuple. Хотя clang не захотел компилировать без них:

[](const auto& item) -> auto {
    return std::tuple(calc1(item), calc2(item));
};

Функция UseCols::sort использует классический std::sort, и выглядит существенно просто:

template <class T, class F>
void sort(T& collection, const F& getFields) {

    auto compare =
        [&getFields](const auto& r1, const auto& r2) -> bool {
            return getFields(r1) < getFields(r2);
    };

    std::sort(collection.begin(), collection.end(), compare);
}

И в результате совместного использования макроса и этой шаблонной функции получается существенно краткая и наглядная конструкция для сортировки:

UseCols::sort(table1, COLUMNS(field1));

Преимущественно все остальные функции так же существенно просты, при желании вы сами можете заглянуть в них и разобраться.

Чуть ниже снова вернуть к COLUMNS более детально. Там вместе с ним идут иногда полезные макросы FOREACH && JOIN моей реализации.

Варианты использования без формирования лямбды.

Для всех описанных ниже функций, пока кроме findSorted && findFirst, есть возможность вызова без формирования лямбды. По крайней мере на внешнем уровне кода.

UseCols::sort(table1, &Row::field1);
UseCols::sort(table1, &Row::field1, &Row::field2);

Для функций с возвращаемым значением, результат выполнения такой же, как и с использованием макроса или построителя membersAccessor: если результат по одной колонке, то непосредственно одно значение, иначе std::tuple результатов.

Реализовано это опять же существенно просто, на базе вызова membersAccessor:

template <class L, class R, class I, class ...M>
void sort(L& collection, R I::* member1, M... members) {
    sort(collection, membersAccessor(member1, members...));
}

Обзор функционала

(объявления: https://github.com/victorprogrammist/useCols/blob/main/useCols/useCols.h)

(реализация: https://github.com/victorprogrammist/useCols/blob/main/useCols/useCols_impl.h)

Все функции размещаются в пространстве имен UseCols. В них параметр getFields это как раз описанная выше лямбда из макроса COLUMNS или из функции membersAccessor.

// создает лямбду для доступа к полям элемента
//  для передачи в параметр getFields,
//  пример использования: membersAccessor(&Row::field1, &Row::field2)
template<typename... Ts>
auto membersAccessor(Ts... members);

// Сортирует список по указанным колонкам по возрастанию значений.
template <class T, class F>
void sort(T& collection, const F& getFields);

// Так же сортирует, но по убыванию значений.
template <class T, class F>
void sortDesc(T& collection, const F& getFields);

//Рассчитывает сумму по каждой колонке из getFields в отдельности.
template <class T, class F>
auto sum(const T& collection, const F& getFields);

// Возвращает максимальные/минимальные значения по указанным колонкам.
// Возвращаемый тип std::pair<auto,bool>,
// где second bool равен ложь, если пустая коллекция.
// (хотя если будете смотреть в коде, то там просто auto, но он pair)

template <class T, class F>
std::pair<auto,bool> maxValue(T& collection, const F& getFields);

template <class T, class F>
std::pair<auto,bool> minValue(T& collection, const F& getFields);

// В случае, если заведомо известно, что коллекция
// не пустая, можно использовать maxValue2/minValue2,
// которая возвращает непосредственно максимальные/минимальные
// значения без std::pair

template <class T, class F>
auto maxValue2(T& collection, const F& getFields);

template <class T, class F>
auto minValue2(T& collection, const F& getFields);

// Возвращает итератор указывающий на элемент с максимальным значением.
// Максимальное значение по всему компаунду от getFields.
// В случае пустой collection возвращает итератор end().

template <class T, class F>
auto maxItem(T& collection, const F& getFields);

template <class T, class F>
auto minItem(T& collection, const F& getFields);

// Находит элемент по значению колонок,
// и возвращает на него итератор, из предположения
// что список отсортирован по этим колонкам по возрастанию.
template <class T, class F, class ...V>
auto findSorted(const T& collection, const F& getFields, const V&... value);

// Находит элемент по значению колонок простым перебором,
// и возвращает на него итератор,
// находит первый элемент соответствующий отбору.
template <class T, class F, class ...V>
auto findFirst(const T& collection, const F& getFields, const V&... value);

Классы Groups && Range

(классы: https://github.com/victorprogrammist/useCols/blob/main/useCols/ranges.h)

Разберем такой вот пример:

// предварительная сортировка
UseCols::sort(table1, FIELD(field1));

// Перечисление групп строк сгруппированных по field1.
// При необходимости можно использовать COLUMNS
// с любым количеством колонок.
for (auto& range1: UseCols::groups(table1, FIELD(field1))) {

    // к списку строк можно применять описанные выше
    // функции аггрегирования, например здесь
    // используется суммирование только для строк этой группы
    auto [suQty,suSum] = UseCols::sum(range1, COLUMNS(qty,sum));

    std::cout
    << "value of group's field: " << range1->field1
    << ", count rows: " << range1.size()
    << ", sum of qty & sum: " << suQty << ", " << suSum
    << std::endl;

    // простое перечисление строк группы
    for (const Row& row: range1) {
        std::cout << " == row: field2, qty, sum: "
        << row.field2 << ", " << row.qty << ", " << row.sum << std::endl;
    }

    // можно строки этой группы еще на что-нибудь сгруппировать
    UseCols::sort(range1, FIELD(field2));
    for (auto& range2: UseCols::groups(range1, FIELD(field2))) {
        std::cout << " ==== group lev2: field2, sum(qty), sum(sum): "
        << r2->field2
        << ", " << UseCols::sum(r2, FIELD(qty))
        << ", " << UseCols::sum(r2, FIELD(sum))
        << std::endl;
    }
}

Класс Range представляет собой пару сохраненных итераторов: m_begin && m_end. Он возвращает эти итераторы как методы begin() && end(). Т.е. это просто некий диапазон строк из исходной коллекции.

Класс Groups является оберткой к итератору, который перечисляет возможные диапазоны Range из исходной коллекции.

Если исходный список отсортирован по колонке field1, то одинаковые значения располагаются рядом. И класс Groups перечисляет эти регионы одинаковых значений.

Для удобного конструирования класса Groups сделана функция groups:

template <class T, class F>
auto groups(T& list, const F& getFields) {
    using Itr = decltype(list.begin());
    return Groups<Itr,F>(list, getFields);
}

Основные свойства класса Range: empty(), size(), first(), last(), begin(), end(). (Их смысл очевиден, поэтому не разворачиваю детальней).

И оператор -> который возвращает указатель на first() - на первую строку, из которой можно получать значения полей группировки, т.к. они для всего множества одинаковые.

Основные свойства класса Groups: begin(), end().

И метод countGroups(), при его использовании нужно учитывать, что он каждый раз при вызове для расчета количества групп перечисляет эти группы.

Т.е. класс Groups не хранит предрасчитанное множество регионов, т.к. для большинства случаев это избыточно.

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

Макросы FOREACH && JOIN

(здесь: https://github.com/victorprogrammist/useCols/blob/main/useCols/macroTools.h, и здесь: https://github.com/victorprogrammist/useCols/blob/main/useCols/macroForeach.h)

Эти макросы не относятся к работе с таблицами. Они вообще в этой статье лишь потому, что на основе их сделан макрос COLUMNS. В общем дальше в статье я детальней описываю макрос COLUMNS, но прежде нужно описать FOREACH && JOIN. Может кто-нибудь найдет для себя кучку полезного и в описании этих макросов.

Делал я их существенно универсальным, и в них присутствуют несколько большие возможности, чем требуются для макроса COLUMNS.

Суть этих макросов, что им передается идентификатор FUNC другого define, и вариадичный список аргументов. И они вызывают FUNC последовательно для каждого из своих вариадичных аргументов. Еще передается один произвольный аргумент, см. в коде ниже.

Кажется что-то вроде этого есть в BOOST, но у меня здесь своя реализация. Обычно эти макросы используются из других макросов, и сами по себе их применение очень редко.

// Определение такое (пока без реализации).
// Будет раскрыто в вызовы: FUNC(NAME1,PARAM) FUNC(NAME2,PARAM) ...
#define FOREACH(FUNC, PARAM, ...)
// Отличие JOIN от FOREACH, что он между
// каждым инстанцированием FUNC вставляет SPL.
// Но только между, и не добавляет его после последнего.
// Будет раскрыто в вызовы: FUNC(NAME1,PARAM) SPL FUNC(NAME2,PARAM) ...
#define JOIN(SPL, FUNC, PARAM, ...)

И примеры использования:

// Таким образом можно объявить несколько переменных
// с одним инициализирующим значением:
//  int var1 = 5; int var2 = 5; int var3 = 5;
#define USE1(NAME, PARAM) int NAME = PARAM;
FOREACH(USE1, 5, var1, var2, var3)

// Следующим образом делаются вставки, требующие разделитель
// между конструкциями. Разворот этого примера будет таким:
// void myFunc(int par1 = 5, int par2 = 5, int par3 = 5);
#define USE2(NAME, PARAM) int NAME = PARAM
void myFunc(JOIN(COMMA, USE2, 5, par1, par2, par3));

Ниже я несколько раз упоминаю про некие недостатки MSVC. Суть в том, что этот код сначала делался под gcc, позже тестировался на clang и были добавлены не существенные правки, вероятно соответствующие стандарту. И после тестировался на MSVC, в процессе чего пришлось вносить существенные правки. Вот здесь демонстрируется основная причина этому: https://stackoverflow.com/questions/5134523/msvc-doesnt-expand-va-args-correctly

// это думаю понятно и без комментариев...
#define COMMA ,

// Что бы передать в макрос параметр содержащий запятые,
// его можно единожды обернуть скобками.
// т.е. вызов макроса оборачивает в скобки,
// и параметр с запятыми передается как единое целое
// в другой макрос: SOMETHING(REPACK(pair<int,int>))
// И другое его использование для
// обхода недостатка MSVC по раскрытию __VA_ARGS__
#define REPACK(...) __VA_ARGS__

// Это перманентное оборачивание в скобки.
// Во многоуровневых вложенных макросах,
// что бы параметр содержащий запятые оставался в одном параметре,
// и не расползался в соседние параметры,
// его обернем в реальные скобки. А после при инстанцированнии
// он будет развернут другим макросом: UNWRAP
#define FIXWRAP(...) (__VA_ARGS__)

// Такой хитроватой конструкцией будет убрана одна пара
// скобок из параметра. Самый внешний REPACK только для MSVC.	
#define UNWRAP_HELPER(...) __VA_ARGS__
#define UNWRAP(X) REPACK(REPACK(UNWRAP_HELPER)X)

// Просто соединяет аргументы в новый идентификатор
#define CAT(A,B) A##B

Теперь чуточку сложней, определение количества параметров вариадичного define. Возможно кто-то уже видел подобное на просторах интернета:

#define CNT_ARGS_HELPER_2( \
    _1,_2,_3,_4,_5,_6,_7,_8,_9,_10, \
    _11,_12,_13,_14,_15,_16,_17,_18,_19, n, ...) n

// Для MSVC требуется такая вложенность. Остальные могут без этого.
#define CNT_ARGS_HELPER_1(...) REPACK(CNT_ARGS_HELPER_2(__VA_ARGS__))

// Подсчитывает количество переданных аргументов.
#define CNT_ARGS(...) \
    CNT_ARGS_HELPER_1(__VA_ARGS__, \
    19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1)

// Это определяет параметр один, или их больше одного.
// Инстанцируется в 1, если один параметр, иначе 0.
#define ONLY_ONE_ARG(...) \
    CNT_ARGS_HELPER_1(__VA_ARGS__, \
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1)

Теперь основа для FOREACH && JOIN:

// Определения типа SEQ_<NUM> делают перечисление
// имен переданных в параметр __VA_ARGS__.
// Для каждого имени вызывается макрос APPLY.
// И между каждым APPLY делается вставка SPL,
// которая предварительно была FIXWRAP,
// а при вставке UNWRAP.
// В них REPACK для обхода глюка MSVC.

#define SEQ_1(SPL, FN, P0, NAME, ...) APPLY(FN, NAME, P0)
#define SEQ_2(SPL, FN, P0, NAME, ...) \
    APPLY_SPL(FN, NAME, P0, SPL) REPACK(SEQ_1(SPL, FN, P0, __VA_ARGS__))
#define SEQ_3(SPL, FN, P0, NAME, ...) \
    APPLY_SPL(FN, NAME, P0, SPL) REPACK(SEQ_2(SPL, FN, P0, __VA_ARGS__))
#define SEQ_4(SPL, FN, P0, NAME, ...) \
    APPLY_SPL(FN, NAME, P0, SPL) REPACK(SEQ_3(SPL, FN, P0, __VA_ARGS__))
#define SEQ_5(SPL, FN, P0, NAME, ...) \
    APPLY_SPL(FN, NAME, P0, SPL) REPACK(SEQ_4(SPL, FN, P0, __VA_ARGS__))
#define SEQ_6(SPL, FN, P0, NAME, ...) \
    APPLY_SPL(FN, NAME, P0, SPL) REPACK(SEQ_5(SPL, FN, P0, __VA_ARGS__))
#define SEQ_7(SPL, FN, P0, NAME, ...) \
    APPLY_SPL(FN, NAME, P0, SPL) REPACK(SEQ_6(SPL, FN, P0, __VA_ARGS__))
#define SEQ_8(SPL, FN, P0, NAME, ...) \
    APPLY_SPL(FN, NAME, P0, SPL) REPACK(SEQ_7(SPL, FN, P0, __VA_ARGS__))
#define SEQ_9(SPL, FN, P0, NAME, ...) \
    APPLY_SPL(FN, NAME, P0, SPL) REPACK(SEQ_8(SPL, FN, P0, __VA_ARGS__))

// начало рекурсии перечисления имен
#define SEQ_NUM(N, SPL, FN, P0, ...) \
    REPACK(CAT(SEQ_,N)(SPL, FN, P0, __VA_ARGS__))

// через этот дефайн происходит вызов пользовательского дефайна.
#define APPLY_SPL(FN, NAME, P0, SPL) APPLY(FN, NAME, P0) UNWRAP(SPL)
#define APPLY(FN, NAME, P0) FN(NAME, UNWRAP(P0))

// управляющий дефайн для FOREACH && JOIN
#define SEQ_HELPER(SPL, FN, P0, ...) \
    SEQ_NUM(CNT_ARGS(__VA_ARGS__), SPL, FN, P0, __VA_ARGS__)

И сами определения FOREACH && JOIN:

// будет раскрыто в вызовы: FN(NAME1, P0) SPL FN(NAME2, P0) ...
#define JOIN(SPL, FN, P0, ...) \
    SEQ_HELPER(FIXWRAP(SPL), FN, FIXWRAP(P0), __VA_ARGS__)
// будет раскрыто в вызовы: FN(NAME1, P0) FN(NAME2, P0) ...
#define FOREACH(FN, P0, ...)   \
    SEQ_HELPER(FIXWRAP(), FN, FIXWRAP(P0), __VA_ARGS__)

Снова возвращаюсь к макросу COLUMNS

(реализация: https://github.com/victorprogrammist/useCols/blob/main/useCols/macroColumns.h)

Сначала простейший случай - FIELD:

// используется преобразование указателя
// в ссылку, если список состоит из указателей.
template <class T>
const T& asReference(const T* p) { return *p; }

template <class T>
const T& asReference(T* p) { return *p; }

template <class T>
const T& asReference(const T& p) { return p; }

template <class T>
const T& asReference(T& p) { return p; }

#define FIELD(X) [](const auto& it) -> const auto& { \
    return asReference(it).X; }

И остальные случаи множественных колонок:

// COLS_HELPER_1 - перенаправление случая одной колонки
#define COLS_HELPER_1(X) FIELD(X)

// COLS_HELPER_0 - группа макросов для случая нескольких колонок
#define COLS_HELPER_0__FIELD(X,DUMMY) asReference(it).X

#define COLS_HELPER_0__DECLTYPE_REMOVE_CVREF(X) \
    typename std::remove_cv< \
    typename std::remove_reference< \
        decltype(asReference(it).X)>::type>::type

#define COLS_HELPER_0__DECLTYPE_WITH_REFERENCE(X,DUMMY) \
    const COLS_HELPER_0__DECLTYPE_REMOVE_CVREF(X)&

// здесь ~ это для обхода глюка MSVC. Позже это уходит в параметр DUMMY.
#define COLS_HELPER_0__TYPE_WITH_REFERENCE(...) \
    std::tuple<JOIN(COMMA, \
        COLS_HELPER_0__DECLTYPE_WITH_REFERENCE, ~, __VA_ARGS__)>

#define COLS_HELPER_0(...) \
    [](const auto& it) -> \
        COLS_HELPER_0__TYPE_WITH_REFERENCE(__VA_ARGS__) { \
            return COLS_HELPER_0__TYPE_WITH_REFERENCE(__VA_ARGS__)( \
                JOIN(COMMA, COLS_HELPER_0__FIELD, ~, __VA_ARGS__) \
        ); \
    }

// выбор варианта, одна колонка - без tuple, или несколько
#define COLS_HELPER_BOOL(ONLY_ONE, ...) \
        CAT(COLS_HELPER_,ONLY_ONE)(__VA_ARGS__)

#define COLUMNS(...) COLS_HELPER_BOOL( \
        ONLY_ONE_ARG(__VA_ARGS__), __VA_ARGS__)

Ну вроде все

Конечно, можно еще по напридумывать финтов в подобном стиле работы с таблицами. Например отборы, всякого рода копирования между списками с разными типами, или соединения таблиц. Но мне пока особо не требовалось, текущее множество функций покрывает существенную часть потребностей. В частности, на самом деле, даже множественный COLUMNS требуется редко, и обычно достаточно FIELD.

Исходники, как я упоминал, здесь: https://github.com/victorprogrammist/useCols

И в частности, здесь можно увидеть пример использования большинства функций: https://github.com/victorprogrammist/useCols/blob/main/main.cpp

UPD: исходники либы уже чуть поменялись с момента написания статьи, согласно комментариям, и возможно еще будут меняться. Особо полезен был комментарий от @KanuTaH.

Tags:

программирование

Hubs: