vectorの実装 : 基礎

クラス、ポインター、メモリー確保を学んだので、とうとうコンテナーの中でも一番有名なstd::vectorを実装する用意ができた。しかしその前に、アロケーターについて学ぶ必要がある。

std::vectorはstd::vector<T>のように要素の型Tを指定して使うので、以下のようになっていると思う読者もいるだろう。

namespace std {
    template < typename T >
    struct vector ;
}

実際には以下のようになっている。

namespace std {
    template < typename T, typename allocator = allocator<T> >
    struct vector ;
}

std::allocator<T>というのは標準ライブラリのアロケーターだ。アロケーターは生のメモリーの確保と解放をするライブラリだ。デフォルトでstd::allocator<T>が渡されるので、普段ユーザーはアロケーターを意識することはない。

std::vectorはmallocやoperator newを直接使わずアロケーターを使ってメモリー確保を行う。

アロケーターはテンプレートパラメーターで指定できる。何らかの理由で独自のメモリー確保を行いたい場合、独自のアロケーターを実装してコンテナーに渡すことができる。

// 独自のアロケーター
template < typename T >
struct custom_allocator
{
    // ...
} ;

template < typename T >
using custom_vector = std::vector< T, custom_allocator<T> > ;

int main()
{
    custom_vector<int> v ;
    // 独自のアロケーターを使ったメモリー確保
    v.push_back(0) ;
}

`std::allocator<T>`の概要

std::allocator<T>はT型を構築できる生のメモリーを確保するために以下のようになっている。

namespace std {
template<class T> class allocator {
    // ネストされた型名の宣言
    using value_type = T;
    using size_type = size_t;
    using difference_type = ptrdiff_t;
    using propagate_on_container_move_assignment = true_type;
    using is_always_equal = true_type;

    // コンストラクター
    // constexprはまだ学んでいない
    constexpr allocator() noexcept;
    constexpr allocator(const allocator&) noexcept;
    template<class U> constexpr allocator(const allocator<U>&) noexcept;
    ~ allocator();
    // コピー代入演算子
    allocator& operator=(const allocator&) = default;

    // ここが重要
    [[nodiscard]] T* allocate(size_t n);
    void deallocate(T* p, size_t n);
};
}

constexprというキーワードがあるが、ここでは気にする必要はない。あとで学ぶ。

重要なのはメモリー確保をするallocateと、メモリー解放をするdeallocateだ。

`std::allocator<T>`の使い方

標準ライブラリのアロケーター、std::allocator<T>は、T型を構築できる生のメモリーの確保と解放をするライブラリだ。重要なメンバーは以下のとおり。

// メモリー確保
[[nodiscard]] T* allocate(size_t n);
// メモリー解放
void deallocate(T* p, size_t n);

allocate(n)はT型のn個の配列を構築できるだけの生のメモリーを確保してその先頭へのポインターを返す。

deallocate(p, n)はallocate(n)で確保されたメモリーを解放する。

int main()
{
    std::allocator<std::string> a ;
    // 生のメモリー確保
    // std::string [1]分のメモリーサイズ
    std::string * p = a.allocate(1) ;
    // メモリー解放
    a.deallocate( p, 1 ) ;
}

allocateには[[nodiscard]]という属性が付いている。これにより戻り値を無視すると警告が出る。

int main()
{
    std::allocator<int> a ;
    // 警告、戻り値が無視されている
    a.allocate(1) ;

    // OK
    int * p = a.allocate(1) ;
}

確保されるのが生のメモリーだということに注意したい。実際にT型の値として使うには、newによる構築が必要だ。

int main()
{
    std::allocator<std::string> a ;
    // 生のメモリー確保
    // std::string [1]分のメモリーサイズ
    std::string * p = a.allocate(1) ;
    // 構築
    std::string * s = new(p) std::string("hello") ;
    // 明示的なデストラクター呼び出し
    s->~basic_string() ;
    // メモリー解放
    a.deallocate( p, 1 ) ;
}

このように書くのはとても面倒だ。特にstd::stringの明示的なデストラクター呼び出しs->~basic_stringが面倒だ。なぜs->~stringではだめなのか。

実はstd::stringは以下のようなクラステンプレートになっている。

namespace std {
template <
    typename charT,
    typename traits     = char_traits<charT>,
    typename Allocator  = allocator<charT>>
class basic_string
{
    // デストラクター
    ~basic_string() ;
} ;

}

本当のクラス名はbasic_stringなのだ。

普段は使っているstd::stringというのは、以下のようなエイリアスだ。

namespace std {
using string = basic_string<char> ;
}

明示的なデストラクター呼び出しにエイリアスは使えないので、本当のクラス名であるbasic_stringを直接指定しなければならない。

この問題はテンプレートで解決できる。

// 明示的なデストラクター呼び出しをする関数テンプレート
template < typename T >
void destroy_at( T * location )
{
    location->~T() ;
}

このようにテンプレートで書くことによって、クラス名を意識せずに破棄ができる。

// 破棄
destroy_at( s ) ;

このようなコードを書くのは面倒なので、標準ライブラリにはstd::destroy_atがある。また、これらをひっくるめたアロケーターを使うためのライブラリであるallocator_traitsがある。

`std::allocator_traits<Alloc>`

std::allocator_traits<Alloc>はアロケーターAllocを簡単に使うためのライブラリだ。

allocator_traits<Alloc>はアロケーターの型Allocを指定して使う。

std::allocator<int> a ;
int * p = a.allocate(1) ;

と書く代わりに、

std::allocator<int> a ;
int * p = std::allocator_traits< std::allocator<int> >::allocate( a, 1 ) ;

と書く。

これはとても使いづらいので、allocator_traitsのエイリアスを書くとよい。

std::allocator<int> a ;
// エイリアス
using traits = std::allocator_traits< std::allocator<int> > ;
int * p = traits::allocate( a, 1 ) ;

これもまだ書きにくいので、decltypeを使う。decltype(expr)は式exprの型として使える機能だ。

// int型
decltype(0) a ;
// double型
decltype(0.0) b ;
// int型
decltype( 1 + 1 ) c ;
// std::string型
decltype( "hello"s ) c ;

decltypeを使うと以下のように書ける。

std::allocator<int> a ;
// エイリアス
using traits = std::allocator_traits< decltype(a) > ;
int * p = traits::allocate( a, 1 ) ;

allocator_traitsはアロケーターを使った生のメモリーの確保、解放と、そのメモリー上にオブジェクトを構築、破棄する機能を提供している。

int main()
{
    std::allocator<std::string> a ;
    // allocator_traits型
    using traits = std::allocator_traits<decltype(a)> ;

    // 生のメモリー確保
    std::string * p = traits::allocate( a, 1 ) ;
    // 構築
    std::string * s = traits::construct( a, p, "hello") ;
    // 破棄
    traits::destroy( a, s ) ;
    // メモリー解放
    traits::deallocate( a, p, 1 ) ;
}

T型のN個の配列を構築するには、まずN個の生のメモリーを確保し、

std::allocator<std::string> a ;
using traits = std::allocator_traits<decltype(a)> ;
std::string * p = traits::allocate( a, N ) ;

N回の構築を行う。

for ( auto i = p, last = p + N ; i != last ; ++i )
{
    traits::construct( a, i, "hello" ) ;
}

破棄もN回行う。

for ( auto i = p + N, first = p ; i != first ; --i )
{
    traits::destroy( a, i ) ;
}

生のメモリーを破棄する。

traits::deallocate( a, p, N ) ;

簡易vectorの概要

準備はできた。簡易的なvectorを実装していこう。以下が本書で実装する簡易vectorだ。

template < typename T, typename Allocator = std::allocator<T> >
class vector
{
private :
    // データメンバー
public :
    // value_typeなどネストされた型名
    using value_type = T ;
    // コンストラクター
    vector( std::size_t n = 0, Allocator a = Allocator() ) ;
    // デストラクター
    ~vector() ;
    // コピー
    vector( const vector & x ) ;
    vector & operator =( const vector & x ) ;

    // 要素アクセス
    void push_back( const T & x ) ;
    T & operator []( std::size_t i ) noexcept ;

    // イテレーターアクセス
    iterator begin() noexcept ;
    iterator end() noexcept ;
} ;

これだけの簡易vectorでもかなり便利に使える。

例えば要素数を定めて配列のようにアクセスできる。

vector v(100) ;
for ( auto i = 0 ; i != 100 ; ++i )
    v[i] = i ;

イテレーターも使える。

std::for_each( std::begin(v), std::end(v),
    []( auto x ) { std::cout << x ; } ) ;

要素を際限なく追加できる。

std::copy(
    std::istream_iterator<int>(std::cin), std::istream_iterator<int>(), 
    std::back_inserter(v) ) ;

classとアクセス指定

簡易vectorの概要では、まだ学んでいない機能が使われていた。classとpublicとprivateだ。

C++のクラスにはアクセス指定がある。public:とprivate:だ。アクセス指定が書かれたあと、別のアクセス指定が現れるまでの間のメンバーは、アクセス指定の影響を受ける。

struct C
{
public :
    // publicなメンバー
    int public_member1 ;
    int public_member2 ;
private :
    // privateなメンバー
    int private_member1 ;
    int private_member2 ;
public :
    // 再びpublicなメンバー
    int public_member3 ;    
} ;

publicメンバーはクラスの外から使うことができる。

struct C
{
public :
    int data_member ;
    void member_function() { }
} ;

int main()
{
    C c;
    // クラスの外から使う
    c.data_member = 0 ;
    c.member_function() ;
}

privateメンバーはクラスの外から使うことができない。

struct C
{
private :
    int data_member ;
    void member_function() ;
} ;

int main()
{
    C c ;
    // エラー
    c.data_member = 0 ;
    // エラー
    c.member_function() ;
}

コンストラクターもアクセス指定の対象になる。

struct C
{
public :
    C(int) { }
private :
    C(double) { }
} ;

int main()
{
    // OK
    C pub(0) ;
    // エラー
    C pri(0.0) ;
}

この例では、C::C(int)はpublicメンバーなのでクラスの外から使えるが、C::C(double)はprivateメンバーなのでクラスの外からは使えない。

privateメンバーはクラスの中から使うことができる。クラスの中であればどのアクセス指定のメンバーからでも使える。

struct C
{
public :
    void f()
    {
        // ここはクラスの中
        data_member = 0 ;
        member_function() ;
    }

private :
    int data_member ;
    void member_function() { }
} ;

privateメンバーの目的はクラスの外から使ってほしくないメンバーを守ることだ。例えば以下のようにコンストラクターでnewしてデストラクターでdeleteするようなクラスがあるとする。

class dynamic_int
{
private :
    int * ptr ;
public :
    dynamic_int( int value = 0  )
        : ptr( new int(value) )
    { }
    ~dynamic_int()
    {
        delete ptr ;
    }
} ;

もしdynamic_int::ptrがpublicメンバーだった場合、以下のようなコードのコンパイルが通ってしまう。

int main()
{
    dynamic_int i ;
    delete i.ptr ;
    int obj{} ;
    i.ptr = &obj ;
}

このプログラムがdynamic_intのデストラクターを呼ぶと、main関数のローカル変数のポインターに対してdeleteを呼び出してしまう。これは未定義の挙動となる。

外部から使われては困るメンバーをprivateメンバーにすることでこの問題はコンパイル時にエラーにでき、未然に回避できる。

クラスを定義するにはキーワードとしてstructもしくはclassを使う。

struct  foo { } ;
class   bar { } ;

違いはデフォルトのアクセス指定だ。

structはデフォルトでpublicとなる。

struct foo
{
    // publicメンバー
    int member ;
} ;

classはデフォルトでprivateとなる。

class bar
{
    // privateメンバー
    int member ;
} ;

structとclassの違いはデフォルトのアクセス指定だけだ。アクセス指定を明示的に書く場合、違いはなくなる。

ネストされた型名

std::vectorにはさまざまなネストされた型名がある。

int main()
{
    using vec = std::vector<int> ;
    vec v = {1,2,3} ;

    vec::value_type val = v[0] ;
    vec::iterator i = v.begin() ;
}

自作の簡易vectorでstd::vectorと同じようにネストされた型名を書いていこう。

要素型に関係するネストされた型名。

template < typename T, typename Allocator = std::allocator<T> >
class vector
{
public :
    using value_type                = T ;
    using pointer                   = T *;
    using const_pointer             = const pointer;
    using reference                 = value_type & ;
    using const_reference           = const value_type & ;
} ;

本物のstd::vectorとは少し異なるが、ほぼ同じだ。要素型がvalue_typeで、あとは要素型のポインター、constポインター、リファレンス、constリファレンスがそれぞれエイリアス宣言される。

アロケーター型もallocator_typeとしてエイリアス宣言される。

template < typename T, typename Allocator = std::allocator<T> >
class vector
{
public :
    using allocator_type = Allocator ;
} ;

size_typeは要素数を表現する型だ。

void f( std::vector<int> & v )
{
    std::vector<int>::size_type s = v.size() ;
}

通常std::size_tが使われる。

size_type = std::size_t ;

difference_typeはイテレーターのdifference_typeと同じだ。これはイテレーター間の距離を表現する型だ。

void f( std::vector<int> & v )
{
    auto i = v.begin() ;
    auto j = i + 3 ;

    // iとjの距離
    std::vector<int>::difference_type d = j - i ;
}

通常std::ptrdiff_tが使われる。

difference_type = std::ptrdiff_t ;

イテレーターのエイリアス。

using iterator                  = pointer ;
using const_iterator            = const_pointer ;
using reverse_iterator          = std::reverse_iterator<iterator> ;
using const_reverse_iterator    = std::reverse_iterator<const_iterator> ;

今回実装する簡易vectorでは、ポインター型をイテレーター型として使う。std::vectorの実装がこのようになっている保証はない。

reverse_iteratorとconst_reverse_iteratorはリバースイテレーターだ。

簡易vectorのデータメンバー

簡易vectorにはどのようなデータメンバーがあればいいのだろうか。以下の4つの情報を保持する必要がある。

動的確保したストレージへのポインター
現在有効な要素数
動的確保したストレージのサイズ
アロケーター

これを素直に考えると、ポインター1つ、整数2つ、アロケーター1つの4つのデータメンバーになる。

template < typename T, typename Allocator = std::allocator<T> >
class vector
{
private :
    // 動的確保したストレージへのポインター
    pointer first = nullptr ;
    // 現在有効な要素数
    size_type valid_size = nullptr ;
    // 動的確保したストレージのサイズ
    size_type allocated_size = nullptr ;
    // アロケーターの値
    allocator_type alloc ;
} ;

確かにstd::vectorはこのようなデータメンバーでも実装できる。しかし多くの実装では以下のようなポインター3つとアロケーター1つになっている。

template < typename T, typename Allocator = std::allocator<T> >
class vector
{
private :
    // 先頭の要素へのポインター
    pointer first ;
    // 最後の要素の1つ前方のポインター
    pointer last ;
    // 確保したストレージの終端
    pointer reserved_last ;
    // アロケーターの値
    allocator_type alloc ;
} ;

このように実装すると、現在有効な要素数はlast - firstで得られる。確保したストレージのサイズはreserved_last - firstだ。ポインターで持つことによってポインターが必要な場面でポインターと整数の演算を必要としない。

効率的な実装はC++が実行される環境によっても異なるので、すべての環境に最適な実装はない。

簡単なメンバー関数の実装

簡易vectorの簡単なメンバー関数を実装していく。ここでのサンプルコードはすべて簡易vectorのクラス定義の中に書いたかのように扱う。例えば

void f() { }

とある場合、これは、

template < typename T, typename Allocator = std::allocator<T> >
class vector
{
    // その他のメンバーすべて
public :
    void f() {}
} ;

のように書いたものとして考えよう。

イテレーター

簡易vectorは要素の集合を配列のように連続したストレージ上に構築された要素として保持する。したがってイテレーターは単にポインターを返すだけでよい。

まず通常のイテレーター

iterator begin() noexcept
{ return first ; }
iterator end() noexcept
{ return last ; }

これは簡単だ。iterator型は実際にはT *型へのエイリアスだ。このメンバー関数は例外を投げないのでnoexceptを指定する。

vectorのオブジェクトがconstの場合、begin/endはconst_iteratorが返る。

int main()
{
    std::vector<int> v(1) ;
    // std::vector<int>::iterator
    auto i = v.begin() ;
    // OK、代入可能
    *i = 0 ;
    // constなvectorへのリファレンス
    auto const & cv = v ;
    // std::vector<int>::const_iterator
    auto ci = cv.begin() ;
    // エラー
    // const_iteratorを参照した先には代入できない
    *ci = 0 ;
}

これを実現するには、メンバー関数をconst修飾する。

struct Foo
{
    // 非const版
    void f() {}
    // const版
    void f() const { }
} ;

int main()
{
    // aは非constなオブジェクト
    Foo a ;
    // 非const版が呼ばれる
    a.f() ;
    // constなリファレンス
    const Foo & cref = a ;
    // const版が呼ばれる
    cref.f() ;
}

すでに学んだようにconst修飾はthisポインターを修飾する。オブジェクトのconst性によって、適切な方のメンバー関数が呼ばれてくれる。

簡易vectorでの実装は単にconst修飾するだけだ。

iterator begin() const noexcept
{ return first ; }
iterator end() const noexcept
{ return last ; }

constではないvectorのオブジェクトからconst_iteratorがほしいときに、わざわざconstなリファレンスに変換するのは面倒なので、const_referenceを返すcbegin/cendもある。

int main()
{
    std::vector<int> v(1) ;
    // std::vector<int>::const_iterator
    auto i = v.cbegin() ;
}

この実装はメンバー関数名以外同じだ。

const_iterator cbegin() const noexcept
{ return first ; }
const_iterator cend() const noexcept
{ return last ; }

std::vectorにはリバースイテレーターを返すメンバー関数rbegin/rendとcrbegin/crendがある。

int main()
{
    std::vector<int> v = {1,2,3,4,5} ;

    // イテレーター
    auto i = v.begin() ;
    *i ; // 1

    // リバースイテレーター
    auto r = v.rbegin() ;
    *r ; // 5
}

beginに対するrbegin/rendの実装は以下のようになる。crbegin/crendは自分で実装してみよう。

reverse_iterator rbegin() noexcept
{ return reverse_iterator{ last } ; }
reverse_iterator rend() noexcept
{ return reverse_iterator{ first } ; }

return文でT{e}という形の明示的な型変換を使っている。これには理由がある。

C++では引数が1つしかないコンストラクターを変換コンストラクターとして特別に扱う。

例えば以下は数値のように振る舞うNumberクラスの例だ。

class Number
{
    Number( int i ) ;
    Number( double d ) ;
    Number( std::string s ) ;
} ;

このNumberは初期値をコンストラクターで取る。そのとき、int型、double型、はては文字列で数値を表現したstd::string型まで取る。この3つのコンストラクターは引数が1つしかないため変換コンストラクターだ。

クラスは変換コンストラクターの引数の型から暗黙に型変換できる。

例えばNumberクラスを引数に取る関数があると、

void print_number( Number n ) ;

変換コンストラクターの型の値を渡せる。

int main()
{
    // int型から変換
    print_number( 123 ) ;
    // double型から変換
    print_number( 3.14 ) ;
    // std::string型から変換
    print_number( "3.14"s ) ;
}

intやdoubleやstd::stringはNumberではないが、変換コンストラクターによって暗黙に型変換される。

戻り値として返すときにも変換できる。

// Number型のゼロを返す
Number zero()
{
    // int型から変換
    return 0 ;
}

しかし、場合によってはこのような暗黙の型変換を行いたくないこともある。そういう場合、コンストラクターにexplicitキーワードを付けると、暗黙の型変換を禁止させることができる。

class Number
{
    explicit Number( int i ) ;
    explicit Number( double d ) ;
    explicit Number( std::string s ) ;
} ;

実はstd::reverse_iterator<Iterator>のコンストラクターにもexplicitキーワードが付いている。

namespace std {
template< typename  Iterator >
class reverse_iterator
{
    constexpr explicit reverse_iterator(Iterator x);
    // ...
} ;
}

explicitキーワード付きの変換コンストラクターを持つクラスは、暗黙の型変換ができないので、明示的に型変換しなければならない。

容量確認

std::vectorには容量を確認するメンバー関数がある。

int main()
{
    std::vector<int> v ;
    // true、要素数0
    bool a = v.empty() ;
    v.push_back(0) ;
    // false、要素数非ゼロ
    bool b = v.empty() ;
    // 1、現在の要素数
    auto s = v.size() ;
    // 実装依存、追加の動的メモリー確保をせずに格納できる要素の最大数
    auto c = v.capacity() ;
}

さっそく実装していこう。

sizeは要素数を返す。イテレーターの距離を求めればよい。

size_type size() const noexcept
{
    return end() - begin() ;
}

イテレーターライブラリを使ってもよい。本物のstd::vectorでは以下のように実装されている。

size_type size() const noexcept
{
    return std::distance( begin(), end() ) ;
}

emptyは空であればtrue、そうでなければfalseを返す。「空」というのは要素数がゼロという意味だ。

bool empty() const noexcept
{
    return size() == 0 ;
}

しかしsize() == 0というのは、begin() == end()ということだ。なぜならば要素数が0であれば、イテレーターのペアはどちらも終端のイテレーターを差しているからだ。本物のstd::vectorでは以下のように実装されている。

bool empty() const noexcept
{
    return begin() == end() ;
}

capacityは、追加の動的メモリー確保をせずに追加できる要素の最大数を返す。これを計算するには、動的確保したストレージの末尾の1つ次のポインターであるデータメンバーであるreserved_lastを使う。最初の要素へのポインターであるfirstからreserved_lastまでの距離が答えだ。ポインターの距離はイテレーターと同じく引き算する。

size_type capacity() const noexcept
{
    return reserved_last - first ;
}

要素アクセス

operator []

std::vectorのoperator []相当のものを簡易vectorにも実装しよう。

int main()
{
    std::vector<int> v = {1,2,3,4,5} ;
    v[1] ; // 2
    v[3] ; // 4
}

operator []は非const版とconst版の2種類がある。

reference operator []( size_type i )
{ return first[i] ; }
const_reference operator []( size_type i ) const
{ return first[i] ; }

at

メンバー関数at(i)はoperator [](i)と同じだが、範囲外のインデックスを指定した場合、std::out_of_rangeが例外として投げられる。

int main()
{
    try {
        // 有効なインデックスはv[0]からv[4]まで
        std::vector<int> v = {1,2,3,4,5} ;
        v[0] = 0 ; // OK
        v[3] = 0 ; // OK
        v[5] = 0 ; // エラー
    } catch( std::out_of_range e )
    {
        std::cout << e.what() ;
    }
}

実装はインデックスをsize()と比較して、範囲外であればstd::out_of_rangeをthrowする。operator []と同じく、非const版とconst版がある。

reference at( size_type i )
{
    if ( i >= size() )
        throw std::out_of_range( "index is out of range." ) ;

    return first[i] ;
}
const_reference at( size_type i ) const
{
    if ( i >= size() )
        throw std::out_of_range( "index is out of range." ) ;

    return first[i] ;
}

front/back

front()は先頭要素へのリファレンスを返す。

back()は末尾の要素へのリファレンスを返す

int main()
{
    std::vector<int> v = {1,2,3,4,5} ;
    v.front() ; // 1
    v.back() ; // 5
}

これにもconst版と非const版がある。vectorのlastが最後の要素の次のポインターを指していることに注意。

reference front()
{ return first ; }
const_reference front() const
{ return first ; }
reference back()
{ return last - 1 ; }
const_reference back() const
{ return last - 1 ; }

data

data()は先頭の要素へのポインターを返す。

int main()
{
    std::vector<int> v = {1,2,3} ;
    int * ptr = v.data() ;
    *ptr ; // 1
}

実装はfirstを返すだけだ。

pointer data() noexcept
{ return first ; }
const_pointer data() const noexcept
{ return first ; }

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

033-vector-implementation.md

033-vector-implementation.md

vectorの実装 : 基礎

`std::allocator<T>`の概要

`std::allocator<T>`の使い方

`std::allocator_traits<Alloc>`

簡易vectorの概要

classとアクセス指定

ネストされた型名

簡易vectorのデータメンバー

簡単なメンバー関数の実装

イテレーター

容量確認

要素アクセス

operator []

at

front/back

data

Files

033-vector-implementation.md

Latest commit

History

033-vector-implementation.md

File metadata and controls

vectorの実装 : 基礎

std::allocator<T>の概要

std::allocator<T>の使い方

std::allocator_traits<Alloc>

簡易vectorの概要

classとアクセス指定

ネストされた型名

簡易vectorのデータメンバー

簡単なメンバー関数の実装

イテレーター

容量確認

要素アクセス

operator []

at

front/back

data

`std::allocator<T>`の概要

`std::allocator<T>`の使い方

`std::allocator_traits<Alloc>`