5 / 5 / 6
Регистрация: 23.03.2018
Сообщений: 98
1

Разреженный массив (с использованием шаблонов), исключение оператора посредством SFINAE

24.03.2018, 19:16. Показов 2099. Ответов 6

Author24 — интернет-сервис помощи студентам
Доброго времени суток.

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

и вот в руки попало тестовое задание, в душе я понимаю, что ловить здесь мне особ нечего в данный момент времени. НО!необходимость и желание освоиться в мире "воздушных замков" превалирует перед судорожным отторжением этой идеи мозгом.

собственно вопрос:

есть не до конца заполненный класс разреженного массива

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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[/*Посчитать размер разреженного массива*/];
};
необходимо заполнить недостающие куски кода.

если у кого есть время пояснить основные моменты, буду весьма благодарен.

пока что понимаю только, что:

есть класс внутри него необходимо описать разреженный массив : либо связный список, либо бинарное дерево.
(бинарное дерево я вполне в силах описать)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.03.2018, 19:16
Ответы с готовыми решениями:

[c++][template][sfinae] перегрузки шаблонов
добрый вечер. сабж: есть шаблон функции работы со строками. если параметр возвращаемого...

Не получается правильно объявить friend перегрузку оператора с использованием шаблонов
Всем привет! Посмотрите код и во вложениях скриншот ошибок, и, пожалуйста, подскажите, что сделал...

Разреженный массив
Дан одномерный массив с большим количеством нулевых элементов. Заменить в нем каждую группу из...

Разреженный массив
Есть ли где ещё, кроме как у Герберта Шилдта, рекомендации по разработке классов разреженных...

6
Неэпический
17869 / 10634 / 2054
Регистрация: 27.09.2012
Сообщений: 26,736
Записей в блоге: 1
26.03.2018, 22:07 2
Здесь вопросов еще больше, чем комментариев к коду.
Цитата Сообщение от perevertysh Посмотреть сообщение
есть не до конца заполненный класс разреженного массива
Цитата Сообщение от perevertysh Посмотреть сообщение
есть класс внутри него необходимо описать разреженный массив
Этот SparseArray прямо из задания или самописный?
А массив в результате должен уметь в constexpr?

Цитата Сообщение от perevertysh Посмотреть сообщение
typename T, uint64_t Mask
Что за Mask? Для чего и как он используется?
Тип T - это непосредственно тип элементов?
Каким образом тогда отражать индекс в массиве на индекс в разреженном массиве?
Цитата Сообщение от perevertysh Посмотреть сообщение
Вернуть значение T, если элемента нет в массиве, иначе вернуть существующий элемент из массива.
get возвращает T&, так что какой-попало объект не вернешь. Необходимо его где-то хранить.
Или имеется ввиду, что если такого элемента нет, то get должна возвращать T, а не T&?
Цитата Сообщение от perevertysh Посмотреть сообщение
Исключить оператор при помощи SFINAE если нет оператора + для пары T и TOther
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <string>
 
#include <type_traits>
 
 
namespace details
{
template<typename T, typename U = T>
class HasOperatorImpl
{
private:
    struct No {};
    template<typename V, typename Z>
    static auto binary_plus(V *) -> decltype(*(V*)(0) + *(Z*)(0));
    template<typename, typename>
    static auto binary_plus(...) -> No;
    
    template<typename V, typename Z>
    static auto binary_minus(V *) -> decltype(*(V*)(0) - *(Z*)(0));
    template<typename, typename>
    static auto binary_minus(...) -> No;
    
    template<typename V>
    static auto prefix_increment(V *) -> decltype(++*(V*)(0));
    template<typename>
    static auto prefix_increment(...) -> No;
public:
    static constexpr bool BinaryPlus =  !std::is_same<decltype(binary_plus<T, U>(nullptr)), No>::value;
    static constexpr bool BinaryMinus =  !std::is_same<decltype(binary_minus<T, U>(nullptr)), No>::value;
    static constexpr bool PrefixIncrement =  !std::is_same<decltype(prefix_increment<T>(nullptr)), No>::value;
};
}//namespace details
 
 
template<class T, class U = T>
constexpr bool HasBinaryPlus = details::HasOperatorImpl<T, U>::BinaryPlus;
 
template<class T, class U = T>
constexpr bool HasBinaryMinus = details::HasOperatorImpl<T, U>::BinaryMinus;
 
template<class T>
constexpr bool HasPrefixIncrement = details::HasOperatorImpl<T>::PrefixIncrement;
 
 
int main()
{
    std::cout << HasBinaryPlus<std::string, char *> << std::endl;
    std::cout << HasBinaryPlus<int, std::string> << std::endl;
    std::cout << HasBinaryMinus<int, double> << std::endl;    
    std::cout << HasBinaryMinus<int, std::string> << std::endl;
    std::cout << HasPrefixIncrement<double> << std::endl;
    std::cout << HasPrefixIncrement<std::string> << std::endl;
}
http://rextester.com/LXGLW24123

И остается выключить SparseArray::operator+, например, с помощью std::enable_if.
Цитата Сообщение от perevertysh Посмотреть сообщение
//Вернёт новый SparseArray с поэлементной суммой двух исходных массивов
А если MaskOther и Mask несовместимы, какой считается "правильным"?
Цитата Сообщение от perevertysh Посмотреть сообщение
/*Посчитать размер разреженного массива*/
В этом месте про этот массив ничего неизвестно.
1
5 / 5 / 6
Регистрация: 23.03.2018
Сообщений: 98
26.03.2018, 22:25  [ТС] 3
Croessmah, вот полный текст задания.

Кликните здесь для просмотра всего текста
Допишите класс SparseArray (разреженный массив) в файле SparseArray.cpp, следуя комментариям и ограничениям, описанным в коде.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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;
}
0
Неэпический
17869 / 10634 / 2054
Регистрация: 27.09.2012
Сообщений: 26,736
Записей в блоге: 1
27.03.2018, 17:00 4
Сделал тупо для прохождения теста:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include <cstdint>
#include <cassert>
#include <type_traits>
#include <utility>
#include <tuple>
 
namespace details
{
template<typename T, typename U = T>
class HasOperatorImpl
{
private:
    struct No {};
    template<typename V, typename Z>
    static auto binary_plus(V *) -> decltype(*(V*)(0) + *(Z*)(0));
    template<typename, typename>
    static auto binary_plus(...) -> No;
public:
    using BinaryPlusType = std::conditional_t<
        std::is_same<decltype(binary_plus<T, U>(nullptr)), No>::value,
        void,
        decltype(binary_plus<T, U>(nullptr))
    >;
    static constexpr bool BinaryPlus =  !std::is_same<decltype(binary_plus<T, U>(nullptr)), No>::value;
};
 
 
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...>;    
};
 
 
template<std::size_t Index, auto FindValue, auto ... Args>
struct FindValueImpl
{
    static constexpr std::size_t value = Index;
};
 
template<std::size_t Index, auto FindValue, auto ... Args>
struct FindValueImpl<Index, FindValue, FindValue, Args...>
{
    static constexpr std::size_t value = Index;
};
 
template<std::size_t Index, auto FindValue, auto Value, auto ... Args>
struct FindValueImpl<Index, FindValue, Value, Args...>
{
    static constexpr std::size_t value = FindValueImpl<Index + 1, FindValue, Args...>::value;
};
 
 
template<auto Value, auto ... Args>
struct FindIndexValue
{
    static constexpr std::size_t value = FindValueImpl<0, Value, Args...>::value;
};
 
 
}//namespace details
 
 
template<class T, class U = T>
constexpr bool HasBinaryPlus = details::HasOperatorImpl<T, U>::BinaryPlus;
template<class T, class U = T>
using BinaryPlusType = typename details::HasOperatorImpl<T, U>::BinaryPlusType;
 
 
template<uint64_t Mask>
struct MakeIndexSeqFromMask
{
    using type = typename details::MakeSeqImpl<Mask, 0>::type;
};
 
 
 
template<std::size_t Index, typename T, T ... Args>
constexpr std::size_t mapped_index(std::integer_sequence<T, Args...>)
{
    return details::FindIndexValue<Index, Args...>::value; 
}
 
 
 
template<typename T, uint64_t Mask>
class SparseArray {
public:
    using SequenceType = typename MakeIndexSeqFromMask<Mask>::type;
    static constexpr std::size_t ArraySize = SequenceType::size();
    using ElementType = T;
 
    constexpr SparseArray(): values{}
    {
    }
 
    template<typename ... Args>
    constexpr SparseArray(Args && ...args): values{std::forward<Args>(args)...}
    {
    }
 
    template<uint8_t Index>
    constexpr std::conditional_t<mapped_index<Index>(SequenceType()) != ArraySize, T&, T const>
    get()
    {        
        constexpr unsigned i = mapped_index<Index>(SequenceType());
        if constexpr (i != ArraySize) {
            return values[i];
        } else {
            return T{};
        }
    }
 
    template<uint8_t Index>
    constexpr std::conditional_t<mapped_index<Index>(SequenceType()) != ArraySize, T const &, T const>
    get() const
    {        
        constexpr unsigned i = mapped_index<Index>(SequenceType());
        if constexpr (i != ArraySize) {
            return values[i];
        } else {
            return T{};
        }
    }
 
 
    template<typename TOther, uint64_t MaskOther>
    constexpr auto operator+(const SparseArray<TOther, MaskOther> & other) ->
        SparseArray<std::enable_if_t<HasBinaryPlus<T, TOther>, BinaryPlusType<T, TOther>>, Mask | MaskOther>
    {
        using ResultType = SparseArray<BinaryPlusType<T, TOther>, Mask | MaskOther>;
        return sum<ResultType>(*this, other, typename ResultType::SequenceType{});
    }
private:
 
    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[] = {
            ((result.template get<Indexes>() = f.template get<Indexes>() + s.template get<Indexes>()), 0)...
        };(void)fake;
        return result;
    }
 
 
    static constexpr T default_value {};
    T values[ArraySize];
};
 
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);
}
GCC 7.2 собирает, тесты проходит, на счет остальных не знаю, других компиляторов с поддержкой C++17 под рукой нет. Код говно, но думать над хорошим решением времени нет.
0
5 / 5 / 6
Регистрация: 23.03.2018
Сообщений: 98
30.03.2018, 21:47  [ТС] 5
Croessmah, спасибо за пример, но только есть несколько вопросов:
-Это только под 64 бит или под 32 тоже собрать можно?
-необходим С++17?
-и еще не подскажешь, как в линуксе GCC к компилятору прикрутить?

Добавлено через 28 минут
и оно немного не компилится
0
Неэпический
17869 / 10634 / 2054
Регистрация: 27.09.2012
Сообщений: 26,736
Записей в блоге: 1
31.03.2018, 01:15 6
Цитата Сообщение от perevertysh Посмотреть сообщение
-Это только под 64 бит или под 32 тоже собрать можно?
Можно
Цитата Сообщение от perevertysh Посмотреть сообщение
-необходим С++17?
Да. В тесте используется std::is_same_v, из чего можно сделать вывод, что C++17 можно использовать.
Цитата Сообщение от perevertysh Посмотреть сообщение
-и еще не подскажешь, как в линуксе GCC к компилятору прикрутить?
А чего там прикручивать? Берешь и собираешь?
Цитата Сообщение от perevertysh Посмотреть сообщение
и оно немного не компилится
Ну значит не судьба. Для другого ответа еще не мешало бы показать версию компилятора, ключи компиляции, список ошибок.
0
5 / 5 / 6
Регистрация: 23.03.2018
Сообщений: 98
31.03.2018, 02:37  [ТС] 7
C++
1
assert(sum.get<0>() == 1.0);
ну там вроде и это тоже в С++17 добавлено.

для меня этот вопрос чисто познавательную ценность несет. в руки задание попалось тестовое для собеседования в контору, в которой математика на уровне, вот интересно стало, сколько мне еще грести в светлое завтра.
0
31.03.2018, 02:37
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
31.03.2018, 02:37
Помогаю со студенческими работами здесь

Разреженный массив
Друзья, как реализовать разреженный массив через односвязный список? Попытался написать, но не...

Разреженный массив
Периодически в некоторых задачах возникает надобность в разреженных массивах. Разреженный массив...

Разреженный массив
Имеется разряженный массив. int a = ; В нем 2 пустых места между 2..4 и 5..undefined...

Перегрузка оператора + для шаблонов
Добрый день Имеется такой класс: #ifndef EXTENDED_H #define EXTENDED_H #include &lt;QString&gt;...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru