C++コンテナ--list
86157 ワード
list紹介
Listは、定数範囲内の任意の位置で挿入および削除できるシーケンスコンテナであり、listを前後に双方向に反復できる下位の双方向チェーンテーブル構造であり、双方向チェーンテーブルの各要素は互いに関連しない独立したノードに格納され、ノード内のポインタは前の位置と後の位置listおよびforward_を指すlistはよく似ています.違いはforward_です.Listは単一チェーンテーブルであり、前方反復のみをサポートし、他のシーケンスコンテナ(array,vector,deque)と比較してより単純で効率的になります.listは通常任意の場所に挿入されます.削除要素の実行効率が良いlistの最大の欠点は、ランダムアクセスをサポートしないことです.6番目の要素にアクセスするには、頭部または末尾からその位置に遍歴する必要があります.この位置には線形時間のオーバーヘッドが必要です.Listは、各ノードの関連情報を保存するために追加のスペースが必要です.
共通インタフェース
こうぞう
反復器
Listの反復器はオリジナルのポインタではなく、カプセル化されたポインタによってここで反復器を直接ポインタとして理解することができ、このポインタはlistのあるノードが実現する前に反復器のカプセル化を実現の構想について述べることを指す.
注意:
beginとendは順方向反復器、反復器は++操作、反復器はrbeginとrendを逆方向反復器、反復器は++操作、反復器はconstシリーズ反復器を前に移動し、値の変更は許されない
容量
要素参照
注意:
referenceは参照の名前を変更し、typedefを使用してconst_の名前を変更します.referenceはconst参照の名前を変更します
変更
List反復器の失効問題
反復器失効すなわち反復器が指すノードが削除されるlistの下位構造は先頭ノードの双方向ループチェーンテーブルであり、listに挿入すると反復器が失効することはない削除時に削除された反復器だけが失効し、他の反復器は影響を受けない
シミュレーション実装list
反復パッケージ
Listの反復器反復器には2つの実現方式がある:1.原生ポインタ-vector;2.原生ポインタをカプセル化した反復器は、以下の方法を備えなければならない.参照を解除し、operator*()を再ロードします. ->スペースを指すメンバーにアクセスし、反復器はoperator->()を再ロードする必要があります. ポインタは++を後方に移動でき、反復器はoperator++()、operator++(int)を再ロードする必要があり、双方向チェーンテーブルの場合は再ロードする必要があります– 反復器は必要なのでoperator=()、operatorをリロードする必要があります!=();
カプセル化された反復器はクラステンプレートパラメータで入力できます
シミュレーション実装
Listは、定数範囲内の任意の位置で挿入および削除できるシーケンスコンテナであり、listを前後に双方向に反復できる下位の双方向チェーンテーブル構造であり、双方向チェーンテーブルの各要素は互いに関連しない独立したノードに格納され、ノード内のポインタは前の位置と後の位置listおよびforward_を指すlistはよく似ています.違いはforward_です.Listは単一チェーンテーブルであり、前方反復のみをサポートし、他のシーケンスコンテナ(array,vector,deque)と比較してより単純で効率的になります.listは通常任意の場所に挿入されます.削除要素の実行効率が良いlistの最大の欠点は、ランダムアクセスをサポートしないことです.6番目の要素にアクセスするには、頭部または末尾からその位置に遍歴する必要があります.この位置には線形時間のオーバーヘッドが必要です.Listは、各ノードの関連情報を保存するために追加のスペースが必要です.
共通インタフェース
こうぞう
list(); // list
list(size_type n, const value_type& val = value_type()); // list n val
list(const list& x); //
list(InputIterator first, InputIterator last); // list
反復器
Listの反復器はオリジナルのポインタではなく、カプセル化されたポインタによってここで反復器を直接ポインタとして理解することができ、このポインタはlistのあるノードが実現する前に反復器のカプセル化を実現の構想について述べることを指す.
begin(); //
end(); //
rbegin(); // reverse_iterator， end
rend(); // reverse_iterator, begin
// (C++11) const
cbegin();
cend();
crbegin();
crend();
注意:
beginとendは順方向反復器、反復器は++操作、反復器はrbeginとrendを逆方向反復器、反復器は++操作、反復器はconstシリーズ反復器を前に移動し、値の変更は許されない
容量
bool empty() const; // list
size_t size() const; // list
要素参照
reference front(); // list
const_reference front() const; // const
reference back(); // list
const_reference back() const; // const
注意:
referenceは参照の名前を変更し、typedefを使用してconst_の名前を変更します.referenceはconst参照の名前を変更します
変更
void push_front(const value_type& val); //
void pop_front(); //
void push_back(const value_type& val); //
void pop_back(); //
iterator insert(iterator position, const value_type& val); // pos
void insert(iterator position, size_type n, const value_type& val); // pos n val
void insert(iterator position,InputIterator first,InputIterator last);
// [first, last)
iterator erase(iterator position); // pos
iterator erase(iterator first, iterator last); // [first,last)
void swap(list& x); // list
void resize(size_type n, value_type val = value_type());
// list n ， val
void clear(); // list
List反復器の失効問題
反復器失効すなわち反復器が指すノードが削除されるlistの下位構造は先頭ノードの双方向ループチェーンテーブルであり、listに挿入すると反復器が失効することはない削除時に削除された反復器だけが失効し、他の反復器は影響を受けない
#include
// list ， ， ，
void TestListIterator1() {
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
std::list<int> l(array, array + sizeof(array) / sizeof(array[0]));
auto it = l.begin();
while (it != l.end()) {
// erase() ，it ， it ， it ，
l.erase(it);
++it;
}
}
//
void TestListIterator() {
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
std::list<int> l(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end()) {
// l.erase(it++);
it = l.erase(it);
}
}
シミュレーション実装list
反復パッケージ
Listの反復器反復器には2つの実現方式がある:1.原生ポインタ-vector;2.原生ポインタをカプセル化した反復器は、以下の方法を備えなければならない.
カプセル化された反復器はクラステンプレートパラメータで入力できます
//
template<class T, class Ref, class Ptr>
class ListIterator {
public:
typedef ListNode<T>* PNode;
typedef ListIterator<T, Ref, Ptr> Self;
public:
ListIterator(PNode pNode = nullptr)
: _pNode(pNode)
{}
ListIterator(const Self& l)
: _pNode(l._pNode)
{}
Ref operator*() {
return _pNode->_val;
}
Ptr operator->() {
return &(operator*());
}
Self& operator++() {
_pNode = _pNode->_next;
return *this;
}
Self operator++(int) {
Self tmp(*this);
_pNode = _pNode->_next;
return tmp;
}
Self& operator--() {
_pNode = _pNode->_prev;
return *this;
}
Self operator--(int) {
Self tmp(*this);
_pNode = _pNode->_prev;
return tmp;
}
bool operator!=(const Self& l) {
return _pNode != l._pNode;
}
bool operator==(const Self& l) {
return _pNode == l._pNode;
}
PNode _pNode;
};
//
template<class T, class Ref, class Ptr, class Iterator>
class ListReverseIterator {
typedef ListReverseIterator<T, Ref, Ptr, Iterator> Self;
public:
ListReverseIterator(const Iterator& it)
: _it(it)
{}
ListReverseIterator(const Self& s)
: _it(s._it)
{}
Ref operator*() {
Iterator tmp = _it;
return *(--tmp);
}
Ptr operator->() {
return &(operator*());
}
// ++ --
Self& operator++() {
--_it;
return *this;
}
Self operator++(int) {
Iterator tmp(_it);
--_it;
return tmp;
}
Self& operator--() {
++_it;
return *this;
}
Self operator--(int) {
Iterator tmp(_it);
++_it;
return tmp;
}
bool operator!=(const Self& s) {
return _it != s._it;
}
bool operator==(const Self& s) {
return _it == s._it;
}
private:
Iterator _it;
};
シミュレーション実装
#include