CodeZine(コードジン)

特集ページ一覧

Visual C++ 2010に追加されたSTLコンテナ「forward_list」

listを簡略化したコンテナ「forward_list」

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加
2010/07/12 14:00

 前回はVisual C++ 2010(以下、VC10)に追加されたアルゴリズムを一挙に紹介しましたが、今回は新しいコンテナの一つ「forward_list」について、特性や特徴をlistと対比しながら紹介します。

目次

はじめに

 前回はVisual C++ 2010(以下、VC10)に追加されたアルゴリズムを一挙に紹介しましたが、今回はコンテナを一つ。

 標準C++ライブラリに新たなコンテナ「forward_list」がお目見えしました。名前から察しがつくとおり、従来からあるlistの仲間です。forward_listの内部構造はlistをほんの少し簡略化したものなのですが、その「ほんの少しの簡略化」によって、クラスが提供するメンバ関数が大きく変わっています。本稿ではforward_listの特性/特徴をlistとの対比とともに解説します。

listの構造とからくり

 forward_listの解説の前にlistについて少しばかりおさらいしておきましょう。標準C++ライブラリが提供するlistは双方向リスト(doubly-linked-list)、すなわち各要素が直後の要素を指すポインタ直前の要素を指すポインタとで数珠繋ぎにすることで要素の集合(順序列)を表現しています。

list-1 : listの要素はこんなものでできている
struct dlink {
  dlink* forward; // 直後のlink
  dlink* backward; // 直前のlink
  dlink() : forward(nullptr), backward(nullptr) {}
  void set_ptr(dlink* p, dlink* n)
    { backward = p; forward = n; }
  virtual ~dlink() {}
};

template<typename T>
struct list_element : dlink {
  T data;
  explicit list_element(const T& d) : data(d) {}
};

 このとき、数珠繋ぎになった一連のlist_element<T>があり、その中の一つ、positionの直前に新たな要素targetを挿入するコードはこんな感じになりますね。

list-2 : positionの直前にtargetを挿入する
// X→position ⇒ X→target→position
// X←position ⇒ X←target←position
#include <cassert>

dlink* insert(dlink* position, dlink* target) {
  assert( position );
  if ( position->backward != nullptr )
    position->backward->forward = target; // X→target
  target->forward = position;         // target→position
  target->backward = position->backward;   // target←X
  position->backward = target;         // position←target
  return target;
}

 同様に一連のlist_element<T>からpositionを削除するには...

list-3 : positionを削除する
// X→position→Y ⇒ X→Y
// X←position←Y ⇒ X←Y
void erase(dlink* position) {
  assert( position );
  // X→position→Y ⇒ X→Y
  if ( position->backward != nullptr )
    position->backward->forward = position->forward;
  // X←position←Y ⇒ X←Y
  if ( position->forward != nullptr )
    position->forward->backward = position->backward;
  delete position;
}

 使ってみましょう。3つのlist_element<string>を数珠繋ぎにしておき、その途中に新たな要素を挿入し、削除します。

list-4 : list-1,2,3に続いて...
#include <iostream>
using namespace std;

template<typename T>
void print_all(const list_element<T>* p) {
  while ( p ) {
    cout << p->data << ' ';
    p = static_cast<list_element<T>*>(p->forward);
  }
  cout << endl;
}

int main() {
  typedef list_element<string> cat;

  cat* zero = new cat("シュウたん");
  cat* one  = new cat("みずき");
  cat* two  = new cat("ろり");

  // 各要素を繋いでおく: zero⇔one⇔two
  zero->set_ptr(nullptr,one); // (null)→zero→one
  one->set_ptr(zero,two);     //         zero→one→two
  two->set_ptr(one,nullptr);  //               one→two→(null)
  print_all(zero);

  // "みずき"の直前に"マグさん"を挿入
  auto hoge = insert(one, new cat("マグさん"));
  print_all(zero);

  // "マグさん"を削除
  erase(hoge);
  print_all(zero);

}
実行結果
シュウたん みずき ろり
シュウたん マグさん みずき ろり
シュウたん みずき ろり

 listのメンバ関数についてもまったく同じ挙動を示し、insertは指定位置の直前に挿入、eraseは指定位置の要素を削除します。

list-5 : listの挙動
#include <iostream>
#include <algorithm>
#include <list>
#include <string>

using namespace std;

int main() {
  list<string> cats;
  cats.push_back("シュウたん");
  cats.push_back("みずき");
  cats.push_back("ろり");
  // "みずき"の位置に
  auto iter = find(cats.begin(), cats.end(), "みずき");
  // "マグさん"を挿入し、
  iter = cats.insert(iter, "マグさん");
  for_each(cats.begin(), cats.end(), 
           [](const string& cat) { cout << cat << ' ';});
  cout << endl;
  // そして削除する
  cats.erase(iter);
  for_each(cats.begin(), cats.end(), 
           [](const string& cat) { cout << cat << ' ';});
  cout << endl;
}
実行結果
シュウたん マグさん みずき ろり
シュウたん みずき ろり

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

  • επιστημη(エピステーメー)

    C++に首まで浸かったプログラマ。 Microsoft MVP, Visual C++ (2004.01~2018.06) "だった"り わんくま同盟でたまにセッションスピーカやったり 中国茶淹れてにわか茶人を気取ってたり、 あと Facebook とか。 著書: - STL標準...

All contents copyright © 2005-2020 Shoeisha Co., Ltd. All rights reserved. ver.1.5