stl容器學習總結

一 迭代器（iterator）

迭代器：
迭代器是類似指針的對象，STL算法利用它們對存儲在容器中的對象序列進行遍歷。
5種類別：1、輸入迭代器???
???????? 2、輸出迭代器???
???????? 3、前向迭代器???
???????? 4、雙向迭代器???
???????? 5、隨機訪問迭代器?

常用的迭代器：
?istream_iterator< >輸入流迭代器
?istreambuf_iterator<>輸入流塊迭代器
?ostream_iterator< >輸出流迭代器
?ostreambuf_iterator<> 輸出流塊迭代器
?back_insert_iterator<Container> 使用Container的push_back成員函數
?front_insert_iterator<Container> 使用Container的push_front成員函數
?insert_iterator<Container> 使用Container的insert成員函數
?reverse_iterator<Container> 從后向前使用Container的insert成員函數
?const——iterator<>

?

二 分配算符（Allocators）

看看stl中默認的allocator：

?namespace std {
????? template <class T>
????? class allocator {
??????? public:
????????? //type definitions
????????? typedef size_t??? size_type;?? //represent the size of the largest object in the allocation model
????????? typedef ptrdiff_t difference_type; //The type for signed integral values that can represent the distance between any two pointers in the???????????

????????????????????????????????? //allocation model
????????? typedef T*??????? pointer;
????????? typedef const T*? const_pointer;
????????? typedef T&??????? reference;
????????? typedef const T&? const_reference;
????????? typedef T???????? value_type;? //The type of the elements

????????? //rebind allocator to type U
????????? template <class U>
????????? struct rebind {
????????????? typedef allocator<U> other;
????????? };

????????? //return address of values
????????? pointer?????? address(reference value) const;
????????? const_pointer address(const_reference value) const;

????????? //constructors and destructor
????????? allocator() throw();
????????? allocator(const allocator&) throw();
????????? template <class U>
??????????? allocator(const allocator<U>&) throw();
????????? ~allocator() throw();

????????? //return maximum number of elements that can be allocated
????????? size_type max_size() const throw();

????????? // allocate but don't initialize num elements of type T
????????? pointer allocate(size_type num,
?????????????????????????? allocator<void>::const_pointer hint = 0);

????????? // initialize elements of allocated storage p with value value
????????? void construct(pointer p, const T& value);

????????? // delete elements of initialized storage p
????????? void destroy(pointer p);

????????? // deallocate storage p of deleted elements
????????? void deallocate(pointer p, size_type num);
????? };
?? }

看了上面的allocator，我們已經基本知道他的用處，他一般用在容器中，作為容器的一個成員，但一般是用模版參數傳入，這樣才可以讓我們換成我們自定義的allocator。

三 容器簡介

STL標準容器類簡介
標準容器類 ?說明
順序性容器
vector ??相當與數組，從后面快速的插入與刪除，直接訪問任何元素
deque ??雙隊列，從前面或后面快速的插入與刪除，直接訪問任何元素
list ??雙鏈表，從任何地方快速插入與刪除
關聯容器
set ??快速查找，不允許重復值
multiset ?快速查找，允許重復值
map ??一對一映射，基于關鍵字快速查找，不允許重復值
multimap ?一對多映射，基于關鍵字快速查找，允許重復值
容器適配器
stack ??后進先出
queue ??先進先出
priority_queue ?最高優先級元素總是第一個出列

所有標準庫共有函數
默認構造函數 ?提供容器默認初始化的構造函數。
復制構造函數 ?將容器初始化為現有同類容器副本的構造函數
析構函數 ?不再需要容器時進行內存整理的析構函數
empty ??容器中沒有元素時返回true,否則返回false
max_size ?返回容器中最大元素個數
size ??返回容器中當前元素個數
operator= ?將一個容器賦給另一個容器
operator< ?如果第一個容器小于第二個容器，返回true，否則返回false，
operator<= ?如果第一個容器小于或等于第二個容器，返回true，否則返回false
operator> ?如果第一個容器大于第二個容器，返回true，否則返回false
operator>= ?如果第一個容器大于或等于第二個容器，返回true，否則返回false
operator== ?如果第一個容器等于第二個容器，返回true，否則返回false
operator!= ?如果第一個容器不等于第二個容器，返回true，否則返回false
swap ??交換兩個容器的元素

其中operator>,operator>=,operator<,operator<=,operator==,operator!=均不適用于priority_queue

順序容器和關聯容器共有函數
begin ?該函數兩個版本返回iterator或const_iterator，引用容器第一個元素
end ?該函數兩個版本返回iterator或const_iterator,引用容器最后一個元素后面一位
rbegin ?該函數兩個版本返回reverse_iterator或const_reverse_iterator,引用容器最后一個元素
rend ?該函數兩個版本返回reverse_iterator或const_reverse_iterator，引用容器第一個元素前面一位
erase ?從容器中清除一個或幾個元素
clear ?清除容器中所有元素

下表顯示了順序容器和關聯容器中常用的typedef，這些typedef常用于變量、參數和函數返回值的一般性聲明。
value_type ?容器中存放元素的類型
reference ?容器中存放元素類型的引用
const_reference 容器中存放元素類型的常量引用，這種引用只能讀取容器中的元素和進行const操作
pointer ?容器中存放元素類型的指針
iterator ?指向容器中存放元素類型的迭代器
const_iterator ?指向容器中存放元素類型的常量迭代器，只能讀取容器中的元素
reverse_iterator ?指向容器中存放元素類型的逆向迭代器，這種迭代器在容器中逆向迭代
const_reverse_iterator ?指向容器中存放元素類型的逆向迭代器，只能讀取容器中的元素
difference_type ?引用相同容器的兩個迭代器相減結果的類型（list和關聯容器沒有定義operator-）
size_type ?用于計算容器中項目數和檢索順序容器的類型（不能對list檢索）

四 容器的比較

vector ?（連續的空間存儲,可以使用[]操作符）快速的訪問隨機的元素，快速的在末尾插入元素，但是在序列中間歲間的插入，刪除元素要慢，而且如果一開始分配的空間不夠的話，有一個重新分配更大空間，然后拷貝的性能開銷.
deque?（小片的連續，小片間用鏈表相連，實際上內部有一個map的指針，因為知道類型，所以還是可以使用[]，只是速度沒有vector快）快速的訪問隨機的元素，快速的在開始和末尾插入元素，隨機的插入，刪除元素要慢，空間的重新分配要比vector快,重新分配空間后，原有的元素不需要拷貝。對deque的排序操作，可將deque先復制到vector，排序后在復制回deque。
list?? （每個元素間用鏈表相連）訪問隨機元素不如vector快，隨機的插入元素比vector快，對每個元素分配空間，所以不存在空間不夠，重新分配的情況

set 內部元素唯一，用一棵平衡樹結構來存儲，因此遍歷的時候就排序了，查找也比較快的哦。
map 一對一的映射的結合，key不能重復。
multiset
multimap

stack 適配器，必須結合其他的容器使用，stl中默認的內部容器是deque。先進后出，只有一個出口，不允許遍歷。
queue 是受限制的deque，內部容器一般使用list較簡單。先進先出，不允許遍歷。
vector<bool> 與bitset<> ,前面的可以動態改變長度。
priority_queue 插入的元素就有優先級順序，top出來的就是優先級最高的了
valarray 專門進行數值計算的，增加特殊的數學函數。

接下來，stl的輸入輸出流

?

?