STL(standard template library) 标準模闆庫
STL包括:
容器,container
疊代器,
算法
STL 分為三類:
順序容器
vector 直接通路任意元素,快速插入,删除尾部元素
deque 直接通路任意元素,快速插入,删除頭部和尾部元素
list 快速插入,删除任意位置元素
*vector資料以附加方式插入,效率高,但如果在任意位置(除了尾部)插入删除,效率很低
*deque和vector類似,在兩端插入删除效率高,内部進行插入删除效率低
*list 使用于頻繁在中間進行插入删除操作
vector額外開銷小,deque稍高,list最高
共同函數
assign(n,elem) 指點元素的N份拷貝加入到容器,拷貝前容器的元素被删除
assign(beg,end) 指派從疊代器beg到end之間的元素,指派前容器的元素被清空
push_back(elem) 附加到容器
pop_back() 删除容器尾元
front() 傳回首元素
back() 傳回容器尾元素
insert(position,elem) 将元素插入到容器指定位置,position 為疊代器
vector特有函數
vector(n,element) 構造向量,填入指定元素的N份拷貝
vector(veg,end) 構造一個向量,用疊代器beg到end之間的元素進行初始化
vector(size) 構造一個指定規模的向量
at(index):dataType 傳回指定位置的元素
deque特有的函數
deque(n,elem)
deque(beg,end)
deque(size)
at(index):dataType
push_front(element) 将元素插入到隊首
pop_front():dataType 删除隊首元素
list 特有的函數
list(n,elem)
list(beg,end)
list(size)
push_front(elem)
pop_front():dataType
remove(elem) 删除清單所有與指定元素相等的元素
remove_if(oper) 删除所有令oper(elem)為真的元素
splice(pos1,list2) 将list2中所有元素剪切到清單指定位置,調用函數後,list2為空
splice(pos1,list2,beg,end) 将list2中beg到end元素剪切到清單指定位置,調用函數後,list2為空
sort() 升序排序
sort(oper) 排序,标準由oper指定
merge(list2) 假定清單和list2都已排序,将list2合并到本清單,list為空
merge(list2,oper)
reverse() 反轉本清單
關聯容器
set 快速查詢元素,無重複關鍵字
multiset 與set相同,允許重複關鍵字
map 關鍵字/值對映射,不允許關鍵字重複,使用關鍵字快速查找
multimap 與map相同允許關鍵字重複
關聯容器共同函數
find(key)
lower_bound(key)
upper_bound(key)
count(key)
set:
容器擴充卡
stack 後進先出容器
queue 先進後出
priority_queue 高優先級元素先删除
stack():
push(elem) 将元素添加到杖頂
pop() 删除杖頂元素
top() 傳回棧頂元素
size()
empty() 若杖空,傳回真
queue:
push(elem)
pop()
front()
back()
size()
empty()
順序容器,關聯容器 稱為一級元素
所有容器的共同函數
無參構造函數
有參數構造函數
拷貝構造函數
析構函數
empty()
size() 傳回容器元素個數
運算符= 将一個元素複制到另一個元素
關系運算符(<,<=,>,>=,==,!=)
一級容器共同函數
c1.swap(c2) 交換兩個容器C1和C2中的元素
max_size() 傳回容器可容納最大元素數目
clear() 删除容器中所有元素
begin() 傳回容器首元素的疊代器
end() 傳回容器尾元素之後位置對應的疊代器
rbegin() 傳回容器尾元素的疊代器 用于逆序周遊
rend() 傳回容器首元素之前位置的疊代器
erase(beg,end) 删除容器從beg到end-1之間的元素,beg,end都是疊代器
疊代器:
vector<int>::iterator itvec; //聲明一個疊代器
itvec++; //将疊代器移到下一個元素
*itvec; //傳回疊代器所指向的元素
疊代器類型:
輸入疊代器 input iterator:用于從容器讀取元素,每一步隻能沿前移動一個元素
輸出疊代器 output iterator: 用于向容器中寫入一個元素,每一步隻能沿前移動一個元素
向前疊代器 forward iterator: 包含輸入輸出疊代器所有的功能,
雙向疊代器 bidrectioal iterator: 包含向前疊代器的所有功能,還有向後移動的能力。可自由選擇向前向後
随機通路疊代器 random-access iterator: 包含雙向疊代器功能,具有按任意順序通路任意元素的能力
STL容器 支援的疊代器類型
vector 随機通路
deque 随機通路
list 雙向
set 雙向
multiset 雙向
map 雙向
multimap 雙向
stack 不支援疊代器
queue 不支援
priority_queue 不支援
疊代器運算符
所有: ++p,p++
輸入疊代器: *p/p1==p2/p1!==p2/
輸出疊代器: *p
雙向疊代器: --p/p--
随機通路疊代器:
p+=i p-=i p+i p-i p1</<=/>/>=p2
p1[i]
預定義疊代器:
vector<it>::iterator it;
iterator:
const_iterator:和iterator一樣,差别:const_iterator是隻讀的
例如:
vector<int> vec;
vec.push_back(10);
vector<int>::iterator it=vec.begin();
vector<int>::const_iterator cit=vec.begin();
*it=12; //OK
*cit=13;//錯
反向疊代器:
reverse_iterator
const_reverse_iterator
istream_iterator
ostream_iterator
向量和集合的疊代器使用
#include <QCoreApplication>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
vector<int>intvec;
intvec.push_back(1);
intvec.push_back(2);
vector<int>::iterator itvec; //聲明一個疊代器
for(itvec=intvec.begin();itvec!=intvec.end();itvec++)
cout<<*itvec<<" ";
set<int>intset;
intset.insert(3);
intset.insert(6);
intset.insert(9);
set<int>::iterator itset;
for(itset=intset.begin();itset!=intset.end();itset++)
cout<<*itset<<" ";
return a.exec();
}
STL算法:
非修改性算法:不改變容器内容,隻是從容器擷取資訊
adjacent_find find lower_bound search binary_search find_end mismatch search_n
count find_first_of mismatch search_n count_if find_if
max_element upper_bound equal for_each min equal_range
includes min_element
修改性算法:插入,删除,重排等操作改變容器内容
copy....
數值算法: accumulate adjacent_difference inner_product partial_sum
堆算法:用于建立堆,從堆中删除元素,向堆插入元素以及排序堆 make_heap pop_heap push_heap sort_heap
copy函數:用于将一個容器的元素複制到另一個容器
template<typename inputIterator,typename outputIterator>
outputIterator copy(InputIterator begin,inputIterator end,outputIterator targetPossition)
函數将源容器 begin .. end-1 間的元素複制到容器targetPosition 起始位置,begin,end ,targetPosition
都是容器疊代器,函數傳回指向複制的最後一個元素之後位置的疊代器
提示:copy函數将資料元素從容器寫入輸出流是一種很友善的方法
警告:目标容器元素包含個數>=源容器元素個數,否則,導緻運作時出錯
fill和fill_n
fill
用于将制定值填入容器beg至end-1之間的元素中,覆寫掉填入位置的值
void fill(ForwardIterator begin,ForwardIterator end,&value)
fill_n
用于将制定值填入容器beg至beg+n-1之間的元素中,覆寫掉填入位置的值
void fill(ForwardIterator begin,size n,&value)
generate和generate_n
将函數傳回值填寫容器中的元素序列
void generate(ForwardIterator beg,ForwardIterator end,function gen);
void generate(ForwardIterator beg ,size n,function gen);
remove,remove_if,remove_copy,remove_copy_if
删除元素序列中給點值value比對的元素
replace,replace_if,replace_copy,replace_copy_if
将序列中所有給定相等的元素替代為新值
find,find_if,find_end,find_first_of
serach,serach_n
sort,vinary_search
adjacent_find,merge,inplace_merge
reverse,reverse_copy
rotate,rotate_copy
swap,iter_swap,swap_ranges
count,count_if
max_element,min_element
random_shuffle
for_each,transform
includes,set_union,set_differrenc,set_intersection,set_symmetric_difference
accumulate,adjacent_difference,inner_product,partial_sum