4
\$\begingroup\$

This function represents an integral type and represents it in a base.

#include <type_traits>
#include <limits>
#include <array>
#include <iterator>

namespace detail {

template <class Integral>
char n_to_digit(Integral n) {
    static const char * digits = "0123456789abcdefghijklmnopqrstuvwxyz";
    return digits[n];
}

/// This implementation is called if Integral is unsigned
template <unsigned Base, class Integral, class OutputIterator>
std::size_t integral_to_base_impl(Integral n, OutputIterator dst_it, std::true_type) {
    /// Length of str is the minimum number of bits to store Integral which is
    /// the number of chars required to store the maximum value of in base 2
    /// representation
    std::array<char, (sizeof(Integral) << 3)> str;
    auto it = str.begin();

    do {
        *it++ = n_to_digit(n % Base);
        n /= Base;
    } while (n != 0);

    while (it != str.begin()) {
        *dst_it++ = *(--it);
    }

    return std::distance(str.begin(), it);
}

/// This implementation is called if Integral is signed
template <unsigned Base, class Integral, class OutputIterator>
std::size_t integral_to_base_impl(Integral n, OutputIterator dst_it, std::false_type) {
    std::size_t length = 0;

    if (n < 0) {
        *dst_it++ = '-';
        ++length;
    }

    length += integral_to_base_impl<Base>(std::abs(n), dst_it, std::true_type());
    return length;
}

}

/// Represents an integral in a certain base
///
/// @tparam Base The base that the integral will be represented as
///
/// @param n The number that will be represented
/// @param dst_it A char OutputIterator that the representation will be written to
///
/// @return The length of the representation
template <unsigned Base, class Integral, class OutputIterator>
std::size_t integral_to_base(Integral n, OutputIterator dst_it) {
    static_assert(2 <= Base && Base <= 36, "Base must be >= 2 and <= 36");
    static_assert(std::is_integral<Integral>::value, "n must be an integral type");

    return detail::integral_to_base_impl<Base>(n, dst_it,
        std::integral_constant<bool, std::is_unsigned<Integral>::value>());
}

My implementation is like the C's non standard function itoa however it takes the base is taken as a template parameter which allow the compiler to make optimizations with operations involving the base such as modulo and divide however it must be known at compile time. This allows integrals to represented as binary and hexadecimal with the Base template parameter being 2 and 16 respectively.

The function integral_to_base has implementation specializiations for unsigned and signed integral types and has static assertions to check that the base is valid at compile time for safety.

Example usage:

int main() {
    std::string test;

    integral_to_base<10>(123343, std::back_inserter(test));
    std::cout << test << std::endl; //prints 123343
}
\$\endgroup\$
  • \$\begingroup\$ @Incomputable How is this a bug? \$\endgroup\$ – nectar_moon Aug 13 '17 at 17:26
  • \$\begingroup\$ @Incomputable The lower bound of the constraint is 2 because wouldn't make sense to represent integrals in base 0 or 1. The higher bound of the constraint is 36 because there is 10 digits and 26 letters. Why 48? \$\endgroup\$ – nectar_moon Aug 13 '17 at 17:34
  • \$\begingroup\$ @Incomputable I get it now. Thanks c: I forgot C++ doesn't have syntax like "2 <= Base <= 36". It should be "2 <= Base && Base <= 36". I updated my code. \$\endgroup\$ – nectar_moon Aug 13 '17 at 17:45
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Vogel612 Aug 14 '17 at 7:58
  • \$\begingroup\$ @Vogel612 I apologize, I will self answer like the linked meta post suggested \$\endgroup\$ – nectar_moon Aug 14 '17 at 9:02
3
\$\begingroup\$

n_to_digit doesn't really need to be a template, since its argument n can only ever be in the range 0 to 35. I'd just make it

char n_to_digit(int n) {
    static const char digits[] = "0123456789abcdefghijklmnopqrstuvwxyz";
    return digits[n];
}

Notice also the replacement of *digits with digits[]; the optimizer will likely generate the same code either way, but without the optimizer's help, making digits the name of the array itself instead of the name of a pointer to the array will remove one level of pointer dereferencing.


YMMV, but I would find

std::array<char, (sizeof(Integral) << 3)> str;

easier to read if it were just

char str[sizeof(Integral) * 8];

Of course then you'd have to use std::begin(str) instead of str.begin(). But you could make up for it by using it - str instead of std::distance(str.begin(), it).

Actually, hang on —

while (it != str.begin()) {
    *dst_it++ = *(--it);
}

return std::distance(str.begin(), it);

The loop never exits unless it == str.begin(), which means std::distance(str.begin(), it) == 0 by definition! This is certainly a bug.


Since you're trying to make this fully generic: note that *dst_it++ is going to be inefficient for a lot of iterator types. If you were writing this for a popular library, you'd write

*dst_it = '-';
++dst_it;

If you consistently avoid postfix operators, your users might even thank you, because your code will work even with their incompletely belled-and-whistled iterator types.


In the signed version, your use of std::abs(n) is a red flag. abs is never appropriate in generic code. For one thing, if Integral n is some clever fixed-point type, std::abs(n) won't compile; what you meant is more like

using std::abs;
... abs(n) ...

to pick up the correct abs through ADL. (But this opens the whole customization-point can of worms, which is still a mess even in C++17.)

No, the real reason abs is a red flag is because std::abs(-1 - 2147483647) invokes undefined behavior (source). You should never call abs on untrusted input.

The usual hack in this domain is to say

if (n < 0) {
    *dst_it = '-'; ++dst_it;
} else {
    n = -n;
}

and then print the negative of n.


std::integral_constant<bool, std::is_unsigned<Integral>::value>()

could conceivably be written

typename std::is_unsigned<Integral>::type{}

but honestly, only the most evil and sadistic library implementation in the universe would make is_unsigned not derived from boolean_constant already. So you can just write

std::is_unsigned<Integral>{}

and be assured that your tag-dispatch code will work at least as well as your neighbor's. :)

\$\endgroup\$
  • \$\begingroup\$ Thanks I considered these and will edit my question with my new code c: \$\endgroup\$ – nectar_moon Aug 14 '17 at 7:46
  • \$\begingroup\$ Can n_to_digit() be declared with constexpr (and is there any benefit to doing so?) \$\endgroup\$ – Toby Speight Aug 14 '17 at 8:45
  • \$\begingroup\$ @TobySpeight It can't be constexpr because the parameter to n_to_digit(int n)would have to be known at compile time. \$\endgroup\$ – nectar_moon Aug 14 '17 at 9:00
  • 1
    \$\begingroup\$ @nectar - that doesn't stop it being constexpr; just that there's no benefit to doing so in that context (meaning "yes, no" to my question). \$\endgroup\$ – Toby Speight Aug 14 '17 at 12:11
  • \$\begingroup\$ @TobySpeight Sorry I didn't phrase it too well. More like "There's no benefit to it being constexpr because the parameter to n_to_digit(int n)would have to be known at compile time." \$\endgroup\$ – nectar_moon Aug 14 '17 at 12:34
2
\$\begingroup\$

This calculation looks suspect:

    std::array<char, (sizeof(Integral) << 3)> str;

The left-shift of 3 seems to assume that CHAR_BIT is 8. Instead of making that assumption, prefer to take the safer choice:

    std::array<char, CHAR_BIT * sizeof n)> buf;

(I replaced (Integral) by n both to save typing and to make the relationship between clearer between the input and the buffer type; also I didn't like the name str for something that's not a string).

This is of course an absolute worst-case (for binary output). For hexadecimal output, this is already four times overspecified. Luckily, we know that each output digit consumes log₂(N) bits; so with some rounding, we can allocate more efficiently:

    std::array<char, size_t(std::ceil(CHAR_BIT * sizeof n / std::log2(Base)))> buf;
\$\endgroup\$
  • \$\begingroup\$ I'm aware str only needs to be std::ceil(std::log2(sizeof(Integral)) / std::log2(Base)) chars long to store the maximum possible value of Integral however this needs to be calculated at compile time and std::ceil and std::log2 aren't defined as constexpr. \$\endgroup\$ – nectar_moon Aug 14 '17 at 12:44
  • \$\begingroup\$ Ah yes, I forgot they'd need to be constexpr. It is of course possible to write something to do the calculation at compile-time, but you might not consider it worth doing so. \$\endgroup\$ – Toby Speight Aug 14 '17 at 14:00
0
\$\begingroup\$

Using the Quuxpostone's suggestions I updated my code to this:

namespace detail {

/// This implementation is called if Integral is unsigned
template <unsigned Base, class Integral, class OutputIterator>
std::size_t integral_to_base_impl(Integral n, OutputIterator dst_it, std::true_type) {
    static const char digits[] = "0123456789abcdefghijklmnopqrstuvwxyz";

    /// Length of str is the minimum number of bits to store Integral which is
    /// the number of chars required to store the maximum value of Integral in base 2 representation
    char str[sizeof(Integral) * 8];
    char * ptr = str;

    do {
        *ptr++ = digits[n % Base];
        n /= Base;
    } while (n != 0);

    std::size_t length = ptr - str;

    while (ptr != str) {
        *dst_it = *(--ptr); ++dst_it;
    }

    return length;
}

/// This implementation is called if Integral is signed
template <unsigned Base, class Integral, class OutputIterator>
std::size_t integral_to_base_impl(Integral n, OutputIterator dst_it, std::false_type) {
    std::size_t length = 0;

    if (n < 0) {
        *dst_it = '-'; ++dst_it;
        n = -n;
        ++length;
    }

    length += integral_to_base_impl<Base>(n, dst_it, std::true_type());

    return length;
}

}

/// Represents an integral in a certain base
///
/// @tparam Base The base that the integral will be represented as
///
/// @param n The number that will be represented
/// @param dst_it A char OutputIterator that the representation will be written to
///
/// @return The length of the representation
template <unsigned Base, class Integral, class OutputIterator>
std::size_t integral_to_base(Integral n, OutputIterator dst_it) {
    static_assert(2 <= Base && Base <= 36, "Base must be >= 2 and <= 36");
    static_assert(std::is_integral<Integral>::value, "n must be an integral type");

    return detail::integral_to_base_impl<Base>(n, dst_it,
        typename std::is_unsigned<Integral>::type());
}

I fixed the bug where the unsigned specialization of detail::integral_to_base_impl would always return 0 instead of the length of the unsigned representation as well using char pointers instead of iterators when operating with str array as they were unnecessary.

I also made removed detail::n_to_digit as it was unnecessary.

\$\endgroup\$
  • 1
    \$\begingroup\$ The line n = -n; still has undefined behavior when n is INT_MIN. You could probably hack it by starting the function with using UIntegral = std::make_unsigned_t<Integral>; and then doing all the subsequent computations (other than n < 0 of course) with UIntegral new_n = -UIntegral(n). \$\endgroup\$ – Quuxplusone Aug 14 '17 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.