fork download
copy 
  1. #include <iostream> 
  2. #include <iterator> 
  3. #include <stdexcept> 
  4. #include <utility> 
  5. #include <vector> 
  6.  
  7. using namespace std::rel_ops; 
  8.  
  9. template<typename T> 
  10. class Fibonacci_Sequence 
  11. { 
  12.         static std::vector<T> mSequence; 
  13.  
  14. public: 
  15.  
  16.         typedef T value_type; 
  17.         typedef typename std::vector<T>::size_type size_type; 
  18.  
  19.         Fibonacci_Sequence(): 
  20.                 mBegin(0), 
  21.                 mEnd(0) 
  22.         { 
  23.                 if(mSequence.empty()) 
  24.                 { 
  25.                         mSequence.push_back(0); 
  26.  
  27.                         T before_last = 0, last = 1; 
  28.  
  29.                         while(last >= before_last) 
  30.                         { 
  31.                                 mSequence.push_back(last); 
  32.                                 last += before_last; 
  33.                                 before_last = last - before_last; 
  34.                         } 
  35.  
  36.                         mEnd.mN = mSequence.size(); 
  37.                 } 
  38.         } 
  39.  
  40.         class iterator : public std::iterator<std::random_access_iterator_tag, 
  41.                                               T, 
  42.                                               size_type, 
  43.                                               T*, 
  44.                                               T> 
  45.         { 
  46.                 friend class Fibonacci_Sequence; 
  47.  
  48.                 mutable size_type mN; 
  49.  
  50.                 iterator(size_type n): 
  51.                         mN(n) {} 
  52.  
  53.         public: 
  54.  
  55.                 iterator(iterator const& i): 
  56.                         mN(i.mN) {} 
  57.  
  58.                 T operator*() const 
  59.                 { 
  60.                         if(mN >= mSequence.size()) 
  61.                                 throw std::out_of_range("Fibonacci_Sequence::iterator::operator*() : Cannot dereference iterator! To high!"); 
  62.                         return mSequence[mN]; 
  63.                 } 
  64.  
  65.                 iterator operator++() const 
  66.                 { 
  67.                         return ++mN; 
  68.                 } 
  69.  
  70.                 iterator operator++(int) const 
  71.                 { 
  72.                         ++*this; 
  73.                         return mN - 1; 
  74.                 } 
  75.  
  76.                 iterator operator+(size_type a) const 
  77.                 { 
  78.                         return mN + a; 
  79.                 } 
  80.  
  81.                 iterator operator+=(size_type a) const 
  82.                 { 
  83.                         return mN += a; 
  84.                 } 
  85.  
  86.                 iterator operator--() const 
  87.                 { 
  88.                         if(!mN) 
  89.                                 throw std::out_of_range("Fibonacci_Sequence::iterator::operator--() : The lower end of the sequence was reached! Invalid decrement!"); 
  90.                         return --mN; 
  91.                 } 
  92.  
  93.                 iterator operator--(int) const 
  94.                 { 
  95.                         --*this; 
  96.                         return mN + 1; 
  97.                 } 
  98.  
  99.                 iterator operator-(size_type a) const 
  100.                 { 
  101.                         if(mN - a > mN) 
  102.                                 throw std::out_of_range("Fibonacci_Sequence::iterator::operator-() : The lower end of the sequence was reached! Invalid subtraction!"); 
  103.                         return mN - a; 
  104.                 } 
  105.  
  106.                 int operator-(iterator a) const 
  107.                 { 
  108.                         return mN - a.mN; 
  109.                 } 
  110.  
  111.                 iterator operator-=(size_type a) const 
  112.                 { 
  113.                         return (*this = *this - a); 
  114.                 } 
  115.  
  116.                 friend bool operator<(iterator a, iterator b) 
  117.                 { 
  118.                         return a.mN < b.mN; 
  119.                 } 
  120.  
  121.                 friend bool operator==(iterator a, iterator b) 
  122.                 { 
  123.                         return a.mN == b.mN; 
  124.                 } 
  125.         }; 
  126.  
  127.         typedef std::reverse_iterator<iterator> reverse_iterator; 
  128.  
  129.         iterator begin() const 
  130.         { 
  131.                 return mBegin; 
  132.         } 
  133.  
  134.         iterator end() const 
  135.         { 
  136.                 return mEnd; 
  137.         } 
  138.         reverse_iterator rbegin() const 
  139.         { 
  140.                 return reverse_iterator(mSequence.size()); 
  141.         } 
  142.  
  143.         reverse_iterator rend() const 
  144.         { 
  145.                 return reverse_iterator(0); 
  146.         } 
  147.  
  148.         T operator[](size_type n) const 
  149.         { 
  150.                 return mSequence[n]; 
  151.         } 
  152.  
  153.         size_type size() const 
  154.         { 
  155.                 return mSequence.size(); 
  156.         } 
  157.  
  158.         T at(size_type n) const 
  159.         { 
  160.                 if(n >= mSequence.size()) 
  161.                         throw std::out_of_range("Fibonacci_Sequence::at() : Index to high!"); 
  162.  
  163.                 return mSequence[n]; 
  164.         } 
  165.  
  166. private: 
  167.  
  168.         iterator const mBegin, mEnd; 
  169. }; 
  170.  
  171. template<typename T> 
  172. std::vector<T> Fibonacci_Sequence<T>::mSequence; 
  173.  
  174. int main() 
  175. { 
  176.         Fibonacci_Sequence<unsigned> sequence; 
  177.         std::copy(sequence.rbegin(), sequence.rend(), std::ostream_iterator<unsigned>(std::cout, "\n")); 
  178. }
Success #stdin #stdout 0.01s 2860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2971215073
1836311903
1134903170
701408733
433494437
267914296
165580141
102334155
63245986
39088169
24157817
14930352
9227465
5702887
3524578
2178309
1346269
832040
514229
317811
196418
121393
75025
46368
28657
17711
10946
6765
4181
2584
1597
987
610
377
233
144
89
55
34
21
13
8
5
3
2
1
1
0
https://ideone.com/JoJZ5A
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
secret

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!