こんにちは、kaageです。
C++のstd::vectorを使っていて、遅い、と感じたことはありませんか？僕はありません。
それはさておき、std::vectorより要素の挿入が速く、（ほぼ）同等の機能を搭載したvectorを実装してみました。
速度が圧倒的に優位というわけでもないですが、C++の言語機能を網羅的に知るという面で意味があると思うので、記事にします。
なお、配列外参照などに関しての安全性は全く保証していません。（というより、速い最大の理由はこれです）
std::vectorとは
C++を使っているなら知っているとは思いますが、一応std::vectorの説明をします。
std::vectorは、C++の標準ライブラリに含まれる可変長配列です。要素数に応じて長さを変化させます。
後方への挿入、後方からの削除は $O(1)$, 任意位置への挿入は、挿入位置を $x$, 長さを $n$ として、$O(n-x)$ が保証されています。
同様に、一般的な配列に要素が連続して配置されると考えれば、直感に対応した計算量がだいたい保証されています。（詳しくはリファレンスを見ましょう。）
実装
さて、ここからは詳細に実装を見ていきますが、競技プログラマーにあまり知られていなさそうな言語仕様には注釈を加えていきます。
template
まず、クラステンプレートで受け取る型からです。
template<class T, class Alloc = std::allocator<T>>
class Vector {
///...
アロケータに馴染みがない方も多いかと思いますが、アロケータというのはメモリの管理を請け負うクラスです。
デフォルトは標準ライブラリで実装されているstd::allocatorを使います。
using 宣言
using hoge = fuga;
で、型名のエイリアスを定義できます。
ここでは、アロケータの中間インターフェースであるstd::allocator_traitsと、vectorを使う上で要件的に必要となる型たちを宣言しておきます。
using traits = std::allocator_traits<Alloc>;
public:
using value_type = T;
using allocator_type = Alloc;
using size_type = unsigned int;
using difference_type = int;
using reference = T&;
using const_reference = const T&;
using pointer = typename traits::pointer;
using const_pointer = typename traits::const_pointer;
メンバ変数・typenameのverify
プライベートで配列のポインタ、長さ、取得した配列の長さを保持しておきます。
pointer e;
size_type length = 0, cap = 1;
Alloc alloc;
また、static_assertというマクロを利用して、vectorのデータ型とアロケータのデータ型が一致していることを確認します。constな要素のコンテナの作成はSTLでも禁止されているので、ここでも禁止しておきます。
static_assertはコンパイル時にチェックされ、型の情報がこれに合っていない場合コンパイルエラーが出ます。
型の一致やconst性を調べるには、std::is_sameやstd::is_constが使えます。
static_assert(std::is_same<T, typename Alloc::value_type>::value, "The allocator value type is not matched the vector value type.");
static_assert(!std::is_const<T>::value, "This library forbids containers of const elements");
コンストラクタ・デストラクタ・代入演算子
コンストラクタとデストラクタについてです。
Vector() :Vector(Alloc()) {}
explicit Vector(const Alloc& a)noexcept :alloc(a) {
e = alloc.allocate(cap);
}
explicit Vector(size_type n, const Alloc& a = Alloc()) :alloc(a) {
while (cap < n)cap *= 2;
e = alloc.allocate(cap);
rep(i, n)emplace_back();
}
explicit Vector(size_type n, const_reference value, const Alloc& a = Alloc()) :alloc(a) {
while (cap < n)cap *= 2;
e = alloc.allocate(cap);
rep(i, n)emplace_back(value);
}
template<class InputIter>
Vector(InputIter first, InputIter last, const Alloc& a = Alloc()) :alloc(a) {
e = alloc.allocate(cap);
for (InputIter i = first; i != last; i++) {
emplace_back(*i);
}
}
Vector(const Vector& x, const Alloc& a = Alloc()) :alloc(a) {
while (cap < x.length)cap *= 2;
length = x.length;
e = alloc.allocate(cap);
rep(i, x.length)traits::construct(alloc, e + i, *(x.e + i));
}
Vector(Vector&& x, const Alloc& a = Alloc())noexcept :alloc(a) {
cap = x.cap;
length = x.length;
e = x.e;
x.e = nullptr;
}
~Vector() {
if (e != nullptr) {
rep(i, length)traits::destroy(alloc, e + i);
alloc.deallocate(e, cap);
}
}
Vector& operator=(const Vector& x) {
rep(i, length)traits::destroy(alloc, e + i);
alloc.deallocate(e, cap);
length = x.length;
cap = 1;
while (cap < length)cap *= 2;
e = alloc.allocate(cap);
rep(i, length)traits::construct(alloc, e + i, *(x.e + i));
return *this;
}
Vector& operator=(Vector&& x) {
rep(i, length)traits::destroy(alloc, e + i);
alloc.deallocate(e, cap);
cap = x.cap;
length = x.length;
e = x.e;
x.e = nullptr;
return *this;
}
まずは、explicitキーワードです。これは明示的でないコンストラクタの呼び出しを禁止します。
つまり、このexplicitがないと、次のようなコードが有効になります。
Vector<int> a = 1;
ここでは、explicitキーワードを用いて、上のコードのように、整数などが暗黙的に
Vector(size_type n, const Alloc& a = Alloc())
などのコンストラクタに渡されることを防いでいます。
次に、noexceptキーワードです。
これは、例外を投げないことを明示的に示します。
他に特に注目すべきなのは、Vector&&を用いた右辺値参照です。
C++では、明確に左辺値と右辺値が区別されます。
右辺値とは、誤解を恐れずに言えば、メモリ上にアドレスを持たない一時オブジェクトです。
リテラルや、関数の返り値などがこれにあたります。
右辺値に対しての操作だけを別に記述することで、無駄な処理を省くことが可能です。
たとえば、次のようなコードを考えてみます。
Vector<int> func(){ return Vector<int>(1000000); }
int main(){
Vector<int> vec = func();
}
ここで、右辺値を取らないコンストラクタ、
Vector(const Vector& x, const Alloc& a = Alloc())
が呼ばれると、新しいVectorでメモリが確保され、func()から返ってきたVectorの要素が、100万回再構築されます。
しかし、これは明らかな無駄です。引数に渡されたfunc()の返り値は、このコンストラクタの処理終了後にはすぐ破棄されるので、そのメモリ領域を新しいVectorと入れ替えてしまえば、再構築が一切必要ないからです。（もっとも、わざわざ入れ替える必要もなく、古いVectorのメンバは、危険でない範囲で自由にしておけます。）
そこで、右辺値をとる新たなコンストラクタを作ります。
Vector(Vector&& x, const Alloc& a = Alloc())
ここでは、保持しているポインタをxのものに差し替えています。
これで、低コストでVectorのコピーができました。
気を付けなければいけないのは、xが保持していた領域が、xのデストラクタ呼び出しに伴って削除されないようにすることです。
領域の所有権が新しいVectorに移った以上、xに所有権の保持を続けさせてはなりません。
そこで、xの持っていたポインタはここでnullptrに差し替えられています。
アロケータによるメモリ解放時にはnullptrチェックを行って、nullptrをAlloc::deallocateに渡さないようにしています。
代入演算子でも同様の処理を行い、右辺値に対する処理の特殊化を行っています。
その他のメンバ関数
その他のメンバ関数もいい感じに実装します。
private:
void extension() {
pointer e_ = alloc.allocate(cap * 2);
rep(i, length)traits::construct(alloc, e_ + i, *(e + i));
rep(i, length)traits::destroy(alloc, e + i);
alloc.deallocate(e, cap);
e = e_;
cap *= 2;
}
void extension(size_type n) {
unsigned int r = 1;
while (cap * r < n)r *= 2;
if (r == 1)return;
pointer e_ = alloc.allocate(cap * r);
rep(i, length)traits::construct(alloc, e_ + i, *(e + i));
rep(i, length)traits::destroy(alloc, e + i);
alloc.deallocate(e, cap);
e = e_;
cap *= r;
}
public:
template<class InputIter>
void assign(InputIter first, InputIter last) {
size_type cnt = 0;
for (InputIter i = first; i != last; i++) {
if (cnt == cap) {
length = std::max(length, cnt);
extension();
}
traits::construct(alloc, e + cnt, *i);
cnt++;
}
}
void assign(size_type n, const_reference value) {
extension(n);
std::fill(e, e + n, value);
}
template<class... Args>
void emplace_back(Args&&... args) {
if (length == cap)extension();
traits::construct(alloc, e + length, std::forward<Args>(args)...);
length++;
}
void push_back(const_reference value) {
emplace_back(value);
}
void push_back(T&& value) {
emplace_back(std::move(value));
}
void pop_back() {
traits::destroy(alloc, e + length);
length--;
}
void reserve(size_type n) {
extension(n);
}
iterator erase(iterator pos) {
const iterator res = pos;
iterator t = pos; t++;
for (iterator i = pos; t != end(); i++, t++) {
*i = std::move(*t);
}
pop_back();
return res;
}
iterator erase(iterator first, iterator last) {
const iterator res = first;
typename iterator::difference_type d = last - first;
for (iterator i = first; i + d != end(); i++) {
*i = std::move(*(i + d));
}
rep(i, d)pop_back();
return res;
}
void swap(Vector& x) {
std::swap(length, x.length);
std::swap(cap, x.cap);
std::swap(e, x.e);
}
void clear() {
while (length)pop_back();
}
size_type size()const {
return length;
}
void resize(size_type n, const_reference value = T()) {
extension(n);
while (n < length)pop_back();
std::fill(e, e + n, value);
}
size_type capacity()const {
return cap;
}
bool empty()const {
return !length;
}
reference operator[](const size_type pos) {
return e[pos];
}
pointer data() {
return e;
}
reference front() {
return *e;
}
reference back() {
return *(e + length - 1);
}
emplace_backなどで利用している、可変引数テンプレートについて少しだけ解説します。
次のような感じで、引数の数を可変にしてテンプレート化できます。
template<class... Args>
void func1(int a, Args... args){ // こうして再帰的に値を取り出していける
// Something
}
template<class... Args>
void func2(Args... args){
func1(args...); // 他の関数に渡すときはこうして展開する
}
引数の数が不明なときに使えます。
イテレータ
ここで、コンテナライブラリの肝、イテレータが出てきます。
そこまで理解が難しいところではありませんが、いかんせん実装量が多いです。
通常のイテレータとconstなイテレータ2つに対して実装を提供する必要があります。幸い、逆向きイテレータについてはSTLにラッパーがあるので、実装は2種類だけで済みます。
実装を貼ります。（長いです。）
Vectorの内包クラスとして実装します。
class iterator {
public:
using difference_type = int;
using value_type = Vector::value_type;
using pointer = Vector::pointer;
using reference = Vector::reference;
using iterator_category = std::random_access_iterator_tag;
private:
T* p;
public:
iterator()noexcept :p(nullptr) {}
iterator(Vector* base, difference_type index) noexcept :p(base->e + index) {}
iterator(const iterator& i) :p(i.p) {}
iterator& operator++() {
p++;
return *this;
}
iterator operator++(int) {
iterator res = *this;
p++;
return res;
}
iterator operator+(const difference_type& x)const {
return iterator(*this) += x;
}
iterator& operator+=(const difference_type& x) {
p += x;
return *this;
}
iterator& operator--() {
p--;
return *this;
}
iterator operator--(int) {
iterator res = *this;
p--;
return this;
}
iterator operator-(const difference_type& x)const {
return iterator(*this) -= x;
}
difference_type operator-(const iterator& i)const {
return p - i.p;
}
iterator& operator-=(const difference_type& x) {
p -= x;
return *this;
}
reference operator*()const {
return *p;
}
reference operator[](const difference_type& x)const {
return *(*this + x);
}
bool operator<(const iterator& i)const {
return p < i.p;
}
bool operator<=(const iterator& i)const {
return p <= i.p;
}
bool operator==(const iterator& i)const {
return p == i.p;
}
bool operator>(const iterator& i)const {
return p > i.p;
}
bool operator>=(const iterator& i)const {
return p >= i.p;
}
bool operator!=(const iterator& i)const {
return p != i.p;
}
};
class const_iterator {
public:
using difference_type = int;
using value_type = Vector::value_type;
using pointer = const Vector::pointer;
using reference = const Vector::reference;
using iterator_category = std::random_access_iterator_tag;
private:
const T* p;
public:
const_iterator()noexcept :p(nullptr) {}
const_iterator(Vector* base, difference_type index) noexcept :p(base->e + index) {}
const_iterator(const iterator& i) :p(i.p) {}
const_iterator(const const_iterator& i) :p(i.p) {}
const_iterator& operator++() {
p++;
return *this;
}
const_iterator operator++(int) {
const_iterator res = *this;
p++;
return res;
}
const_iterator operator+(const difference_type& x)const {
return const_iterator(*this) += x;
}
const_iterator& operator+=(const difference_type& x) {
p += x;
return *this;
}
const_iterator& operator--() {
p--;
return *this;
}
const_iterator operator--(int) {
const_iterator res = *this;
p--;
return this;
}
const_iterator operator-(const difference_type& x)const {
return const_iterator(*this) -= x;
}
difference_type operator-(const const_iterator& i)const {
return p - i.p;
}
const_iterator& operator-=(const difference_type& x) {
p -= x;
return *this;
}
reference operator*()const {
return *p;
}
reference operator[](const difference_type& x)const {
return *(*this + x);
}
bool operator<(const const_iterator& i)const {
return p < i.p;
}
bool operator<=(const const_iterator& i)const {
return p <= i.p;
}
bool operator==(const const_iterator& i)const {
return p == i.p;
}
bool operator>(const const_iterator& i)const {
return p > i.p;
}
bool operator>=(const const_iterator& i)const {
return p >= i.p;
}
bool operator!=(const const_iterator& i)const {
return p != i.p;
}
};
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
各iteratorクラス内のusing宣言は、イテレータの要件として定められており、STLライブラリなどから参照されることも多いです。
あとは、イテレータを取得する関数を実装して、完成です。
iterator begin() noexcept {
return iterator(this, 0);
}
const_iterator begin()const noexcept {
return const_iterator(this, 0);
}
const_iterator cbegin()const noexcept {
return const_iterator(this, 0);
}
iterator rbegin()noexcept {
return reverse_iterator(this, 0);
}
const_iterator rbegin()const noexcept {
return const_reverse_iterator(this, 0);
}
const_iterator crbegin()const noexcept {
return const_reverse_iterator(this, 0);
}
iterator end() noexcept {
return iterator(this, length);
}
const_iterator end()const noexcept {
return const_iterator(this, length);
}
const_iterator cend()const noexcept {
return const_iterator(this, length);
}
iterator rend()noexcept {
return reverse_iterator(this, length);
}
const_iterator rend()const noexcept {
return const_reverse_iterator(this, length);
}
const_iterator crend()const noexcept {
return const_reverse_iterator(this, length);
}
速度計測
10000000個emplace_back
std::vector:159ms
Vector:118ms
10000000個emplace_back+10000000個pop_back
std::vector:195ms
Vector:126ms
10000000個emplace_back+std::sortでソート
std::vector:425ms
Vector:487ms
おわりに
ほとんど使わないinsert,emplaceは省略してしまいました（ダメ）
ソートすると結構遅い（イテレータ操作？）ので、改良したらまたここに掲載します。
みなさんも、雑な実装でもいいのでVectorを実装してC++に親しみましょう（？）