迭代集合，而不首先生成集合。

Question

所以，假设我们想要迭代一些函数，对所有的偶数，小于或等于100。我们可以这样做：

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

其他更简单的方法是：

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

现在，假设我们有一个想要迭代的更复杂的集合。例如，回文数字(基数10)小于1000000。我们可以这样做：

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;
    } 
}

然后：

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

我们如何才能做到同样的，而不产生孔集合，然后迭代它呢？

(注意: getPalindromial函数可能更简单，它是这样做的，所以它更复杂)

Answer 1

为此，我将尝试设计一个带有定制迭代器的类。

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); }
};

我没有尝试编译这个代码片段，但我希望您能理解。您还必须考虑需要支持哪些算法以及它们所需的运算符。

Answer 2

Python通过实现生成器函数来处理这个问题。生成器函数只在需要时生成列表中的元素，而不是一次性将它们存储在内存中。您可以在C++中实现类似的结构，如本question中所讨论的那样。

理想情况下，您应该将前面的数字存储在一个表中，这样生成的数据将是自下而上的，而不是自上而下的。

然而，使用回文编号，您将不需要这样做。您所需要做的就是计算给定模式的可能性数量。例如，对于1位数字，x可以被0到9之间的所有10个数字匹配。对于2位数，xx可以被9个数字匹配(0已经包含在单数数字中)。对于xyx，回文数为9* 10 (9因为前导零无效)。对于xyyx，9* 10是有效的回文。

根据这些模式，您不需要递归地生成数字，您只需根据给定的索引生成数字。例如，0的索引应该返回第一个单数模式，0。指数100应返回3位模式xyx数的(100 -9- 10 =)指数81。知道该模式的第一个数字为101，并且每个第一个数字有10个有效数字，索引81处的元素将为919 (909位于索引80)。