使用STL vector 接口：
#include <iostream>
#include <vector>
using namespace std;
void TestVector( )
{
vector<int> v1;
v1.push_back( 1 );
v1.push_back( 2 );
v1.push_back( 3 );
v1.push_back( 4 );
PrintVector( v1 );
vector<int> v2( 3, 10 );
PrintVector( v2 );
}
int main( )
{
TestVector( );
return 0;
}
//封裝是為了複用，調用這個函數即可，不用每次都寫列印代碼
void PrintVector( vector<int>& v1 )//引用 //加 const 編譯不通過 如果要編譯通過 1.普通疊代器(可讀，可寫) 2.const 疊代器(可讀) 3.反向疊代器(反着周遊)
{
//疊代器 是 類似指針的一個對象 -> 和智能指針相似
//[begin, end) 疊代器是 左閉右開 區間
vector<int>::iterator it/*疊代器對象*/; //如果用const_iterator 則 ++(*it) 會報錯， 因為不能給常量指派
it = v1.begin( );
while ( v1.end( ) != it )
{
//1.列印
cout << *it << " ";
++it;
//2.列印奇數
//if ( 0 != *it % 2 )
//{
// cout << *it << " ";
//}
/*++it;*/
//3.每個數加 1
//++(*it);
//++it;
}
cout << endl;
//反向疊代器 是 倒着走
vector<int>::const_reverse_iterator rIt = v.rbegin( );
while ( v.rend() != rIt )
{
cout << *rIt << " ";
++rIt;
}
cout << endl;
}
list：
#include <iostream>
#include <list>
using namespace std;
void TestList( );
void PrintList( list<int>& l );
int main( )
{
TestList( );
return 0;
}
void TestList( )
{
list<int> l1;
l1.push_back( 1 );
l1.push_back( 2 );
l1.push_back( 3 );
l1.push_back( 4 );
list<int> l2( 5, 1 ); //帶值的初始化
}
void PrintList( /*const*/list<int>& l )
{
list<int>::/*const_*/iterator it = l.begin( );
while ( l.end( ) != it )
{
cout << *it << " ";
/* *it = 10; *///如果是 const疊代器 則不能指派
++it;
}
cout << endl;
}
模拟實作：STL 中 名字為 list， 我們模拟實作名字為 List
:
//連結清單的四次實作
//1.C -> 基本實作和面試題
//2.C++ -> 面向對象 C 和 C++差別 深拷貝
//3.C++ -> 泛型程式設計 + T -- string
//4.資料結構 -- STL
//搜尋 ctrl + f -> 快捷鍵查找F3 -> 倒着搜尋 shift + F3
//名稱 小寫加下劃線
#pragma once//防止重定義
#include "Iterator.h"//為了實作 List 反向疊代器
template<class T>
struct __ListNode
{
T _data;
__ListNode<T>* _next;
__ListNode<T>* _prev;
__ListNode( const T& x )
:_data( x )
,_next( NULL )
,_prev( NULL )
{}
};
//疊代器 是一個 類 通過 運算符重載 使它像指針一樣使用
//T T& T* 有了 T 為什麼 還有傳 T&, T* ，為了實作 const疊代器
//T const T& const T*
template<class T, class Ref, class Ptr>
struct __ListIterator // sizeof(__ListIterator) == 4 因為它裡面還是一個指向節點的指針，隻是通過封裝1讓它變為新的類型， 大小不變，為4
{
typedef __ListNode<T> Node;
typedef __ListIterator<T, Ref, Ptr> Self;
typedef Ref Reference;//反向疊代器
typedef Ptr Pointer;//反向疊代器
__ListIterator( Node* node )
:_node( node )
{}
Ref operator*( )//1.出了作用域存在，是以傳&。而且為了效率， 如果不傳引用， string對象， 深拷貝。 2. 引用是為了可以更改資料
{
return _node->_data;
}
const Ref operator*( )//const 疊代器 中 用 const 修飾 Ref即可。
{
return _node->_data;
}
Ptr operator->( )
{
return &_node->_data;
}
Self& operator++( )//前置++ //注意後置 前置的差別
{
_node = _node->_next;
return *this;
}
Self operator++( int )//後置++ 不能給& 因為出了作用域對象不存在，不能給引用
{
Self tmp( _node );//構造 1
//Self tmp( *this );//拷貝構造 2
_node = _node->_next;
return tmp;
}// 1 or 2 時 構造 or 拷貝構造， 然後 return 時， 再拷貝構造個臨時對象傳回。
Self& operator--( )
{
_node = _node->_prev;
return *this;
}
Self operator--( int )
{
Node* cur = _node;
_node = _node->_prev;
return Self( cur );//先構造出一個對象，再拷貝構造出臨時對象傳回，但是他們是在傳回步驟的一個表達式裡，編譯器會進行優化 -> 不會先構造再拷貝構造而是 直接構造臨時對象 作為傳回值, 是以 這裡的代碼 比 後置++實作的好.
}
bool operator!=( const Self& s ) const
{
return /*this->*/_node != s._node;//指針全是通過->調用，調用函數也是->。 對象全是 通過.調用
}
Node* _node;
};
template<class T>
class List
{
typedef __ListNode<T> Node;
public:
typedef __ListIterator<T, T&, T*> Iterator;
typedef __ListIterator<T, const T&, const T*> ConstIterator;//實作 const 疊代器
typedef ReverseIterator<ConstIterator> ConstReverseIterator;//注意這一句和後一句順序不能颠倒， 否則， 最後一句 的ReverseIterator 已經被 typedef 這裡就用不了了
typedef ReverseIterator<Iterator> ReverseIterator;
//此時隻能實作 List 的反向疊代器， Vector的反響疊代器不能這樣實作， 需要類型萃取才可以！
Node* GetNode( const T& x )
{
return Node* node = new Node( x );
}
List( )
{
_head = GetNode( T( )/*匿名對象*/ );
_head->_next = _head;
_head->_prev = _head;
}
~List( )
{
Clear( );//清掉資料 。 but 析構還沒完， 除了清掉資料還要把整個連結清單全銷毀了
delete _head;
_head = NULL;
}
Iterator Begin( )//const對象不能調用 普通成員函數
{
return Iterator( _head->_next );
}
//不能這樣寫
//Iterator Begin( ) const
//{
// return Iterator( _head->_next );
//}
//const 成員函數 ， 被 const 對象調用 --> 不可修改
//應該傳回 const 疊代器
ConstIterator Begin( ) const
{
return ConstIterator( _head->_next );
}
Iterator End( )
{
return Iterator( _head );
}
ConstIterator End( ) const
{
return ConstIterator( _head );
}
ReverseIterator RBegin( )//如圖， 正向疊代器和反向疊代器的 begin 和 end 完全對應起來！ 也由此圖了解解引用 --> 為什麼取前一個位置資料。 Node* --> 正向疊代器 --> 反向疊代器
{
return ReverseIterator( End( ) );
}
ReverseIterator REnd( )
{
return ReverseIterator( Begin( ) );
}
ConstReverseIterator RBegin( ) const
{
return ConstReverseIterator( End( ) );
}
ConstReverseIterator REnd( ) const
{
return ConstReverseIterator( Begin( ) );
}
void PushBack( const T& x )
{
//我們以前實作方法
//Node* tail = _head->_prev;
//Node* tmp = GetNode( x );
//tail->_next = tmp;
//tmp->_prev = tail;
//tmp->_next = _head;
//_head->_prev = tmp;
//STL 實作方法
Insert( End( ), x );
}
void PushFront( const T& x )
{
Insert( Begin( ), x );
}
void PopBack( )
{
//assert( !Empty( ) );//不為空才行， 否則不讓你删除
//Node* tail = _head->_prev;
//Node* prev = tail->_prev;
//
//delete tail;
//prev->_next = _head;
//_head->_prev = prev;
Erase( _head->_prev );
Erase( --End( ) );
}
void PopFront( )
{
Erase( Begin( ) );
}
void Clear( )
{
Iterator it = Begin( );//注意不用寫為: List<int>::Iterator 因為這是類裡面， Iterator就是屬于這個類域的
while ( End( ) != it )
{
Node* del = it._node; //注意 為. 而不是 ->
++it;
delete del;
}
_head->_next = _head; //别忘了 ，還需要重置
_head->_prev = _head;
}
Iterator Find( const T& x )
{
//Node* cur = _head->_next;
//while ( _head != cur )
//{
// if ( x == cur->_data )
// {
// return cur;//隐式類型轉換， Iterator為單參數構造函數。 用 cur 構造臨時對象發貨
// //return Iterator( cur );
// }
// else
// {
// cur = cur->_next;
// }
// //如string s = "1111"， 一個是c風格字元串， 一個是字元串， 即用了 隐式類型轉換
// return _head;
//}
Iterator it = Begin( ); //成員函數可以調用其他成員函數 是因為有隐含this指針
while ( End( ) != it )
{
if ( x == *it )
{
return it;
}
else
{
++it;
}
}
return it; //這裡傳回的 是 End這個位置
}
//在 pos 的前面進行插入
void Insert( Iterator pos, const T& x )
{
assert( pos._node );//pos這個疊代器中的結點不能為空
Node* next = pos._node;
Node* prev = next->_prev;
Node* cur = new Node( x );
prev->_next = cur;
cur->_prev = prev;
cur->_next = next;
next->_prev = cur;
}
//測試考慮到：1。正常情況， 2.邊界情況(頭，尾，空)
//但這種情況會引起我們下面提出的問題，疊代器失效， 是以這種方案不好， 采用下面的方案
//void Erase( Iterator pos )
//{
// assert( (End( ) != pos) && (NULL != pos._node) );//等于 End( ) 相當于删除 頭節點 --> 1.沒有結點情況 2.給了非法的位置 ，如有多個結點，你卻給了我頭節點。
// Node* del = pos._node;
// Node* prev = del->_prev;
// Node* next = del->_next;
// delete del;
// prev->_next = next;
// next->_prev = prev;
//}
Iterator Erase( Iterator pos )
{
assert( (End( ) != pos) && (NULL != pos._node) );
Node* del = pos._node;
Node* prev = del->_prev;
Node* next = del->_next;
delete del;
prev->_next = next;
next->_prev = prev;
//解決疊代器失效方法， 傳回 删除位置下一個位置的疊代器
return next; //單參數構造函數 進行 隐式轉換
}
bool Empty( )
{
return _head == _head->_next;
}
//[)
//模闆類中成員函數也可以給成 模闆函數
template <class InputIterator>
void Assign( InputIterator first, InputIterator last )
{
Clear( );
while ( first != last )
{
PushBack( *first );
++first;
}
}
protected:
Node* _head;
};
struct AA
{
int _a1;
int _a2;
};
template<template T>
void PrintList( const List<T>& l1 )//因為隻是列印， 是以你不應該修改我 傳const對象
{//const 對象 應該調用 const疊代器
List<int>::Iterator it = l1.Begin( );//const對象 不能調用 非const 的成員函數 Begin( ) -> 加一個const的成員函數 Begin( )傳回const 疊代器
//這裡應該是 const 疊代器.
while ( l1.End( ) != it )
{
cout << *it << " ";
++it;
}
cout << endl;
}
template<template T>
void PrintList( const List<T>& l1 )
{
List<int>::Iterator it = l1.Begin( );//假設const對象調用const 成員函數，但傳回普通疊代器
while ( l1.End( ) != it )
{
*it = 10;//const 對象， 理論上裡面資料不能修改， 但是這裡可以修改， 這不合理。 是以 把普通疊代器 -> const 疊代器 :
//此時(const疊代器)編譯報錯， 不能給常量指派
cout << *it << " ";
++it;
}
cout << endl;
}
void TestList( )
{
List<int> l1;
l1.PushBack( 1 );
l1.PushBack( 2 );
l1.PushBack( 3 );
l1.PushBack( 4 );
//疊代器
List<int>::Iterator it = l1.Begin( );拷貝構造 -> 這裡是淺拷貝(沒毛病！)
while ( l1.End( ) != it )//it != l1.End( ) -> it.operator!=( &it/*傳 this 指針*/, l.End( ) ) 但是像我那樣寫可以嗎？
{//判斷條件若為小于 or 不等于 則是 左閉右開 區間
cout << *it << " ";
++it;
}
cout << endl;
List<AA> l2;
l2.PushBack( AA( ) );
l2.PushBack( AA( ) );
List<AA>::Iterator it2 = l2.Begin( );
while ( l2.End( ) != it2 )
{
//cout << *it2 << " ";//此時 *it2 -> 是AA (它是自定義類型，不是内置類型 ，庫裡面不支援它的輸出)
cout << it2->_a1 << " ";//疊代器中包含指向節點的指針 疊代器通過 重載 operator->( ), 它成為指向節點中資料的指針
//(it2.operator->( ))(指向節點中資料(AA)的指針) -> _a1;
//編譯器做的就是 把 it2->_a1 解釋為 it2.operator->( ) ->_a1
//(it2.operator->( )) == it2-> 然後 ，如果要通路a1 應該是： it2->->_a1 但這樣可讀性不好，是以編譯器做了優化，隻需要一個 ->.
//operator->(這是函數名) 隐含了一個參數 this指針，但是不需要我們傳
++it2;
}
cout << endl;
List<int>:;Iterator pos = l1.Find( 3 );
l1.Insert( pos, 30 );
}
C++中：
左右都存在 -> 指派
左不存在 -> 拷貝構造
*it = 10;
it 如果是普通疊代器 調用 operator*( ) 傳回 Ref 我也不知道 Ref 是誰。
但如果是普通疊代器 傳回的是 T&
const疊代器 則傳回 const T&.
*it 傳回_node->_data(Ref) 或者AA& 如何通路AA的成員呢.
(*it2)._a1 對象.成員 指向對象指針->成員 我們把疊代器想象為指向結點中資料(此時為AA)的指針。 如指向AA的指針 則it2->_a1更形象 是以疊代器支援 operator->( )
(it2.operator->( ))->_a1; const疊代器，(it2.operator->( )) 傳回 const T* 是以此時_a1不能指派。 const 修飾指針指向内容。
const疊代器用于const對象， 如Print函數 我傳const對象，是不想讓你修改，你隻周遊通路就可以了。 但我要傳引用，而不是傳值(因為拷貝構造代價太大). 但引用我又不能讓你改變我。 是以 傳 const List<int>& l1 傳 const疊代器（如果是普通疊代器， 則雖然是const對象，但還是可以修改裡面資料） 因為這個const隻能修飾這個對象及對象成員(_node)，但const不能修飾到 _node後面連結的結點。 如果普通疊代器取到後面結點， 依舊修改你的資料。這樣不合理。 是以傳 const疊代器。 const對象調用 const 成員函數Begin() 傳回const疊代器。
const 對象 ->（使用） const 疊代器。 const對象調用成員函數Begin( )時是調用 const版本 Begin() -> 它傳回const疊代器，也限制保證了const對象不能使用普通疊代器 不會出錯。
string s( "1" );//拷貝構造
string s = "21213"; -> （隐式轉換）先構造，再拷貝構造 但是編譯器優化後 就是一個構造了. 凡是 傳回值 ，指派， 傳參 在一個步驟裡面時， 凡是臨時對象時， 編譯器都會把它優化成一個步驟。
STL 中 empty -> 時間複雜度O(1) size ->時間複雜度 O(n)
連結清單中别寫出這樣的代碼
for ( size_t i = 0; i < l.size( ); ++i ){ } 不好的代碼 時間複雜度為O(n*n) 因為每次 l.size( ) 都會周遊連結清單一遍
list中接口介紹：
max_size( ) size_t( -1 )會轉換成無符号最大的數; 最多可以有多少位元組
pop_front/push_front 都是調用 Insert 和 Erase 實作
resize 更改大小 你的資料多則删除資料， 你的資料少則補充資料， 多出來的位置給預設值或你傳的值
cleae 清掉資料，不清頭節點
assign:
list<int> l1; l1.push_back( 1 ); ----- list<int> l2;
template<class InputInterator>
void assign( InputIterator first, InputIterator lase );
可以認為InputInterator就是一個疊代器， 因為它是一個模闆函數
l2.assign( l1.begin( ), l1.end( ) ); 疊代器區間， 左閉右開
PrintList( l1 );
PrintList( l2 );
也就是把我資料給你， 同時給資料也可以進行選擇， 如 ++l1.begin( ), --l1.end( ) 也就是給疊代器區間，
vectot<int> v; //可以給不同疊代器，但疊代器裡必須是相同資料類型(如這裡必須是 int 資料類型必須比對)
v.push_back( 10 );
12.assign( v.begin( ), v.end( ) ); //也就是說 它是模闆函數 根據實際實際類型進行推演 疊代器類型
remove 删除值 erase 位置
尾插時： 原 雙向循環連結清單 有結點 和 沒有結點 兩種情況分析如圖：
1.有結點
2.沒有結點：
如圖分析可知，兩種情況是一樣的，可以用相同的邏輯處理尾插操作，而不需要分别處理。
尾删時:
Insert 在指定位置pos的前面插入資料 和
erase 删除指定位置的資料:
疊代器失效：比如我們上面代碼中，第一次實作的erase方法，傳回void, 即沒有傳回值， 此時++it，程式會挂，這就是疊代器失效：
此時，如圖：
STL 中解決疊代器失效采用的方法是， erase方法會傳回一個疊代器， 這個疊代器是被删除位置的下個位置的疊代器
但如下使用方式就有問題：
list<int>::iterator it = l1.begin( );
while ( l1.end( ) != it )
{
if ( 0 == *it % 2 )
l1.erase( it );
++it;
}
此時程式會跳過一些資料。
正确寫法：
while ( l1.end( ) != it )
{
if ( 0 == *it % 2 )
it = l1.erase( it );
else
++it;
}
如果， 現在就是失效了， 怎麼解決！即我們代碼就是這樣：
while ( l1.end( ) != it )
{
if ( 0 == *it % 2 )
l1.erase( it );
++it;
}
此時需要做的，就是修改 erase方法：
Iterator Erase( Iterator& pos )
{
assert( (End( ) != pos) && (NULL != pos._node) );
Node* del = pos._node;
Node* prev = del->_prev;
Node* next = del->_next;
delete del;
prev->_next = next;
next->_prev = prev;
pos = prev;//2
return next;
}
疊代器 用 * 和 -> 修改資料
STL算法中去重：
測試各種list各種接口：
void TestList1( )
{
list<int> l1;
l1.push_back( 3 );
l1.push_back( 2 );
l1.push_back( 1 );
l1.push_back( 0 );
l1.push_back( 4 );
l1.sort( );//預設升序， 降序需要給一個仿函數
l1.sort( less<int>( ) );// less 小于 < 即升序 greater 大于 > 降序
l1.unique( );//去重 邏輯如圖
l1.reverse( );//逆置
l1.remove( 2 );//remove 删不存在元素 沒什麼影響（現象）.
//erase 需要 配合 Find(即傳回它一個位置) 但 List 沒Find方法 解決方法 --> 算法 用 STL 算法 find
list<int>::iterator pos = find( l1.begin( ), l1.end( ), 4 );//#include <algorithm>
//l1.erase( pos ); //删除不存在元素時， 程式會挂， 是以像下面一樣寫
if ( l1.end( ) != pos )
{
l1.erase( pos );
}
PrintList( l1 );
}
注意我們模拟實作list時：一定不能建立一個 list.h 再建立一個 list.cpp因為模闆不能分離編譯。
反向疊代器實作 ---> Iterator.h:
//反向疊代器的++， 即正向疊代器的 --
//是以， 利用擴充卡模式實作反向疊代器
//STL 中 反向疊代器 模闆參數是 Iterator --> 即你傳我 什麼容器的疊代器， 我就變成什麼容器的反向疊代器
//32 位系統下指針 是4位元組。 64位系統下， 8位元組或4位元組(關鍵看你是 32 位程式 還是 64位程式)。
//Node* 4位元組， Iterator 包含封裝Node* 但不增加它大小， 也是4位元組。 從意義上變為新的類型。 反向疊代器也是4位元組。
#pragma once
//class 和 typename 差別
template <class/*改為typename*/ Iterator>//編譯錯誤 ， 因為下面用到Iterator::Reference。 它不認識Iterator， 因為Iterator是模闆， 是以沒執行個體化前沒有具體類型， 編譯器找不到 Reference。 我們需要在 前面加 typename 才行
class ReverseIterator
{
protected:
Iterator _current;
typedef ReverseIterator<Iterator> Self;
public:
ReverseIterator( Iterator it )
: _current( it )
{}
typename Iterator::Reference operator*( )//編譯器找不到Reference，但是在其它地方可以找到， 我們幫助編譯器确認這個事情， 是以加 typename( 取模闆類的内嵌類型時(沒有執行個體化， 沒有生成代碼， 編譯器不認識它) )
{
Iterator tmp = _current;
return *( --tmp );
//之是以要這樣實作，如圖，為了和正向疊代器的 begin 和 end 位置對應起來, 是以要取到第一個資料( 4 )時 ---> *( --rbegin( ) )
}
typename Iterator::Pointer operator->( )
{
return &operator*( );
}
Self& operator++( )//前置
{
--_current;
return *this;
}
Self operator++( int );//後置 傳回++前的臨時對象， 是以不用引用
Self& operator--( )
{
--_current;
return *this;
}
Self operator--( int );
bool operator!=( const Self& s )
{
return _current != s._current;
}
};
void PrintMyListR( List<int>& l1 )
{
List<int>::ReverseIterator rit = l1.RBegin( );
while ( l1.REnd( ) != rit )
{
cout << *rit << " ";
++rit;
}
cout << endl;
}
void PrintMyListR( const List<int>& l1 )
{
List<int>::ConstReverseIterator rit = l1.RBegin( );
while ( l1.REnd( ) != rit )
{
cout << *rit << " ";
++rit;
}
cout << endl;
}