STL スタイルのランダム アクセス イテレータを提供するコレクションを作成しました。イテレータの実装例を探していましたが、見つかりませんでした。[]および*演算子の const オーバーロードの必要性については知っています。イテレータを「STL スタイル」にするための要件と、避けるべきその他の落とし穴 (ある場合) は何ですか?
追加のコンテキスト: これはライブラリ用であり、本当に必要でない限り、依存関係を導入したくありません。私は、同じコンパイラで C++03 と C++11 の間のバイナリ互換性を提供できるように、独自のコレクションを作成します (そのため、壊れる可能性のある STL はありません)。
http://www.cplusplus.com/reference/std/iterator/には、C++11標準の§24.2.2の仕様を詳しく説明した便利なチャートがあります。基本的に、イテレータには有効な操作を説明するタグがあり、タグには階層があります。以下は純粋に象徴的なものであり、これらのクラスは実際にはそのようには存在しません。
iterator {
iterator(const iterator&);
~iterator();
iterator& operator=(const iterator&);
iterator& operator++(); //prefix increment
reference operator*() const;
friend void swap(iterator& lhs, iterator& rhs); //C++11 I think
};
input_iterator : public virtual iterator {
iterator operator++(int); //postfix increment
value_type operator*() const;
pointer operator->() const;
friend bool operator==(const iterator&, const iterator&);
friend bool operator!=(const iterator&, const iterator&);
};
//once an input iterator has been dereferenced, it is
//undefined to dereference one before that.
output_iterator : public virtual iterator {
reference operator*() const;
iterator operator++(int); //postfix increment
};
//dereferences may only be on the left side of an assignment
//once an output iterator has been dereferenced, it is
//undefined to dereference one before that.
forward_iterator : input_iterator, output_iterator {
forward_iterator();
};
//multiple passes allowed
bidirectional_iterator : forward_iterator {
iterator& operator--(); //prefix decrement
iterator operator--(int); //postfix decrement
};
random_access_iterator : bidirectional_iterator {
friend bool operator<(const iterator&, const iterator&);
friend bool operator>(const iterator&, const iterator&);
friend bool operator<=(const iterator&, const iterator&);
friend bool operator>=(const iterator&, const iterator&);
iterator& operator+=(size_type);
friend iterator operator+(const iterator&, size_type);
friend iterator operator+(size_type, const iterator&);
iterator& operator-=(size_type);
friend iterator operator-(const iterator&, size_type);
friend difference_type operator-(iterator, iterator);
reference operator[](size_type) const;
};
contiguous_iterator : random_access_iterator { //C++17
}; //elements are stored contiguously in memory.
特殊std::iterator_traits<youriterator>化するか、同じtypedefをイテレータ自体に配置するか、std::iterator（これらのtypedefを持つ）から継承することができます。名前空間の変更を避け、読みやすくするために、2番目のオプションを好みますstdが、ほとんどの人はから継承しstd::iteratorます。
struct std::iterator_traits<youriterator> {
typedef ???? difference_type; //almost always ptrdiff_t
typedef ???? value_type; //almost always T
typedef ???? reference; //almost always T& or const T&
typedef ???? pointer; //almost always T* or const T*
typedef ???? iterator_category; //usually std::forward_iterator_tag or similar
};
iterator_categoryは、イテレータが満たす要件に応じて、、、、、、またはのいずれかstd::input_iterator_tagである必要があることに注意してください。イテレータによっては、、、、などを特殊化することもできますが、これが必要になることはめったにありません。非常にまれなケースでは、とを専門にすることをお勧めします。std::output_iterator_tagstd::forward_iterator_tagstd::bidirectional_iterator_tagstd::random_access_iterator_tagstd::nextstd::prevstd::advancestd::distancestd::beginstd::end
コンテナにはおそらく、も含まれている必要があります。これは、から暗黙的に構築可能であり、ユーザーがデータを変更できないことを除いてconst_iterator、と同様の定数データへの（おそらく可変の）イテレータです。内部ポインタが非定数データへのポインタであるのが一般的であり、コードの重複を最小限に抑えるためにから継承しています。iteratoriteratoriteratorconst_iterator
独自のSTLコンテナーの作成に関する私の投稿には、より完全なコンテナー/イテレーターのプロトタイプがあります。
Boost.Iteratorのiterator_facade ドキュメントは、リンクされたリストの反復子を実装するための優れたチュートリアルのように見えるものを提供します。コンテナにランダム アクセス イテレータを構築するための出発点として、それを使用できますか?
他に何もない場合でも、によって提供されるメンバー関数と typedef を見て、iterator_facadeそれを独自のビルドの開始点として使用できます。
これは、生のポインター反復子のサンプルです。
生のポインターを操作するために iterator クラスを使用しないでください。
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <assert.h>
template<typename T>
class ptr_iterator
: public std::iterator<std::forward_iterator_tag, T>
{
typedef ptr_iterator<T> iterator;
pointer pos_;
public:
ptr_iterator() : pos_(nullptr) {}
ptr_iterator(T* v) : pos_(v) {}
~ptr_iterator() {}
iterator operator++(int) /* postfix */ { return pos_++; }
iterator& operator++() /* prefix */ { ++pos_; return *this; }
reference operator* () const { return *pos_; }
pointer operator->() const { return pos_; }
iterator operator+ (difference_type v) const { return pos_ + v; }
bool operator==(const iterator& rhs) const { return pos_ == rhs.pos_; }
bool operator!=(const iterator& rhs) const { return pos_ != rhs.pos_; }
};
template<typename T>
ptr_iterator<T> begin(T *val) { return ptr_iterator<T>(val); }
template<typename T, typename Tsize>
ptr_iterator<T> end(T *val, Tsize size) { return ptr_iterator<T>(val) + size; }
生ポインタ範囲ベースのループ回避策。生のポインターから範囲ベースのループを作成するより良い方法があれば、私を修正してください。
template<typename T>
class ptr_range
{
T* begin_;
T* end_;
public:
ptr_range(T* ptr, size_t length) : begin_(ptr), end_(ptr + length) { assert(begin_ <= end_); }
T* begin() const { return begin_; }
T* end() const { return end_; }
};
template<typename T>
ptr_range<T> range(T* ptr, size_t length) { return ptr_range<T>(ptr, length); }
そして簡単なテスト
void DoIteratorTest()
{
const static size_t size = 10;
uint8_t *data = new uint8_t[size];
{
// Only for iterator test
uint8_t n = '0';
auto first = begin(data);
auto last = end(data, size);
for (auto it = first; it != last; ++it)
{
*it = n++;
}
// It's prefer to use the following way:
for (const auto& n : range(data, size))
{
std::cout << " char: " << static_cast<char>(n) << std::endl;
}
}
{
// Only for iterator test
ptr_iterator<uint8_t> first(data);
ptr_iterator<uint8_t> last(first + size);
std::vector<uint8_t> v1(first, last);
// It's prefer to use the following way:
std::vector<uint8_t> v2(data, data + size);
}
{
std::list<std::vector<uint8_t>> queue_;
queue_.emplace_back(begin(data), end(data, size));
queue_.emplace_back(data, data + size);
}
}
Thomas Becker は、このテーマに関する有益な記事をここに書いています。
SO で以前に登場したこの (おそらくもっと単純な) アプローチもありました:カスタム イテレータと const_iterators を正しく実装するには?
まず、個々のイテレータ型がサポートする必要があるさまざまな操作のリストについては、こちらを参照してください。
次に、イテレータ クラスを作成したら、そのクラスに特化して必要なs (または など)std::iterator_traitsを提供するか、必要な s を定義するから派生させて、デフォルトで使用できるようにする必要があります。typedefiterator_categoryvalue_typestd::iteratortypedefstd::iterator_traits
免責事項:あまり好きcplusplus.comではない人もいることは知っていますが、これに関する非常に役立つ情報を提供しています。
私はさまざまな理由であなたと同じ船に乗っていました/現在です（一部は教育的、一部は制約）。標準ライブラリのすべてのコンテナを書き直す必要があり、コンテナは標準に準拠する必要がありました。つまり、コンテナーをstlバージョンに交換しても、コードは同じように機能します。これは、イテレータを書き直さなければならないことも意味していました。
とにかく、私はEASTLを見ました。stlコンテナーを使用したり、学部課程でこれまで学んだことのないコンテナーについて多くのことを学んだことは別として。主な理由は、EASTLが対応するstlよりも読みやすいことです(これは単に、すべてのマクロがなく、コーディング スタイルが単純なためです)。そこには厄介なもの (例外の #ifdefs など) がありますが、圧倒されるものは何もありません。
他の人が述べたように、イテレーターとコンテナーに関する cplusplus.com のリファレンスを見てください。