constexpr overloading

Question

Related: Function returning constexpr does not compile

I feel like constexpr is limited in usefulness in C++11 because of the inability to define two functions that would otherwise have the same signature, but have one be constexpr and the other not constexpr. In other words, it would be very helpful if I could have, for example, a constexpr std::string constructor that takes constexpr arguments only, and a non-constexpr std::string constructor for non-constexpr arguments. Another example would be a theoretically complicated function that could be made more efficient by using state. You can't easily do that with a constexpr function, so you are left with two choices: have a constexpr function that is very slow if you pass in non-constexpr arguments, or give up on constexpr entirely (or write two separate functions, but you may not know which version to call).

My question, therefore, is this:

Is it possible for a standard-compliant C++11 implementation to allow function overloading based on the arguments being constexpr, or would this require updating the standard? If it is not allowed, was it intentionally not allowed?

---

@NicolBolas: Say I have a function that maps an enum to a std::string. The most straight-forward way to do this, assuming my enum goes from 0 to n - 1, is to create an array of size n filled with the result.

I could create a static constexpr char const * [] and construct a std::string on return (paying the cost of creating a std::string object every time I call the function), or I can create a static std::string const [] and return the value I look up, paying the cost of all of the std::string constructors the first time I call the function. It seems like a better solution would be to create the std::string in memory at compile time (similar to what is done now with char const *), but the only way to do this would be to alert the constructor that it has constexpr arguments.

For a an example other than a std::string constructor, I think it's pretty straight-forward to find an example where, if you could ignore the requirements of constexpr (and thus create a non-constexpr function), you could create a more efficient function. Consider this thread: constexpr question, why do these two different programs run in such a different amount of time with g++?

If I call fib with a constexpr argument, I can't beat do better than the compiler optimizing away the function call entirely. But if I call fib with a non-constexpr argument, I may want to have it call my own version that implements things like memoization (which would require state) so I get run time similar to what would have been my compile time had I passed a constexpr argument.