This question led me to create a small "STLish" container for digits... More for fun than for real life usage. But nevertheless, here it is:
#ifndef __DIGITS_H__
# define __DIGITS_H__
# include <type_traits>
# include <cmath>
# include <cassert>
# include <iterator>
# include <sstream>
# include <algorithm>
namespace digits
{
// Default base type traits, infer base size from the number of character
template <char... Chars>
struct base_char_traits
{
// Mandatory for the digits container, maybe someone want to make
// another traits with wchar ?
typedef char value_type;
// Size of the base, computed from the number of characters passed
static constexpr size_t size = sizeof...(Chars);
// Array of characters use to print the output
static constexpr value_type characters[sizeof...(Chars)] = { Chars... };
};
// **sigh**
// Instantiation of the array of character; otherwise there will be a link
// error
template <char... Chars>
constexpr typename base_char_traits<Chars...>::value_type base_char_traits<Chars...>::characters[sizeof...(Chars)];
// All your bases are belong to us !
struct base2_traits : public base_char_traits<'0', '1'> { };
struct base8_traits : public base_char_traits<'0', '1', '2', '3', '4', '5', '6', '7'> { };
struct base10_traits : public base_char_traits<'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'> { };
struct base12_traits : public base_char_traits<'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b'> { };
struct base16_traits : public base_char_traits<'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'> { };
// The digit container with the base traits and the type as template
// parameter.
//
// It is a read only container that allows you to iterate on the digit in
// the base given as template parameter.
template <typename BaseTraits, typename T = unsigned long>
class digits
{
public:
// Assert that T fullfil our criteria
static_assert(std::is_integral<T>(), "T must be integral");
static_assert(std::is_unsigned<T>(), "T must be unsigned");
// Value type is defined by the base traits to allow the use of more
// complicated digit type (here we only handle char)
typedef typename BaseTraits::value_type value_type;
// Reference type is defined to be the same as value type because this is an immutable container
typedef typename BaseTraits::value_type reference;
// The size type of the container, i.e. the type that will be used to
// express a digit position
typedef size_t size_type;
// Iterator class allowing one to walk through the number's digit from
// the lowest to the highest
class iterator
{
public:
// Type used to return iterator substraction result
typedef size_t difference_type;
// type used by algorithms (e.g. find)
typedef typename digits::reference reference;
// type used by algorithms (e.g. find)
typedef typename digits::reference pointer;
// type returned by operator*
typedef typename digits::value_type value_type;
// Iterator category, here we can randomly walk in the digit
typedef std::random_access_iterator_tag iterator_category;
// Mandatory default constructor, initialize to an invalid iterator
iterator()
{
_current_digit = 0;
_digits = nullptr;
}
// Build an iterator other a digits container starting at digit
iterator(const digits* digits, size_type digit)
{
_current_digit = digit;
_digits = digits;
}
iterator(const iterator& it) :
iterator(it._digits, it._current_digit)
{
}
// Move using swap idiom
iterator(iterator&& it) :
iterator()
{
swap(*this, it);
}
~iterator()
{
_digits = nullptr;
}
// assignment iterator using swap idiom
iterator& operator=(iterator it)
{
swap(*this, it);
return *this;
}
// Comparison operators
bool operator==(const iterator& it) const
{
assert(_digits == it._digits);
return (_current_digit == it._current_digit);
}
bool operator!=(const iterator& it) const
{
return !(operator==(it));
}
bool operator<(const iterator& it) const
{
assert(_digits == it._digits);
return (_current_digit < it._current_digit);
}
bool operator>(const iterator& it) const
{
assert(_digits == it._digits);
return (_current_digit > it._current_digit);
}
bool operator<=(const iterator& it) const
{
assert(_digits == it._digits);
return (_current_digit <= it._current_digit);
}
bool operator>=(const iterator& it) const
{
assert(_digits == it._digits);
return (_current_digit >= it._current_digit);
}
// Moving the iterator
iterator& operator++()
{
++_current_digit;
return *this;
}
iterator operator++(int)
{
iterator it(*this);
operator++();
return it;
}
iterator& operator--()
{
--_current_digit;
return *this;
}
iterator operator--(int)
{
iterator it(*this);
operator--();
return it;
}
iterator& operator+=(size_type increment)
{
_current_digit += increment;
return *this;
}
iterator operator+(size_type increment) const
{
iterator it(*this);
return (it += increment);
}
friend iterator operator+(size_type increment, const iterator& it)
{
return (it + increment);
}
iterator& operator-=(size_type decrement)
{
_current_digit -= decrement;
return *this;
}
iterator operator-(size_type decrement) const
{
iterator it(*this);
return (it - decrement);
}
difference_type operator-(const iterator& it) const
{
assert(_digits == it._digits);
return (_current_digit - it._current_digit);
}
value_type operator*() const
{
assert(nullptr != _digits);
return _digits->digit(_current_digit);
}
friend void swap(iterator& first, iterator& second)
{
std::swap(first._digits, second._digits);
std::swap(first._current_digit, second._current_digit);
}
private:
// The current digit we will be printing when calling operator*().
// From 0 to (digits.size() - 1)
size_t _current_digit;
// The digit container we're working on.
const digits* _digits;
};
// Define the reverse iterator, that will allow to iterator from the
// highest digit to the lowest (more printing friendly)
typedef std::reverse_iterator<iterator> reverse_iterator;
// Default constructor use 0 as a number
digits()
{
_number = 0;
}
// Build a container over a number given as parameter
digits(T number)
{
_number = number;
}
digits(const digits& copy) :
digits(copy._number)
{
}
// Move constructor using swap idiom
digits(digits&& move) :
digits()
{
swap(*this, move);
}
~digits()
{
}
// Retrieve the digit character
value_type digit(size_t digit) const
{
assert(digit < size());
constexpr size_t base = BaseTraits::size;
// @warning
// llround is mandatory because of a double to unsigned long problem
T modul = static_cast<T>(llround(std::pow(base, digit + 1)));
T div = static_cast<T>(llround(std::pow(base, digit)));
T digit_index = (_number % modul) / div;
return BaseTraits::characters[digit_index];
}
// Assignment using swap idiom
digits& operator=(digits assign)
{
swap(_number, assign._number);
}
// Comparison operator
bool operator==(const digits& comp) const
{
return (_number == comp._number);
}
bool operator!=(const digits& comp) const
{
return !(operator==(comp));
}
// Iterators creation
iterator begin() const
{
return iterator(this, static_cast<size_type>(0));
}
iterator cbegin() const
{
return begin();
}
iterator end() const
{
return iterator(this, size());
}
iterator cend() const
{
return end();
}
reverse_iterator rbegin() const
{
return reverse_iterator(end());
}
reverse_iterator crbegin() const
{
return reverse_iterator(cend());
}
reverse_iterator rend() const
{
return reverse_iterator(begin());
}
reverse_iterator crend() const
{
return reverse_iterator(cbegin());
}
// swap function
friend void swap(digits& first, digits& second)
{
std::swap(first._number, second._number);
}
// cast to string
operator std::string () const
{
std::ostringstream stream;
// print from high to low
std::copy(rbegin(), rend(),
std::ostream_iterator<value_type>(stream, ""));
return stream.str();
}
// The number of digits of this _number
size_type size() const
{
const double log_number = std::log(_number);
constexpr double log_base = std::log(BaseTraits::size);
return std::ceil(log_number / log_base);
}
// The maximum nulber of digits this type can have
size_type max_size() const
{
constexpr double max_number = std::pow(2, sizeof(T) * 8);
constexpr double log_max_number = std::log(max_number);
constexpr double log_base = std::log(BaseTraits::size);
return log_max_number / log_base;
}
private:
// The number we will iterate over the digits
T _number;
};
}
#endif // __DIGITS_H__
Basic usage would be something like:
digits::digits<digits::base10_traits> dig(123456);
for (auto digit: dig)
{
std::cout << "Digit: " << digit << std::endl;
}
I think that most of the STD algorithm on immutable container (for_each, find, copy, etc.) will work with that container.
A small test here (header + test in the same file): http://ideone.com/BoMX5Q
Ok, it's pretty useless, but it was really fun to do. :)
https://stackoverflow.com/questions/20614707
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian