迭代对于容器C++

Question

之间跳跃我有个整数的容器的容器。可以说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迭代器。这样的迭代器应该为每个deques持有一个迭代器，但是也应该为它们的每一个结束（为什么你需要这个会在下面解释）。但这些迭代器应该在一个载体，而不是一个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);