C++ でリストを繰り返す

  2. プログラミングのヒント
  3. C++ ハウツー
  4. C++ でリストを繰り返す
Naila Saad Siddiqui 2023年10月12日
C++ C++ List
  1. C++ でのリスト
  2. C++ でリストを繰り返す
C++ でリストを繰り返す

この簡単なプログラミングチュートリアルでは、C++ で広く使用されているデータ構造、つまりリストについて説明します。C++ 標準テンプレートライブラリ（STL）には、このデータ構造に使用できるクラスリストがあります。

リストで複数の操作を実行するために使用できる機能のバンドルがパッケージ化されています。この記事の後半で、リストをトラバースしてリストを表示または編集する方法について説明します。

C++ でのリスト

リストまたはリンクリストは、データコンテナとして機能し、データをメモリに格納できる線形データ構造です。ベクトルや配列とは異なり、リスト内のデータは連続したメモリ位置に保存されません。

代わりに、データはランダムなメモリ位置に保存されます。リストに挿入された各要素は、ノードと呼ばれます。

リスト内の各ノードには、リストの次の要素を指すポインターが含まれています。これが、リストの要素が連続した場所に保存されない理由です。したがって、リンクリストとも呼ばれます。

リストは 2つのタイプに分類できます。

  1. 単一リンクリスト
  2. 二重リンクリスト

単一リンクリスト

このタイプのリンクリストでは、すべてのノードに 2つの部分があり、1つはデータ用で、もう 1つは次のノードを指すポインターを格納するためのものです。2 番目の部分には、リストの次のノードのアドレスが格納されます。

二重リンクリスト

このタイプのリンクリストでは、すべてのノードに 3つの部分があり、最初の部分は前のノードへのポインター用、2 番目の部分はデータの保存用、3 番目の部分にはリストの次の要素を参照するポインターが含まれます。

STL の list クラスには、二重にリンクされたリストが含まれています。配列と同様に、このリストタイプでの挿入と削除には直線的な時間がかかります。

ただし、リストには伝染性のメモリブロックは必要ありません。さらに、一度に 1つのリストノードをアタッチしてリストを拡張する方が、動的配列全体を再割り当てするよりも簡単で合理的です（ベクトルによって行われるように）。

したがって、配列やベクトルなどの他のデータ構造よりも柔軟なデータ構造と見なされます。

もう 1つのデータ構造 forward_list は、一方向にのみ反復でき、単一にリンクされたリストです。他のデータ構造と比較して、リストとフォワードリストの主な欠点は、配列のように位置を指定することによってリスト要素に直接アクセスできないことです。

たとえば、リストの 5 番目の要素にアクセスするには、あるエンドポイントから開始する必要があり、その位置まで開始または終了する必要があり、線形の時間がかかります。リストはまた、追加の RAM を使用して、各要素の接続情報を格納します。

C++ でリストを繰り返す

標準テンプレートライブラリ C++ の iterator クラスを使用して、リスト要素をトラバースできます。この構文は次のとおりです。

std::list<int>::iterator itr;

リストには、反復するためのさまざまな方法があります。

関数名 説明
itr.begin() リストの最初のノードへのポインタを与えます。
itr.end() リストの最後のノードへのポインタを与えます。

リストクラスのさまざまな関数を使用する以下のコードを見てみましょう。

#include <cstdlib>
#include <iostream>
#include <iterator>
#include <list>
using namespace std;

void displaylist(list<int> l)  // print function to show list
{
  list<int>::iterator myitr;
  for (myitr = l.begin(); myitr != l.end(); ++myitr) cout << "  " << *myitr;
  cout << endl;
}
int main() {
  list<int> mylist1;
  for (int a = 0; a < 10; ++a) {
    int r = 1 + (rand() % 50);
    mylist1.push_back(r);
  }
  cout << "\nData of List 1 : ";
  displaylist(mylist1);
  cout << "\nList first element : " << mylist1.front();
  cout << "\nAfter we pop first element: ";
  mylist1.pop_front();
  displaylist(mylist1);

  cout << "\nWhen we sort the list: ";
  mylist1.sort();
  displaylist(mylist1);

  return 0;
}

出力：

Data of List 1 :   34  37  28  16  44  36  37  43  50  22

List first element : 34
After we pop first element:   37  28  16  44  36  37  43  50  22

When we sort the list:   16  22  28  36  37  37  43  44  50

関連記事 - C++ List