Итерация по коллекции без создания коллекции первого

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

Теперь предположим, что у нас есть более сложная коллекция, которую мы хотим повторить. Например palindromical чисел (в базе 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

Представлять свою коллекцию в качестве объекта генератора с методами, чтобы перейти к следующему логическому элементу, чтобы получить текущий элемент, и сравнить текущий элемент с элементом .

Тогда либо использование Повысьте итератор Фасад, 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/

Answer 2

Python сделки с этой проблемой реализации функции генератора. Функция генератора только генерирует элементы списка по мере необходимости и не сохраняет их в памяти все сразу. Вы можете реализовать аналогичную структуру в C++, как описано в этом question.

В идеале вы сохранили бы предыдущие номера в таблице, чтобы генерация была снизу вверх, а не сверху вниз.

Однако, с номерами палиндрома, вам не нужно будет это делать. Все, что вам нужно сделать, - подсчитать количество возможностей для данного шаблона. Например, для 1 цифры x может быть сопоставлен всеми 10 цифрами от 0 до 9. Для 2 цифр xx может быть сопоставлен 9 цифрами (нуль уже включен в однозначные числа). Для xyx число палиндромов составляет 9 * 10 (9, потому что ведущие нули недействительны). Для xyyx, 9 * 10 являются действительными палиндромами.

На основе шаблонов вам не нужно генерировать числа рекурсивно, вы можете просто сгенерировать число, основанное на заданном индексе. Например, индекс 0 должен возвращать первый из шаблонов с одной цифрой, 0. Индекс 100 должен вернуть индекс (100 - 9 - 10 =) 81 чисел 3-значного шаблона xyx. Зная, что первое число для этого шаблона равно 101, и каждая первая цифра имеет 10 действительных чисел, элемент с индексом 81 будет равен 919 (909 - по индексу 80).

Answer 3

Для этого я попытался бы создать класс с помощью итератора на заказ.

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

Я не пытался скомпилировать этот фрагмент кода, но надеюсь, что вы поняли эту идею. Вам также нужно будет подумать о том, какие алгоритмы вам нужны для поддержки и требуемые им операторы.