以下を提供するものが欲しい:
std::list head;
std::list::node node;
while (node = head->next) {
do something with this node
};
リストに次のポインターがないことは、私にはかなり奇妙です。
C++11 以降、 stl には単一の連結リストがあります。その使用法は、通常の二重連結リストに似ています。
特に:
std::forward_list<node> my_list;
for(auto iter = my_list.begin(); iter != my_list.end(); ++iter)
{
node &curr_node = *iter;
// Do something with curr_node.
}
それはあります。インターフェイスのみが変更されます。
std::list
リンクリストと同じようにアイテムを保存します。GCC 4.6.1 標準ライブラリのソース コード ファイルstd_list.h
を調べると、次のものが見つかります。
struct _List_node_base
{
_List_node_base* _M_next;
_List_node_base* _M_prev;
//...
};
二重にリンクされたリスト。
std::list<T>::iterator
「次へ」のポインターを使用した場合と同じように、すべての要素を確認できます。同じファイルの 151 行目に次のように書かれています。
_Self&
operator++()
{
_M_node = _M_node->_M_next;
return *this;
}
すべての実装の詳細がプログラマーから隠されている理由の 1 つは、コンテナーを簡単に変更できることです。パフォーマンス上の理由から、別のコンテナを使用したり、独自のコンテナを作成したりする場合は、タイプを変更するだけです。
typedef std::list<MyItems> itemContainer;
for (itemContainer::const_iterator it = allItems.begin(); it != allItems.end(); ++it)
{
// do something
}
リストの実際の実装は隠されています。標準では、特定の位置での要素の挿入と削除が一定時間内に可能であることが規定されているため、ノードのようなものが使用されると想定できます。
23.3.5 クラステンプレート一覧 [一覧]
23.3.5.1 クラステンプレート一覧の概要 [list.overview]
A
list
は、双方向反復子をサポートするシーケンス コンテナーであり、ストレージ管理が自動的に処理され、シーケンス内の任意の場所で一定時間の挿入および消去操作が可能です。vector (23.3.6) や deques (23.3.3) とは異なり、リスト要素への高速ランダム アクセスはサポートされていませんが、多くのアルゴリズムはシーケンシャル アクセスのみを必要とします。
ただし、C++ コンテナーに関する重要な点は、コンテンツを実際にトラバースするための同じインターフェイス ( iterators ) をすべて提供することです。
for(std::list<double>::iterator it = list.begin(); it != list.end(); ++it){
*it += 3.0; // add 3.0 to each element
}
リストをCスタイルのオブジェクトと考えると、
struct node{
struct node * next;
struct node * prev;
double value;
};
struct list{
struct node * first;
struct node * last;
}
上記のループは、
for(struct node * it = list.first; it != list.last + 1; it = it->next){
*it += 3.0; // add 3.0 to each element
}
ただし、it = it->next
の実際の実装には次のようなことが隠されていstd::list::iterator
ます。それらはすべてのクラスにほぼ*統一されたインターフェイスを提供するため、それらの使用方法を学ぶ必要があります。
RandomAccessIterators
* 実際にはvs.のように他よりも少し多くの機能を提供するものもありBidirectionalIterators
ますが、これについては後で学習します。