fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <deque>
  4. using namespace std;
  5.  
  6. class nested_deque_iterator 
  7. {
  8.     vector<deque<int>::const_iterator>            iterators;
  9.     vector<deque<int>::const_iterator>            ends;
  10.     vector<deque<int>::const_iterator>::iterator  current;
  11.     bool                                          at_end = false;
  12.  
  13. public:
  14.     nested_deque_iterator(vector<deque<int>::const_iterator> iterators,
  15.                           vector<deque<int>::const_iterator> ends) :
  16. 		iterators(iterators),
  17. 		ends(ends)
  18.     {
  19.     	update_current();
  20.     }
  21.  
  22.     int operator *() const {
  23. 	    return **current;
  24. 	}
  25. 	nested_deque_iterator& operator++() {
  26. 	    if (!at_end) {
  27. 	    	++(*current);
  28. 	        update_current();
  29. 	    }
  30. 	    return *this;
  31. 	}
  32. 	nested_deque_iterator operator++(int) {
  33. 	    nested_deque_iterator old(*this);
  34. 	    ++(*this);
  35. 	    return old;
  36. 	}
  37. 	bool operator==(const nested_deque_iterator &o) const {
  38. 		// If either iterator is at the end, don't dereference current!
  39. 		if (at_end || o.at_end)
  40. 			return at_end == o.at_end;
  41. 	    return *current == *(o.current);
  42. 	}
  43. 	bool operator!=(const nested_deque_iterator &o) const {
  44. 	    return !(*this == o);
  45. 	}
  46.  
  47. private:
  48.     void update_current() {
  49. 	    if (!at_end && iterators.size() > 0) {
  50. 	        // At the beginning, we assume that we didn't find any
  51. 	        // new "next smaller element" in any deque.
  52. 	        at_end = true;
  53.  
  54. 	        // Iterate through the deques (with two iterators in parallel)
  55. 	        for (auto i = iterators.begin(), e = ends.begin();
  56. 	             i != iterators.end() && e != ends.end();
  57. 	             ++i, ++e)
  58. 	        {
  59. 	            // We ignore deques which are already at their end
  60. 	            if (*i != *e) {
  61. 	                // If we found a smaller next element (or the first try)...
  62. 	                if (at_end || **i < **current) {
  63. 	                    // ... then replace the current iterator with it:
  64. 	                    at_end = false;
  65. 	                    current = i;
  66. 	                }
  67. 	            }
  68. 	        }
  69. 	    }
  70. 	}
  71. };
  72.  
  73. //-----------------------------------------------------------------------------
  74.  
  75. nested_deque_iterator nested_deque_begin(const deque<deque<int>> & deques) {
  76.     vector<deque<int>::const_iterator>   iterators;
  77.     vector<deque<int>::const_iterator>   ends;
  78.     for (const auto & d : deques) {
  79.         iterators.push_back(d.begin());
  80.         ends.push_back(d.end());
  81.     }
  82.     return { iterators, ends };
  83. }
  84.  
  85. nested_deque_iterator nested_deque_end(const deque<deque<int>> & deques) {
  86.     vector<deque<int>::const_iterator>   ends;
  87.     for (const auto & d : deques) {
  88.         ends.push_back(d.end());
  89.     }
  90.     return { ends, ends };
  91. }
  92.  
  93. //-----------------------------------------------------------------------------
  94.  
  95. struct nested_deque {
  96.     deque<deque<int>> deques;
  97. };
  98.  
  99. nested_deque_iterator begin(const nested_deque & nd) {
  100.     return nested_deque_begin(nd.deques);
  101. }
  102. nested_deque_iterator end(const nested_deque & nd) {
  103.     return nested_deque_end(nd.deques);
  104. }
  105.  
  106. //-----------------------------------------------------------------------------
  107.  
  108. int main() {
  109.     deque<deque<int>> deques;
  110.     // until 40, here we have the powers of two:
  111. 	deques.push_back(deque<int>{1,2,4,8,16,32});
  112. 	// ..and the prime numbers:
  113. 	deques.push_back(deque<int>{2,3,5,7,11,13,17,19,23,29,31,37});
  114.  
  115. 	// Here we make use of the adaptor which overloads begin() and end():
  116. 	for (int i : nested_deque{deques})
  117. 	    cout << i << ' ';
  118.  
  119. 	return 0;
  120. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 2 3 4 5 7 8 11 13 16 17 19 23 29 31 32 37
https://ideone.com/NTlk4f
language:
C++14 (gcc 8.3)
created:
10 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!