RE: [boost] Submission: typelist

From: Aleksey Gurtovoy (alexy_at_[hidden])
Date: 2001-12-17 17:55:22

Peter Dimov wrote:
> One problem with the "functional" push_back is that 
> programmers will be mislead by the analogy with the STL, 
> where push_back is more frequently supported than 
> push_front. In our case push_front is a primitive:
> 
> (let's assume that the pair data structure A.B is called pair<A, B>)
> 
> template<class List, class Value> struct push_front
> {
>     typedef pair<Value, List> type;
> };
> 
> while push_back is (much) more taxing 

For this particular data structure. There are other compile-time containers
for which 'push_pack<C,T>' is O(1).

> (since it's effectively a form of append):
> 
> template<class List, class Value> struct push_back;
> 
> template<class F, class R, class V> struct push_back<pair<F, R>, V>
> {
>     typedef pair<F, typename push_back<R, V>::type> type;
> };
> 
> template<class V> struct push_back<nil, V>
> {
>     typedef pair<V, nil> type; // append would have had 
> typedef V type;
> };
> 
> It's true that programmers would rarely need to write this 
> kind of code (especially if they have MPL at their disposal) but they 
> would still need to be able to understand what happens under the hood,

Why? If I write 'push_back<C,T>::type', and it works, and satisfies its
complexity specification (which IMO should be O(1)), I don't care how it's
implemented.

> and the false STL/meta analogy isn't going to help them. 
> push_back(L, V) is usually O(1) in STL, but O(|L|) in "meta."

Not necessarily. For one, mpl::push_back<mpl::type_vector<>, T>::type is
O(1).

Aleksey