Я не знаю ни одной реализации в основной библиотеке, но это выглядело как интересная проблема, поэтому я написал базовую реализацию. Я протестировал его только с тестовым набором, который я здесь представляю, поэтому я не рекомендую использовать его без дальнейшего тестирования.
Проблема немного сложнее, чем кажется, потому что некоторые из "внутренних" контейнеров могут быть пустыми, и вам придется их пропустить Это означает, что продвижение flattening_iterator на одну позицию может фактически переместить итератор во «внешний» контейнер более чем на одну позицию. Из-за этого flattening_iterator необходимо знать, где находится конец внешнего диапазона, чтобы он знал, когда ему нужно остановиться.
Эта реализация является прямым итератором. Двунаправленный итератор также должен отслеживать начало внешнего диапазона. Шаблоны функций flatten используются для упрощения построения flattening_iterator s.
#include <iterator>
// A forward iterator that "flattens" a container of containers. For example,
// a vector<vector<int>> containing { { 1, 2, 3 }, { 4, 5, 6 } } is iterated as
// a single range, { 1, 2, 3, 4, 5, 6 }.
template <typename OuterIterator>
class flattening_iterator
{
public:
typedef OuterIterator outer_iterator;
typedef typename OuterIterator::value_type::iterator inner_iterator;
typedef std::forward_iterator_tag iterator_category;
typedef typename inner_iterator::value_type value_type;
typedef typename inner_iterator::difference_type difference_type;
typedef typename inner_iterator::pointer pointer;
typedef typename inner_iterator::reference reference;
flattening_iterator() { }
flattening_iterator(outer_iterator it) : outer_it_(it), outer_end_(it) { }
flattening_iterator(outer_iterator it, outer_iterator end)
: outer_it_(it),
outer_end_(end)
{
if (outer_it_ == outer_end_) { return; }
inner_it_ = outer_it_->begin();
advance_past_empty_inner_containers();
}
reference operator*() const { return *inner_it_; }
pointer operator->() const { return &*inner_it_; }
flattening_iterator& operator++()
{
++inner_it_;
if (inner_it_ == outer_it_->end())
advance_past_empty_inner_containers();
return *this;
}
flattening_iterator operator++(int)
{
flattening_iterator it(*this);
++*this;
return it;
}
friend bool operator==(const flattening_iterator& a,
const flattening_iterator& b)
{
if (a.outer_it_ != b.outer_it_)
return false;
if (a.outer_it_ != a.outer_end_ &&
b.outer_it_ != b.outer_end_ &&
a.inner_it_ != b.inner_it_)
return false;
return true;
}
friend bool operator!=(const flattening_iterator& a,
const flattening_iterator& b)
{
return !(a == b);
}
private:
void advance_past_empty_inner_containers()
{
while (outer_it_ != outer_end_ && inner_it_ == outer_it_->end())
{
++outer_it_;
if (outer_it_ != outer_end_)
inner_it_ = outer_it_->begin();
}
}
outer_iterator outer_it_;
outer_iterator outer_end_;
inner_iterator inner_it_;
};
template <typename Iterator>
flattening_iterator<Iterator> flatten(Iterator it)
{
return flattening_iterator<Iterator>(it, it);
}
template <typename Iterator>
flattening_iterator<Iterator> flatten(Iterator first, Iterator last)
{
return flattening_iterator<Iterator>(first, last);
}
Следующая минимальная тестовая заглушка:
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
int main()
{
// Generate some test data: it looks like this:
// { { 0, 1, 2, 3 }, { 4, 5, 6, 7 }, { 8, 9, 10, 11 } }
std::vector<std::vector<int>> v(3);
int i(0);
for (auto it(v.begin()); it != v.end(); ++it)
{
it->push_back(i++); it->push_back(i++);
it->push_back(i++); it->push_back(i++);
}
// Flatten the data and print all the elements:
for (auto it(flatten(v.begin(), v.end())); it != v.end(); ++it)
{
std::cout << *it << ", ";
}
std::cout << "\n";
// Or, since the standard library algorithms are awesome:
std::copy(flatten(v.begin(), v.end()), flatten(v.end()),
std::ostream_iterator<int>(std::cout, ", "));
}
Как я уже говорил в начале, я не проверил это полностью. Дайте мне знать, если вы найдете какие-либо ошибки, и я буду рад их исправить.