Help us understand the problem. What is going on with this article?

ランダムアクセス・追加削除が爆速な可変長配列

More than 5 years have passed since last update.

下記のデメリットに示す制約があるものの、用意されているメソッドは全て高速に動作します。
JavaとC++では一部動作が異なります。
(実はどちらもテストしていません・・・脳内でバッグでは完璧でしたが間違っていたらコメント下さい)

■メリット

ランダムアクセスが高速
データの追加・削除が高速

■デメリット

格納できる最大要素数を指定しなければいけない
先頭と終端からしかデータの追加・削除を行えない

■ソース

Java

SocketArray.java
public class SocketArray<T> {
    private final Object[] dataList;
    private final int capacity; //  ↑のlengthと同じ値(できるだけ高速にアクセスするためにここに持つ)
    private int size;           //  現在の配列の長さ
    private int first, last;    //  先頭と終端のインデックス(sizeが0の時値は保証されない)

    //  最大要素数を指定する
    public SocketArray(int capacity) {
        dataList = new Object[capacity];
        this.capacity = capacity;
        this.size = 0;
    }

    //  配列の長さを取得(最大登録可能数)
    //  コンストラクタで指定した値
    public int capacity() {
        return capacity;
    }

    //  登録されている要素数を取得
    public int size() {
        return size;
    }

    //  要素を追加できるかチェック
    //  size() < capacity() の結果を返す
    public boolean hasSpace() {
        return size < capacity;
    }

    //  要素を取得
    @SuppressWarnings("unchecked")
    public T get(int index) {
        if (index<0 || index>=size) {
            throw new ArrayIndexOutOfBoundsException();
        }

        index += first;
        if (index >= capacity) {
            index -= capacity;
        }
        return (T)dataList[index];
    }

    //  要素をセット
    public void set(int index, T object) {
        if (index<0 || index>=size) {
            throw new ArrayIndexOutOfBoundsException();
        }

        index += first;
        if (index >= capacity) {
            index -= capacity;
        }

        dataList[index] = object;
    }

    //  先頭の要素を取得
    //  get(0) よりさらに高速
    @SuppressWarnings("unchecked")
    public T getFirst() {
        if (size == 0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return (T)dataList[first];
    }

    //  終端の要素を取得
    //  get(size()-1) よりさらに高速
    @SuppressWarnings("unchecked")
    public T getLast() {
        if (size == 0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return (T)dataList[last];
    }

    //  先頭に要素を追加する
    public void addFirst(T object) {
        if (size >= capacity) {
            //  これ以上追加できない
            throw new ArrayIndexOutOfBoundsException();
        }

        //  登録先のインデックス
        int index;
        if (size == 0) {
            //  最初の要素を追加するとき
            index = 0;
            last = 0;
        } else {
            //  1つでも要素が存在するとき
            index = first-1;
            if (index < 0) {
                index = capacity-1;
            }
        }

        size++;
        first = index;
        dataList[index] = object;
    }

    //  終端に要素を追加する
    public void addLast(T object) {
        if (size >= capacity) {
            //  これ以上追加できない
            throw new ArrayIndexOutOfBoundsException();
        }

        //  登録先のインデックス
        int index;
        if (size == 0) {
            //  最初の要素を追加するとき
            index = 0;
            first = 0;
        } else {
            //  1つでも要素が存在するとき
            index = last+1;
            if (index >= capacity) {
                index = 0;
            }
        }

        size++;
        last = index;
        dataList[index] = object;
    }

    //  先頭の要素を削除
    //  削除した要素を返すが、要素がないときはnull
    @SuppressWarnings("unchecked")
    public T removeFirst() {
        if (size > 0) {
            Object object = dataList[first];
            dataList[first] = null;

            if (++first >= capacity) {
                first = 0;
            }

            size--;
            return (T)object;
        }
        return null;
    }

    //  終端の要素を削除
    //  削除した要素を返すが、要素がないときはnull
    @SuppressWarnings("unchecked")
    public T removeLast() {
        if (size > 0) {
            Object object = dataList[last];
            dataList[last] = null;

            if (--last < 0) {
                last = capacity-1;
            }

            size--;
            return (T)object;
        }
        return null;
    }

    //  すべての要素を削除する
    public void clear() {
        for (int i=0; i<capacity; i++) {
            dataList[i] = null;
        }
        size = 0;
    }
}

C++

SocketArray.hpp
#include <memory>

template<class T>
class SocketArray {
private:
    const std::unique_ptr<T[]> ptDataList;
    const int capacity; //  dataListのメモリ確保している長さ
    int length;         //  持っている要素数
    int first, last;    //  先頭と終端のインデックス(lengthが0の時は値は保証されない)

public:
    //  capasity:   最大格納可能要素数
    SocketArray(int capacity) : capacity(capacity), ptDataList(new T[capacity]) {
        this->length = 0;
    }

    //  配列の長さを取得(最大格納可能要素数)
    int getCapacity() {
        return capacity;
    }

    //  現在の配列の長さを取得(格納している要素数)
    int getLength() {
        return length;
    }

    //  要素を追加できるかチェック
    //  size() < capacity() の結果を返す
    bool hasSpace() {
        return length < capacity;
    }

    //  要素を取得
    T& operator[](int index) {
        if (index<0 || index>=length) {
            throw "ArrayIndexOutOfBoundsException";
        }

        index += first;
        if (index >= capacity) {
            index -= capacity;
        }
        return ptDataList[index];
    }

    //  先頭の要素を取得
    //  [0] より更に高速
    T& getFirst() {
        if (length == 0) {
            throw "ArrayIndexOutOfBoundsException";
        }
        return ptDataList[first];
    }

    //  終端の要素を取得
    //  [size()-1] より更に高速
    T& getLast() {
        if (length == 0) {
            throw "ArrayIndexOutOfBoundsException";
        }
        return ptDataList[last];
    }

    //  先頭に要素を追加する
    void addFirst(const T& object) {
        if (length >= capacity) {
            //  これ以上追加できない
            throw "ArrayIndexOutOfBoundsException";
        }

        //  登録先のインデックス
        int index;
        if (length == 0) {
            //  最初の要素を追加するとき
            index = 0;
            last = 0;
        } else {
            //  1つでも要素が存在するとき
            index = first-1;
            if (index < 0) {
                index = capacity-1;
            }
        }

        length++;
        first = index;
        ptDataList[index] = object;
    }

    //  終端に要素を追加する
    void addLast(const T& object) {
        if (length >= capacity) {
            //  これ以上追加できない
            throw "ArrayIndexOutOfBoundsException";
        }

        //  登録先のインデックス
        int index;
        if (length == 0) {
            //  最初の要素を追加するとき
            index = 0;
            first = 0;
        } else {
            //  1つでも要素が存在するとき
            index = last+1;
            if (index >= capacity) {
                index = 0;
            }
        }

        length++;
        last = index;
        ptDataList[index] = object;
    }

    //  先頭の要素を削除
    //  削除した要素を返す
    T& removeFirst() {
        if (length <= 0) {
            throw "ArrayIndexOutOfBoundsException";
        }

        int removedIndex = first;

        if (++first >= capacity) {
            first = 0;
        }

        length--;
        return ptDataList[removedIndex];
    }

    //  終端の要素を削除
    //  削除した要素を返す
    T& removeLast() {
        if (length <= 0) {
            throw "ArrayIndexOutOfBoundsException";
        }

        int removedIndex = last;

        if (--last < 0) {
            last = capacity-1;
        }

        length--;
        return ptDataList[removedIndex];
    }

    //  すべての要素を削除する
    void clear() {
        length = 0;
    }
};
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away