質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.92%

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

解決済

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 13K+

RyuSuzuki

score 127

前提

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;

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

+2

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;
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/05/22 17:17

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

    いいですね!

    キャンセル

checkベストアンサー

+1

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と思って使用するのがベターです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/05/22 15:36

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

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

    キャンセル

  • 2017/05/22 17:14 編集

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

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

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

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

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

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

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

    キャンセル

  • 2017/05/22 17:20

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

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

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

    キャンセル

+1

こんには。

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の思想と思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/05/22 17:23

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

    キャンセル

  • 2017/05/22 18:47

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

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.92%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る