株式会社エス・スリー・フォー

コンテナの種類による計算量の相違

はじめに

「C++はCより遅い」と言われることがよくあります。これはある意味で正しいといえるでしょう。

Cではプログラマが明示的に行なっている、変数に対する初期化/代入/後始末が、C++では暗黙のうちに行われます。

これは、プログラマの負担を軽減してくれる、とても便利な機能には違いありませんが、裏を返せば、プログラマの意識しない(コードに現われない)初期化/代入/後始末が起こるということであり、変数すなわちオブジェクトの初期化/代入/後始末に要する処理時間が大きいほど、「C++はCより遅い」と感じるはずです。

プログラムの中で日常的に用いられる配列やリストなどのコンテナに対する要素の挿入/削除を行なうとき、いったいどれほどの頻度で初期化/代入/後始末が起こっているのか、実際に計測してみることにしましょう。

前準備

まず、計測器をこしらえておきます。これはコンストラクタ/デストラクタ/'='演算子が呼び出された回数をカウントする簡単なクラスです。

/*
 * Counter
 */

class Counter {
  static string message_;
  static bool   on_;
  static int    count_[5];
 
public:
  enum kind_id { 
    dctor = 0, // default constructor
    vctor = 1, // value   constructor
    cctor = 2, // copy    constructor
    dtor  = 3, //         destructor
    copy  = 4  // copy    operator
  };
 
  static void clear();
  static void start(const string& message);
  static void count(kind_id kind);
  static void stop();
  static void report(ostream& stream);
};

string Counter::message_;
bool   Counter::on_;
int    Counter::count_[5];

void Counter::clear() {
  fill(count_, count_+5, 0);
}

void Counter::start(const string& message) {
  message_ = message;
  on_ = true;
}

void Counter::count(kind_id kind) {
  if ( on_ )
    ++count_[kind];
}
    
void Counter::stop() {
  on_ = false;
}

void Counter::report(ostream& stream) {
  stream << message_ << endl;
  stream << " default constructor : " << count_[1] << endl;
  stream << " copy    constructor : " << count_[2] << endl;
  stream << "         destructor  : " << count_[3] << endl;
  stream << " copy    operator    : " << count_[4] << endl;
  stream << " TOTAL               : "
         << accumulate(count_, count_+5, 0) << endl << endl;
}

つぎにコンテナの要素となるクラスElementを用意し、Elementのコンストラクタ/デストラクタ/代入演算子にCounterのメソッドを埋め込んでおきます。

/*
 * Element
 */

class Element {
  typedef int value_type;
  value_type value_;
public:
  Element();
  explicit Element(value_type value);
  Element(const Element&);
  ‾Element();
  Element& operator=(const Element& rhs);
  value_type value() const;
};

Element::Element() : value_(0) {
  Counter::count(Counter::dctor);
}

Element::Element(value_type value) : value_(value) {
  Counter::count(Counter::vctor);
}

Element::Element(const Element& element) : value_(element.value_) {
  Counter::count(Counter::cctor);
}

Element::‾Element() {
  Counter::count(Counter::dtor);
}

Element& Element::operator=(const Element& element) {
  Counter::count(Counter::copy);
  value_ = element.value_;
  return *this;
}

Element::value_type Element::value() const {
  return value_;
}

bool operator==(const Element& element_lhs, const Element& element_rhs) {
  return element_lhs.value() == element_rhs.value();
}

標準C++ライブラリ(STL)の提供するコンテナ:vector/deque/listのそれぞれについて、要素の挿入/削除にどれほどの手間、つまり初期化/代入/後始末の回数をカウントします。

各コンテナの先頭/中央/末尾を要素の挿入点/削除点としましょう。以下に示すのは、vector/deque/listのどれにでも使える挿入/削除関数テンプレート群です。

/*
 * insert
 */

template<class Container>
void insert_first(Container& container, 
                          const Container::value_type& value, const string& message) {
  char buffer[6];
  Counter::clear();
  Counter::start("insert an element at the first of " + message + 
                  " that has " + itoa(container.size(),buffer,10) + " elements");
  container.insert(container.begin(), value);
  Counter::stop();
  Counter::report(cout);
}

template<class Container>
void insert_middle(Container& container, 
                           const Container::value_type& value, const string& message) {
  char buffer[6];
  Counter::clear();
  Counter::start("insert an element at the middle of " + message + 
                  " that has " + itoa(container.size(),buffer,10) + " elements");
  Container::iterator iterator = container.begin();
  advance(iterator, container.size()/2);
  container.insert(iterator, value);
  Counter::stop();
  Counter::report(cout);
}

template<class Container>
void insert_last(Container& container, const Container::value_type& value, 
                         const string& message) {
  char buffer[6];
  Counter::clear();
  Counter::start("insert an element at the last of " + message + 
                  " that has " + itoa(container.size(),buffer,10) + " elements");
  Container::iterator iterator = container.end();
  advance(iterator, -1);
  container.insert(iterator, value);
  Counter::stop();
  Counter::report(cout);
}

/*
 * erase
 */

template<class Container>
void erase_first(Container& container, const string& message) {
  char buffer[6];
  Counter::clear();
  Counter::start("erase an element at the first of " + message + 
                  " that has " + itoa(container.size(),buffer,10) + " elements");
  container.erase(container.begin());
  Counter::stop();
  Counter::report(cout);
}

template<class Container>
void erase_middle(Container& container, const string& message) {
  char buffer[6];
  Counter::clear();
  Counter::start("erase an element at the middle of " + message + 
                  " that has " + itoa(container.size(),buffer,10) + " elements");
  Container::iterator iterator = container.begin();
  advance(iterator, container.size()/2);
  container.erase(iterator);
  Counter::stop();
  Counter::report(cout);
}

template<class Container>
void erase_last(Container& container, const string& message) {
  char buffer[6];
  Counter::clear();
  Counter::start("erase an element at the last of " + message + " 
                 that has " + itoa(container.size(),buffer,10) + " elements");
  Container::iterator iterator = container.end();
  advance(iterator, -1);
  container.erase(iterator);
  Counter::stop();
  Counter::report(cout);
}

/*
 * init : コンテナの初期化
 *    0, 1, 2, .. 9, 0, 1, 2, ... をコンテナに挿入しておく
 */
template<class Container>
void init(Container& container, int n) {
  container.clear();
  for ( int index = 0; index < n; ++index )
    container.push_back(Element(index%10));
}

vectorへの挿入と削除

void vector_insert() {
  vector<Element> element_vector;

  init(element_vector, 100);
  insert_first(element_vector, Element(0), "vector");
  init(element_vector, 100);
  insert_middle(element_vector, Element(0), "vector");
  init(element_vector, 100);
  insert_last(element_vector, Element(0), "vector");
}

void vector_erase() {
  vector<Element> element_vector;

  init(element_vector, 100);
  erase_first(element_vector, "vector");
  init(element_vector, 100);
  erase_middle(element_vector, "vector");
  init(element_vector, 100);
  erase_last(element_vector, "vector");
};

予想通りの結果ですね。vectorは各要素をメモリの連続領域に確保します。したがって、要素の挿入時には挿入点より後にある要素をひとつづつずらして空席を確保しますし、削除時にはその逆にひとつづつずらして空席を埋めます。
頭に近い位置への挿入/削除ほど遅くなることがわかります。

dequeへの挿入と削除

void deque_insert() {
  deque<Element> element_deque;

  init(element_deque, 100);
  insert_first(element_deque, Element(0), "deque");
  init(element_deque, 100);
  insert_middle(element_deque, Element(0), "deque");
  init(element_deque, 100);
  insert_last(element_deque, Element(0), "deque");
}

void deque_erase() {
  deque<Element> element_deque(100);

  init(element_deque, 100);
  erase_first(element_deque, "deque");
  init(element_deque, 100);
  erase_middle(element_deque, "deque");
  init(element_deque, 100);
  erase_last(element_deque, "deque"");
};

dequeのふるまいはvectorとはちょっと違います。要素を格納する連続領域を複数個確保し、挿入/削除に伴う"ずらし"の回数を減らしています。
つまり連続領域をいくつかに分割していますから、末端(先頭側/削除側)での"ずらし"処理が分割された小さな連続領域の中だけで行なえ、それだけ高速になります。それにより、挿入点/削除点が末端に近いほど高速です。

listへの挿入と削除

void list_insert() {
  list<Element> element_list;

  init(element_list, 100);
  insert_first(element_list, Element(0), "list");
  init(element_list, 100);
  insert_middle(element_list, Element(0), "list");
  init(element_list, 100);
  insert_last(element_list, Element(0), "list");
}

void list_erase() {
  list<Element> element_list(100);

  init(element_list, 100);
  erase_first(element_list, "list");
  init(element_list, 100);
  erase_middle(element_list, "list");
  init(element_list, 100);
  erase_last(element_list, "list");
};

listは要素の格納領域は連続ではありません。小さな領域を(次/前の領域を指す)ポインタで繋ぎ、挿入/削除はそのポインタの付け替えを行なうことで実現しています。ですから、list上のどこであれ、vector/dequeで必要であった"ずらし"の処理を行なうことがありません。

2つのremove

標準C++の<algorithm>に、関数テンプレートremoveが定義されています。removeは、ふたつのイテレータで示されるシーケンスの中から特定の値を持つ要素を削除します。ただし、この関数が削除処理まで行なってくれるわけではなく、単に条件を満たす要素の位置に、それ以降にある要素をコピーするだけです。ですから、コンテナ内の要素をremoveで削除処理を行なうには、removeに引き続いて後続する要素をコンテナからeraseしなければなりません。

template<class Container>
void remove_1(Container& container, 
                      const Container::value_type& value, const string& message) {
  char buffer[6];
  Counter::clear();
  Counter::start("[1] remove the specified elements form " + message + 
                  " that has " + itoa(container.size(),buffer,10) + " elements");
  Container::iterator iterator = remove(container.begin(), container.end(), value);
  container.erase(iterator, container.end());
  Counter::stop();
  Counter::report(cout);
}

関数テンプレートremoveを使わない削除ルーチンを書いてみました。コンテナ内の要素をイテレータで取り出し、条件を満たしたらその要素をコンテナから直接eraseします。このときメンバ関数eraseは直後の要素を指すイテレータを返します。

template<class Container>
void remove_2(Container& container, 
                      const Container::value_type& value, const string& message) {
  char buffer[6];
  Counter::clear();
  Counter::start("[2] remove the specified elements form " + message + 
                  " that has "" + itoa(container.size(),buffer,10) + " elements");
  Container::iterator iterator = container.begin();
  while ( iterator != container.end() ) {
    if ( *iterator == value )
      iterator = container.erase(iterator);
    else
      ++iterator;
  }
  Counter::stop();
  Counter::report(cout);
}

では、この2つのアルゴリズムをvector/deque/listに適用してみましょう。

void vector_remove() {
  vector<Element> element_vector;

  init(element_vector, 100);
  remove_1(element_vector, Element(0), "vector");
  init(element_vector, 100);
  remove_2(element_vector, Element(0), "vector");
}

void deque_remove() {
  deque<Element> element_deque;

  init(element_deque, 100);
  remove_1(element_deque, Element(0), "deque");
  init(element_deque, 100);
  remove_2(element_deque, Element(0), "deque");
}

void list_remove() {
  list<Element> element_list;

  init(element_list, 100);
  remove_1(element_list, Element(0), ""list");
  init(element_list, 100);
  remove_2(element_list, Element(0), "list");
}

remove_1の結果は以下のようになりました。

コンテナが異なってもどれも同じ結果ですね。

対してremove_2ではどうでしょう。

ごらんの通り、vector/dequeでは遅くなってしまいました。メンバ関数eraseが呼ばれるたびに"ずらし"が発生するからです。

一方、listではコピーが行われず、速度の向上が見込めることがわかります。

ついでにsortでも調べてみました。

// Elementにoperator>() を追加
bool operator<(const Element& element_lhs, const Element& element_rhs) {
  return element_lhs.value() < element_rhs.value();
}

void vector_sort() {
  vector<Element> element_vector;
  init(element_vector, 100);
  char buffer[6];
  Counter::clear();
  Counter::start(string("sorting a vector that has ") + 
                  itoa(element_vector.size(),buffer,10) + " elements");
  sort(element_vector.begin(), element_vector.end());
  Counter::stop();
  Counter::report(cout);
}

void deque_sort() {
  deque<Element> element_deque;
  init(element_deque, 100);
  char buffer[6];
  Counter::clear();
  Counter::start(string("sorting a deque that has ") + 
                 itoa(element_deque.size(),buffer,10) + " elements");
  sort(element_deque.begin(), element_deque.end());
  Counter::stop();
  Counter::report(cout);
}

void list_sort() {
  list<Element> element_list;
  init(element_list, 100);
  char buffer[6];
  Counter::clear();
  Counter::start(string("sorting a list that has ") + 
                  itoa(element_list.size(),buffer,10) + " elements");
  element_list.sort();
  Counter::stop();
  Counter::report(cout);
}

なるほど、listではsortに伴う要素の交換をポインタの付け替えだけで実現しているようです。