C++シミュレーションJDKにおけるArrayListとLinkedListの実現

JavaがArrayListとLinkedListを実現する方式は配列とチェーンテーブルを採用している.以下はC++コードによるシミュレーションです.
Collectionインタフェースの宣言:

#ifndef COLLECTION_H_
#define COLLECTION_H_
template<class T>
class Collection {
public:
    virtual ~Collection() {
    }
    virtual bool add(T* e) = 0;
    virtual int contains(T* e) = 0;
    virtual bool isEmpty() = 0;
    virtual bool remove(T* e) = 0;
    virtual int size() = 0;
};

#endif /* COLLECTION_H_ */

Listインタフェースの宣言

#ifndef LIST_H_
#define LIST_H_
#include "Collection.h"
template<class T>
class List: public Collection {
public:
    virtual ~List() {
    }
    virtual void add(int index, T* e) = 0;
    virtual T* get(int index) = 0;
    virtual T* remove(int index) = 0;
};

#endif /* LIST_H_ */

インタフェース宣言が完了すると、具体的な実装が行われます.Javaにおける汎用機構をC++のテンプレートでシミュレートし,Iteratorクラスをネストすることでそれぞれの反復器を実現した.JavaでIteratorが最もよく使う方法はhasNext()とnext()です.そこで本稿では,この2つの方法の実装についてのみ行った.
ArrayList.h

#ifndef ARRAYLIST_H_
#define ARRAYLIST_H_
#include "List.h"
template<class T, int bsz = 10> // bsz           
class ArrayList: public List { //   List Collection
    int len; //     
    int max; //     
    T** items;
    void inflate(); //     
    ArrayList(const ArrayList&); //             ，           
public:
    ArrayList() :
            len(0), max(bsz), items(new T*[bsz]) {
    }
    virtual ~ArrayList();
    bool add(T* e); //     
    int contains(T* e); //       
    bool isEmpty(); //         
    bool remove(T* e); //     
    int size(); //       
    void add(int index, T* e); //     
    T* get(int index); //     
    T* remove(int index); //     
    class Iterator;
    friend class Iterator;
    class Iterator { //      
        ArrayList& al;
        int index;
    public:
        Iterator(ArrayList& list) :
                al(list), index(0) {
        }
        bool hasNext() {
            if (index < al.len) {
                return true;
            }
            return false;
        }
        T* next() {
            if (hasNext()) {
                return al.items[index++];
            }
            return 0;
        }
    };
};
/**
 *      ，        。        inline。
 */
template<class T, int bsz>
ArrayList::~ArrayList() {
    for (int i = 0; i < len; i++) {
        delete items[i];
        items[i] = 0; //     
    }
    delete items; //     
}
template<class T, int bsz>
void ArrayList::inflate() {
    if (len == max) {
        max += bsz; //              
        T** newItems = new T*[max];
        for (int i = 0; i < len; i++)
            newItems[i] = items[i];
        delete[] items; //       ：     ！                  。
        items = newItems;
    }
}
template<class T, int bsz>
bool ArrayList::add(T* e) {
    inflate();
    items[len++] = e;
    return true;
}
template<class T, int bsz>
int ArrayList::contains(T* e) { //       ：                         。
    for (int i = 0; i < len; i++) {
        if (get(i) == e) {
            return i; //     
        }
    }
    return -1;
}
template<class T, int bsz>
int ArrayList::size() { //       
    return len;
}
template<class T, int bsz>
bool ArrayList::remove(T* e) { //                
    int index = contains(e);
    if (index != -1) {
        remove(index);
        return true;
    }
    return false;
}
template<class T, int bsz>
bool ArrayList::isEmpty() { //         
    if (len == 0) {
        return true;
    } else {
        return false;
    }
}
template<class T, int bsz>
void ArrayList::add(int index, T* e) { //     ：  
    inflate();
    T* newItems[++len];
    index--; //   
    for (int i = 0; i < len; i++) {
        if (i < index) {
            newItems[i] = items[i];
        }
        if (i == index) {
            newItems[i] = e;
        }
        if (i > index) {
            newItems[i] = items[i - 1];
        }
    }
    items = newItems;
}
template<class T, int bsz>
T* ArrayList::get(int index) { //     
    if (index < 0 || index >= len) {
        return 0;
    }
    return items[index];
}
template<class T, int bsz>
T* ArrayList::remove(int index) { //     
    if (index < 0 || index >= len) {
        return 0;
    }
    T* result = get(index);
    T* newItems[len - 1];
    for (int i = 0; i < len; i++) {
        if (i < index) {
            newItems[i] = items[i];
        }
        if (i > index) {
            newItems[i - 1] = items[i];
        }
    }
    delete items;
    items = newItems;
    len--;
    return result;
}
#endif /* ARRAYLIST_H_ */

明らかに,JavaにおけるArrayListと同様である.挿入を行う代価は高い.
LinkedList.h

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include "List.h"
#include 
using namespace std;
template<class T>
class LinkedList: public List {
    struct Item { //     
        Item(T* d, Item* nxt = 0, Item* pre = 0) : // d:    ，nxt:         ，pre:         。
                data(d), next(nxt), prev(pre) {
        }
        T* data;
        Item* next;
        Item* prev;
    };
    int len; //   
    Item* head; //       
    Item* tail; //       
    LinkedList(const LinkedList&); //       
public:
    LinkedList() :
            len(0), head(0), tail(0) {
    }
    virtual ~LinkedList() {
        if (len != 0) {
            while (head->next != 0) {
                Item* item = head;
                head = item->next;
                delete item;
                item = 0;
            }
        }
    }
    bool add(T* e); //     
    int contains(T* e); //       
    bool isEmpty(); //         
    bool remove(T* e); //     
    int size(); //       
    void add(int index, T* e); //     
    T* get(int index); //     
    T* remove(int index); //     
    class Iterator;
    friend class Iterator;
    class Iterator {
        LinkedList& ll;
        int index;
    public:
        Iterator(LinkedList& list) :
                ll(list), index(0) {
        }
        bool hasNext() {
            if (index < ll.len) {
                return true;
            }
            return false;
        }
        T* next() {
            if (hasNext()) {
                return ll.get(index++);
            }
            return 0;
        }
    };
};
/**
 *      
 */
template<class T>
bool LinkedList::add(T* e) { //     
    add(len, e);
    return true;
}
template<class T>
int LinkedList::contains(T* e) {
    Item* temp = head;
    for (int i = 0; i < len; i++) {
        if (temp->data == e) {
            return i;
        }
        temp = temp->next;
    }
    return -1;
}
template<class T>
bool LinkedList::isEmpty() {
    if (len == 0) {
        return true;
    } else {
        return false;
    }
}
template<class T>
bool LinkedList::remove(T* e) {
    int index = contains(e);
    if (index != -1) {
        remove(index);
        return true;
    }
    return false;
}
template<class T>
int LinkedList::size() {
    return len;
}
template<class T>
void LinkedList::add(int index, T* e) { //   
    if (index > 0 || index <= len) {
        if (len == 0) { //           ，head   tail       
            Item* first = new Item(e);
            head = first;
            tail = first;
        } else if (index == 0) { //          ，   head  
            Item* temp = new Item(e, head, 0);
            head->prev = temp;
            head = temp;
        } else if (index == len) { //           ，   tail  
            Item* temp = new Item(e, 0, tail);
            tail->next = temp;
            tail = temp;
        } else { //       
            Item* itemPrev = head;
            for (int i = 1; i < index; i++) {
                itemPrev = itemPrev->next;
            }
            Item* itemNext = itemPrev->next;
            Item* newItem = new Item(e, itemNext, itemPrev);
            itemPrev->next = newItem;
            itemNext->prev = newItem;
        }
        len++;
    }
}
template<class T>
T* LinkedList::get(int index) { //
    if (index >= 0 || index < len) {
        Item* result = head;
        for (int i = 0; i < index; i++) {
            result = result->next;
        }
        return result->data;
    }
    return 0;
}
template<class T>
T* LinkedList::remove(int index) {
    if (index > 0 || index <= len) {
        if (index == 0) { //   head  
            Item* temp = head;
            head = temp->next;
            head->prev = 0;
            T* result = temp->data; //           。
            delete item;
            item = 0;
            return result;
        } else if (index == len) { //   tail  
            Item* temp = tail;
            tail = temp->prev;
            tail->next = 0;
            T* result = temp->data;
            delete item;
            item = 0;
            return result;
        } else {
            Item* item = head;
            for (int i = 0; i < index; i++) { //           
                item = item->next;
            }
            Item* itemPrev = item->prev;
            Item* itemNext = item->next;
            itemPrev->next = itemNext;
            itemNext->prev = itemPrev;
            T* result = item->data;
            delete item;
            item = 0;
            return result;
        }
        len--;
    }
    return 0;
}

#endif /* LINKEDLIST_H_ */

 
LinkedListのすべてのクエリーは反復に依存して完了する必要があります.コストが高いです.しかし、挿入の代価は低い.この点はJDKでの表現と一致している.
まとめ:
(1)C++のメモリモデルはJavaより複雑であるため選択の余地も多い.本ルーチンは完全にポインタを用いて実現されており、基本的にJavaと同等の実現方式を採用している.もちろんビットコピー方式や&リファレンスを用いてもよい.興味のある方は自分で模索することができる.
(2)C++でのゴミ収集は手動で行う必要があり、Javaによる利便性はない.自己呼び出しも可能な構造関数も提供されているが、インスタンスを観察することですべての作業を構造関数に任せることができるわけではないことは明らかである.より典型的な方法は、関数内部で随時整理することである.
使用方法:単純なテストルーチン

#include "ArrayList.h"
#include "LinkedList.h"
#include 
#include 
using namespace std;
int main() {
    //   ArrayList
    ArrayList<int> ia;
    for (int i = 0; i < 15; i++) {
        int* v = new int(i);
        ia.add(v);
    }
    cout << ia.size() << endl;
    for (int i = 0; i < ia.size(); i++)
        cout << *ia.get(i) << endl;

    //   ArrayList
    ArrayList<string> sa;
    fstream in;
    in.open("Main.cpp");
    string line;
    while (getline(in, line)) {
        sa.add(new string(line));
    }
    for (int i = 0; i < sa.size(); i++) {
        cout << *sa.get(i) << endl;
    }
    in.close();

    //   LinkedList
    LinkedList<int> il;
    for (int i = 0; i < 33; i++) {
        il.add(new int(i));
    }
    for (int i = 0; i < il.size(); i++) {
        cout << *il.get(i) << endl;
    }

    //   LinkedList
    LinkedList<string> sl;
    in.open("Main.cpp");
    while (getline(in, line)) {
        sl.add(new string(line));
    }
    for (int i = 0; i < sl.size(); i++) {
        cout << *sl.get(i) << endl;
    }
    in.close();

    //   ArrayList   
    ArrayList<int>::Iterator iat(ia);
    while (iat.hasNext()) {
        cout << *iat.next() << endl;
    }

    //   ArrayList   
    ArrayList<string>::Iterator ist(sa);
    while (ist.hasNext()) {
        cout << *ist.next() << endl;
    }

    //   LinkedList   
    LinkedList<int>::Iterator ilt(il);
    while (ilt.hasNext()) {
        cout << *ilt.next() << endl;
    }

    //   LinkedList   
    LinkedList<string>::Iterator slt(sl);
    while (slt.hasNext()) {
        cout << *slt.next() << endl;
    }
}