last day (15 days later) » 

6:58 PM
2
A: How to create compile-time templatized set/array/vector with fibonacci numbers using templates?

Justin TimeDue to a quirk of the language, Fib() and make_fibonacci_set(), as written, will have infinite recursion (specifically, to my understanding, the problem is that while only one branch is chosen, both are evaluated; this causes the compiler to instantiate the templates required by the recursive bra...

 
Faaar too many template instantiations just to get a few Fibonacci numbers, really :-). I'd try to use more constexpr, especially if C++14 is an option. Also, the method for finding the largest representable number assumes there are no integral types larger than ULL, which may not be the case.
 
@JustinTime Thanks a lot! I won't pretend I understand all of that, but it works :) I tried to slightly simplify it for my needs (and to better understand it) and that's what I ended up with: pastebin.com/UWPnE2Ff Could you tell me if that solution is correct, and if not - why not?
@bogdan how would you simplify it using constexpr? And what would you change, so that it would also work if typename U is bigger than unsigned long long?
 
@Jecke A quick solution requiring a compiler with reasonable support for C++14 constexpr could look like this. It works on relatively recent Clang and GCC versions, and also on MSVC 2017 RC. (Note that I don't think it makes sense to allow floating point types.) Of course, this is only one variation of many. For example, you could build that std::array iteratively in a constexpr function, but that would require some C++17 support in the standard library that I think only GCC 7 has currently.
 
I see, that is, indeed, significantly simple. But how do you put that in a template class (template<typename U, ...more...> class A)? I tried static constexpr auto fibonacci = make_fibonacci_sequence<U>(); and static constexpr auto fibonacci = make_fib_hlp<U>(1, 1, std::make_index_sequence<seq_size<U>(1, 1)>{}); but both give me error " undefined reference to `A<...arguments....>::fibonacci'"
 
@Jecke If you're using that variable in a way that requires it to have a definition, you need to provide one out-of-class (the in-class one is only a declaration in C++14 and before). Given that the two declarations need to specify the same type (and it can't be auto), here's one way to do it. This is no longer a problem in C++17, due to the introduction of the notion of inline variables.
@Jecke However, note that each of A<short, char> and A<short, long> will have its own copy of that static member, even if they're identical. I don't think the linker will be able to fold those sections into one, unless the compiler can somehow prove that the code doesn't rely on their addresses being different, or you indicate that through some compiler-specific mechanism. That's not something I'd want to depend upon, so I'd separate that variable into a construct that only depends on U: a standalone variable template, or a base of A of the form B<U>, something like that.
 
6:58 PM
Thanks a lot! I know, I share your concerns (several copies of identical array, if I understand correctly), but unfortunately it's not up to me - I have to create (at compile time) a public field fibonacci. Could you please explain what exactly does the return {{n1, n2, ((void)Is, n2 += n1, n1 = n2 - n1, n2)...}}; line do?
 
@Jecke You can provide the public member through a base class that depends only on U, as I said above.
That return statement constructs a braced init list by expanding the Is parameter pack. The pack is only used as a counter, hence the cast to void, otherwise the compiler may warn that it's unused.
The pack expansion pattern is an expression (in parentheses) using several comma operators, which evaluate those subexpressions in order for each instance of the counter in Is. The two subexpressions in the middle have side effects: they switch n2 -> n1 and n1 + n2 -> n2 by doing that little dance (in order to avoid using a temporary). The final result of each big expression is the last operand, the newly calculated n2.
It's basically what you would do in a loop, but unrolled in a sequence using the pack expansion mechanism. Since it's all evaluated at compile time, none of that code will end up in the executable, so the fact that we're essentially unrolling a loop over several tens of elements is not a concern.
While it's nice for showing off, it looks a bit like black magic, so I wouldn't have chosen such a solution if it weren't for the fact that std::array has poor constexpr support in C++14, so you can't do things like a[i] = n2 in a constant expression.
That's all much better in C++17. A quickly hacked-together solution that takes advantage of that and is purely procedural could look like this:
You can only compile that in GCC 7 at the moment. Longer code, but probably easier to read.
You can do most of that in C++14, but you can't use std::array internally, as I said above. You'd have to use a built-in array, U a[seq_size<U>()] = {};, fill it with the numbers, then use an index_sequence and pack expansion to build a braced init list from the built-in array to initialize an std::array to return. Since you'd still have to do the pack expansion dance anyway, I preferred to do everything in one go using that obscure expression.
 
8:13 PM
ok, I see how a sequence of operations
n2 += n1;
n1 = n2 - n1;
"shifts" n1 and n2 by one fibonacci number (so n1 is now old n2 and n2 is old n1 + old n2)

I've seen {{list_of_values}} being used to create an array from list_of_values, so I understand that part too.

But I've never seen std::index_sequence<Is...> (at all) or parentheses (used that way).
I've seen thing similar to this:
std::set function(ArgumentType... arguments) {
return {{arguments...}};
}
where "arguments..." means "argument1, argument2, ...."
 
@Jecke The commas are not the same commas that separate, say, function arguments. They're the comma operator.
std::index_sequence is only used as a holder for a sequence 0, 1, 2, ..., N that we can then expand, just like in your example.
The thing is you can have other kinds of expressions instead of arguments in a pack expansion. The pack expansion mechanism will take the expression (which has to contain at least one parameter pack) and replicate it as many times as there are elements in the pack.
(There can be several packs in there, but all the packs expanded by the same ... must have the same length.)
 
8:29 PM
Do I understand correctly, that "(void)Is" doesn't do anything, but is necessary, because the pack expansion "..." requires Is to "show up" in it?
 
@Jecke Yes, pretty much, the pack expansion needs to expand something, and we've built something that will expand to the number of elements that we need, but that's all there is to it in this case.
So, if you have two packs, Is containing 1, 2 and Js containing 3, 4, the pack expansion Is + Js... will yield 1 + 3, 2 + 4.
 
Ok, I think I understand, thanks a lot :) And, as You said, you could just write "(Is, n2 += n1, n1 = n2 - n1, n2)...", but then you'd get warnings, so you cast "Is" to void to avoid them?
 
Yes, the compiler sees that the value of that operand goes nowhere and that it has no side-effects, so... who in their right mind would do that? The cast to void is a way to say "I know what I'm doing, I really want this expression's result to be discarded".
Also note that the parentheses are necessary because, in the grammar, the comma operator is the only one "below" the pack expansion in a braced-init-list.
It kind of makes sense - we have to distinguish between the two kinds of commas.
 
8:45 PM
I see
Hmm, I tried changing make_fib_hlp a little, I wrote:
{
int temp = 0;
return {{n1, n2, ((void)Is, temp = n2, n2 += n1, n1 = temp, n2)...}};
}

But it gives slightly different results...
I mean - all fibonaccis are ok, but when U is unsigned long long, it gives one more (wrong)
 
Well, if temp is int, and those numbers are large unsigned long longs...
 
yeah, that explains it
but this works:

{
U temp = 0;
return {{n1, n2, ((void)Is, temp = n2, n2 += n1, n1 = temp, n2)...}};
}
 
Yup.
One note about those double braces:
Normally, you only need one pair. But the thing is std::array is typically internally implemented as an aggregate with the only non-static member a built-in array. So, those braces do aggregate initialization of that member array. It works fine with only one pair, due to "brace elision", but Clang warns about that, suggesting that you don't use brace elision (the worry is that you did it by mistake, not in this case, but for more complicated aggregates).
So, again, the double braces are there only to silence a compiler warning in this case.
 
9:06 PM
So one pair of braces is for construction of the object std::array and the other for construction of its field? And I could skip one pair similar to how I can write both "A a{{1},{2}};" or "A a{1,2};", when I have
class B {
int b;
public: B(int b_) : b(b_) {}
};

class A {
B b1, b2;
public: A(B b1_, B b2_) : b1(b1_), b2(b2_) {}
};
 
"So one pair of braces is for construction of the object std::array and the other for construction of its field?" - exactly.
The rest is not exactly the same thing, because A in your example is not an aggregate - it has a user-provided constructor.
The equivalent example would be with A of the form:
class A
{
public:
   B b1, b2;
};
And the same for B. Initializing that with either A a{{1},{2}}; or A a{1,2}; is aggregate initialization, and brace elision applies in the second case.
When constructors are present, the mechanisms of initialization are different - those initializations will actually call the constructors, instead of initializing the members with the corresponding elements of the braced init lists as aggregate initialization does.
 
I see:) I can't thank you enough; I've learned more today than in a week at the university ;)
 
Glad to help :-)
Where are you studying?
(just curious, no need to answer :-D )
 
9:21 PM
University of Warsaw
 
Nice. That's one beautiful city that I didn't get to visit yet, but will, one day.
In closing, what about n1 > std::numeric_limits<U>::max() - n2? Did that raise your eyebrows?
 
It is, sure worth visiting :)
should it? This is how I understand it:
std::numeric_limits<U>::max() returns a max_value for U,
then you check if n1 + n2 > max_value,
but since n1 + n2 will eventually be greater than max_value (that's why we check it in a first place) and probably loop around, we instead check n2 > max_value - n1, which should be in the U range
 
Yes, that's correct. The fundamental issue is that signed overflow is undefined behaviour in standard C++ (unsigned is defined as doing modulo arithmetic, so it's defined that it will wrap around). Since U can be a signed integer type, we have to avoid doing the addition unless we're sure it doesn't overflow.
Your initial code has a comparison Fib<U, n>() <= Fib<U, n-1>() that actually relies on wraparound.
If U were guaranteed to be unsigned, that would be fine (unless it could wrap around by more than 2^N...).
But if it's signed, two things would happen:
A constant expression cannot have undefined behaviour, so the compiler will reject that.
In a non-constant expression context, a smart compiler may see that the values of Fib can only monotonically increase unless there's overflow, and since you're not supposed to have overflow, optimize that check away as always false.
 
9:45 PM
yeah, that would be quite problematic; not only would it not work as I'd want it to, but it could compile and pretend everything is ok... (in the second case)
 
Right.
 
ok, I must be going, thanks again for your time and help :)
 
10:25 PM
Cheers!
 

last day (15 days later) »