I propose we put the [[deprecated("Please use the move constructor instead")]] tag on this constructor which would help both performance and help avoid the segfault.

template <class U>
   polynomial(const U* data, unsigned order)
      : m_data(data, data + order + 1)
   {
       normalize();
   }

The target constructor does not seem so intuitive. The interface only makes sense when I open the source and see that order of the polynomial is requested here. If I somehow knew that the second parameter is order, then using

polynomial<double> p(coeffs.data(), coeffs.size() - 1)

is quite natural for the consumer/caller of this constructor IMHO.

What I would consider idiomatic(for better of a better wording, read "programmers are used to it") is to pass a raw pointer and a corresponding length. In that case,

template <class U>
 polynomial(const U* data, unsigned offset)
    : m_data(data, data + offset)
 {
     normalize();
 }

seem to be making more sense for the general public but nonetheless as error-prone as the other approach.

Agreed; I think it's not idiomatic.

Adding the deprecation would move this to C++-14 compatibility only though; I don't think it's possible to change the current behavior.

@jzmaddock : Would a C++-11 break to recommend the move constructor be ok for this one?

The interface only makes sense when I open the source and see that order of the polynomial is requested here. If I somehow knew that the second parameter is order, then using polynomial<double> p(coeffs.data(), coeffs.size() - 1) is quite natural for the consumer/caller of this constructor IMHO.

Well... that parameter is clearly labelled as "order" in the docs, though I confess the class is otherwise rather under-documented :(

Adding the deprecation would move this to C++-14 compatibility only though; I don't think it's possible to change the current behavior.

@jzmaddock : Would a C++-11 break to recommend the move constructor be ok for this one?

That function has always been that way, so I kind of hesitate to deprecate it.

However, adding a deprecate attribute when in C++14 would do not harm, even if it was just to emphasise the point that the second parameter is polynomial order not number of terms.

I agree with @NAThompson that it's not an intuitive interface, since a constructor for a container-esque class with that signature is a pretty widely established convention to mean (first, size).
I know it would be an API break to change the meaning of that constructor now... but I wonder... would you get more problems by breaking it or not breaking it? Yes, if we break it, existing users will be annoyed and have to change their code, but that's a finite, non-increasing number of people. On the other hand, there is an 'infinite' number of people that will start using it, and be surprised by this constructor, and potentially open bug reports like this one. :)
If we don't break it, we'll have to keep explaining it and warning people about it.
I'm ruthless, I would break it for the good of the future and warn the existing users, with a generous timeline of warning messages, etc.
But that's easy for me to say, I won't be the one receiving the hate mail for breaking it.