c++arrayListの実装
5019 ワード
≪データ構造|Data Structure|emdw≫:データ構造はデータ・オブジェクトであり、このオブジェクトのインスタンスおよびインスタンスを構成する要素には関連する関数によって規定されています.
C++にはint,boolなど多くの基本データ型が存在し,データ構造はこれらの基本データ型を関数と対応する規則を組み合わせて新しいデータ型を形成する.
抽象クラスLinearList:
抽象クラスLinearListは純粋な虚関数を多く用い,挿入,削除などの線形配列に含まなければならない一般的な関数を規定している.含む
純粋な虚関数のクラスはインスタンス化できないため、継承クラスはすべての純粋な虚関数を実現する必要があります.ここで解析関数は虚関数の形式で書かれており、クラスで虚関数を定義すると、クラスは自動的に虚関数テーブルを生成し、サブクラスの関数が虚関数を呼び出すと、システムはまずベースクラスの虚関数を呼び出し、その後、虚関数テーブルはその関数を呼び出すサブクラスが対応するサブクラスの解析関数を優先的に呼び出す.したがって、ベースクラスの構造関数を呼び出す前にサブクラスの構造関数を優先的に呼び出すことを保証し、メモリの漏洩を防止します.
ArrayListクラス:
上のarrayListクラスはベースクラスのすべての純粋な虚関数を書き換え,他の多くの関数を追加した.
上はコンストラクション関数、ostringstreamは文字列入出力ストリームで、まず文字列をostringstreamストリームに入力し、str()関数で取り出します.
次に、指定した配列サイズnewに基づいて連続した新しいメモリを出力し、初期化サイズlistSizeは0になります.
上は構造関数をコピーするので簡単ですが、stlのcopy関数を使っています.前にこの関数を話したことがありますが、ここでは言いません.
補足:クラスのメンバー関数は、クラスのインスタンス内のプライベート変数に直接アクセスできます.また、使用するnewのクラスでは、コンストラクション関数はデフォルトのレプリケーションコンストラクション関数を使用しないでください.
直接newは配列を出したので、デフォルトの配列は基本データ型なので、operator[]とfind()関数をカスタマイズせずにelement[theIndex]とfind()のstl関数を直接使用しました.
ここではstlのfindの関数を紹介しましょう.
1.find(first, end, value);
戻り区間[first,end]の最初の値がvalueに等しい要素の位置を返し、見つからない場合はendを返します.関数は、反復器とポインタ、すなわち位置情報を返します.
2.find_if(first, end, bool pred);
一元判定式でpredがtrueである区間[first,end]の最初の要素を満たす位置を返し,endを返すことが見つからない.
3.find_first_of(first1, end1, first2, end2);
区間[first 1,end 1]で区間[first 2,end 2]と重複する最初の要素の位置を返します.
すなわち、1番目の区間の1番目の要素を選択して、2番目の区間にこの要素があるかどうかを見て、ある場合は位置を返して、2番目の要素を続けていないので、順番に探します.
配列の中で1つの要素を削除するのは実はその右側のデータを左に移動して、最後にその析構は実は呼び出さなくてもいいです.
上はこれが挿入のコードで、挿入と削除は同じようにすべて要素を移動して、挿入はtheIndexの後の要素をすべて1位後ろに移動して、theIndexを空けます
そしてtheIndexという位置に挿入するコードを挿入しますが、ここで問題があります.それは、元の配列がいっぱいであれば挿入操作を実行できないので、元の配列の長さを2倍に拡大しなければなりません.私たちはnewの新しい数のグループ長度を元の2倍にし、前の配列メモリを削除しなければなりません.古いメモリのポインタを新しいメモリに向けます.
上は重荷<
クラスメンバー関数を再ロードしてから<
以上の基本機能を満たすarrayListクラスは、あまり書かれていません.
C++にはint,boolなど多くの基本データ型が存在し,データ構造はこれらの基本データ型を関数と対応する規則を組み合わせて新しいデータ型を形成する.
抽象クラスLinearList:
template
class linearList
{
public:
virtual ~linearList() {};
virtual bool empty() const=0;
virtual int size() const=0;
virtual int indexOf(const T& theElement) const=0;
virtual T& get(int theIndex) const=0;
virtual void erase(int theIndex)=0;
virtual void insert(int theIndex,const T& theElement)=0;
virtual void output(ostream& out)const=0;
} 抽象クラスLinearListは純粋な虚関数を多く用い,挿入,削除などの線形配列に含まなければならない一般的な関数を規定している.含む
純粋な虚関数のクラスはインスタンス化できないため、継承クラスはすべての純粋な虚関数を実現する必要があります.ここで解析関数は虚関数の形式で書かれており、クラスで虚関数を定義すると、クラスは自動的に虚関数テーブルを生成し、サブクラスの関数が虚関数を呼び出すと、システムはまずベースクラスの虚関数を呼び出し、その後、虚関数テーブルはその関数を呼び出すサブクラスが対応するサブクラスの解析関数を優先的に呼び出す.したがって、ベースクラスの構造関数を呼び出す前にサブクラスの構造関数を優先的に呼び出すことを保証し、メモリの漏洩を防止します.
ArrayListクラス:
template
class arrayList:public linearList
{
public:
arrayList(int initialCapacity=10);
arrayList(const arrayList&);
~arrayList(){delete [] element};
bool empty() const {return listSize==0;}
int size() const {return listSize;}
T& get(int theIndex)const;
int indexOf(const T& theElement)const;
void erase(int theIndex);
void insert(int theIndex,const T& theElement);
void output(ostream& out)const;
int capacity(){return arrayLength;}
protected:
void checkIndex(int theIndex)const;
T* element;
int arrayLength;
int listSize;
};
上のarrayListクラスはベースクラスのすべての純粋な虚関数を書き換え,他の多くの関数を追加した.
template
arrayList::arrayList(int initialCapacity)
{
if(initialCapacity<1)
{
ostringstream s;
s<0";
throw illegalParameterValue(s.str());
}
arrayLength=initialCapacity;
element=new T[arrayLength];
listSize=0;
}
上はコンストラクション関数、ostringstreamは文字列入出力ストリームで、まず文字列をostringstreamストリームに入力し、str()関数で取り出します.
次に、指定した配列サイズnewに基づいて連続した新しいメモリを出力し、初期化サイズlistSizeは0になります.
template
arrayList::arrayList(const arrayList& theList)
{
arrayLength=theList.arrayLength;
listSize=theList.listSize;
element=new T[arrayLength];
copy(theList.element,theList.element+listSize,element);
}
上は構造関数をコピーするので簡単ですが、stlのcopy関数を使っています.前にこの関数を話したことがありますが、ここでは言いません.
補足:クラスのメンバー関数は、クラスのインスタンス内のプライベート変数に直接アクセスできます.また、使用するnewのクラスでは、コンストラクション関数はデフォルトのレプリケーションコンストラクション関数を使用しないでください.
template
void arrayList::checkIndex(int theIndex)const
{
if(theIndex<0||theIndex>listSize)
{
ostringstream s;
s<
T& arrayList::get(int theIndex) const
{
checkIndex(theIndex);
return element[theIndex];
}
template
int arrayList::indexOf(const T& theElement)const
{
int theIndex=(int)(find(element,element+listSize,theElement)-element);
if(theElement==listSize)
return -1;
else
return theIndex;
} 直接newは配列を出したので、デフォルトの配列は基本データ型なので、operator[]とfind()関数をカスタマイズせずにelement[theIndex]とfind()のstl関数を直接使用しました.
ここではstlのfindの関数を紹介しましょう.
1.find(first, end, value);
戻り区間[first,end]の最初の値がvalueに等しい要素の位置を返し、見つからない場合はendを返します.関数は、反復器とポインタ、すなわち位置情報を返します.
2.find_if(first, end, bool pred);
一元判定式でpredがtrueである区間[first,end]の最初の要素を満たす位置を返し,endを返すことが見つからない.
3.find_first_of(first1, end1, first2, end2);
区間[first 1,end 1]で区間[first 2,end 2]と重複する最初の要素の位置を返します.
すなわち、1番目の区間の1番目の要素を選択して、2番目の区間にこの要素があるかどうかを見て、ある場合は位置を返して、2番目の要素を続けていないので、順番に探します.
template
void arrayList::erase(int theIndex)
{
checkIndex(theIndex);
copy(element+theIndex+1,element+listSize,element+theIndex);
element[--listSize].~T();
}
配列の中で1つの要素を削除するのは実はその右側のデータを左に移動して、最後にその析構は実は呼び出さなくてもいいです.
template
void changeLength1D(T*& a,int oldLength,int newLength)
{
if(newLength<0)
throw illegalParameterValue("new length must be>=0");
T* temp=new T[newLength];
int number=min(oldLength,newLength);
copy(a,a+number,temp);
delete [] a;
a=temp;
}
template
void arrayList::insert(int theIndex,const T& theElement)
{
if(theIndex<0||theIndex>listSize)
{
ostringstream s;
s< 上はこれが挿入のコードで、挿入と削除は同じようにすべて要素を移動して、挿入はtheIndexの後の要素をすべて1位後ろに移動して、theIndexを空けます
そしてtheIndexという位置に挿入するコードを挿入しますが、ここで問題があります.それは、元の配列がいっぱいであれば挿入操作を実行できないので、元の配列の長さを2倍に拡大しなければなりません.私たちはnewの新しい数のグループ長度を元の2倍にし、前の配列メモリを削除しなければなりません.古いメモリのポインタを新しいメモリに向けます.
template
void arrayList::output(cout->out)const
{
copy(element,element+listSize,ostream_iterator(cout," "));
}
template
ostream& operator<& x)
{
x.output(out);
return out;
}
上は重荷<
クラスメンバー関数を再ロードしてから<
以上の基本機能を満たすarrayListクラスは、あまり書かれていません.