Iterating over a collection without generating the collection first

Question

So, let's say we want to iterate some function over all the even positive numbers less or equal to 100. We could do:

vector<int> v;
for (int i=0; i<=100; i+=2) v.push_back(i);
for_each(v.begin(), v.end(), ourFunction);

Other simpler way is:

for (int i=0; i<=100; i+=2) ourFunction(i);

Now, let's say we have a more complex collection we want to iterate. For example palindromical numbers (in base 10) less than 1000000. We could do:

inline int tenTo(int power) { int n= 1; for(int i=0; i<power; i++) n*=10; return n; }

vector<int> getPalindromial(int digits, bool firstCall = true,vector<int> &fakePalindromial = vector<int>()) {
    if (digits == 1) {
        // Base Case 1
        vector<int> v;
        fakePalindromial.push_back(0);
        for (int i=1; i<=9; i++) {
            v.push_back(i);
            fakePalindromial.push_back(i);
        }
        return v;
    } else if (digits == 2) {
        // Base Case 2
        vector<int> v;
        fakePalindromial.push_back(0);
        for (int i=11; i<=99; i += 11) {
            v.push_back(i);
            fakePalindromial.push_back(i);
        }
        return v;
    } else {
        if (firstCall) {
            // If this is the first call, we built all the odd lenght numbers and the even length numbers and then we join them and return.
            vector<int> v1 = getPalindromial(digits,false);
            vector<int> v2 = getPalindromial(digits-1,false);
            v1.insert(v1.end(), v2.begin(), v2.end());
            return v1;
        }
        /* Recursive case:
         * For each palindromical number with 2 less digits, we add each digit at start and at the end
         */
        vector<int> v = getPalindromial(digits-2,false,fakePalindromial);
        const int size = fakePalindromial.size();

        for (int i=0; i<size; i++) {
            const int n = fakePalindromial[i];
            int nDigits = 1;
            for (int i=0; i< digits-2; i++) {
                nDigits *= 10;
            }

            /* Numbers with leading 0 are not really palindromical, but will be usefull to the functions building higher
             * numbers ( 010 is not palindromical, but it is usefull for building 50105)
             */
            int digit = 0;
            fakePalindromial.push_back(10*(nDigits*digit + n) + digit);

            for (int digit=1; digit<=9; digit++) {
                v.push_back(10*(nDigits*digit + n) + digit);
                fakePalindromial.push_back(10*(nDigits*digit + n) + digit);
            }
        }

        // Clean the palindromical numbers that we have used
        for (int i=0; i<size; i++) {
            fakePalindromial.erase(fakePalindromial.begin());
        }
        return v;
    } 
}

And then:

vector<int> v = getPalindromial(6);
for_each(v.begin(), v.end(), ourFunction);

How can we achieve the same without generating the hole collection and then iterate over it?

(Note: The getPalindromial function could be simplier, it's been made that way so it is more complex)

score 3 · Accepted Answer · answered Jul 28 '13 at 16:50

3

Represent your collection as a generator object with methods to advance to next logical element, to get current element, and to compare current element with the end element.

Then either use Boost Iterator Facade, http://www.boost.org/doc/libs/1_54_0/libs/iterator/doc/index.html#iterator-facade-and-adaptor (see their examples) or implement your own: http://www.cplusplus.com/reference/iterator/iterator/

answered Jul 28 '13 at 16:50

Anycorn

50,217
42
167
261

I sort of like python generator based iterators: each call on the non const lambda returns `optional`, and when it fails we have reached the end. – Yakk - Adam Nevraumont Jul 28 '13 at 17:03
It'd certainly makes things a lot easier if there was no need for the end iterator but my guess is to do so within c++ framework would be a hack. I tried to implement similar generators with exceptions but it's not a pretty hack – Anycorn Jul 28 '13 at 17:09
You just end up having to cache one return value within the `iterator`, and read a new value when you advance: which is pretty much exactly how input iterators from streams work. Then either use a `boost::iterator_facade` to finish it, or do the messy work yourself. – Yakk - Adam Nevraumont Jul 28 '13 at 17:20

score 1 · Answer 2 · answered Jul 28 '13 at 17:07

For this purpose I would try to design a class with a bespoke iterator.

class Palindromial {
  public:
    class PalindromialIterator {
       public:
          PalindromialIterator(Palindromial * rhs_palindromial) : palindromial(rhs_palindromial) {}
          int operator*() const { return palindromial->current(); }
          Palindromial * operator++( if (palindromial->next() {
                                        return self;
                                     } else {
                                        return palindromial->end();
          }
          bool operator==(PalindromialIterator const & rhs) { 
             return palindromial == rhs.palindromial;
          }
      private:
          Palindromial * palindromial;
    };
    bool next(); //Updates current an returns true if there was an element.
    int current() const; //Returns the current value in the sequence.
    PalindromialIterator begin() { return PalindromialIterator(self); }
    PalindromialIterator end() { return PalindromialIterator(0); }
};

I have not tried to compile this code snippet, but I hope you get the idea. You would also have to think about which algorithms you need to support and the operators they require.

score 0 · Answer 3 · edited May 23 '17 at 10:31

Python deals with this problem by implementing generator functions. A generator function only generates the elements of the list as they are needed and does not store them in memory all at once. You could implement a similar structure in C++ as discussed in this question.

Ideally, you would store the previous numbers in a table so that the generation would be bottom up instead of top down.

However, with palindrome numbers, you would not need to do this. All you need to do is count the number of possibilities for a given pattern. For example, for 1 digit, x can be matched by all 10 numbers between 0 and 9. For 2 digits, xx can be matched by 9 numbers (zero is already included in the single digit numbers). For xyx, the numbers of palindromes is 9 * 10 (9 because leading zeros are invalid). For xyyx, 9 * 10 are valid palindromes.

Based on the patterns, you need not actually generate the numbers recursively, you can just generate the number based on a given index. For example, the index of 0 should return the first of the single digit patterns, 0. The index of 100 should return the (100 - 9 - 10 =) index 81 of the numbers of the 3 digit pattern xyx. Knowing that the first number for that pattern is 101, and each first digit has 10 valid numbers, the element at index 81 would be 919 (909 is at index 80).

Iterating over a collection without generating the collection first

3 Answers3