fork(4) download
copy 
  1. #include <iterator>
  2.  
  3. namespace detail
  4. {
  5.     template< typename T >
  6.     class basic_range
  7.     {
  8.     private:
  9.         static T align_to_step(T const first, T const last, T const step)
  10.         {
  11.             using UT = typename std::make_unsigned<T>::type;
  12.             UT const difference = std::abs(last - first);
  13.             UT const stepping   = std::abs(step);
  14.  
  15.             T const underflow = T(difference % stepping) * (step / T(stepping));
  16.             if (underflow == 0) return last;
  17.  
  18.             return last + (step - underflow);
  19.         }
  20.     public:
  21.         explicit basic_range(T const last, int const step = 1)
  22.             : basic_range(T{ 0 }, last, step)
  23.         {}
  24.  
  25.         explicit basic_range(T const first, T const last, int const step = 1)
  26.             : first{ first, step }, last{ align_to_step(first, last, step), step }
  27.         {}
  28.  
  29.         basic_range(basic_range const& other) = delete;
  30.         basic_range(basic_range && other) = default;
  31.         basic_range operator=(basic_range const& other) = delete;
  32.         basic_range operator=(basic_range && other) = delete;
  33.  
  34.     public:
  35.         struct iterator : std::iterator< std::forward_iterator_tag, T >
  36.         {
  37.         private:
  38.             explicit iterator(T const from, int const step = T{ 1 })
  39.                 : from{ from }, step{ step }
  40.             {}
  41.  
  42.             friend class basic_range< T >;
  43.         public:
  44.             iterator(iterator const& other) = default;
  45.             iterator(iterator && other) = delete;
  46.             iterator operator=(iterator const& other) = delete;
  47.             iterator operator=(iterator && other) = delete;
  48.  
  49.             T const operator*() const { return from; }
  50.  
  51.             bool operator==(iterator const& other) const { return from == other.from; }
  52.             bool operator!=(iterator const& other) const { return from != other.from; }
  53.  
  54.             void operator++() { from += step; }
  55.  
  56.         private:
  57.             T         from;
  58.             T const step;
  59.         };
  60.  
  61.         typedef iterator       iterator;
  62.         typedef iterator const const_iterator;
  63.  
  64.         const_iterator begin() const { return first; }
  65.         const_iterator end()   const { return last; }
  66.  
  67.     private:
  68.         const_iterator first;
  69.         const_iterator last;
  70.     };
  71.  
  72.     template< typename T, bool is_enum = std::is_enum< T >::value >
  73.     struct get_integral_type
  74.     {
  75.         typedef std::underlying_type_t< T > type;
  76.     };
  77.  
  78.     template< typename T >
  79.     struct get_integral_type< T, false >
  80.     {
  81.         typedef T type;
  82.     };
  83.  
  84.     template< typename T, bool is_enum = std::is_enum< T >::value >
  85.     using get_integral_type_t = typename get_integral_type< T >::type;
  86. }
  87.  
  88. template< typename T >
  89. auto range(T const begin, T const end, int const step = 1)
  90. {
  91.     typedef detail::get_integral_type_t< T > type;
  92.  
  93.     static_assert(std::is_integral< type >::value,
  94.                   "Only integer-based types allowed!");
  95.  
  96.     return detail::basic_range< type >{
  97.         static_cast<type>(begin),
  98.         static_cast<type>(end),
  99.         step
  100.     };
  101. }
  102.  
  103. template< typename T, typename U >
  104. auto range(T const begin, U const end, int const step = 1)
  105. {
  106.     typedef std::common_type_t
  107.     <
  108.         detail::get_integral_type_t< T >,
  109.         detail::get_integral_type_t< U >
  110.     > type;
  111.  
  112.     static_assert(std::is_integral< type >::value,
  113.                   "Only integer-based types allowed!");
  114.  
  115.     return detail::basic_range< type >{
  116.         static_cast<type>(begin),
  117.         static_cast<type>(end),
  118.         step
  119.     };
  120. }
  121.  
  122. template< typename T >
  123. auto reverse_range(T const from, T const to, int const step = -1)
  124. {
  125.     return range(from, to, step);
  126. }
  127.  
  128. template< typename T, typename U >
  129. auto reverse_range(T const from, U const to, int const step = -1)
  130. {
  131.     return range(from, to, step);
  132. }
  133.  
  134. /**************************************************
  135.  * Unit testing framework
  136.  *************************************************/
  137. #include <string>
  138. #include <functional>
  139. #include <iostream>
  140. #include <exception>
  141.  
  142. namespace test
  143. {
  144.     struct test_spec
  145.     {
  146.         std::string const name;
  147.         std::function< void() > const function;
  148.     };
  149.  
  150.     struct failure : std::runtime_error
  151.     {
  152.         failure(std::string const& message)
  153.             : std::runtime_error{ message }
  154.         {}
  155.     };
  156.  
  157.     bool expect(bool expression, std::string && message)
  158.     {
  159.         if (!expression)
  160.         {
  161.             throw failure(message);
  162.         }
  163.         return true;
  164.     }
  165.  
  166.     bool expect(std::function< bool() > const function, std::string && message)
  167.     {
  168.         if (!function())
  169.         {
  170.             throw failure(message);
  171.         }
  172.         return true;
  173.     }
  174.  
  175.     template< std::size_t N >
  176.     bool run_tests(test_spec const (&specification)[N], std::ostream & os = std::cout)
  177.     {
  178.         unsigned int failures = 0;
  179.  
  180.         for (auto const& test : specification)
  181.         {
  182.             try
  183.             {
  184.                 os << test.name;
  185.                 test.function();
  186.                 os << " - PASS\n";
  187.             }
  188.             catch (failure const& f)
  189.             {
  190.                 os << " - FAIL: " << f.what() << "\n";
  191.                 ++failures;
  192.             }
  193.         }
  194.  
  195.         if (failures > 0)
  196.         {
  197.             os << "\n" << failures << " out of " << N << (failures == 1 ? " test" : " tests") << " failed\n";
  198.         }
  199.  
  200.         return failures == 0 ? true : false;
  201.     }
  202. }
  203.  
  204. /**************************************************
  205.  * Implement test cases here
  206.  *************************************************/
  207. #include <algorithm>
  208. template< typename Container1, typename Container2 >
  209. auto equal(Container1 const container1, Container2 const container2)
  210. {
  211.     return std::equal(std::cbegin(container1), std::cend(container1),
  212.                       std::cbegin(container2), std::cend(container2));
  213. }
  214.  
  215. test::test_spec tests[] =
  216. {
  217.     "Range_TestForwardRange", []
  218.     {
  219.         auto expected = { 0, 1, 2, 3, 4 };
  220.         std::vector< int > result;
  221.         for (auto const i : range(0, 5))
  222.         {
  223.             result.emplace_back(i);
  224.         }
  225.         test::expect(equal(result, expected) == true,
  226.                      "Generated range does not match expected result!");
  227.     },
  228.     "Range_TestForwardRangeStep", []
  229.     {
  230.         auto expected = { 0, 2, 4, 6, 8 };
  231.         std::vector< int > result;
  232.         for (auto const i : range(0, 10, 2))
  233.         {
  234.             result.emplace_back(i);
  235.         }
  236.         test::expect(equal(result, expected) == true,
  237.                      "Generated range does not match expected result!");
  238.     },
  239.     "Range_TestReverseRange", []
  240.     {
  241.         auto expected = { 5, 4, 3, 2, 1 };
  242.         std::vector< int > result;
  243.         for (auto const i : reverse_range(5, 0))
  244.         {
  245.             result.emplace_back(i);
  246.         }
  247.         test::expect(equal(result, expected) == true,
  248.                      "Generated range does not match expected result!");
  249.     },
  250.     "Range_TestReverseRangeStep", []
  251.     {
  252.         auto expected = { 10, 8, 6, 4, 2 };
  253.         std::vector< int > result;
  254.         for (auto const i : reverse_range(10, 0, -2))
  255.         {
  256.             result.emplace_back(i);
  257.         }
  258.         test::expect(equal(result, expected) == true,
  259.                      "Generated range does not match expected result!");
  260.     },
  261.     "Range_TestGetIntegralType", []
  262.     {
  263.         bool is_same = std::is_same< int, detail::get_integral_type_t< int > >::value;
  264.         test::expect(is_same == true, "Types not identical for int case");
  265.  
  266.         enum class SomeType : unsigned int { };
  267.         is_same = std::is_same< unsigned int, detail::get_integral_type_t< SomeType > >::value;
  268.         test::expect(is_same == true, "Could not convert enum to underlying type");
  269.     }
  270. };
  271.  
  272. #include <vector>
  273. #include <chrono>
  274.  
  275. int main(int argc, char* argv[])
  276. {
  277.     if(test::run_tests(tests))
  278.     {
  279.         constexpr auto num_elements = 1000000;
  280.         {
  281.             std::vector< int > range_vector(num_elements);
  282.             auto start = std::chrono::high_resolution_clock::now();
  283.             for(auto const i: range(0, num_elements))
  284.             {
  285.                 range_vector[i] = i;
  286.             }
  287.             auto end = std::chrono::high_resolution_clock::now();
  288.             std::chrono::duration< double > diff = end - start;
  289.             std::cout << "Range for loop: " << diff.count() << "s\n";
  290.         }
  291.         {
  292.             std::vector< int > for_vector(num_elements);
  293.             auto start = std::chrono::high_resolution_clock::now();
  294.             for(int i = 0; i < num_elements; i++)
  295.             {
  296.                 for_vector[i] = i;
  297.             }
  298.             auto end = std::chrono::high_resolution_clock::now();
  299.             std::chrono::duration< double > diff = end - start;
  300.             std::cout << "Standard for loop: " << diff.count() << "s\n";
  301.         }
  302.     }
  303.     return 0;
  304. }
  305.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Range_TestForwardRange - PASS
Range_TestForwardRangeStep - PASS
Range_TestReverseRange - PASS
Range_TestReverseRangeStep - PASS
Range_TestGetIntegralType - PASS
Range for loop: 0.00165256s
Standard for loop: 0.00165403s
https://ideone.com/A8fv3P
numeric range iteration
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!