Constant time 'cons'_问答_开发者_运维开发者技术经验分享

Is there any way (for example, modifying argument types) to make the following 'cons' function take constant time not O(n) time. i.e. building the list should take O(n) time, not O(n^2) time.

Can I do so under the following conditions:

(1) No dynamic memory allocation

(2) x must still remain valid (i开发者_如何学编程.e. may not have references to temporaries)

(3) Type HEAD may have a constructors which are separately compiled (not inlinable)

#include <type_traits>

template <typename HEAD, typename TAIL>
struct List
{
  List(HEAD head, TAIL tail) : head(head), tail(tail) {}
  typename std::remove_reference<HEAD>::type head;
  typename std::remove_reference<TAIL>::type tail;
};

template <typename HEAD, typename TAIL>
List<HEAD, TAIL> cons(HEAD head, TAIL tail)
{
  return List<HEAD, TAIL>(head, tail);
}

struct Empty {};

int main()
{
  auto x = cons(1, cons(2, cons(3, Empty())));
  // x should still be valid here
}

Example of how can work.

Compiler knows the type of x, so allocates space on the stack.

So the stack looks like this:

| Int1 | Int2 | Int3 |
| p    | p+4  | p+8  |

Where p is an arbitrary address.

Compiler creates call cons(2, cons(3, Empty())), directing the return value to p+4.

Inside cons(2, cons(3, Empty())), compiler creates call to cons(3, Empty()) directing return value to p+8.

This way, each time cons is called, tail does not need to be copied.

I'm just not sure code so the compiler can (as in, is allowed) to do this optimization. If there is another way of getting constant run time though, I'd be happy to use that.

You seem to be reinventing std::tuple with a worse std::make_tuple helper. Use that instead. The Standard doesn't make complexity guarantees either for the forwarding constructor of std::tuple or for std::make_tuple but it's kinda moot because those two uses perfect forwarding, so exactly one move/copy/emplace construction per element is made for a call to std::make_tuple; the rest is shuffling references around. It's a linear number of constructions at least.

Of course it's not guaranteed that your compiler will gracefully deal with all the reference shuffling, but you're optimizing at the wrong level anyway.

For illustration purposes, almost but not quite what happens:

template<typename... T>
class tuple {
    T... members; // this is not correct, only here for illustration

    // The forwarding constructor
    template<typename... U>
    explicit
    tuple(U&&... u)
        : member(std::forward<U>(u)...)
    {}
};

template<typename... T>
tuple<typename std::decay<T>::type...>
make_tuple(T&&... t)
{ return tuple<typename std::decay<T>::type...>(std::forward<T>(t)...); }

Thus in a call to auto tuple = std::make_tuple(1, 2, 3), there are three temporary ints from the call to make_tuple, then three int&& xvalues from the first calls to std::forward<int>(t)... inside make_tuple which bind to the arguments of the constructors which are forwarded again as int&& xvalues to the conceptual three members of std::tuple<int, int, int> which are move constructed from them.

Just realized that what I said about the number of constructions only applies the call to std::make_tuple, not the whole expression auto tuple = std::make_tuple(...);. Since the tuple is returned from the function it may require a move/RVO to the final variable. It's still linear and it's still one of the thing compilers like to optimize and it's still the wrong spot to worry about optimization.

However, C++0x is so filled with goodness that it can already do what you describe in your answer:

int i = 3;
std::tuple<int, int, int> tuple = std::forward_as_tuple(1, 2, i);

The call to forward_as_tuple will return a std::tuple<int&&, int&&, int&>. This helper never returns a tuple with values, only a 'shallow' tuple of references. The appropriate converting constructor of std::tuple<int, int, int> will then initialize its 'members' with two moves and a copy. Note that this silly (un)optimization puts you at risk to write auto tuple = std::forward_as_tuple(1, 2, i); which is a tuple with two dangling references.

I'm going to give an answer to my own question after my investigations, but I'd still be interested if anyone knows a better way.

(1) Rename List to TempList.
(2) Make the constructors (including move and copy) of TempList private.
(3) Make cons a friend of TempList.
(4) Make HEAD and TAIL members into references.

Now TempList only holds references, so there are no copies. These may be references to temporaries however, but that's ok because temporaries last til the end of the expression, and because TempList only has private constructors, it can't be assigned to the LHS of an expression. Only cons can create a TempList, and can't outlive the expression it is created in.

Now create a function save or something of that effect that takes a TempList and returns a real List, another type that has it's data stored by value.

So we have

auto x = save(cons(1, cons(2, cons(3, Empty()))));

And data will be copied or moved at most once (by save), the whole construct now being O(n). The TempList structure will probably be optimised away, as long as both cons and save are inlined.

Constant time 'cons'

精彩评论

关注公众号

热门标签

图文推荐

Constant time 'cons'

更多 问答 相关资讯：

精彩评论

关注公众号

热门标签

图文推荐

更多问答相关资讯：