STL :基於各種結構良好的組件，核心的有：containers、iterators、algorithms
container：容器，用來存放和管理某種具體的對象，每種容器都有自己的特點，使用時候按需採用
iterator：迭代器，用來遍歷容器內的元素，這種介面可以獨立於某個容器而不關心內部實現，對外提供統一的訪問介面，例如向後移動++，取得元素*，其行為類似於指針但比指針安全多了。
algorithm：演算法，處理容器內的元素，例如查找、排序、修改等等。演算法使用iterator，因此一個演算法可以適用於大部分容器，因為基本都提供了相同的iterator介面
STL建立在數據和操作分離的基礎上，容器管理數據，演算法是操作，迭代器是中間的橋樑。
為了適應不同的需求，STL提供了不同種類的容器：
兩種類型：
順序容器sequence： vector，deque，list，元素有序且有個特定的位置，與插入的時間和位置有關
關聯容器associative： set，multiset，map，multimap，根據值內部自動排好序，與插入無關，僅僅取決於值
vector：動態數組
可以通過下標隨機存儲
尾部增加、刪除元素非常快 - 常量，中間或前面插入元素較慢 - 線性
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> coll;
for(int i=1; i<=6; i++)
{
coll.push_back(i);
}
for(int i=0; i<coll.size(); i++)
{
cout << coll[i] << " ";
}
cout << endl;
return 0;
}
/*
* 1 2 3 4 5 6
*/
vector<int> coll; //創建空容器沒有任何元素
push_back(); //順序容器都有的函數，尾部添加元素
size(); //返回元素的元素個數
[]；操作符取得容器內元素
deque：double-ended queue，動態數組，兩端都可以動態增長，首尾插入元素都很快
#include <iostream>
#include <deque>
using namespace std;
int main()
{
deque<float> coll;
for(int i=1; i<=6; i++)
{
coll.push_front(i * 1.1);
}
for(int i=0; i<coll.size(); i++)
{
cout << coll[i] << " ";
}
cout << endl;
return 0;
}
/*
* 6.6 5.5 4.4 3.3 2.2 1.1
*/
list：雙向鏈表，不提供隨機存儲，但是在中間插入和刪除元素非常快，每個鏈表元素都有個前驅和後繼
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<char> coll;
for(char c='a'; c<='z'; c++)
{
coll.push_back(c);
}
while(!coll.empty())
{
cout << coll.front() << " ";
coll.pop_front();
}
cout << endl;
return 0;
}
//a b c d e f g h i j k l m n o p q r s t u v w x y z
string:類似於vector<char>
包括basic_string<>,string, wstring三個
普通數組：可以調用STL中的algorithm
associative container: < 默認比較，二叉樹實現，模板參數
set：根據值排序好的集合，每個元素僅僅出現一次，不允許副本
multiset：允許副本的set，也就是相同的值出現
map：包含鍵值對key/value元素的容器，key 是基於一定標準的排序而且僅僅出現一次
multimap：允許出現相同的key
容器適配器：adapter，以基礎容器為藍本實現的
棧stack：後進先出
隊列queue：先進先出
priority_queue:優先順序隊列
iterator迭代器：代表容器中的某個位置
operator*：取得對象值，如果對象有members，還可以直接用->直接調用取得。
operator++：++移至下一個元素，--向前推一個元素
operator==：==兩個迭代器指向同一個位置，！=則相反
operator=：賦值（iter指向的元素的位置的賦值）
所有的容器都提供的方法支持迭代器：
begin()：容器的首個元素
end()：容器的超出末端，最後一個元素的下一個位置
#include <list>
using namespace std;
int main()
{
list<char> coll;
for(char c='a'; c<='z'; c++)
{
coll.push_back(c);
}
list<char>::const_iterator pos;
for(pos = coll.begin(); pos != coll.end(); pos++)
{
cout << *pos << " ";
}
cout << endl;
return 0;
}
//a b c d e f g h i j k l m n o p q r s t u v w x y z
每種容器都定義了兩種迭代器：
container::iterator : 讀寫
container::const_iterator : 只讀
list<char>iterator iter;
for(iter=coll.begin();iter!=coll.end();iter++)
{
*iter = toupper(*iter);
}
注意：++pos比 pos++更快
set 使用iterator：
#include <iostream>
#include <set>
using namespace std;
int main()
{
typedef set<int> IntSet;
IntSet coll;
coll.insert(3);
coll.insert(1);
coll.insert(5);
coll.insert(4);
coll.insert(1);
coll.insert(6);
coll.insert(2);
IntSet::const_iterator pos;
for(pos=coll.begin(); pos!=coll.end(); ++pos)
{
cout << *pos << " ";
}
cout << endl;
return 0;
}
//1 2 3 4 5 6
如果希望排序規則按照從大到小：typedef set<int, greater<int> > IntSet;
greater是一個函數對象
所有的關聯容器都提供了一個insert(）函數
#include <iostream>
#include <map>
using namespace std;
int main()
{
//typedef set<int> IntSet;
typedef multimap<int, string> IntString;
IntString coll;
coll.insert(make_pair(5,"tagged"));
coll.insert(make_pair(2,"a"));
coll.insert(make_pair(1,"this"));
coll.insert(make_pair(4,"of"));
coll.insert(make_pair(6,"strings"));
coll.insert(make_pair(1,"is"));
coll.insert(make_pair(3,"multimap"));
IntString::const_iterator pos;
for(pos=coll.begin(); pos!=coll.end(); ++pos)
{
//cout << pos->second << " ";
cout << (*pos).second << " ";
}
cout << endl;
return 0;
}
//this is a multimap of tagged strings
如果是map，還可以這樣賦值給map，類似於一個關聯數組：map<int, string> coll;
|
1
2
3
4
5
6
7
|
coll[5]"tagged";coll[2]"a";coll[0]"this";coll[4]"of";coll[6]"strings";coll[1]"is";coll[3]"multimap"; |
迭代器分類：
bidirectional，雙向的：list，set，multiset，map，multimap
random access，隨機存儲：也是雙向的而且有< 和 >：vector，deque，string
演算法：搜索、排序、拷貝、重新排序、修改、數值運算
以迭代器為基礎的全局函數
泛型函數式編程思維模式 - 介面，演算法可以操作不同的容器，只要有相同的介面，即迭代器
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
vector<int> coll;
vector<int>::iterator pos;
coll.push_back(2);
coll.push_back(5);
coll.push_back(4);
coll.push_back(1);
coll.push_back(6);
coll.push_back(3);
pos = min_element(coll.begin(), coll.end());
cout << "min : " << *pos << endl; //1
pos = max_element(coll.begin(), coll.end());
cout << "max : " << *pos << endl; //6
sort(coll.begin(), coll.end());
pos = find(coll.begin(), coll.end(), 3);
reverse(pos, coll.end());
for(pos=coll.begin(); pos!=coll.end(); ++pos)
{
cout << *pos << " ";
}
cout << endl;
return 0;
}
//1 2 6 5 4 3
區間：range
演算法處理的都是半開區間，[begin, end)
注意：只有隨機迭代器可以的運算不能用在別的不支持隨機迭代器的容器上，盡量使用迭代器通用的操作。
區間的begin一定是在end左邊，也就是說begin++最終是能到達end的
多個區間，通常第二個區間的元素個數是根據第一個區間推導得知
#include <iostream>
#include <vector>
#include <list>
using namespace std;
int main()
{
vector<int> coll1;
list<int> coll2;
for(int i=1; i<=9; i++)
{
coll1.push_back(i);
}
//確認目標區間內有足夠的元素空間
coll2.resize(coll1.size());
copy(coll1.begin(), coll1.end(), coll2.begin());
for(list<int>::iterator iter=coll2.begin(); iter!=coll2.end(); ++iter)
{
cout << *iter << " ";
}
cout << endl;
return 0;
}
//1 2 3 4 5 6 7 8 9
迭代器適配器：
1. 插入迭代器：insert iterator
2. 流迭代器：stream iterator
3. 逆向迭代器：reverse iterator
插入迭代器：
使得演算法以安插方式而非覆寫的方式運作。解決演算法目標空間不足的問題。
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <iterator>
#include <deque>
#include <set>
using namespace std;
int main()
{
list<int> coll1;
vector<int> coll2;
deque<int> coll3;
set<int> coll4;
for(int i=1; i<=9; i++)
{
coll1.push_back(i);
}
copy(coll1.begin(), coll1.end(), back_inserter(coll2));
copy(coll2.begin(), coll2.end(), ostream_iterator<int>(cout, " "));
//1 2 3 4 5 6 7 8 9
cout << endl;
copy(coll1.begin(), coll1.end(), front_inserter(coll3));
copy(coll3.begin(), coll3.end(), ostream_iterator<int>(cout, " "));
//9 8 7 6 5 4 3 2 1
cout << endl;
copy(coll1.begin(), coll1.end(), inserter(coll4, coll4.begin()));
copy(coll4.begin(), coll4.end(), ostream_iterator<int>(cout, " "));
//1 2 3 4 5 6 7 8 9
return 0;
}
back_inserter(container):安插於尾部迭代器，只有提供了push_back()成員函數才能使用此迭代器，vector, deque, list
front_inserter(container):前端插入迭代器，push_front()函數，deque，list
inserter(container, pos)：一般插入迭代器，在pos位置插入元素
流迭代器：stream iterator
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <string>
using namespace std;
int main()
{
vector<string> col;
//從cin讀入string到col，直到EOF
copy(istream_iterator<string>(cin), istream_iterator<string>(),
back_inserter(col));
//排序
sort(col.begin(), col.end());
//輸出到cout，並且無重複
unique_copy(col.begin(), col.end(),
ostream_iterator<string>(cout,"\n"));
return 0;
}
逆向迭代器：reverse iterator
將遞增運算轉換為遞減運算
所有容器都可以透過函數rbegin(), rend()產生reverse iterator
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
int main()
{
vector<int> coll;
for(int i=1; i<=9; ++i)
{
coll.push_back(i);
}
copy(coll.rbegin(), coll.rend(), ostream_iterator<int>(cout," "));
cout << endl;
return 0;
}
//9 8 7 6 5 4 3 2 1