Zip 迭代器

Author: David Abrahams, Thomas Becker
Contact: dave@boost-consulting.com, thomas@styleadvisor.com
Organization: Boost Consulting, Zephyr Associates, Inc.
Date: 2006-09-11
Copyright: Copyright David Abrahams and Thomas Becker 2003.
概要: zip 迭代器提供了同步地在多個序列上進行並發迭代的能力。zip 迭代器由一組迭代器構造而成。移動 zip 迭代器會並發地移動所有這些迭代器。提領 zip 迭代器將返回一個 tuple,其中包含各個迭代器提領得到的結果。

目錄

zip_iterator 概要

template<typename IteratorTuple>
class zip_iterator
{

public:
typedef /* 見下文 */ reference;
typedef reference value_type;
typedef value_type* pointer;
typedef /* 見下文 */ difference_type;
typedef /* 見下文 */ iterator_category;

zip_iterator();
zip_iterator(IteratorTuple iterator_tuple);

template<typename OtherIteratorTuple>
zip_iterator(
const zip_iterator<OtherIteratorTuple>& other
, typename enable_if_convertible<
OtherIteratorTuple
, IteratorTuple>::type* = 0 // exposition only
);

const IteratorTuple& get_iterator_tuple() const;

private:
IteratorTuple m_iterator_tuple; // exposition only
};

template<typename IteratorTuple>
zip_iterator<IteratorTuple>
make_zip_iterator(IteratorTuple t);

zip_iteratorreference 成員的類型為由 IteratorTuple 參數中的各個迭代器類型的引用類型所組成的 tuple.

zip_iteratordifference_type 成員為 IteratorTuple 參數中的第一個迭代器類型的 difference_type.

zip_iteratoriterator_category 成員可轉換為 IteratorTuple 參數中各個迭代器類型中遍歷能力最小的那個遍歷類別標誌。例如,如果 zip_iterator 只持有 vector 迭代器,則 iterator_category 可轉換為 boost::random_access_traversal_tag. 如果你加入一個 list 迭代器,則 iterator_category 將只能可轉換為 boost::bidirectional_traversal_tag, 而不再是 boost::random_access_traversal_tag.

zip_iterator 的要求

參數 IteratorTuple 中的所有迭代器都應符合可讀迭代器。

zip_iterator 的模型

zip_iterator 的結果符合可讀迭代器。

zip_iterator 只符合可讀迭代器的事實並不會阻止你修改個別迭代器所指向的值。由 zip_iteratoroperator* 所返回的 tuple 是由各個迭代器的引用類型所構造的,而不是由它們的值類型所構造的。例如,如果 zip_it 是一個 zip_iterator,其第一個成員迭代器是一個 std::vector<double>::iterator, 則以下代碼將會修改 zip_it 的第一個成員迭代器當前所指的值:

zip_it->get<0>() = 42.0;

考慮一個由 IteratorTuple 參數中的各個迭代器類型所符合的標準遍歷概念中最強化者所組成的集合。zip_iterator 符合該集合中的標準遍歷概念的最小者。

zip_iterator<IteratorTuple1>zip_iterator<IteratorTuple2> 可交互,當且僅當 IteratorTuple1  IteratorTuple2 是可交互的。

zip_iterator 的操作

除了 zip_iterator 所符合的概念所要求的操作以外,zip_iterator 還提供了以下操作。

zip_iterator();

返回: 一個 zip_iterator 實例,其 m_iterator_tuple 為缺省構造。

zip_iterator(IteratorTuple iterator_tuple);

返回: 一個 zip_iterator 實例,其 m_iterator_tuple 初始化為 iterator_tuple.
template<typename OtherIteratorTuple>
zip_iterator(
const zip_iterator<OtherIteratorTuple>& other
, typename enable_if_convertible<
OtherIteratorTuple
, IteratorTuple>::type* = 0 // exposition only
);
返回: 一個 zip_iterator 實例,複製自 other.
要求: OtherIteratorTuple 可隱式轉換為 IteratorTuple.

const IteratorTuple& get_iterator_tuple() const;

返回: m_iterator_tuple

reference operator*() const;

返回: A tuple consisting of the results of dereferencing all iterators in m_iterator_tuple.

zip_iterator& operator++();

作用: 遞增 m_iterator_tuple 中的每個迭代器。
返回: *this

zip_iterator& operator--();

作用: 遞減 m_iterator_tuple 的每個迭代器。
返回: *this
template<typename IteratorTuple>
zip_iterator<IteratorTuple>
make_zip_iterator(IteratorTuple t);
返回: 一個 zip_iterator<IteratorTuple> 實例,其 m_iterator_tuple 初始化為 t.
 

例子

主要有兩類 zip_iterator 應用。第一類關心運行時效率:如果你有幾個相同長度的序列需要某種處理,如使用 for_each 算法,那麼使用一個同時並發的迭代要比幾個獨立的迭代會有更高的效率。例如,假定 vect_of_doublesvect_of_ints 是兩個相同長度的 vectors,分別保存了 doubles 和 ints, 考慮以下兩次迭代:

std::vector<double>::const_iterator beg1 = vect_of_doubles.begin();
std::vector<double>::const_iterator end1 = vect_of_doubles.end();
std::vector<int>::const_iterator beg2 = vect_of_ints.begin();
std::vector<int>::const_iterator end2 = vect_of_ints.end();

std::for_each(beg1, end1, func_0());
std::for_each(beg2, end2, func_1());

現在可以用以下一次迭代來替代這兩次迭代:

std::for_each(
boost::make_zip_iterator(
boost::make_tuple(beg1, beg2)
),
boost::make_zip_iterator(
boost::make_tuple(end1, end2)
),
zip_func()
);

zip_func 的一個非泛型實現可能如下:

struct zip_func :
public std::unary_function<const boost::tuple<const double&, const int&>&, void>
{
void operator()(const boost::tuple<const double&, const int&>& t) const
{
m_f0(t.get<0>());
m_f1(t.get<1>());
}

private:
func_0 m_f0;
func_1 m_f1;
};

zip_iterator 的第二類重要應用是,創建組合的迭代器。組合迭代器即是,並發遍歷多個被控序列的單個迭代器,其提領操作返回對各個序列中對應位置的值應用一個函數對像所得的結果。將 zip_iteratortransform_iterator 一起使用就可以完成這一任務。

例如,假設你有兩個 doubles 的 vector, 分別為 vect_1vect_2, 你需要向用戶提供一個由 vect_1vect_2 的元素的積所組成的序列。不需要將這些積放在第三個 vector 中,你可以使用一個組合迭代器來就地計算乘積。我們假定 tuple_multiplies 是一個象 std::multiplies 一樣的函數對象,區別是它接受被打包在一個 tuple 中的兩個參數。以下定義的兩個迭代器 it_beginit_end 界定了一個被控序列,其中包含 vect_1vect_2 中的元素的乘積:

typedef boost::tuple<
std::vector<double>::const_iterator,
std::vector<double>::const_iterator
> the_iterator_tuple;

typedef boost::zip_iterator<
the_iterator_tuple
> the_zip_iterator;

typedef boost::transform_iterator<
tuple_multiplies<double>,
the_zip_iterator
> the_transform_iterator;

the_transform_iterator it_begin(
the_zip_iterator(
the_iterator_tuple(
vect_1.begin(),
vect_2.begin()
)
),
tuple_multiplies<double>()
);

the_transform_iterator it_end(
the_zip_iterator(
the_iterator_tuple(
vect_1.end(),
vect_2.end()
)
),
tuple_multiplies<double>()
);