SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

特集記事

「std::vector」観察記録
~慣れ親しんだ可変長配列の仕組みとふるまいを検証してみた

  • X ポスト
  • このエントリーをはてなブックマークに追加

 僕がSTLを触り始めたのはVisual C++のオマケ的扱いだった1996年頃だったでしょうか。当時のSTLはtemplateが現在ほどには充実/安定していなかったこともあって機能的に貧相でしたが、それでもvectorはこの頃から提供されていました。以来ずっとお世話になってきたvector、改めて"vectorの仕組みとふるまいを観察してみよう"が今回のお題です。

  • X ポスト
  • このエントリーをはてなブックマークに追加

イケてる実装

 vectorは可変長配列、内包する要素数の増加に伴って自動的に要素の格納領域を拡張してくれます。C++の教本を通読した程度のスキルでvectorもどき:novice_vectorをこしらえると、ざっとこんなカンジになりますかしら、至極オーソドックスな実装かと存じます。

novice_vector.h
#ifndef NOVICE_VECTOR_H__
#define NOVICE_VECTOR_H__

template<typename T>
class novice_vector {
private:
  T* data_;          // 要素格納領域
  size_t size_;      // 要素数
  size_t capacity_;  // 容量(格納可能な要素数)

public:
  novice_vector() : data_(nullptr), size_(0), capacity_(0) {}
  ~novice_vector() { delete[] data_; }

  size_t size() const { return size_; }
  size_t capacity() const { return capacity_; }
  void   clear() { size_ = 0; }

  // 少なくとも要素n個分の領域を確保する
  void reserve(size_t n) {
    if ( n > capacity_ ) {
      capacity_ = n;
      T* new_data = new T[capacity_];
      T* old_data = data_;
      for ( size_t i = 0; i < size_; ++i ) {
        new_data[i] = old_data[i];
      }
      data_ = new_data;
      delete[] old_data;
    }
  }

  // itemを末尾に追加する
  void push_back(const T& item) {
    // capacityを超えるときは拡張する
    if ( size_ == capacity_ ) {
      reserve(capacity_ == 0 ? 1 : capacity_*2);
    }
    data_[size_++] = item;
  }

  // そのほかモロモロ...

};

#endif

 novice_vectorと本家(?)vectorのふるまいを比べてみます。コンストラクト/デストラクト/コピー(代入)が行わるたびにその旨をプリントするクラス: itemを用意しました。

item.h
#ifndef ITEM_H__
#define ITEM_H__

#include <iosfwd>

class item {
private:
  int x_;
  int y_;
public:
  item();
  item(int x, int y =0);
  item(const item& other);
  item(item&& other);
  ~item();

  item& operator=(const item& other);
  item& operator=(item&& other);

  std::ostream& print_on(std::ostream& stream) const;
};

inline std::ostream& operator<<(std::ostream& stream, const item& x) {
  return x.print_on(stream);
}
#endif
item.cpp
#include "item.h"
#include <iostream>

using namespace std;

item::item() : x_(0), y_(0) {
  cout << "ctor()" << endl;
}

item::item(int x, int y) : x_(x), y_(y) {
  cout << "ctor(int x, int y) x=" << x << ", y=" << y << endl; 
}

item::item(const item& other) : x_(other.x_), y_(other.y_) {
  cout << "ctor(const item& other) other=" << other << endl;
}

item::item(item&& other) : x_(other.x_), y_(other.y_) {
  cout << "ctor(item&& other) other=" << other << endl;
}

item::~item() {
  cout << "dtor() *this=" << *this << endl;
}

item& item::operator=(const item& other) {
  cout << "copy(const item& other) other=" << other << endl;
  x_ = other.x_;
  y_ = other.y_;
  return *this;
}

item& item::operator=(item&& other) {
  cout << "copy(item&& other) other=" << other << endl;
  x_ = other.x_;
  y_ = other.y_;
  return *this;
}

std::ostream& item::print_on(std::ostream& stream) const {
  return stream << '{' << x_ << ',' << y_ << '}';
}

 novice_vector<item>とstd::vector<item>に要素をpush_back()したときのふるまいを観察しましょう。

VectorExample01.cpp
#include <iostream>
#include <vector>

#include "item.h"
#include "novice_vector.h"

using namespace std;

int main() {
  {
  cout << "\n----- novice_vector<item>::push_back()" << endl;
  novice_vector<item> c;
  c.reserve(5);
  cout << "----- push_back-1" << endl;
  c.push_back(item());
  cout << "----- push_back-2" << endl;
  c.push_back(item(1));
  cout << "-----" << endl;
  }

  {
  cout << "\n----- vector<item>::push_back()" << endl;
  vector<item> c;
  c.reserve(5);
  cout << "----- push_back-1" << endl;
  c.push_back(item());
  cout << "----- push_back-2" << endl;
  c.push_back(item(1));
  cout << "-----" << endl;
  }

}
fig01
fig01

 ……違いますね。要素を格納する領域の確保:reserve(5)したとき、novice_vectorは要素(item)のデフォルト・コンストラクタを5回(対になるデストラクタも5回)呼んでいますが、vectorにはその呼び出しが見当たりません。加えてpush_back()の引数からコンテナ内要素へのコピー時に、vectorは右辺値参照コンストラクトを行っています。Visual C++ 12.0のvectorは効率重視のイケてる実装がなされているみたいです。

 効率を云々するからにはC++11から導入された右辺値参照(R-value reference)について、少しばかり語っておきましょう。

 右辺値(R-value)はその名のとおり、代入文の右辺に現れる値です。代表的なのは関数の戻り値、y = f(x);においてf(x)が返す値(ただし参照を除く)です。f(x)が返した値がyに代入されたあと、その値はお役御免となりいずれ廃棄される運命です。せっかく作った右辺値を捨ててしまうのはもったいない、使えるものは使って時間と空間の無駄を抑えたいシチュエーションで右辺値参照が用いられます。サンプルをお見せしましょう、さきほどのnovice_vector<T>にコピー・コンストラクタを追加します。

novice_vector.h(抜粋)
template<typename T>
class novice_vector {
  ...
public:

  novice_vector(const novice_vector& other) : size_(other.size_), capacity_(other.capacity_) {
    data_ = new T[capacity_];
    for ( size_t i = 0; i < size_; ++i ) {
      data_[i] = other.data_[i];
    }
  }
  ...
};

 novice_vector<item>を返す関数: make_vector()を用意し、その戻り値でnovice_vector<item>をコンストラクトしたときの様子を見てみましょう。

VectorExample02.cpp
#include <iostream>
#include <vector>

#include "item.h"
#include "novice_vector.h"

using namespace std;

template<typename Vec>
Vec make_vector(size_t n) {
  Vec result;
  result.reserve(n);
  for ( size_t i = 0; i < n; ++i ) result.push_back(item());
  cout << "----- vector made!" << endl;
  return result;
}

int main() {
  {
  cout << "\n----- novice_vector<item>" << endl;
  cout << "----- novice_vector<item> copy-ctor" << endl;
  novice_vector<item> c(make_vector<novice_vector<item>>(3));
  cout << "-----" << endl;
  }
}
fig02
fig02

 make_novice(3)が戻り値であるnovice_vector<item>を返して以降、itemのコピーが3回、戻り値の廃棄に伴うデストラクトが3回行われています。

注意

 Visual C++の最適化オプションによっては、このような挙動となりません。Debugモードで指定されている/Od(最適化なし)での結果です。

 では、novice_vector<T> に右辺値参照を引数に取るコンストラクタを追加します。捨てられる運命の右辺値を有効活用しましょう、取り壊し寸前のおうちから家財道具を運び出します。

novice_vector.h(抜粋)
template<typename T>
class novice_vector {
  ...

  // 右辺値参照コンストラクタ(&&が右辺値参照を表す)
  novice_vector(novice_vector&& other) : size_(other.size_), capacity_(other.capacity_) {
    data_ = other.data_;    // 家財道具を運び出し、新居に据える
    other.data_ = nullptr;  // 右辺値廃棄時の辻褄を合わせる
    other.size_ = 0;
    other.capacity_ = 0;
  }

  ...
};
fig03
fig03

 ご覧のとおり、右辺値が内包していた3つの要素は格納領域ごと(コピーではなく)移動されたため、右辺値のデストラクトに伴うitemの廃棄が行われていません。右辺値参照をうまく使えば、コンストラクト/デストラクト/コピーのコストが高いオブジェクトに対し、時間の空間の無駄な消費を抑えることができます。C++11ではvectorに限らずほとんどのコンテナで右辺値参照コンストラクタ/コピー演算子が追加されています。

 それに併せ、vectorにはコスト高な操作に代わるメンバ関数が追加されています。emplace/emplace_backがそれ。"emplace"は配置する/据え付けるといった意味で、insert/push_backが引数に渡された要素をコンテナ内にコピーするのに対し、emplace/emplace_backは要素のコンストラクトに必要な引数をそのまま受け取り、コンテナ内に直接"据え付け"ます。

VectorExample04.cpp
#include <iostream>
#include <vector>

#include "item.h"

using namespace std;


int main() {
  {
  cout << "\n----- vector<item>::push_back()" << endl;
  vector<item> c;
  c.reserve(10);
  cout << "----- push_back-1" << endl;
  c.push_back(item());
  cout << "----- push_back-2" << endl;
  c.push_back(item(1,2));
  cout << "-----" << endl;
  }

  {
  cout << "\n----- vector<item>::emplace_back()" << endl;
  vector<item> c;
  c.reserve(10);
  cout << "--- emplace_back-1" << endl;
  c.emplace_back();
  cout << "--- emplace_back-2" << endl;
  c.emplace_back(1,2);
  cout << "-----" << endl;
  }

}
fig04
fig04

次のページ
メモリーの使われ方

この記事は参考になりましたか?

  • X ポスト
  • このエントリーをはてなブックマークに追加
特集記事連載記事一覧

もっと読む

この記事の著者

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

C++に首まで浸かったプログラマ。Microsoft MVP, Visual C++ (2004.01~2018.06) "だった"りわんくま同盟でたまにセッションスピーカやったり中国茶淹れてにわか茶...

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この記事は参考になりましたか?

この記事をシェア

  • X ポスト
  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/7849 2014/07/23 14:00

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング