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
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.