
Boost : 
From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 20061127 18:14:11
Daryle Walker wrote:
>>Did you consider using expression templates to
>>
>> eliminate temporaries in expressions
>> detect temporaries to use inplace operations instead of copying ones, IOW
>>exploiting destructibility of values
>> decorate the allocator for stackbased allocation during evaluation
>> replacing widening conversion operations with views
>>
>>?
>
>
> No. An type aided with expression templates eventually has to forward to
> some algorithms somewhere. I substituted for that by having member
> functions that combine operations together. Only operations that can be
> reasonably combined are done; operations that can interfere with each other
> aren't combined. That's why division and modulus don't combine with
> anything besides each other. However, a class like mine can be used as the
> implementation class for something that does use expression templates!
> Also, expression templates would interfere with presenting the code clearly
> (for educational purposes).
I see.
>
>>The last point of the above list can probably be implemented with a "hollow
>>base", CRTP and deducefrombase instead of ET (similar to polymorphism of
>>parsers in Spirit).
>
>
> What's CRTP stand for?
>
It's the Curiously Recurring Template Pattern (some code attached).
You can make a base class know its dervied class by specializing a base class template with the derived type. This way you can use static_cast to downcast the 'this' pointer and implement compile time polymorphism. I gave a code example in reply to Maarten Kronenburg.
>
>>The ET approach could also be used to implement interesting syntactic
>>properties. I once wrote a Wiki page about it:
>>
>> http://tinyurl.com/qtyhh
>
>
> I've read that page. I got some of my ideas from it (like the memory
> management at the end).
>
> Natural logarithm and/or any base?
log_Radix is there already and it's called digit_count(), isn't it?
Base N where N is an integer would be useful (e.g. to deal with tree structures larger than main memory).
> How can it be done, especially since I
> would be limited to integer arithmetic and results? I only have access to
> Knuth's _The Art of Computer Programming_ books, Wikipeida, plus occasional
> bignum pages I see on the web. I don't have access to the ACM/IEEE stuff,
> where I suspect a lot of "kewl" algorithms live.
Well, I don't have a really cool algorithm in my pocket. What follows is possibly amateurish intuitive guessing  there are probably better algorithms around (probably even in Knuth's TAOCP). Anyway, I'll give it a try:
Let's first look at cases where things are easy:
Given Radix = pow(b_r,n), where b_r,n are integers
log_b_r(x) = log_Radix(x)*n + log_b_r(most_significant_digit(x))
Example:
Radix = 256
b_r = 2, n = 8
log_2(550) = 1*8 + 1 = 9
For some Radix/base combination things can be put to work real smoothly.
BTW. it seems possible to calculate b_r and n at compile time.
Another good thing to check is probably b > x in this case we can just return 0.
For other cases (and for the single digit, above) we pick a rather lame algorithm:
int log(int b, int x)
{
int r = 0; for (int y = 1; y < x; y *= b, ++r);
return r;
}
Now the question is: "Can we estimate a value less than the result so we can let (r,y) start at (r_0,pow(b,r_0))?"
It might work to use the least base logarithm we have a special case for (called log_b_r, above  that would be log_Radix, worst case) to do the estimation. Basically the log_a(x) = log_b(x) / log_b(a) sort of thing, while we have to make sure we never overestimate the result.
<snip>
[ ... Spirit code ... ]
>>But it might be faster to just handcode the whole thing (in particular to
>>avoid copying), I figure.
>
>
> One key point of my type is that it specifies the radix at compiletime, to
> take full advantage of that, I/O is always done in that radix. This code
> here seems to be fixed at radix8/10/16, probably using the appropriate I/O
> flags.
It's just a number parser (it matches strings such as "42", "0xcafe" or "077"). It should work with any radix for the destination, but there will be a conversion, of course. Since you mentioned Serialization, I figured that the only IO left would be initialization from human readable form...
Regards,
Tobias
template<typename Derived>
struct base
{
void caller
{
static_cast<Derived*>(this)>compile_time_polymorphic();
}
void compile_time_polymorphic()
{
// default implementation
}
}
struct derived : base<derived>
{
void compile_time_polymorphic()
{
// override
}
}
#include <iostream>
template<class Derived>
struct crtp_base
{
Derived & derived()
{ return *static_cast<Derived*>(this); }
Derived const & derived() const
{ return *static_cast<Derived const *>(this); }
};
class concrete_class
: public crtp_base<concrete_class>
{
int val_state;
public:
concrete_class(int v)
: val_state(v)
{ }
int get_state() const
{ return val_state; }
};
template<class Derived>
void func(crtp_base<Derived> const & arg)
{
std::cout << "value == " << arg.derived().get_state() << std::endl;
}
int main()
{
func( concrete_class(42) );
return 0;
};
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk