JavaScriptでデータ構造を実装したい！ (基本編)

前回の記事「JavaScriptで競技プログラミングを始めよう！」ではJavaScriptで競技プログラミングするために必要な知識やデバッグの方法をまとめました。しかし、プログラミングコンテストでより難しい問題を解くときには使い勝手の良いスタック・キュー・優先度付きキュー・連想配列・Union-Findなどがほしいときがあります。今回の記事ではこれらのデータ構造を実装するためどうしたらいいかをまとめました。

C++のようにクラス(のようなもの)をつくりたい

C++でクラスという概念を用いて自作のデータ構造やデータの管理をするときがあります。例えば2つの整数を組にしたデータ(Pair)をC++で実装するときは次のようにするでしょう。(C++には標準でstd::pairがあるので自分で実装する必要はない)

#include <iostream>
using namespace std;

class Pair{
public:
    // メンバ変数
    int first, second;
    // コンストラクタ
    Pair(int first, int second){
        (*this).first = first;
        (*this).second = second;
    }
    // 等しいかどうか
    bool equals(const Pair &p){
        return ((*this).first == p.first && (*this).second == p.second);
    }
    // 1増やす
    void inc(){
        (*this).first++;
        (*this).second++;
    }
};

int main(){
    Pair p(3, 5);
    Pair q(2, 4);
    p.equals(q); // => false
    q.inc(); // => q.fisrt = 3, q.second = 5
    p.equals(q); // => true
}

2つの整数を組にしたデータ(Pair)をJavaScriptで実装するときは次のようにします。

function Pair(first, second) {
    this.first = first;
    this.second = second;
    this.equals = function (p) {
        return (this.first == p.first && this.second == this.second);
    }
    this.inc = function () {
        this.first++;
        this.second++;
    }
}

function Main() {
    var p = new Pair(3, 5);
    var q = new Pair(2, 4);
    p.equals(q); // => false
    q.inc(); // => q.first = 3, q.second = 5
    p.equals(q); // => true
}

C++ではインスタンスはメンバ変数(今回はfirst,second)とメンバ関数・メソッド(今回はequals, inc)を持っていますが、JavaScriptでは関数(function)もただのオブジェクトなのでインスタンスはプロパティ(メンバ変数)しか持っていないことになります。ということはJavaScriptではインスタンスごとに関数名が同じでも処理の異なるメソッドを持つことができます。例えば次のようにします。

function Pair(first, second) {
    this.first = first;
    this.second = second;
    this.equals = function (p) {
        return (this.first == p.first && this.second == this.second);
    }
    this.inc = function () {
        this.first++;
        this.second++;
    }
}

function Main() {
    var p = new Pair(3, 5);
    var q = new Pair(2, 4);
    p.equals(q); // => false
    
    // inc を 2 増やす関数に変えてあげよう！
    q.inc = function () {
        this.first += 2;
        this.second += 2;
    };
    q.inc(); // => q.first = 4, q.second = 6
    p.equals(q); // => false
}

インスタンスごとに関数をプロパティに持つのは無駄だし、どうせメソッド名が同じでもインスタンスごとに異なる処理のメソッドが欲しいことなんてあまりないでしょう。そこでメソッドはprototypeに全部書いてあげると同じオブジェクトでもインスタンスごとに関数をプロパティに持つわけではなくなるのでうれしいです。

function Pair(first, second) {
    this.first = first;
    this.second = second;    
}
Pair.prototype.equals = function (p) {
    return (this.first == p.first && this.second == this.second);
}
Pair.prototype.inc = function () {
    this.first++;
    this.second++;
}
// 以下は省略

JavaScriptはC++やJavaと違いクラスベースではなくプロトタイプベース(インスタンスベース)らしいです。クラスベースの言語ではクラスを定義し、そのクラスを元にインスタンスを生成します。しかし、JavaScriptのような言語ではインスタンスを元に新しいインスタンスを生成します。このあたりの話はhttp://www.geocities.jp/m_hiroi/light/js04.htmlを見るとわかりやすいかもしれません。

まとめ

とりあえずC++やJavaのようにクラス(のようなもの)をつくりたいときは以下のようにコードを書けばよいことがわかりました。

// コンストラクタの代わり
function クラス名( /* 引数 */ ) {
    /* 処理(初期化など) */    
}
Pair.prototype.メソッド名1 = function ( /* 引数 */ ) {
    /* 処理 */
}
Pair.prototype.メソッド名2 = function ( /* 引数 */ ) {
    /* 処理 */
}
...

// インスタンスを生成するとき
var x = new クラス名(引数);

次回の記事は「JavaScriptでデータ構造を実装したい！ (スタック・キュー・ヒープ実装編)」です。