std::listにおけるイテレータの指定の仕方

Question

###前提
std::listにおいて、指定したindexに要素にアクセスする際に適切な記述の仕方がわかりません。

std::list lst{1,2,3,4,5,6,7,8,9};
// 1と表示される
std::cout << *(lst.begin()) << std::endl;
// でも、次のはエラー
std::cout << *(lst.begin()＋2) << std::endl;

どのように記述すればよいのでしょうか？

Answer 1

std::listコンテナはstd::vectorや配列と違って、ランダムアクセスができません。そのため、N回だけイテレータを進めて要素を参照する必要があります。
そのような用途には、std::next()関数を使用できます。

#include <iostream>
#include <list>
#include <iterator> // std::next()関数が所属するヘッダ

int main()
{
    std::list<int> lst{1,2,3,4,5,6,7,8,9};

    // 1と表示される
    std::cout << *(lst.begin()) << std::endl;

    // 3と表示される
    std::cout << *std::next(lst.begin(), 2) << std::endl;
}

この関数は、指定されたイテレータをN回進めたイテレータを返します。(指定したイテレータ自体は書き換えない)

std::next()をサポートしていない古いコンパイラの場合は、std::advance()関数を使用します。こちらは指定したイテレータ自体をN回進めます。

#include <iostream>
#include <list>
#include <iterator> // std::advance()関数が所属するヘッダ

int main()
{
    std::list<int> lst{1,2,3,4,5,6,7,8,9};

    // 1と表示される
    std::cout << *(lst.begin()) << std::endl;

    // 3と表示される
    std::list<int>::iterator it = lst.begin();
    std::advance(it, 2); // itを2回進める
    std::cout << *it << std::endl;
}

Comments

[haru666]

おお…nextあったんですね。なんでないんだろうと思ってたんですが、C++11から増えてたんですね。

いいですね！

Answer 2

iteratorを使って回数分移動するしかありません。
これを変わりにしてくれるものにstd::advanceがあります。

UINT index;
auto it = lst.begin();

// このようにする
for (int i=0; i < index; ++i)
{
    it++;
}

// 代わりに以下のようにかけます。
std::advance(it, index);

forループにせよadvanceにせよ単純にiteratorをインクリメントするだけなので
インデックスアクセスで範囲外を参照しないようにsizeと事前に比較しておいてください。

if (lst.size() <= index) return;

見ての通りlistにおける要素の取得は高コストです。
ランダムアクセスを主目的とする場合はvector等別のコンテナを使った方がいいでしょう。
基本的には編集可能なqueueと思って使用するのがベターです。

Comments

[episteme]

ご指摘の通り、listにおける要素の取得は高コストです。
が、イテレータをn個進めるのは「次の要素に移動する」すなわちp = p->next をn回繰り返すだけで、
やってらんないほど遅いわけではありません。あくまでRandomAccessIteratorと比べれば高コストってことで。

listのコストはむしろ「ひとつの要素ごとにポインタふたつ余計に必要」っていうメモリ効率の方が問題大きいかもです。

[haru666]

深く考えないなら大体vectorの方が問題が少ない、と思っているから上記のように書きました。

無作法な反論をお許し下さい。
値の保持の仕方こそこの両コンテナの重要な違いであって、メモリコストは私はあまり問題視していません。

vectorは値の挿入によってオブジェクトの配置が換わる可能性があります。
listなら変わりません。これはあまり話題にされない気がしますが、最も重要な違いです。

コスト面で言えば、値の挿入時、vectorはcapacityの拡張で内部配列の移動によるコピーコストが発生する可能性があります。
また、オブジェクトのメモリ上の配置が換わってしまう可能性があります。
listを使えばこのコストは発生しません。

ランダムアクセスを元にした二分木のようなアルゴリズムがあります。
ランダムアクセスをベースとした仕組みは直観的で作りやすいため、度々使われます。
一方、listを使う場合には直接要素のポインタ/イテレータを保持するのが再アクセス手段のベストプラクティスです。
そういった操作に慣れてない多くの人はランダムアクセスによってコンテナ内の要素に再アクセスしようとします。

listで可能なイテレータの保存という行為はvectorではできません。
先に述べたように、vectorでは値の挿入時、イテレータがズレてしまう可能性があるからです。
これを嫌ってunique_ptrを使ってオブジェクトをヒープ内にラップし、vector配列にしてしまうこともあります。
listではそもそもそんな配慮が不要です。

シーケンシャルアクセスするだけならどちらでもよいのです。
しかし…listは使いづらいし、正しくパフォーマンスを出すのが難しい。
特に、リファレンスを読まない作業者がチーム内にいると混乱の元かな、と。
このため、基本的にランダムアクセスを理由にvectorをオススメしている次第です。

[episteme]

ぃぇぃぇ、無作法な反論だなんてとんでもない。

スピードとメモリ効率なら各要素を連続に配置するvectorが一番で、そのかわりイテレータがしょっちゅう無効になる。これの対極(?)にあるのがlistってことで、全面的に同意します。

「コンテナにどれ使うか迷ったらひとまずvector使っとけ」は大抵の場合正解ですし。

Answer 3

こんには。

std::list lst{1,2,3,4,5,6,7,8,9};

は下記の間違いですね？

std::list<int> lst{1,2,3,4,5,6,7,8,9};

std::listのbegin()はイテレータを返却しますが、それはbidirectional_iteratorですので、+整数演算をサポートしていません。一旦変数へ獲得し、2回++しましょう。

auto itr = lst.begin();
++itr;
++itr;
std::cout << *itr << std::endl;

全てのコンテナが同じ機能をサポートすれば良いのにとも思いますが、STLは性能が出ない機能はサポートしない方針のようです。性能がでなくても問題ないのであればコンテナを派生して、必要な機能を追加するのが良いと思います。

もしくは、random_access_iteratorをサポートしているstd::vector<>やstd::deque<>に代えることも考えられます。

アプリケーションの要求に応じてどの性能を最大化するのかにより適切なコンテナを選択するのがSTLの思想と思います。

Comments

[faithandbrave]

C++17では std::list lst{1,2,3,4,5,6,7,8,9}; は妥当なコードになりますので、使用しているコンパイラのバージョンによっては通りますね。クラステンプレートの型推論機能によるものです。

[Chironian]

faithandbraveさん、コメントありがとうございます。

なるほど、そう言えばコンストラクタで暗黙の実体化ができるようになる話を聞いた記憶が有ります。既に使えるようになっていたのですね。時の流れは速い。