2

因此，假设我们要对小于或等于 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 函数可能更简单，它是这样制作的，所以它更复杂）

4

3 回答 3

3

将您的集合表示为具有前进到下一个逻辑元素、获取当前元素以及将当前元素与结束元素进行比较的方法的生成器对象。

然后使用 Boost Iterator Facade，http://www.boost.org/doc/libs/1_54_0/libs/iterator/doc/index.html#iterator-facade-and-adaptor（参见他们的示例）或实现您自己的： http://www.cplusplus.com/reference/iterator/iterator/

于 2013-07-28T16:50:30.360 回答
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); }
};

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

于 2013-07-28T17:07:13.783 回答
0

Python 通过实现生成器函数来处理这个问题。生成器函数仅在需要时生成列表的元素，并且不会一次将它们全部存储在内存中。您可以在 C++ 中实现与此问题中讨论的类似结构。

理想情况下，您会将以前的数字存储在一个表中，以便生成自下而上而不是自上而下。

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

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

于 2013-07-28T17:01:04.690 回答