Итератор для прыжков между контейнерами C++

Question

У меня есть контейнер с контейнером ints. Давайте скажем deque< deque<int> >. Все цифры в deque<int> сортируются в возрастающем размере. Таким образом, информация в контейнере выглядит примерно так:

deque<deque<int>> // main container 
    5 11 22 44  // deque<int> number 1 
    1 7 12   // deque<int> number 2 
    4 5 7 9 1112 // deque<int> number 3 

Я хочу сделать итератор, который проходит через все числа в deque<deque<int>> в порядке возрастания. Это означает, что мой итератор может прыгать между контейнерами, и после того, как я пройду через них, я пройду через номера в этом порядке: 1 4 5 5 7 7 9 11 12 22 44 1112. Как я могу это сделать? Я думал о том, чтобы поместить все числа в один контейнер и отсортировать их, но позже, если я хочу сказать *it = 10, я не смогу, потому что не знаю, в какой позиции контейнера находится it. Поэтому приветствуются любые идеи и решения :)

Answer 1

Давайте сосредоточимся на итераторе const. Такой итератор должен иметь итератор для каждого из требований, но также и каждому из них (зачем вам это объясняется ниже). Но эти итераторы должны храниться в векторе вместо deque, потому что вы никогда не будете выталкивать или выскакивать с любого конца этих контейнеров, так как время жизни такого итератора заканчивается модификацией вашей структуры данных.

Так в основном, вам необходимо добавить следующую структуру:

struct const_iterator { 
    vector<deque<int>::const_iterator> iterators; 
    vector<deque<int>::const_iterator> ends; 
    //... 
}; 

Теперь вам нужно реализовать оператор инкремента (может быть, вы хотите оператор декремента, который может быть реализован аналогично), а также разыменования оператор.

Оператор приращений должен найти итератор deque, который в настоящее время указывает на наименьший элемент, и увеличивать его.

Оператор разыменования также должен найти итератор deque, который в настоящее время указывает на наименьший элемент, и разыгрывает его.

Если вы ищете самый маленький элемент в настоящее время, не обращайте внимания на знаки, которые уже указывают на их конец. Для этого вам нужны все итераторы конца deque. Возможно, было бы полезно запомнить самый маленький элемент в другой переменной-члене, так что разыменование становится постоянной операцией времени. Мы сохраняем этот текущий итератор как итератор в вектор итераторов, чтобы мы могли его увеличивать (поэтому итератор в векторе изменяется).

struct nested_deque_iterator { 
    vector<deque<int>::const_iterator>   iterators; 
    vector<deque<int>::const_iterator>   ends; 
    vector<deque<int>::const_iterator>::iterator current; 
    bool           at_end = false; 
}; 

Обновление наименьший элемент может быть реализован в виде вспомогательной функции, которая изменяет переменную-член current, а также at_end. Это должно быть названо в конструкторе для правильной инициализации переменной-члена:

void update_current() { 
    if (!at_end && iterators.size() > 0) { 
     // At the beginning, we assume that we didn't find any 
     // new "next smaller element" in any deque. 
     at_end = true; 

     // Iterate through the deques (with two iterators in parallel) 
     for (auto i = iterators.begin(), e = ends.begin(); 
      i != iterators.end() && e != ends.end(); 
      ++i, ++e) 
     { 
      // We ignore deques which are already at their end 
      if (i != e) { 
       // If we found a smaller next element (or the first try)... 
       if (at_end || *i < *next) { 
        // ... then replace the current iterator with it: 
        at_end = false; 
        current = i; 
       } 
      } 
     } 
    } 
} 

Затем разыменования становится столь же легко, как разыменования текущий итератор дважды (так как это итератор в вектор итераторов. .. Я знаю, что это немного запутывает ...)

int operator *() const { 
    return **current; 
} 

И приращение будет увеличивать (разыменованный) текущий итератор, а также вызвать вспомогательную функцию, чтобы обновить его (это Преинкремент оператор):

nested_deque_iterator& operator++() { 
    if (!at_end) { 
     ++(*current); 
     update_current(); 
    } 
} 

Вы можете реализовать оператор пост-инкремент с помощью предварительного инкрементирования:

nested_deque_iterator operator++(int) { 
    nested_deque_iterator old(*this); 
    ++(*this); 
    return old; 
} 

Нам понадобится оператор равенства для сравнения итераторы друг с другом:

bool operator==(const nested_deque_iterator &o) const { 
    // If either iterator is at the end, don't dereference current! 
    if (at_end || o.at_end) { 
     return at_end == o.at_end; 
    } 
    return *current == *(o.current); 
} 

И, наконец, оператор неравенства с помощью равенства:

bool operator!=(const nested_deque_iterator &o) const { 
    return !(*this == o); 
} 

---

Наконец, написать в начало и конец строительства вспомогательные функции для ваших вложенных двусторонних очередей.

nested_deque_iterator nested_deque_begin(const deque<deque<int>> & deques) { 
    vector<deque<int>::const_iterator> iterators; 
    vector<deque<int>::const_iterator> ends; 
    for (const auto & d : deques) { 
     iterators.push_back(d.begin()); 
     ends.push_back(d.end()); 
    } 
    return { iterators, ends }; 
} 

nested_deque_iterator nested_deque_end(const deque<deque<int>> & deques) { 
    vector<deque<int>::const_iterator> ends; 
    for (const auto & d : deques) { 
     ends.push_back(d.end()); 
    } 
    return { ends, ends }; 
} 

И если вы хотите, также адаптер контейнера (если вы уже не имеете такой), который использует эти строительные вспомогательные функции, как их по умолчанию начальные и конечные методы:

struct nested_deque { 
    deque<deque<int>> deques; 
    //... 
} 

nested_deque_iterator begin(const nested_deque & nd) { 
    return nested_deque_begin(nd.deques); 
} 
nested_deque_iterator end(const nested_deque & nd) { 
    return nested_deque_end(nd.deques); 
} 

Таким образом, вы можно написать:

deque<deque<int>> mydeque = ...; 

for (int i : nested_deque{mydeque}) { 
    // Here you go. 
} 

---

полная реализация доступна here.

Answer 2

реализовать свой собственный итератор:

struct sorted_iterator { 
    int& operator*() { return *(*this->it); } 
    sorted_iterator& operator++() { ++(this->it); return *this;} 
    bool operator==(const sorted_iterator& other) const; 
    bool operator!=(const sorted_iterator& other) const; 

    private: 
     std::vector<int*> sorted; 
     decltype(sorted)::iterator it; 
}; 

и в ней, внутренне, построить вектор int*

std::vector<int*> sorted; 

for(std::deque<int> x : main_container) 
    for(int& i : x) 
     sorted.push_back(&i); 

auto compare = [](int* i, int* j) { return *i < *j; } 
std::sort(sorted.begin(), sorted.end(), compare);