自作 Vector ライブラリ提供 : C++ の vector の計算量を言えますか

はじめに

C++ の std::vector は素晴らしいライブラリです。中身は実はよくわかってないですが、とってもいい感じに処理されていてすごいです。

ところで、C++ の std::vector の処理の計算量はどうでしょうか。ランダムアクセスなどが定数時間なのは嬉しいですよね。それに対して、僕はあまり気にして使ってませんが(✊)、要素の挿入および削除が定数時間ではないことは有名な話です。というのも、挿入/削除のためのアロケートが必要だからです。多分。

僕の自作 Vector ライブラリでは、実行する処理の回数を $Q$ として、処理 $1$ 回あたりのならし計算量が $O(\log{Q})$ 時間になる代わりに、std::vector ではサポートされていない様々な機能がサポートされています。

中身

データ構造の概要は こちらの記事 (平衡二分木入門 : Splay Tree) で説明しています。

平衡二分木と聞いた時、std::set などを想像されるかもしれません。std::set などの順序付き集合はソートされた数列、すなわち数列の特殊な場合を表現していますが、平衡二分木は本来 std::set などのソートされた数列に限らず、一般的な数列を表現できるのです。

プログラミングにおける活用

自作 Vector の活躍できる場面としては以下のような場合があります。

1. 任意の箇所に要素を 挿入/削除 したい。
2. 区間取得や区間更新をしたい。
3. 区間シフトや区間反転など、区間に対する操作を行いたい。
4. ある値をもつ要素が、列の何番目に登場するかを見つけたい。

これらのそれなりにリッチな要求を $O(\log{Q})$ 時間で処理できるのは驚きではないですか！？ このデータ構造が必ず必要な場面は少ないですが、このデータ構造があるおかげで楽することができる場面は多いと思います。

計算量の定数倍も、軽いとは言えないですが実用で困るほどではありません。

ソースコード

使い方は後述します。あとコメントの英語が拙いのは気にしないでください。雰囲気がわかればいいのです。

ライセンスは守ってくださいね (このライブラリの冒頭に以下を書くだけで良いです)。

• Copyright ©️ (c) NokonoKotlin (okoteiyu) 2024. Released under the MIT license(https://opensource.org/licenses/mit-license.php)

ライセンスに従わない利用を確認した場合、ライセンスに従わない利用をやめるよう指示するなどの処置を取る場合があります。

#include <unordered_map>
#include <cassert>
#include <vector>
#include <list>
#include <iostream>
using namespace std;


/*   
    Copyright ©️ (c) NokonoKotlin (okoteiyu) 2024.
    Released under the MIT license(https://opensource.org/licenses/mit-license.php) 
*/
template<class T , bool _use_find_ = false >
class MyBinaryVector{
    private:
    struct SplayNode{
        SplayNode *parent = nullptr;
        SplayNode *left = nullptr;
        SplayNode *right = nullptr;
        T Value;
        T Min,Max,Sum;
        bool isThisDeleted = false;
        int SubTreeSize = 1;
        private:
        bool copied_instance = false;
        public:
        SplayNode copy(){
            assert(copied_instance == false);
            SplayNode res = *this;
            res.left = nullptr;
            res.right = nullptr;
            res.parent = nullptr;
            res.copied_instance = true;
            return res;
        }
        bool lazy_reverse = false;
        void set_lazyReverse(){
            this->lazy_reverse = !(this->lazy_reverse);
        }
        pair<bool,pair<T,T> > lazy_affine ={false , {T(),T()}};
        void set_lazyAffine(T& a, T& b){
            if(this->lazy_affine.first)this->lazy_affine.second = { a*this->lazy_affine.second.first , a*this->lazy_affine.second.second + b};
            else this->lazy_affine = {true , {a,b}};
        }
        pair<bool,T> lazy_update = {false,T()};
        void set_lazyUpdate(T &x){
            this->lazy_update.first = true;
            this->lazy_update.second=x;
            this->lazy_affine.first = false;
        }
        SplayNode(){}
        SplayNode(T val){
            Value = val;
            update();
        }
        void rotate(){
            if(this->parent->parent != nullptr){
                if(this->parent == this->parent->parent->left)this->parent->parent->left = this;
                else this->parent->parent->right = this;
            }
            this->parent->eval();
            this->eval();
            if(this->parent->left == this){
                this->parent->left = this->right;
                if(this->right != nullptr)this->right->parent = this->parent;
                this->right = this->parent;
                this->parent = this->right->parent;
                this->right->parent = this;
                this->right->update();
            }else{
                this->parent->right = this->left;
                if(this->left != nullptr)this->left->parent = this->parent;
                this->left = this->parent;
                this->parent = this->left->parent;
                this->left->parent = this;
                this->left->update();
            }
            this->update();
            return;
        }
        int state(){
            if(this->parent == nullptr)return 0;
            this->parent->eval();
            if(this->parent->left == this)return 1;
            else if(this->parent->right == this)return 2;
            return 0;
        }
        void splay(){
            while(this->parent != nullptr){
                if(this->parent->state() == 0){
                    this->rotate();
                    break;
                }
                if( this->parent->state() == this->state() )this->parent->rotate();
                else this->rotate();
                this->rotate();
            }
            this->update();
            return;
        }
        void update(){
            assert(copied_instance == false);
            this->eval();
            this->Sum = this->Max = this->Min = this->Value;
            this->SubTreeSize = 1;
            if(this->left != nullptr){
                this->left->eval();
                this->SubTreeSize += this->left->SubTreeSize;
                if(this->left->Min < this->Min)this->Min = this->left->Min;
                if(this->left->Max > this->Max)this->Max = this->left->Max;
                this->Sum += this->left->Sum;
            }
            if(this->right != nullptr){
                this->right->eval();
                this->SubTreeSize += this->right->SubTreeSize;
                if(this->right->Min < this->Min)this->Min = this->right->Min;
                if(this->right->Max > this->Max)this->Max = this->right->Max;
                this->Sum += this->right->Sum;
            }
            return;
        }
        void eval(){
            assert(copied_instance == false);
            if(this->lazy_reverse){
                swap(this->left , this->right);
                if(this->left != nullptr)this->left->set_lazyReverse();
                if(this->right != nullptr)this->right->set_lazyReverse();
                this->lazy_reverse = false;
            }
            if(this->lazy_update.first){
                this->Value = this->Min = this->Max = this->lazy_update.second;
                this->Sum = (this->lazy_update.second)*(this->SubTreeSize);
                if(this->left != nullptr)this->left->set_lazyUpdate(this->lazy_update.second);
                if(this->right != nullptr)this->right->set_lazyUpdate(this->lazy_update.second);
                this->lazy_update.first = false;
            }
            if(this->lazy_affine.first){
                this->Value = this->lazy_affine.second.first * this->Value + this->lazy_affine.second.second;
                this->Min = this->lazy_affine.second.first * this->Min + this->lazy_affine.second.second;
                this->Max = this->lazy_affine.second.first * this->Max + this->lazy_affine.second.second;
                this->Sum = this->lazy_affine.second.first * this->Sum + this->SubTreeSize*this->lazy_affine.second.second;
                if(this->Max < this->Min)swap(this->Max,this->Min);
                if(this->left != nullptr)this->left->set_lazyAffine(this->lazy_affine.second.first,this->lazy_affine.second.second);
                if(this->right != nullptr)this->right->set_lazyAffine(this->lazy_affine.second.first,this->lazy_affine.second.second);
                this->lazy_affine.first = false;
            }
        }
    };
    SplayNode *get_sub(int index , SplayNode *root){
        if(root==nullptr)return root;
        SplayNode *now = root;
        while(true){
            now->eval();
            int left_size = 0;
            if(now->left != nullptr)left_size = now->left->SubTreeSize;
            if(index < left_size)now = now->left;
            else if(index > left_size){
                now = now->right;
                index -= left_size+1;
            }else break;
        }
        now->splay();
        return now;
    }
    SplayNode *merge(SplayNode *leftRoot , SplayNode *rightRoot){
        if(leftRoot!=nullptr)leftRoot->update();
        if(rightRoot!=nullptr)rightRoot->update();
        if(leftRoot == nullptr)return rightRoot;
        if(rightRoot == nullptr)return leftRoot;
        rightRoot = get_sub(0,rightRoot);
        rightRoot->left = leftRoot;
        leftRoot->parent = rightRoot;
        rightRoot->update();
        return rightRoot;
    }
    std::pair<SplayNode*,SplayNode*> split(int leftnum, SplayNode *root){
        if(leftnum<=0)return std::make_pair(nullptr , root);
        if(leftnum >= root->SubTreeSize)return std::make_pair(root, nullptr);
        root = get_sub(leftnum , root);
        SplayNode *leftRoot = root->left;
        SplayNode *rightRoot = root;
        if(rightRoot != nullptr)rightRoot->left = nullptr;
        if(leftRoot != nullptr)leftRoot->parent = nullptr;
        leftRoot->update();
        rightRoot->update();
        return std::make_pair(leftRoot,rightRoot);
    }
    protected:
    SplayNode *m_Root = nullptr;
    unordered_map<T , list<SplayNode*> > m_pointers;
    void release(){
        while(m_Root != nullptr)Delete(0);
    }
    void init(){
        m_Root = nullptr;
        m_pointers.clear();
    }
    const SplayNode* const begin(){
        if(size() == 0)return nullptr;
        m_Root = get_sub(0,m_Root);
        return m_Root;
    }
    public:
    MyBinaryVector(){init();}
    ~MyBinaryVector(){release();}
    MyBinaryVector(const MyBinaryVector<T,_use_find_> &x) = delete ;
    MyBinaryVector& operator = (const MyBinaryVector<T,_use_find_> &x) = delete ;
    MyBinaryVector ( MyBinaryVector<T,_use_find_>&& x){assert(0);}
    MyBinaryVector& operator = ( MyBinaryVector<T,_use_find_>&& x){assert(0);}
    void copy(MyBinaryVector<T,_use_find_>& x){
        if(this->begin() == x.begin())return;
        release();
        init();
        for(int i = 0 ; i < x.size() ; i++ )this->push_back(x[i]);
    }
    int size(){
        if(m_Root == nullptr)return 0;
        return m_Root->SubTreeSize;
    }
    SplayNode get(int i){
        assert(0 <= i && i < size());
        m_Root = get_sub(i,m_Root);
        return m_Root->copy();
    }
    SplayNode GetRange(int l , int r){
        assert(0 <= l && l < r && r <= size());
        std::pair<SplayNode*,SplayNode*> tmp = split(r,m_Root);
        SplayNode* rightRoot = tmp.second;
        tmp = split(l,tmp.first);
        SplayNode res = tmp.second->copy();
        m_Root = merge(merge(tmp.first,tmp.second),rightRoot);
        return res;
    }
    void insert(int index , T x){
        assert(0 <= index && index <= size());
        SplayNode* NODE = new SplayNode(x);
        NODE->update();
        if(m_Root == nullptr)m_Root = NODE;
        else{
            std::pair<SplayNode*,SplayNode*> Trees = split(index,m_Root);
            m_Root = merge(merge(Trees.first,NODE),Trees.second);
        }
        if(_use_find_ == false)return;
        m_pointers[NODE->Value].push_back(NODE);
    }
    void Delete(int index){
        assert(0 <= index && index < size());
        SplayNode *center = get_sub(index,m_Root);
        SplayNode *leftRoot = center->left;
        SplayNode *rightRoot = center->right;
        if(leftRoot != nullptr)leftRoot->parent = nullptr;
        if(rightRoot != nullptr)rightRoot->parent = nullptr;
        center->left = nullptr;
        center->right = nullptr;
        center->update();
        m_Root = merge(leftRoot,rightRoot);
        if(_use_find_)center->isThisDeleted = true;
        else delete center;
    }
    void update_val(int x , T y){
        assert(0 <= x && x < size());
        m_Root = get_sub(x,m_Root);
        m_Root->Value = y;
        m_Root->update();
        if(_use_find_ == false)return;
        m_pointers[y].push_back(m_Root);
        return;
    }
    void reverse(int l , int r){
        assert(0 <= l && l < r && r <= size());
        if(r-l <= 1)return;
        std::pair<SplayNode*,SplayNode*> tmp = split(r,m_Root);
        SplayNode* rightRoot = tmp.second;
        tmp = split(l,tmp.first);
        tmp.second->set_lazyReverse();
        tmp.second->update();
        m_Root = merge(merge(tmp.first, tmp.second),rightRoot);
        return;
    }
    void RangeAffine(int l , int r , T A , T B){
        assert(!_use_find_);
        assert(0 <= l && l < r && r <= size());
        std::pair<SplayNode*,SplayNode*> tmp = split(r,m_Root);
        SplayNode* rightRoot = tmp.second;
        tmp = split(l,tmp.first);
        tmp.second->set_lazyAffine(A,B);
        tmp.second->update();
        m_Root = merge(merge(tmp.first, tmp.second),rightRoot);
        return;
    }
    void RangeAdd(int l , int r , T x){
        assert(!_use_find_);
        assert(0 <= l && l < r && r <= size());
        RangeAffine(l,r,T(1),x);
        return;
    }
    void RangeUpdate(int l , int r , T x){
        assert(!_use_find_);
        assert(0 <= l && l < r && r <= size());
        std::pair<SplayNode*,SplayNode*> tmp = split(r,m_Root);
        SplayNode* rightRoot = tmp.second;
        tmp = split(l,tmp.first);
        tmp.second->set_lazyUpdate(x);
        tmp.second->update();
        m_Root = merge(merge(tmp.first, tmp.second),rightRoot);
        return;
    }
    void circular_shift(int l , int r , long long c){
        assert(0 <= l && l < r && r <= size());
        if(abs(c) == r - l)return;
        assert(c < abs(r-l));
        if(c == 0)return;
        if(c < 0)c = r-l+c;
        std::pair<SplayNode*,SplayNode*> tmp = split(r,m_Root);
        SplayNode* rightRoot = tmp.second;
        tmp = split(l,tmp.first);
        SplayNode* leftRoot = tmp.first;
        SplayNode* center = tmp.second;
        tmp = split(r-l-c , center);
        m_Root = merge(merge(merge(leftRoot,tmp.second),tmp.first),rightRoot);
        return;
    }
    vector<int> find(T x , int count){
        assert(_use_find_);
        if(size() == 0)return vector<int>(0);
        if(m_pointers[x].size() == 0)return vector<int>(0);
        vector<int> res;
        unordered_map<SplayNode*,bool> checked;
        typename list<SplayNode*>::const_iterator it = m_pointers[x].end();
        while(it != m_pointers[x].begin()){
            if(res.size()>=count)break;
            SplayNode *Nd = *(--it);
            assert(Nd != nullptr);
            if(checked[Nd])it = m_pointers[x].erase(it);
            else if(Nd->isThisDeleted)it = m_pointers[x].erase(it);
            else if(Nd->Value != x)it = m_pointers[x].erase(it);
            else{
                Nd->splay();
                m_Root = Nd;
                int index = 0;
                if(Nd->left != nullptr)index+=Nd->left->SubTreeSize;
                res.push_back(index);
            }
            checked[Nd] = true;
        }
        return res;
    }
    void Debug(){std::cerr<<"DEBUG:" << std::endl;for( int i = 0 ; i < size() ; i++)std::cerr<< get(i).Value << " ";std::cerr<< std::endl;}
    void push_back(T val){insert(this->size() , val);return;}
    void push_front(T val){insert(0 , val);return;}
    T back(){assert(size()>0);return get(size()-1).Value;}
    T front(){assert(size()>0);return get(0).Value;}
    void pop_back(){assert(size()>0);Delete(size()-1);}
    void pop_front(){assert(size()>0);Delete(0);}
    T operator [](int index){return get(index).Value;}
    /*   
        Copyright ©️ (c) NokonoKotlin (okoteiyu) 2024.
        Released under the MIT license(https://opensource.org/licenses/mit-license.php) 
    */
};

使用例

後述の概要と併せて参考にしてください。

void usage_array(){
    /*
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        区間操作あり、要素検索なしの使い方
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    */
    // find を使わない (区間変更などをする) 場合、テンプレートの第二引数を false にする
    MyBinaryVector<long long , false> V;

    // std::vector -like の push_back が使える。(push_front,pop_front,pop_back も可能)
    for(int i = 0 ; i < 15 ; i++)V.push_back(-6 + (i*i*i)%20);

    // index を指定して列操作 (0-index)
    V.update_val(3,-2);     // 値の変更
    V.insert(5,9);          // 要素の挿入
    V.Delete(1);            // 要素の削除

    V.Debug();              // デバッグ出力
    /*
        DEBUG:
        -6 2 -2 -2 9 -1 10 -3 6 3 -6 5 2 11 -2 
    */


    // 各種要素アクセス
    std::cerr 
        << V.front() << " , " 
        << V[12] << " , " // [] は読み込み専用
        << V.back() 
    << std::endl;// -6 , 2 , -2


    // 区間 [2,7) のデータを取得
    auto RangeDataCopy = V.GetRange(2,7);

    // 区間 [2,7) の Sum,Min,Max の出力
    std::cerr 
        << RangeDataCopy.Sum << " , "
        << RangeDataCopy.Min << " , "
        << RangeDataCopy.Max 
    << std::endl;// 14 , -2 , 10 

    // 区間 [4,8) の要素を全て 0 に変更
    V.RangeUpdate(4,8,0);
    V.Debug();
    /*
        DEBUG:
        -6 2 -2 -2 0 0 0 0 6 3 -6 5 2 11 -2 
    */

    // 区間 [0,6) の要素を全て 3 倍して 10 足す
    V.RangeAffine(0,6,3,10);
    V.Debug();
    /*
        DEBUG:
        -8 16 4 4 10 10 0 0 6 3 -6 5 2 11 -2 
    */


    // 区間 [2,10) の要素の順番を左右反転
    V.reverse(2,10);
    V.Debug();
    /*
        DEBUG:
        -8 16 3 6 0 0 10 10 4 4 -6 5 2 11 -2 
    */


    // 区間 [1,7) を右に 2 だけ回転シフト (スロットのリールのような回転)
    V.circular_shift(1,7,2);
    V.Debug();
    /*
        DEBUG:
        -8 0 10 16 3 6 0 10 4 4 -6 5 2 11 -2   
    */


    // 区間 [6,11) を!!!左!!!に 2 だけ回転シフト (スロットのリールのような回転)
    V.circular_shift(6,11,-2);
    V.Debug();
    /*
        DEBUG:
        -8 0 10 16 3 6 4 4 -6 0 10 5 2 11 -2   
    */



    /*
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        区間操作なし、要素検索ありの使い方
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    */

    // find を使う場合、テンプレートの第二引数を true にする
    MyBinaryVector<long long , true> F;
    for(int i = 0 ; i < 15 ; i++)F.push_front(0);

    // 1 を追加して、1 の位置を追っていこう (ダジャレ)
    F.insert(4,1);
    F.insert(7,1);

    F.Debug();
    /*
        DEBUG:
        0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 
    */

    // 1 が 2 つあるので、find で 2 つとってきてチェック
    std::cerr 
        << F.find(1,2)[0] << " , " 
        << F.find(1,2)[1] 
    << std::endl;// 7 , 4
    //                 -> find でとってくる位置に関して、順番は保証しないことに注意
    
    F.Delete(4);
    F.Delete(5);
    F.insert(10,1);
    F.insert(8,2);

    F.Debug();
    /*
        DEBUG:
        0 0 0 1 0 1 0 0 2 0 0 1 0 0 0 0 0   
    */

    // 1 の位置をあらためてチェック
    std::cerr 
        << F.find(1,2)[0] << " , " 
        << F.find(1,2)[1] 
    << std::endl;// 11 , 5
    
    // 新たに追加した 2 の位置もチェック
    std::cerr << F.find(2,1)[0] << std::endl;// 8

    // 区間取得は可能
    std::cerr << F.GetRange(0,10).Sum << std::endl;// 3

    // F.RangeAdd(0,10,4); 
    //      -> find するのに区間更新を呼ぶとエラー

    // 区間操作は OK だけどなぜかめっちゃおそい。計算量解析があってるか心配なレベル。
    F.reverse(0,10);
}

概要

数列型の Splay Tree。SplayNodeというデータ構造に必要なデータを持たせ、m_Root から探索することで列にアクセスする。

SplayNode にモノイド積などの集約データを持たせる(Sum,Min など)。基本的に、機能の変更をしたい場合は SplayNode のメンバや update や eval を編集することになる。また、いらない集約や作用、デストラクタを消すと速くなる。

基本機能

• get(i) で i 番目のノードのコピーを 0-index で取得。ただし隣接頂点へのアクセス (ポインタ) が封印されたものを返す。
• GetRange(l,r) はindexの半開区間 [l,r) をカバーする部分木の根のコピーを返す。get() 同様に、隣接頂点のポインタは封印されている。
  • GetRange(l,r).Sum のようにして [l,r) の持つ要素のモノイド積を取得する
• insert(i,x) で i 番目に x をもつ要素を挿入する。
• Delete(i) で i 番目の要素を削除する。
• update_val(i,x) で i 番目の要素を x に変更する。

区間取得/区間更新

• SplayNode には集約の特殊化で Sum,Min,Max を定義している。
  • GetRange(l,r).Min などのようにして取り出す。
• RangeAffine(l,r,A,B) := 区間アフィン変換
  • 区間 [l,r) 内の要素を全てを A 倍してから B 加算する。
• RangeAdd(l,r,x) := 区間加算
  • 区間 [l,r) 内の要素を全てに x 加算する。
• RangeUpdate(l,r,x) := 区間更新
  • 区間 [l,r) 内の要素を全て x に変更する。

区間操作

• reverse(l,r) := 区間反転
  • 区間 [l,r) 内の要素の順番を左右反転で折り返す。
• circular_shift(l,r,c) := 区間シフト
  • 区間 [l,r) をスロットのリールのように c 回分回転させる。
  • c が負の場合は左回転になる。
  • 一周以上回る場合はエラー

要素の検索

• find(x,c) : a_i = x である様な i を c 個まで検索する。
  • ケースによってはめっちゃ遅い (計算量解析が合ってるか心配なレベル)
  • 区間シフトや区間反転を使うとなぜか遅くなる。なぜ？

その他

std::vector と同様に push_front,push_back,pop_front,pop_back を使用できます。また、列の中身をデバッグする用に Debug を用意しています。

要素の読み込み専用アクセスとして、[i] や front,back も使えます。

T が modint などの自作クラスの場合、m_pointers のキーにできないので注意。m_pointers のキーを long long にしてキャストを働かせるか、あるいは T に順序 < が定義されているなら m_pointers を std::map　にして解決できる。