STL常用數(shù)據(jù)結(jié)構(gòu)總結(jié)

2019-11-08 02:26:49

字體：大中小

供稿：網(wǎng)友

數(shù)據(jù)結(jié)構(gòu)機(jī)考的你，想不想偷懶？快來看一看c++的STL吧。 STL（standard template library）標(biāo)準(zhǔn)模板庫提供了一些列數(shù)據(jù)結(jié)構(gòu)和算法，幫你更高效地解決問題。下面列出一些常用的(STL的一小部分)數(shù)據(jù)結(jié)構(gòu)和算法接口，標(biāo)準(zhǔn)采用sgi stl，參考自The annotated STL Sources （所有容器采用泛型設(shè)計，可采用泛型方式調(diào)用，頭文件為容器名）一、vector 向量容器 vector與array相比，其差異在于vector動態(tài)分配空間（線性連續(xù)地址），并且集成了一系列操作函數(shù)。 public接口：(構(gòu)造函數(shù)與析構(gòu)函數(shù)不列出且有省略) iterator begin(); //返回首元素 inerator end(); //返回末尾元素的下一個位置指針，注意不是最后一個元素 size_type size() const; //返回vector長度 size_type capacity() const; //返回容器容量 bool empty() const; //返回向量是否為空 reference Operator[]; //可用[]符號進(jìn)行同數(shù)組一樣的下標(biāo)訪問 void push_back(const T& x); //將x元素添加到最后 void pop_back(); //將最后一個元素取出 iterator erase(iterator position); //刪除position位置的元素，并返回操作后position位置的元素 void resize(size_type new_size); //改變向量長度 void clear(); //清空向量遍歷：迭代器方法、直接線性遍歷方法二、 stack 棧 stack沒有迭代器，不可遍歷。 stack底層采用list實現(xiàn)。 public接口：(構(gòu)造函數(shù)與析構(gòu)函數(shù)不列出且有省略) bool empty() const; size_type size() cosnt; reference top(); //返回棧頂元素 void push(const value_type& x); //元素入棧 void pop(); //棧頂元素彈棧三、queue 隊列 queue沒有迭代器，不可遍歷。 queue底層采用list實現(xiàn)。 public接口：(構(gòu)造函數(shù)與析構(gòu)函數(shù)不列出且有省略) bool empty() const; size_type size() const; reference front(); //返回隊首元素 reference back(); //返回隊尾元素 void push(const value_type& x); //元素入隊 void pop(); //元素出隊四、 set 集合 set中所有元素會根據(jù)鍵值自動排序，set中不允許有相同鍵值元素。set是非線性排列的，其底層采用紅黑樹，采用平衡二叉搜索機(jī)制，set的迭代器是const類型，不能寫入修改值。（默認(rèn)升序）set的遍歷采用迭代器，迭代器重載過操作符對平衡樹進(jìn)行中序遍歷。 public接口：(構(gòu)造函數(shù)與析構(gòu)函數(shù)不列出且有省略) iterator begin() const; iterator end() const; bool empty() const; size_type size() const; void swap(set<Key, Compare, Alloc>& x); //交換兩個集合中元素 pair<iterator, bool> insert(cosnt value_type& x); //插入x元素 void insert(InputIterator first, InputIterator last); //插入first到last區(qū)間(前閉后開)內(nèi)的所有元素 void erase(iterator position); //刪除position位置迭代器的元素 size_type erase(const key_type& x); //刪除key為x的元素 void erase(iterator first, iterator last); //刪除集合中等于first到last區(qū)間內(nèi)的所有元素 void clear(); iterator find(const key_type& x); //查找key等于x的元素，查找成功返回x的迭代指針，失敗返回end() 在algorithm里提供了一些列對set操作的算法： OutputIterator set_union(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result); //函數(shù)求兩個集合的并集并返回結(jié)果 OutputIterator set_intersection(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result); //函數(shù)求兩個集合的交集并返回結(jié)果 OutputIterator set_difference(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result); //函數(shù)求兩個集合的差集，出現(xiàn)在[first1, last1)但不出現(xiàn)在[first2, last2)的元素五、map 鍵值對容器所有元素會根據(jù)鍵值排序（默認(rèn)升序），map中的所有元素都是pair，同時擁有實值和鍵值，pair的第一元素為鍵值，第二元素為實值。map不允許有兩個相同鍵值的元素。map底層實現(xiàn)依靠紅黑樹機(jī)制。map的迭代器不能修改鍵值，但可以修改實值，遍歷采用迭代器方式，自動對平衡樹進(jìn)行中序遍歷。 public接口：(構(gòu)造函數(shù)與析構(gòu)函數(shù)不列出且有省略) iterator begin(); iterator end(); iterator rbegin(); bool empty() const; size_type size() const; T& operator[] (const key_type& k); //根據(jù)key值，通過下邊方式取得實值 pair<iterator, bool> insert(const value_type& x); iterator insert(iterator position, const value_type& x); void insert(InputIterator first, InputIterator last); void erase(iterator position); size_type erase(const key_type& x); void erase(iterator first, iterator last); //刪除集合中等于first到last區(qū)間內(nèi)的所有元素 iterator find(const key_type& x); //查找key等于x的元素，查找成功返回x的迭代指針，失敗返回end() 鍵值對的構(gòu)造，可以采用make_pair的方式，也可以采用map::value_type(k, T())的類型轉(zhuǎn)換。

上一篇：Kmeans++

下一篇：常用排序算法小結(jié)