Re: Разреженный массив в compile-time
От: Слава  
Дата: 05.07.18 13:52
Оценка: +1
Здравствуйте, avovana, Вы писали:

A>Дорогие форумчане, здравствуйте!


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

A>Да вот хотя бы для этого — нужно решить задачу на современных плюсах(С++14, С++17) с использованием шаблонов.

Пожалуйста, объясните практическую ценность этого.
Разреженный массив в compile-time
От: avovana Россия  
Дата: 05.07.18 11:44
Оценка:
Дорогие форумчане, здравствуйте!

В соседней ветке по плюсам развернулась дискуссия о том, зачем нужны шаблоны.
Да вот хотя бы для этого — нужно решить задачу на современных плюсах(С++14, С++17) с использованием шаблонов.

В решение данной задачи помогла в т.ч. книга
Автор: LaptevVV
Дата: 21.05.18
, описанная Валерием Лаптевым.
Три года назад я начал изучать программирование по его книги "C++. Экспресс курс".
Тогда для меня задача по вычислению дня рождения в зависимости от високосности года было верхом программисткой мысли.
Сейчас пошли уже такие "игрушки"

Выложу:

    1. Саму задачу.
    2. Что получилось.
    3. В чем прошу помощи.

1. Задача.

Как будет видно из кода, необходимо реализовать разреженный массив:
#include <cstdint>
#include <cassert>
#include <type_traits>

template<typename T, uint64_t Mask>
class SparseArray {
public:
    using ElementType = T;

    //Написать constexpr конструкторы:
    //1. Дефолтный конструктор SparseArray()
    //2. Конструктор, принимающий значения именно всех элементов прореженного массива

    template<uint8_t Index>
    constexpr T get() {  //Возвращает элементы именно по значению, не по ссылке.
        //Вернуть дефолтное значение T, если элемента нет в массиве, иначе вернуть существующий элемент из массива.
    }

    //Исключить оператор при помощи SFINAE если нет оператора + для пары T и TOther
    template<typename TOther, uint64_t MaskOther>
    constexpr auto operator +(const SparseArray<TOther, MaskOther>& other) {
        //Вернёт новый SparseArray с поэлементной суммой двух исходных массивов
    }

private:
    T values[/*Посчитать размер прореженного массива*/];
};

int main() {

    SparseArray<float,  3 > array0(1.0f, 2.0f);
    SparseArray<double, 10> array1(      4.0,    7.0);

    auto sum = array0 + array1;

    static_assert(sizeof(sum) == sizeof(double) * 3, "Invalid sum array size");
    static_assert(sizeof(array0) == sizeof(float) * 2, "Invalid array size");
    static_assert(sizeof(array1) == sizeof(double) * 2, "Invalid array size");

    assert((std::is_same_v<typename decltype(sum)::ElementType, double> == true));

    assert(sum.get<0>() == 1.0);
    assert(sum.get<1>() == 6.0);
    assert(sum.get<2>() == 0.0);
    assert(sum.get<3>() == 7.0);

    SparseArray<float, 3> array2;
    assert(array2.get<0>() == 0.0f);
    assert(array2.get<1>() == 0.0f);

    return 0;
}


2. Что получилось.

Получилось всё, кроме реализации оператора сложения:
// My SparseArray implementation

#include <cstdint>
#include <iostream>
#include <cassert>
#include <utility>
#include <bitset>

template<typename T, uint64_t Mask>
class SparseArray 
{
    public:
    using ElementType = T;

    constexpr SparseArray() 
        : values() { 
            std::cout << "Default ctor" << '\n';
        }

    template<typename... Args>
    constexpr SparseArray(Args&&... args) 
    : values{args...} {
        std::cout << "Args ctor. Mask = " << Mask << '\n';
    }

    template<uint8_t Index>
    constexpr ElementType get() const {
        if(isSet(Index))
            return values[countEntityNumber(Index)];
        else
            return T();
    }

    constexpr static std::size_t countEntityNumber (size_t index) {
        uint64_t subMask{0};

        for(uint64_t i = 0; i < index; ++i) {
            subMask = subMask | 0b1;

            if(i + 1 < index)
                subMask <<= 1;
        }
        return popcount(Mask & subMask);
    }

    constexpr static std::size_t popcount (size_t value) {
        return value != 0 ? (value & 0b1) + popcount(value >> 1) : 0;
    }

    constexpr static std::size_t isSet (size_t pos) {
        return (Mask >> pos) & 0b1;
    }

    static const int mask = Mask;
    static const int size = popcount(Mask);

    ElementType values[size];  
};

int main ()
{
    SparseArray<float,  3> array0(1.0f, 2.0f);
    SparseArray<double, 10> array1(      4.0,    7.0);

    static_assert(sizeof(array0) == sizeof(float) * 2, "Invalid array size");
    static_assert(sizeof(array1) == sizeof(double) * 2, "Invalid array size");

    SparseArray<float, 3> array2;
    assert(array2.get<0>() == 0.0f);
    assert(array2.get<1>() == 0.0f);

    return 0 ;
}


3. В чем прошу помощи.

Прошу помочь с реализацией operator+.
То что я сделал, к сожалению, не компилируется.
Ошибка в попытке использования объекта в выражение std::index_sequence.
Не получается всё в compile-time сделать.
Описал конкретно эту проблему здесь.

с++14 с++17 templates constexpr
Re: Разреженный массив в compile-time
От: Chorkov Россия  
Дата: 05.07.18 14:00
Оценка:
Здравствуйте, avovana, Вы писали:


На github, практически работающий пример.
Видимо stackoverflow.com работает оперативнее .

Единственное, VS2015 ругается не countEntityNumber — не хочет циклы в constexpr функции.

Вынес в отдельный namespace SparseArrayDitails, в качестве отдельной функции. Это также позволило нормально тестировать битовые фокусы через static_assert.
    constexpr static std::size_t countEntityNumber (size_t index, uint64_t Mask ) {
        return index==0  ?  0
            : ( countEntityNumber( index-1, Mask >>1 ) + ( Mask%2==1 ? 1 : 0 ) );
    }

    static_assert( countEntityNumber( 0, 3    ) == 0, "" );
    static_assert( countEntityNumber( 1, 3    ) == 1, "" );
    static_assert( countEntityNumber( 1, 6    ) == 0, "" );
    static_assert( countEntityNumber( 2, 6    ) == 1, "" );

...
class SparseArray {
... 
    constexpr static std::size_t countEntityNumber (size_t index) {
        return SparseArrayDitails::countEntityNumber(index, Mask);
    }
...


maxIndex и popcount, тоже стоило бы вынести.

Еще, с точки зрения использования, маска — очень плохая идея.
Гораздо удобнее задать индексы используемых элементов.
namespace SparseArrayDitails
{
    constexpr uint64_t summ()
    { return 0; }
    template <typename ... Args>
    constexpr uint64_t summ(uint64_t i0, Args ...args  )
    { return i0 + summ(args...); }

    constexpr bool is_ordered()
    { return true; }
    constexpr bool is_ordered(uint64_t )
    { return true; }
    template <typename ... Args>
    constexpr bool is_ordered(uint64_t i0, uint64_t i1, Args ...args  )
    {
        return  (i0 < i1) && is_ordered( i1, args);
    }


    template< size_t... index >
    constexpr uint64_t mask()
    {
        static_assert( is_ordered(index...), "Wrong index order!" );
        return  summ( ( uint64_t(1) << index  )...  );
    }
    static_assert( mask<0,2,3>() == 1 + 4 + 8 , "test mask");

}
... 
template< typename T, size_t ...  index >
using SparseArrayI = SparseArray<T, SparseArrayDitails::mask<index...>() >;


Если сразу писать template< typename T, size_t ... index > , то код, тоже, должен получиться чуть по проще...
Re: Разреженный массив в compile-time
От: vopl Россия  
Дата: 05.07.18 14:21
Оценка:
Здравствуйте, avovana, Вы писали:

A>Дорогие форумчане, здравствуйте!


A>

3. В чем прошу помощи.


A>Прошу помочь с реализацией operator+.
A>То что я сделал, к сожалению, не компилируется.
A>Ошибка в попытке использования объекта в выражение std::index_sequence.
A>Не получается всё в compile-time сделать.
A>Описал конкретно эту проблему здесь.

A>


У тебя попутались индексы и значения, одно смешалось с другим, надо там навести марафет. В общем — коллизия примерно такого плана: индексы — они нормально перерабатываются в compile-time, а вот хранимые значения — не очень, вот и образуется ругань от компилятора, мол ‘this’ is not a constant expression когда ты пытаешся значение засунуть в compile-time константу...

А именно:
неправильно: результатСложения -> integer_sequence -> конструкторРезультата
правильно: результатСложения -> конструкторРезультата

operator+ для с++17:
  не подсматривать
    constexpr static uint8_t countIndex(uint8_t entityNumber) { // обратный к countEntityNumber
        uint8_t idx = 0;
        while(countEntityNumber(idx) <= entityNumber) {
            idx++;
        }

        return idx-1;
    }

    template<typename TOther, uint64_t MaskOther>
    constexpr auto operator +(const SparseArray<TOther, MaskOther>& other) const {
        using Result = SparseArray<decltype(T{} + TOther{}), Mask | MaskOther>;

        return [this, other]<uint8_t... EntityNumbers>(std::integer_sequence<uint8_t, EntityNumbers...>)
        {
            return Result{(get<Result::countIndex(EntityNumbers)>() + other.template get<Result::countIndex(EntityNumbers)>())...};
        }(std::make_integer_sequence<uint8_t, Result::size>{});
    }

Отредактировано 05.07.2018 14:42 vopl . Предыдущая версия .
Re: Разреженный массив в compile-time
От: reversecode google
Дата: 05.07.18 14:24
Оценка:
http://www.cyberforum.ru/cpp-beginners/thread2216255.html
походу где то на собеседованиях дают
Re[2]: Разреженный массив в compile-time
От: avovana Россия  
Дата: 05.07.18 15:48
Оценка:
Здравствуйте, Слава, Вы писали:

С>Пожалуйста, объясните практическую ценность этого.


Здравствуйте, reversecode, Вы писали:


R>http://www.cyberforum.ru/cpp-beginners/thread2216255.html

R>походу где то на собеседованиях дают

Совершенно верно.
Мне дали эту тестовую задачку и попросили сказать за сколько её получилось сделать когда пришлю ответ.
Я её делаю уже 2ой месяц
Это уже более практический интерес.
В ту тему на форуме не хочу заглядывать, т.к. хочу сам дойти и в т.ч. с вашей помощью.
Здесь я размышляю с участниками форума, а там как бы смотрю на готовое решение.
Такие вот у меня мысли)

Здравствуйте, Chorkov, Вы писали:

C>Здравствуйте, avovana, Вы писали:



C>На github, практически работающий пример.

C>Видимо stackoverflow.com работает оперативнее .

Из данного ответа на stackoverflow.com так и не понял что делать.
Скорее-всего, это потому, что сам не смог точно сформулировать вопрос и, как мне кажется, ответили чуть не в ту стезю.

C>Единственное, VS2015 ругается не countEntityNumber — не хочет циклы в constexpr функции.

То что ругается на циклы в constexpr методе countEntityNumber в VS2015 — это, скорее-всего, потому что еще не реализована до конца функциональность С++14.

Там еще закомментировал вызовы operator+ в main. Вот если их раскомментировать — и пойдет жара от компилятора)

C>Вынес в отдельный namespace SparseArrayDitails

Это то, что вертелось в голове("убери эту функциональность куда-нибудь, убери, выдели это как-нибудь")! Спасибо за приём!

C>Еще, с точки зрения использования, маска — очень плохая идея.

Это данное условие задачи
Спасибо за предложенную идею.

V>У тебя попутались индексы и значения, одно смешалось с другим, надо там навести марафет. В общем — коллизия примерно такого плана: индексы — они нормально перерабатываются в compile-time, а вот хранимые значения — не очень, вот и образуется ругань от компилятора, мол ‘this’ is not a constant expression когда ты пытаешся значение засунуть в compile-time константу...

Вот-вот... наверное, в этом дело.

V>Не подсматривать

А... держусь! Сейчас попробую разобраться с этой путаницей.
Если не пойдет, то прибегну к этой помощи)
Re[3]: Разреженный массив в compile-time
От: reversecode google
Дата: 05.07.18 16:17
Оценка:
ну так вы расскажите нам кто это такие задачки раздает
имя компании
Re[2]: Разреженный массив в compile-time
От: avovana Россия  
Дата: 05.07.18 16:22
Оценка:
Здравствуйте, vopl, Вы писали:

V>operator+ для с++17:

V>
  не подсматривать
V>
V>    constexpr static uint8_t countIndex(uint8_t entityNumber) { // обратный к countEntityNumber
V>        uint8_t idx = 0;
V>        while(countEntityNumber(idx) <= entityNumber) {
V>            idx++;
V>        }

V>        return idx-1;
V>    }

V>    template<typename TOther, uint64_t MaskOther>
V>    constexpr auto operator +(const SparseArray<TOther, MaskOther>& other) const {
V>        using Result = SparseArray<decltype(T{} + TOther{}), Mask | MaskOther>;

V>        return [this, other]<uint8_t... EntityNumbers>(std::integer_sequence<uint8_t, EntityNumbers...>)
V>        {
V>            return Result{(get<Result::countIndex(EntityNumbers)>() + other.template get<Result::countIndex(EntityNumbers)>())...};
V>        }(std::make_integer_sequence<uint8_t, Result::size>{});
V>    }
V>

V>


Вот это лямбда! Сижу с лупой
Я таких шаблонных лямбд не встречал еще.
Получается, здесь создается лямбда(какая-то шаблонная) и в ней происходит раскрытие parameter pack прямо в конструкторе.
Затем сразу идет её вызов.
Получившейся объект возвращается наружу.
Но почему в этой лямбде получилось обойти ту ошибку — `this` is not constant... ?



Здравствуйте, reversecode, Вы писали:
R>ну так вы расскажите нам кто это такие задачки раздает
R>имя компании
Я сейчас точно не могу сказать. Возможно, рекрутер даже не сказал, что за компания.
У меня где-то в списке сообщений от разных рекрутеров в "моем круге" лежит.
Помню, что написали, что компания занимается беспилотниками.
Отсюда приходит понимание, что разработка embedded system, для который вычисления в compile-time — просто первая необходимость, чтобы сберечь ресурсы во время выполнения программы.
Отредактировано 05.07.2018 16:30 avovana . Предыдущая версия .
Re[3]: Разреженный массив в compile-time
От: reversecode google
Дата: 05.07.18 16:48
Оценка:
не думаю то в embedded это нужно
просто мониторят рынок
хр которые раздают тестовое задание ? это что то новое

начните отвечать оппоненту на в ветку
это все же деревовидный форум а не линейный(линейный он уже потом)
Re[3]: Разреженный массив в compile-time
От: vopl Россия  
Дата: 05.07.18 19:05
Оценка:
Здравствуйте, avovana, Вы писали:

A>Но почему в этой лямбде получилось обойти ту ошибку — `this` is not constant... ?


Она не обойдена, просто та твоя проблемная ситуация — отсутствует: внутри operator+() не делается попыток использования состояния объекта в compile-time. Дистилированный пример:

struct Container
{
    int value;
};

constexpr Container cc{10};
Container ncc{10};

enum
{
    v1 = cc.value,
    //v2 = ncc.value
};

— сс гарантированно может быть исчислен во время компиляции, ncc — нет. Раскоментируй строку про v2 — получится ошибка компиляции.
Re: Разреженный массив в compile-time
От: kov_serg Россия  
Дата: 05.07.18 22:05
Оценка:
Здравствуйте, avovana, Вы писали:

A>Да вот хотя бы для этого — нужно решить задачу на современных плюсах(С++14, С++17) с использованием шаблонов.

В чем состоит задача? Постановка задачи, входные и выходные данные какие ограничения и т.п.?

A>Как будет видно из кода, необходимо реализовать разреженный массив:

Что таке разряженный массив?
Это в котором можно задать 5-ый и 2073-й элементы? Потом что с ним планируется делать? Сортировать, вычислять медиану, оценку дисперсии, делать преобразование фурье... Или цель просто ломами лужи с платца подметать?

A>2. Что получилось

Действительно, что же получилось?
И что мешает подготавливать данные нормальными средствами до компиляции, а не во время, засоряя код лишним шумом.
Re[2]: Разреженный массив в compile-time
От: avovana Россия  
Дата: 07.07.18 04:51
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>В чем состоит задача? Постановка задачи, входные и выходные данные какие ограничения и т.п.?


Это очень интересные вопросы. К сожалению, у меня нет на них ответа.
Могу лишь сказать, что выложил задачу как есть — как мне она была дана.

_>Что таке разряженный массив?

_>Это в котором можно задать 5-ый и 2073-й элементы?

Массив при вставке элемента.
Я думаю, здесь разреженный массив предполагает то, что можно задать 5ый и 2073ий элементы и тогда массив будет содержать 2 элемента.
Если запросить у такого массива 5ый или 2073ий элементы, то он вернет заданные значения.

Массив при выдаче элемента.
Но также есть возможность запросить 0ой, 4ый, 4000ый и т.д. элемент.
В этом случае массив поймет, что такие элементы не были заданы ранее и просто создаст на ходу какое-нибудь значение(дефолтное, 0, любое на вкус) и вернет его.
При этом, массив всё также будет иметь лишь 2 ранее заданных элемента.

Массив при сбросе элемента.
Также можно сбросить заранее заданный элемент. Для этого, к примеру, 5му элементу(заранее заданному) присваивается какое-нибудь значение(дефолтное, 0, любое на вкус).
Массив после этого будет содержать лишь 1 элемент(2073ий).

_>Потом что с ним планируется делать? Сортировать, вычислять медиану, оценку дисперсии, делать преобразование фурье... Или цель просто ломами лужи с платца подметать?

Возможно, после устройства на эту работу с таким массивом, действительно, буду делать такие операции
Но сейчас, цель, скорее, соответствует последнему предположению.
Я бы сказал, что это "конструирование ради конструирования".
Чтобы, возможно, показать, навыки владения шаблонами, умение писать ясный и понятный код.

A>>2. Что получилось

_>Действительно, что же получилось?
_>И что мешает подготавливать данные нормальными средствами до компиляции, а не во время, засоряя код лишним шумом.
Здесь хотел бы уточнить, что имелось ввиду — что за "нормальные средства до компиляции"?
Re[4]: Разреженный массив в compile-time
От: avovana Россия  
Дата: 07.07.18 05:00
Оценка:
Здравствуйте, vopl, Вы писали:

V>Она не обойдена, просто та твоя проблемная ситуация — отсутствует: внутри operator+() не делается попыток использования состояния объекта в compile-time. Дистилированный пример:


Спасибо большое за разъяснение!
У меня, всё же, остаются вопросы по проблеме и реализации, в которых очень хочется разобраться.

В коде всё также присутствует std::integer_sequence — я так понимаю, это compile-time выражение.
Самое главное различие которое я здесь вижу, что теперь раскрытие parameter pack прямо в конструкторе.

Не могли бы описать реализацию? Пока, к сожалению, не даётся она мне.
Сильно не привычный синтаксис такой лямбды. И не могу понять подноготную — почему было сделано именно так.
Re[3]: Разреженный массив в compile-time
От: kov_serg Россия  
Дата: 07.07.18 07:22
Оценка:
Здравствуйте, avovana, Вы писали:

A>Здесь хотел бы уточнить, что имелось ввиду — что за "нормальные средства до компиляции"?

R, python, perl, lua... Где можно обработать данные естественным способом, выбрать, преобразовать, упорядочить и сформировать нужные части исходных файлов по шаблонам с малыми накладными расходами.
Re[4]: Разреженный массив в compile-time
От: avovana Россия  
Дата: 07.07.18 07:35
Оценка:
Здравствуйте, kov_serg, Вы писали:

A>>Здесь хотел бы уточнить, что имелось ввиду — что за "нормальные средства до компиляции"?

_>R, python, perl, lua... Где можно обработать данные естественным способом, выбрать, преобразовать, упорядочить и сформировать нужные части исходных файлов по шаблонам с малыми накладными расходами.

Спасибо за пояснение. Кроме С++ с другими языками мало работал. Поэтому плохо представляю их ценность. Теперь шторка немного приоткрылась)
Re[5]: Разреженный массив в compile-time
От: vopl Россия  
Дата: 09.07.18 10:28
Оценка:
Здравствуйте, avovana, Вы писали:

A>У меня, всё же, остаются вопросы по проблеме и реализации, в которых очень хочется разобраться.


A>В коде всё также присутствует std::integer_sequence — я так понимаю, это compile-time выражение.

A>Самое главное различие которое я здесь вижу, что теперь раскрытие parameter pack прямо в конструкторе.

A>Не могли бы описать реализацию? Пока, к сожалению, не даётся она мне.

A>Сильно не привычный синтаксис такой лямбды. И не могу понять подноготную — почему было сделано именно так.

Уберу лямбду, разнесу исчисление индексов и конструирование результата по самостоятельным методам, получится то же самое что в том первом варианте с лямбдой, только более детально:
    ////////////////////////////////////////////////////////////////////////////////
    constexpr static uint8_t countIndex(uint8_t entityNumber) { // обратный к countEntityNumber
        uint8_t idx = 0;
        while(countEntityNumber(idx) <= entityNumber) {
            idx++;
        }

        return idx-1;
    }

    ////////////////////////////////////////////////////////////////////////////////
    template<typename TOther, uint64_t MaskOther>
    constexpr auto operator +(const SparseArray<TOther, MaskOther>& other) const {
        using Result = SparseArray<decltype(T{} + TOther{}), Mask | MaskOther>;

        //формирование последовательности EntityNumber для результата
        std::make_integer_sequence<uint8_t, Result::size> entityNumbersSequence{};

        return operatorPlusStage1<Result>(other, entityNumbersSequence);
    }

    ////////////////////////////////////////////////////////////////////////////////
    template<typename Result, typename Other, uint8_t... EntityNumbers>
    constexpr auto operatorPlusStage1(const Other& other, std::integer_sequence<uint8_t, EntityNumbers...>) const {

        //преобразование EntityNumber в Index через countIndex
        std::integer_sequence<uint8_t, Result::countIndex(EntityNumbers)...> indicesSequence{};

        return operatorPlusStage2<Result>(other, indicesSequence);
    }

    ////////////////////////////////////////////////////////////////////////////////
    template<typename Result, typename Other, uint8_t... Indices>
    constexpr auto operatorPlusStage2(const Other& other, std::integer_sequence<uint8_t, Indices...>) const {

        //взятие своего и другого значения по индексу, поштучное суммирование и передача полученного пака в конструктор результата
        return Result{ (get<Indices>() + other.template get<Indices>())... };
    }



A>В коде всё также присутствует std::integer_sequence — я так понимаю, это compile-time выражение.


std::integer_sequence — сам по себе это шаблон, мы в него заряжаем один раз — пак из 8-битных целых EntityNumbers..., второй раз — пак Indices... — вот эти паки — они исключительно в compile-time.
Re[6]: Разреженный массив в compile-time
От: avovana Россия  
Дата: 13.07.18 18:37
Оценка:
Здравствуйте, vopl, Вы писали:

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


Спасибо за разъяснение! Принялся к изучению кода.
Re[3]: Разреженный массив в compile-time
От: Croessmah  
Дата: 19.07.18 11:31
Оценка:
A>Мне дали эту тестовую задачку и попросили сказать за сколько её получилось сделать когда пришлю ответ.
A>Я её делаю уже 2ой месяц

Решение, на киберфоруме, ссылку на которое Вам дали, сделалось примерно за час-полтора. )))

Что у Вас не получается? Задача, в принципе, не особо сложная.

Вам нужно пройти по элементам каждого из массивов и сложить их, соответственно, нужен некий get, возвращающий значение элемента массива по индексу (либо из массива, либо значение по-умолчанию).

Переделал своё решение с киберфорума под Ваше.

//Добавил оттуда MakeIndexSeqFromMask и details, чтобы заново не придумывать
namespace details
{

template<uint64_t Value, unsigned Index, uint64_t ... Args>
struct MakeSeqImpl;
 
template<bool Need, uint64_t Value, unsigned Index, uint64_t ... Args>
struct TypeImpl
{
    using type = typename MakeSeqImpl<(Value >> 1), Index + 1, Args..., Index>::type;
};
template<uint64_t Value, unsigned Index, uint64_t ... Args>
struct TypeImpl<false, Value, Index, Args...>
{
    using type = typename MakeSeqImpl<(Value >> 1), Index + 1, Args...>::type;
};
 
 
template<uint64_t Value, unsigned Index, uint64_t ... Args>
struct MakeSeqImpl
{
    using type = typename TypeImpl<Value & 1, Value, Index, Args...>::type;    
};
 
 
template<unsigned Index, uint64_t ... Args>
struct MakeSeqImpl<0, Index, Args...>
{
    using type = typename std::index_sequence<Args...>;    
};

}//namespace details


template<uint64_t Mask>
struct MakeIndexSeqFromMask
{
    using type = typename details::MakeSeqImpl<Mask, 0>::type;
};


//В SparseArray сделал константную и не константную версию get.
//Внимание на conditional_t - если элемент содержится в массиве, 
//то возвращаем ссылку, в ином случае возвращаем копию значения по-умолчанию.
    template<uint8_t Index>    
    constexpr std::conditional_t<(Mask >> Index) & 0b1, T const &, T>
    get() const {
        if constexpr (isSet(Index))
            return values[countEntityNumber(Index)];
        else
            return T();
    }

     template<uint8_t Index>    
    constexpr std::conditional_t<(Mask >> Index) & 0b1, T&, T>
    get() {
        if constexpr (isSet(Index))
            return values[countEntityNumber(Index)];
        else
            return T();
    }

    //Переделал operator+. Он подготавливает аргументы для sum
    using SequenceType = typename MakeIndexSeqFromMask<Mask>::type;
    template<typename TOther, uint64_t MaskOther>
    constexpr auto operator+(const SparseArray<TOther, MaskOther> & other) -> 
        SparseArray<decltype(std::declval<T>() + std::declval<TOther>()), Mask | MaskOther>
    {
        using ResultType = SparseArray<decltype(std::declval<T>() + std::declval<TOther>()), Mask | MaskOther>;
        //ResultType::SequenceType{} - это index_sequence с индексами содержащихся в массиве элементов,
        //т.е. только те индексы, для которых в маске результирующего типа содержится установленные биты
        return sum<ResultType>(*this, other, typename ResultType::SequenceType{});
    }
    
    
    //sum занимается сложением
    template<typename R, typename F, typename S, std::size_t ... Indexes>
    constexpr R sum(F && f, S && s, std::index_sequence<Indexes...>)
    {        
        R result;
        int fake[] = {
             //Разворачиваем индексы и складываем значения. 
             //За счет того, что проходим только по установленным индексам, 
             //и за счет того, что get для таких элементов возвращает ссылку,
             //мы можем присвоить значения элементам массива.
            ((result.template get<Indexes>() = f.template get<Indexes>() + s.template get<Indexes>()), 0)...
        };(void)fake;
        return result;
    }

Полный код:
https://wandbox.org/permlink/JlKgmCKzBvwDIyUp
Как видите, такой код проходит все тесты в main.
c++ c++17
Re[4]: Разреженный массив в compile-time
От: vopl Россия  
Дата: 20.07.18 14:25
Оценка:
Здравствуйте, Croessmah, Вы писали:

C>Как видите, такой код проходит все тесты в main.


А я бы вот докопался все таки

1. Метод sum — сначала конструируется пустой результат а затем наполняется значениями. Почему сразу не конструировать с нужными значениями?
2. Метод get своим именем как бы намекает, что с его помощью нужно "получать". А на практике, с его помощью можно еще и модифицировать. Такой get должен называться как нибудь типа at
3. operator+ получился не консэкспр, хотя таковым обозначен
4. SFINAE для operator+ так и не сделано
Re[5]: Разреженный массив в compile-time
От: Croessmah  
Дата: 20.07.18 16:52
Оценка:
Здравствуйте, vopl, Вы писали:

V>А я бы вот докопался все таки


Докопаться всегда можно и приятно. )))

V>1. Метод sum — сначала конструируется пустой результат а затем наполняется значениями. Почему сразу не конструировать с нужными значениями?


Да, можно и так:

template<typename R, typename F, typename S, std::size_t ... Indexes>
constexpr R sum(F && f, S && s, std::index_sequence<Indexes...>)
{        
    return {(f.template get<Indexes>() + s.template get<Indexes>())...};
}


V>2. Метод get своим именем как бы намекает, что с его помощью нужно "получать". А на практике, с его помощью можно еще и модифицировать. Такой get должен называться как нибудь типа at


Так мы и получаем, либо ссылку на существующий элемент, либо копию значения по-умолчанию.
В защиту себя могу сказать, что я не знаю английский язык.
В защиту get могу привести в пример std::get, а не std::at.


V>3. operator+ получился не консэкспр, хотя таковым обозначен


Убрать из конструктора и деструктора вывод, на operator+ навесить const, переменные в main сделать constexpr и готово, дело-то минута.
https://wandbox.org/permlink/KWzCCxayORVCTagc
Отредактировано 20.07.2018 16:55 Croessmah . Предыдущая версия .
Re[6]: Разреженный массив в compile-time
От: vopl Россия  
Дата: 23.07.18 08:53
Оценка:
Здравствуйте, Croessmah, Вы писали:

V>>2. Метод get своим именем как бы намекает, что с его помощью нужно "получать". А на практике, с его помощью можно еще и модифицировать. Такой get должен называться как нибудь типа at


C>Так мы и получаем, либо ссылку на существующий элемент, либо копию значения по-умолчанию.

C>В защиту себя могу сказать, что я не знаю английский язык.
C>В защиту get могу привести в пример std::get, а не std::at.

Посмотри на аналоги

https://en.cppreference.com/w/cpp/container/vector/at
https://en.cppreference.com/w/cpp/container/array/at
https://doc.qt.io/qt-5/qlist.html#at
https://www.boost.org/doc/libs/1_67_0/doc/html/boost/circular_buffer.html#idp42094176-bb
https://www.boost.org/doc/libs/1_67_0/doc/html/boost/container/stable_vector.html#idp58502304-bb

А std::get — это немного другое
Re[4]: Разреженный массив в compile-time
От: avovana Россия  
Дата: 25.07.18 10:46
Оценка:
Здравствуйте, Croessmah, Вы писали:

C>Решение, на киберфоруме, ссылку на которое Вам дали, сделалось примерно за час-полтора. )))


C>Что у Вас не получается? Задача, в принципе, не особо сложная.


Croessmah, рад Вас здесь видеть!
То решение мне сложновато давалось для понимания, т.к. опыта у меня немного.
Оказалось, что проще было написать что-то своё и уточнить)

C>Вам нужно пройти по элементам каждого из массивов и сложить их, соответственно, нужен некий get, возвращающий значение элемента массива по индексу (либо из массива, либо значение по-умолчанию).


C>Переделал своё решение с киберфорума под Ваше.

C>Как видите, такой код проходит все тесты в main.
Спасибо за взгляд на решение проблемы с такой стороны.

Так понимаю, что реализация SequenceType написана в стиле шаблонного программирования:
Представлена шаблонная структура со специализацией. Причем два раза.

Первый раз увидел std::declval<>() в реальном коде. Интересно.

Не совсем понял смысл trailing return type
-> SparseArray<decltype(std::declval<T>() + std::declval<TOther>()), Mask | MaskOther>

Вроде бы auto и так должно вывести тип.

Интересная возможность вернуть ссылку с помощью применения std::conditional_t.

Изучаю код. Спасибо за ответ


Странно, что если раскомментирую секцию private в примере с operatorPlusStage1, operatorPlusStage2, то компилятор начинает ругаться, что в методе operator+ идет обращение к закрытой части класса.
operator+ ведь обычный метод класса, который должен иметь доступ ко всем полям и методам класса.
Отредактировано 25.07.2018 10:52 avovana . Предыдущая версия .
Re[5]: Разреженный массив в compile-time
От: vopl Россия  
Дата: 26.07.18 07:58
Оценка:
Здравствуйте, avovana, Вы писали:

A>Странно, что если раскомментирую секцию private в примере с operatorPlusStage1, operatorPlusStage2, то компилятор начинает ругаться, что в методе operator+ идет обращение к закрытой части класса.

A>operator+ ведь обычный метод класса, который должен иметь доступ ко всем полям и методам класса.

Хм.. Вроде это мои названия отсюда http://rsdn.org/forum/cpp.applied/7191800.1
Автор: vopl
Дата: 09.07.18


(этот форум — он деревянный, ответ лучше давать на исходное сообщение а не на любое, иначе становится сложно отслеживать ход дискуссии так как начинается каша)

У меня там вроде не было никаких private Покажи проблемный код целиком?
Re[6]: Разреженный массив в compile-time
От: vopl Россия  
Дата: 26.07.18 09:14
Оценка:
Здравствуйте, Croessmah, Вы писали:

C>Здравствуйте, vopl, Вы писали:


V>>А я бы вот докопался все таки


C>Докопаться всегда можно и приятно. )))


V>>1. Метод sum...

C>Да, можно и так:...

V>>2. Метод get...

C>Так мы и получаем...

V>>3. operator+...

C>Убрать из конструктора...

4. SFINAE для operator+ так и не сделано
оно есть. Недосмотрел
Отредактировано 26.07.2018 9:19 vopl . Предыдущая версия .
Re[6]: Разреженный массив в compile-time
От: avovana Россия  
Дата: 26.07.18 18:36
Оценка:
Здравствуйте, vopl, Вы писали:

V>Здравствуйте, avovana, Вы писали:


A>>Странно, что если раскомментирую секцию private в примере с operatorPlusStage1, operatorPlusStage2, то компилятор начинает ругаться, что в методе operator+ идет обращение к закрытой части класса.

A>>operator+ ведь обычный метод класса, который должен иметь доступ ко всем полям и методам класса.

V>Хм.. Вроде это мои названия отсюда http://rsdn.org/forum/cpp.applied/7191800.1
Автор: vopl
Дата: 09.07.18


V>(этот форум — он деревянный, ответ лучше давать на исходное сообщение а не на любое, иначе становится сложно отслеживать ход дискуссии так как начинается каша)


V>У меня там вроде не было никаких private Покажи проблемный код целиком?


Да, всё верно. Это тот самый пример. Сейчас использую твой подход в реализации operator+
Думал улучшить защищенность класса, но добавление секции private рубит идею на корню:
https://github.com/avovana/CodeBase/blob/fc8c27a423c13f909a375a439e8b2123f4b78e6b/SparseArray.cpp#L55

(П.с. На этот раз, думаю, получилось ответить на нужное сообщение)
Re[7]: Разреженный массив в compile-time
От: vopl Россия  
Дата: 27.07.18 08:41
Оценка:
Здравствуйте, avovana, Вы писали:

A>>>Странно, что если раскомментирую секцию private в примере с operatorPlusStage1, operatorPlusStage2, то компилятор начинает ругаться, что в методе operator+ идет обращение к закрытой части класса.

A>>>operator+ ведь обычный метод класса, который должен иметь доступ ко всем полям и методам класса.

V>>У меня там вроде не было никаких private Покажи проблемный код целиком?


A>Думал улучшить защищенность класса, но добавление секции private рубит идею на корню:

A>https://github.com/avovana/CodeBase/blob/fc8c27a423c13f909a375a439e8b2123f4b78e6b/SparseArray.cpp#L55

да, действительно, ругань есть. Обрати внимание, что ругань идет на обращение к закрытой части другого класса. Дистилированный пример:


// из этого шаблона можно порождать разные типы
template <typename T>
class C
{
private:
    int v;

public:

    template <typename T2>
    void f(C<T2> another)
    {
        v = another.v;//обращение к приватному члену C<T2>::v
    }
};

int main ()
{
    C<int> c1;  //объект c1 имеет тип C<int>
    C<char> c2; //объект c2 имеет тип C<char> - обрати внимание, это уже другой тип, хотя и полученный из одного и того же шаблона

    c1.f(c1);   //нормально, так как внутри C<int>::f будет обращение к C<int>::v.
    c2.f(c2);   //нормально


    //c1.f(c2); //а тут уже не будет компилироваться так как C<int>::f будет пытаться получить доступ к C<char>::v
    //c2.f(c1); //аналогично

    //struct Some;
    //c2.f(C<Some>{}); //аналогично

    return 0 ;
}


То есть, другими словами:
SparseArray это не класс, это шаблон. Из него получаются разные конкретные типы. Один из них в своих методах пытается получить доступ к приватным членам другого типа. Компилятор об этом резонно сообщает.

Что делать? Вариантов на самом деле масса, думаю сам вполне придумаешь как это красиво обрулить. Все таки задача — спортивная)
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.