STLのvectorソース実装(クラウドアルゴリズム<<[]=リロード,new delete,throw catch)
12797 ワード
まとめ:
(1)異常クラス、try-throw-catchの応用:空間が申請に成功したかどうかを検査する;配列境界処理、境界処理エラー、throw異常クラスのデフォルト構造関数、catch後に異常クラスのオブジェクトでshow_を呼び出すMessage()メンバー関数は、特定の例外表示を行います.
(2)algorithmのcopy()の原型:
STL algorithmのcopy templateOutputIterator copy(InputIterator first,InputIterator last,OutputIteratorresult);役割:[first,last)範囲の要素をresultで始まる範囲にコピーします.memcopy()と同様です.
(3)演算子リロード:/const int&operator[](const size_t)const;
最初のconstは戻り値を言い、戻りは定数参照であり、2番目のconstはパラメータであり、関数内でこのパラメータを変更しないことを示します.最後のconstはthisポインタがconstを指していることを示します.つまり、この関数内で、このクラスのすべてのメンバーはconstに相当します.
演算子のリロード機能では、新しい演算子を使用したり、演算子の優先度を変更したりすることはできません.したがって、演算子のリロードバージョンは、式の値を計算するときに元の基本演算子と同じ優先度になります.
(4)演算子のリロードされたパラメータの個数:
1.メンバー関数として再ロードする場合:
両目演算子には1つのパラメータしかありません.単一演算子では、パラメータを明示的に説明することはできません.メンバー関数として再ロードすると、メンバー関数オブジェクトを呼び出すポインタを指すパラメータが常に隠されます.
2.友関数として再ロード:
演算子リロード関数は、友元関数であってもよい.友元関数を再ロードすると、隠されたパラメータthisポインタはありません.このように,両目演算子に対しては,友元関数に2つのパラメータがあり,単目演算子に対しては,友元関数に1つのパラメータがある.ただし、=,(),[]および->の実行子は、友元関数として再ロードできない場合があります.
(5)演算子の再ロード方法:
同じ演算記号に対して、通常の関数、友員関数、クラスメンバー関数の3つの方法でリロードを実現し、同じ機能を完了することが多い.通常の関数で演算子のリロードを実現する特徴は、カスタムクラスがクラスのメンバー変数にアクセスできるようにメンバー変数を公開しなければならないことであり、クラスのパッケージ性を破壊するため、このようなリロード方式は少ないか、使用しないことです.C++言語がこの方式を提供したのは,C言語との互換性のためである.クラスのパッケージ性を損なうことなく、クラスのメンバー変数はプライベートであってもよいが、クラスにメンバー関数を定義し、クラスのプライベートメンバー変数を操作できるようにする必要がある.これは実際の使用においても不便であるため、必要でない場合は使用しないでください.ここでは、coutおよびcin用のストリーム抽出子など、クラスメンバー関数でリロードを実現できない演算子があることを意味します.クラスメンバー関数によるリロード演算子は推奨されています.演算子リロード関数はクラスのメンバー関数であり、クラスのカプセル化要件を満たしています.
(6)リロード演算子は、4つの「変更不可」を保持します.
演算子のオペランドの個数を変更することはできません.演算子の元の優先度を変更することはできません.
演算子の既存の結合性を変更することはできません.演算子の既存の構文構造は変更できません.
(7)なぜ「<<」と「>>」をリロードした関数のみを友元関数または一般関数として定義できず、メンバー関数として定義できないのか
<<出力ストリームオブジェクト(私たちがよく使うcout)と出力するものの2つのパラメータがあります.例えば、cout<「haha」;すなわち、<<の最初のパラメータは、出力ストリームオブジェクトである必要があります.メンバー関数で<<リロードを実現し、
私たちはthisが最初のパラメータとして使用されることを知っていますが、これは要求に合致しません.
(8)ポインタを配列として用いる.
もしあなたがchar*pを定義しただけなら;そしてp[3]、p[4]、明らかにpは野指針です!指向が不確定!このやり方は間違っている.正しい使い方:char a[10]=「asdas」;p=a; そして、p[3]はa 3]またはint*pa=new int[5]に等価である.p[3]も可能です.配列を動的に申請したので、int pa[5]とは差が少ない(以下のように)
/**** overload operator [] ****/
一:vector異常類Myexcep.h
二:vectorクラスのコードvec.h
三vec.hの実現とmain関数Vec,cpp
四知識補足-vectorクラスでよく使われる関数は以下の通りです.
vectorクラスはベクトルクラスと呼ばれ、要素の数が変化するオブジェクト配列に使用される動的配列を実現します.配列のようにvectorクラスも0から始まる下付きで要素の位置を表す.ただし、配列とは異なり、vectorオブジェクトが作成されると、配列の要素数はvectorオブジェクトの要素数の増加と縮小に伴って自動的に変化します.
1.コンストラクタ
vector():空のvector を作成します.
vector(int nSize):nSize の要素数を持つvectorを作成します.
vector(int nSize,const t&t):要素の個数がnSizeで、値がt のvectorを作成します.
vector(const vector&):コンストラクション関数をコピー
vector(begin,end):vector に[begin,end)区間内の別の配列の要素をコピーする
2.関数の追加
void push_back(const T&x):ベクトルの末尾に要素X を追加
iterator insert(iterator it,const T&x):ベクトル内の反復器が要素を指す前に要素x を追加
iterator insert(iterator it,int n,const T&x):ベクトル内の反復器が要素を指す前にn個の同じ要素x を増加する
iterator insert(iterator it,const_iterator first,const_iterator last):ベクトル内の反復器が要素を指す前に別の同じタイプのベクトルを挿入する[first,last]間のデータ3.関数の削除
iterator erase(iterator it):ベクトル内の反復器が要素を指すを削除します.
iterator erase(iterator first,iterator last):ベクトルの[first,last]の要素を削除します.
void pop_back():ベクトルの最後の要素を削除
void clear():ベクトル内のすべての要素をクリア
4.遍歴関数
referenceat(int pos):pos位置要素の参照を返します.
reference front():ヘッダ要素の参照を返します.
reference back():末尾要素の参照を返します.
iterator begin():ベクトルヘッダポインタを返し、最初の要素を指します.
iterator end():ベクトルテールポインタを返し、ベクトルの最後の要素の次の位置を指します.
reverse_iterator rbegin():最後の要素を指す逆反復器
reverse_iterator rend():最初の要素の前の位置を指す逆反復器
5.判定関数
bool empty()const:ベクトルが空であるか否かを判断し、空であればベクトル中の無元6.サイズ関数
int size()const:ベクトル内の要素の個数を返すint capacity()const:現在のベクトルレッドが収容できる最大要素値を返す.
int max_size()const:最大許容vector要素数値を返します.
7.その他の関数
void swap(vector&):2つの同型ベクトルのデータを交換するvoid assign(int n,const T&x):ベクトルのn番目の要素の値をx に設定する.
void assign(const_iterator first,const_iterator last):ベクトル内の[first,last)要素が現在のベクトル要素に設定されている
(1)異常クラス、try-throw-catchの応用:空間が申請に成功したかどうかを検査する;配列境界処理、境界処理エラー、throw異常クラスのデフォルト構造関数、catch後に異常クラスのオブジェクトでshow_を呼び出すMessage()メンバー関数は、特定の例外表示を行います.
(2)algorithmのcopy()の原型:
STL algorithmのcopy template
(3)演算子リロード:/const int&operator[](const size_t)const;
最初のconstは戻り値を言い、戻りは定数参照であり、2番目のconstはパラメータであり、関数内でこのパラメータを変更しないことを示します.最後のconstはthisポインタがconstを指していることを示します.つまり、この関数内で、このクラスのすべてのメンバーはconstに相当します.
演算子のリロード機能では、新しい演算子を使用したり、演算子の優先度を変更したりすることはできません.したがって、演算子のリロードバージョンは、式の値を計算するときに元の基本演算子と同じ優先度になります.
(4)演算子のリロードされたパラメータの個数:
1.メンバー関数として再ロードする場合:
両目演算子には1つのパラメータしかありません.単一演算子では、パラメータを明示的に説明することはできません.メンバー関数として再ロードすると、メンバー関数オブジェクトを呼び出すポインタを指すパラメータが常に隠されます.
2.友関数として再ロード:
演算子リロード関数は、友元関数であってもよい.友元関数を再ロードすると、隠されたパラメータthisポインタはありません.このように,両目演算子に対しては,友元関数に2つのパラメータがあり,単目演算子に対しては,友元関数に1つのパラメータがある.ただし、=,(),[]および->の実行子は、友元関数として再ロードできない場合があります.
(5)演算子の再ロード方法:
同じ演算記号に対して、通常の関数、友員関数、クラスメンバー関数の3つの方法でリロードを実現し、同じ機能を完了することが多い.通常の関数で演算子のリロードを実現する特徴は、カスタムクラスがクラスのメンバー変数にアクセスできるようにメンバー変数を公開しなければならないことであり、クラスのパッケージ性を破壊するため、このようなリロード方式は少ないか、使用しないことです.C++言語がこの方式を提供したのは,C言語との互換性のためである.クラスのパッケージ性を損なうことなく、クラスのメンバー変数はプライベートであってもよいが、クラスにメンバー関数を定義し、クラスのプライベートメンバー変数を操作できるようにする必要がある.これは実際の使用においても不便であるため、必要でない場合は使用しないでください.ここでは、coutおよびcin用のストリーム抽出子など、クラスメンバー関数でリロードを実現できない演算子があることを意味します.クラスメンバー関数によるリロード演算子は推奨されています.演算子リロード関数はクラスのメンバー関数であり、クラスのカプセル化要件を満たしています.
(6)リロード演算子は、4つの「変更不可」を保持します.
演算子のオペランドの個数を変更することはできません.演算子の元の優先度を変更することはできません.
演算子の既存の結合性を変更することはできません.演算子の既存の構文構造は変更できません.
(7)なぜ「<<」と「>>」をリロードした関数のみを友元関数または一般関数として定義できず、メンバー関数として定義できないのか
<<出力ストリームオブジェクト(私たちがよく使うcout)と出力するものの2つのパラメータがあります.例えば、cout<「haha」;すなわち、<<の最初のパラメータは、出力ストリームオブジェクトである必要があります.メンバー関数で<<リロードを実現し、
私たちはthisが最初のパラメータとして使用されることを知っていますが、これは要求に合致しません.
(8)ポインタを配列として用いる.
もしあなたがchar*pを定義しただけなら;そしてp[3]、p[4]、明らかにpは野指針です!指向が不確定!このやり方は間違っている.正しい使い方:char a[10]=「asdas」;p=a; そして、p[3]はa 3]またはint*pa=new int[5]に等価である.p[3]も可能です.配列を動的に申請したので、int pa[5]とは差が少ない(以下のように)
/**** overload operator [] ****/
一:vector異常類Myexcep.h
#include<string>
#include<iostream>
using namespace std;
class Myexcep
{
public:
Myexcep() :m_exnote("Get a exception ") {}
Myexcep(const string &other){m_exnote = other;}
virtual ~Myexcep(){}
virtual void show_message() {cout << m_exnote <<endl;}
private:
string m_exnote;
};
class Outofbond :public Myexcep
{
public:
Outofbond() :m_outnote("Get a Out of bond exception ") {}
Outofbond(const string &other){m_outnote = other;}
~Outofbond(){}
void show_message(){cout << m_outnote <<endl;}
private:
string m_outnote;
};
class Allocfail :public Myexcep
{
public:
Allocfail():m_alonote("Get a Allocate fail exception "){}
Allocfail(const string &other){m_alonote = other;}
~Allocfail(){}
void show_message(){cout << m_alonote <<endl;}
private:
string m_alonote;
};
二:vectorクラスのコードvec.h
#ifndef VEC_H_H
#define VEC_H_H
#include "Myexce.h"
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cassert>
using namespace std;
template <class T>
class Vec
{
public:
typedef T* iterator;
typedef const T* const_iterator;
typedef size_t size_type;
typedef T value_type;
public:
Vec();
Vec(size_type,const T&);
Vec(const Vec &);
Vec& operator=(const Vec&);
~Vec();// create() uncreate()
T& operator[](size_type index);
const T& operator[](size_type index) const;//
void push_back(const T&);
void pop_back();
void erase(const size_type&);// ,push_back() grow()
size_type size() const {return (m_finished - m_start);}
iterator begin() {return m_start;}
const_iterator begin() const {return m_start;}
iterator end() {return m_finished;}
const_iterator end() const {return m_finished;}
private:
void create();
void create(size_type,const T&);
void create(const_iterator,const_iterator);// allocate() , init_fill(),init_copy()
void uncreate();
T* allocate(size_type);
void init_fill(iterator,iterator,const T&);
void init_copy(const_iterator,const_iterator,iterator);
void grow();// size(), max()
void append_element(const T&);
private:
iterator m_start;
iterator m_finished;
iterator m_limit;// ,
};
#endif
三vec.hの実現とmain関数Vec,cpp
//---------------------vec.cpp-------------
#include "vec.h"
/**** constructor ****/
template <class T>
Vec<T>::Vec()
{
create();
}
template <class T>
Vec<T>::Vec(size_type sz,const T& val)
{
create(sz,val);
}
template <class T>
Vec<T>::Vec(const Vec &rhs)
{
create(rhs.begin(),rhs.end());
}
template <class T>
Vec<T>& Vec<T>::operator=(const Vec& rhs)
{
if(&rhs == this)
return *this;
uncreate();
create(rhs.begin(),rhs.end());
return *this;
}
template <class T>
Vec<T>::~Vec()
{
uncreate();
}
/**** we have a create function to inital the data ****/
template <class T>
void Vec<T>::create()
{
m_start = m_finished = m_limit = NULL;
}
template <class T>
void Vec<T>::create(size_type sz,const T&val)
{
m_start = allocate(sz);
m_finished = m_limit = m_start+sz;
init_fill(m_start,m_limit,val);
}
template <class T>
void Vec<T>::create(const_iterator first,const_iterator end)
{
size_type sz = end - first;
m_start = allocate(sz);
m_finished = m_limit = m_start+sz;
init_copy(first,end,m_start);
}
template <class T>
void Vec<T>::uncreate()
{
iterator iter = m_start;
iterator end = m_limit;
for(; iter != end; )
{
iterator next_iter = iter + 1;
delete(iter);
iter = next_iter;
}
m_start = m_finished =m_limit =0;
}
/**** we define a function to allocate memory ****/
template <class T>
T* Vec<T>::allocate(size_type sz)
{
T* t = new T[sizeof(T) * sz];
if(!t)
{
throw Allocfail();
}
return t;
}
template <class T>
void Vec<T>::init_fill(iterator data,iterator limit,const T& val)
{
iterator iter = data;
iterator end = limit;
for(; iter != end; iter++)
{
*iter = val;
}
}
template <class T>
void Vec<T>::init_copy(const_iterator first,const_iterator end,iterator lhs)
{
copy(first,end,lhs);// copy 。。。
}
// STL algorithm copy template <class InputIterator, class OutputIterator> OutputIterator copy ( InputIterator first, InputIterator last, OutputIterator result );
// : [first, last) , result 。 :memcopy()
/**** overload operator [] ****/
template <class T>
T& Vec<T>::operator[](size_type index)
{
if(index >= size())
{
throw Outofbond();
}
return m_start[index];
}
template <class T>
const T& Vec<T>::operator[](size_type index) const
{
if(index >= size())
{
throw Outofbond();
}
return m_start[index];
}
/**** push_back ,pop_back,erase ****/
template <class T>
void Vec<T>::push_back(const T& val)
{
if(m_finished == m_limit)
grow();
append_element(val);
}
template <class T>
void Vec<T>::pop_back()
{
if(size() == 0)
return ;
m_finished--;
}
template <class T>
void Vec<T>::erase(const size_type& ipos)
{
if(ipos <0 || ipos >size())
{
throw Outofbond();
}
size_type iend = size()-1;
size_type i = ipos;
for(;i >= ipos && i < iend ; i++)
{
m_start[i] = m_start[i+1];
}// ,
m_finished--;
}
template <class T>
void Vec<T>::append_element(const T& val)
{
assert(m_finished!=m_start);
*m_finished++ = val;
}
inline size_t max(const size_t lhs,const size_t rhs)
{
return lhs > rhs ? lhs:rhs;
}
template <class T>
void Vec<T>::grow()
{
size_type new_size = max( 2*size(), 1);
iterator new_start = allocate(new_size);
iterator new_limit = new_start + new_size;
iterator new_finished = new_start + size();
init_copy(begin(),end(),new_start);
uncreate();
m_start = new_start;
m_finished = new_finished;
m_limit = new_limit;
}
/**** output the vector ****/
template <class T>
ostream& operator<<(ostream &os, const Vec<T> &me)
{
const T* iter = me.begin(); //Is "const T*" replaced by "const_iterator"?
for(;iter != me.end(); iter++)
{
os << *iter <<", ";
}
return os;
}
/**** test the case ****/
int main()
{
try
{
cout << "Test begin: " << endl;
Vec<int> v1(4,3);
cout << "After v1(4,3), v1[3]: " << v1[3] <<endl;
Vec<int> v2(v1);
cout << "After v2(v1), v2--value: " << v2 <<endl;
Vec<int> v3;
v3 = v2;
cout << "After v3=v2, v3--value: " << v3 <<endl;
v3.pop_back();
cout << "After v3.pop_back(), v3--value: " << v3 <<endl;
v3.push_back(5);
cout << "After v3.push_back(5), v3--value: " << v3 <<endl;
Vec<double> v4(5, 222.2);
cout << "After v4(5,222.2),v4--value:" << v4 << endl;
Vec<char> v5(5, 'a');
cout << "After v5(5,222.2),v5--value:" << v5 << endl;
string aa = "hi world";
// string bb = aa;
// cout << bb << endl;
Vec<string> v6(5, aa);
v6.push_back("hello ");
cout << v6 << endl;
Vec<string> v7;
v7 = v6;
cout << v7[4] << endl;
v3.erase(2);
cout << "After v3.erase(2), v3--value: " << v3 <<endl;
cout << "After v3.erase(2), v3--value: " << v3[6] <<endl;
}
catch(Outofbond e)
{
e.show_message();
exit(-1);
}
catch(Allocfail e){
e.show_message();
exit(-1);
}
return 0;
}
四知識補足-vectorクラスでよく使われる関数は以下の通りです.
vectorクラスはベクトルクラスと呼ばれ、要素の数が変化するオブジェクト配列に使用される動的配列を実現します.配列のようにvectorクラスも0から始まる下付きで要素の位置を表す.ただし、配列とは異なり、vectorオブジェクトが作成されると、配列の要素数はvectorオブジェクトの要素数の増加と縮小に伴って自動的に変化します.
1.コンストラクタ
vector():空のvector を作成します.
vector(int nSize):nSize の要素数を持つvectorを作成します.
vector(int nSize,const t&t):要素の個数がnSizeで、値がt のvectorを作成します.
vector(const vector&):コンストラクション関数をコピー
vector(begin,end):vector に[begin,end)区間内の別の配列の要素をコピーする
2.関数の追加
void push_back(const T&x):ベクトルの末尾に要素X を追加
iterator insert(iterator it,const T&x):ベクトル内の反復器が要素を指す前に要素x を追加
iterator insert(iterator it,int n,const T&x):ベクトル内の反復器が要素を指す前にn個の同じ要素x を増加する
iterator insert(iterator it,const_iterator first,const_iterator last):ベクトル内の反復器が要素を指す前に別の同じタイプのベクトルを挿入する[first,last]間のデータ3.関数の削除
iterator erase(iterator it):ベクトル内の反復器が要素を指すを削除します.
iterator erase(iterator first,iterator last):ベクトルの[first,last]の要素を削除します.
void pop_back():ベクトルの最後の要素を削除
void clear():ベクトル内のすべての要素をクリア
4.遍歴関数
referenceat(int pos):pos位置要素の参照を返します.
reference front():ヘッダ要素の参照を返します.
reference back():末尾要素の参照を返します.
iterator begin():ベクトルヘッダポインタを返し、最初の要素を指します.
iterator end():ベクトルテールポインタを返し、ベクトルの最後の要素の次の位置を指します.
reverse_iterator rbegin():最後の要素を指す逆反復器
reverse_iterator rend():最初の要素の前の位置を指す逆反復器
5.判定関数
bool empty()const:ベクトルが空であるか否かを判断し、空であればベクトル中の無元6.サイズ関数
int size()const:ベクトル内の要素の個数を返すint capacity()const:現在のベクトルレッドが収容できる最大要素値を返す.
int max_size()const:最大許容vector要素数値を返します.
7.その他の関数
void swap(vector&):2つの同型ベクトルのデータを交換するvoid assign(int n,const T&x):ベクトルのn番目の要素の値をx に設定する.
void assign(const_iterator first,const_iterator last):ベクトル内の[first,last)要素が現在のベクトル要素に設定されている