イケてる実装
vectorは可変長配列、内包する要素数の増加に伴って自動的に要素の格納領域を拡張してくれます。C++の教本を通読した程度のスキルでvectorもどき:novice_vectorをこしらえると、ざっとこんなカンジになりますかしら、至極オーソドックスな実装かと存じます。
#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を用意しました。
#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
#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()したときのふるまいを観察しましょう。
#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;
}
}
……違いますね。要素を格納する領域の確保: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>にコピー・コンストラクタを追加します。
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>をコンストラクトしたときの様子を見てみましょう。
#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;
}
}
make_novice(3)が戻り値であるnovice_vector<item>を返して以降、itemのコピーが3回、戻り値の廃棄に伴うデストラクトが3回行われています。
Visual C++の最適化オプションによっては、このような挙動となりません。Debugモードで指定されている/Od（最適化なし）での結果です。
では、novice_vector<T> に右辺値参照を引数に取るコンストラクタを追加します。捨てられる運命の右辺値を有効活用しましょう、取り壊し寸前のおうちから家財道具を運び出します。
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;
}
...
};
ご覧のとおり、右辺値が内包していた3つの要素は格納領域ごと（コピーではなく）移動されたため、右辺値のデストラクトに伴うitemの廃棄が行われていません。右辺値参照をうまく使えば、コンストラクト／デストラクト／コピーのコストが高いオブジェクトに対し、時間の空間の無駄な消費を抑えることができます。C++11ではvectorに限らずほとんどのコンテナで右辺値参照コンストラクタ／コピー演算子が追加されています。
それに併せ、vectorにはコスト高な操作に代わるメンバ関数が追加されています。emplace／emplace_backがそれ。"emplace"は配置する／据え付けるといった意味で、insert／push_backが引数に渡された要素をコンテナ内にコピーするのに対し、emplace／emplace_backは要素のコンストラクトに必要な引数をそのまま受け取り、コンテナ内に直接"据え付け"ます。
#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;
}
}
