C++實(shí)現(xiàn)STL容器的示例

更新時(shí)間：2022年02月04日 10:27:52 作者：__JAN__

本文主要介紹了C++實(shí)現(xiàn)STL容器的示例，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

各大容器的特點(diǎn)：

1.可以用下標(biāo)訪問(wèn)的容器有（既可以插入也可以賦值）：vector、deque、map；

特別要注意一下，vector和deque如果沒(méi)有預(yù)先指定大小，是不能用下標(biāo)法插入元素的！

2. 序列式容器才可以在容器初始化的時(shí)候制定大小，關(guān)聯(lián)式容器不行；

3.注意，關(guān)聯(lián)容器的迭代器不支持it+n操作，僅支持it++操作。

適配器的概念

適配器的意思就是將某些已經(jīng)存在的東西進(jìn)行限制或者組合變成一個(gè)新的東西，這個(gè)新的東西體現(xiàn)一些新的特性，但底層都是由一些已經(jīng)存在的東西實(shí)現(xiàn)的。

STL中的容器

vector :矢量（并非數(shù)學(xué)意義上的） STL最簡(jiǎn)單的序列類型，也是一些適配器的默認(rèn)底層類

deque：雙端隊(duì)列可從頭尾出隊(duì)入隊(duì)

list：雙向鏈表

forwardd_list：?jiǎn)蜗蜴湵?，功能少一些，不可反轉(zhuǎn)。

queue：隊(duì)列，一個(gè)適配器類（底層模板類默認(rèn)deque），不允許隨機(jī)訪問(wèn)和歷遍；展示隊(duì)列的接口

priority_queue：優(yōu)先隊(duì)列，一個(gè)適配器類（底層模板類默認(rèn)vector），默認(rèn)大根堆（最大的元素在最前面）。

stack：棧，一個(gè)適配器類（底層模板類默認(rèn)vector），給底層類提供典型的棧接口。

特別的

array：并非STL容器，長(zhǎng)度固定，但也能使用一些STL算法

容器基本都有以下幾種功能，具體情況視容器而定

p,q,i,j表示迭代器

序列基本要求，拿vector舉例，p , q , i , j 表示迭代器

vector <int> vec (n,t); //創(chuàng)建并初始化
vector <int> (n,t); ? ? //創(chuàng)建匿名對(duì)象并初始化
vector <int> vec (i,j); //創(chuàng)建并初始化為另一個(gè)容器[i,j)內(nèi)容
vector <int> ?(i,j); ? ?//創(chuàng)建匿名對(duì)象并初始化為另一個(gè)容器[i,j)內(nèi)容
vec.insert(p,t); ? ? ? ?//插入t到p的前面
vec.insert(p,n,t); ? ? ?//插入n個(gè)t到p的前面
vec.insert(p,i,j); ? ? ?//將區(qū)間[i,j)插入到p的前面(可以為自己的區(qū)間后者其他容器的區(qū)間)
vec.erase(p); ? ? ? ? ? //刪除p指向的元素
vec.erase(p,q); ? ? ? ? //刪除[p,q)區(qū)間的元素
vec.clear(); ? ? ? ? ? ?//清空容器，等價(jià)于vec.erase(vec.begin(),vec.end());

一些可選要求，見(jiàn)名知義了，不解釋。

.front();
.back();
.push_front();
.push_back();
.pop_front();
.pop_back();
 
[n]
.at(n);

.at()和 [ ]很像，不過(guò)前者在越界是會(huì)引發(fā)一個(gè)異常，我們可以進(jìn)行捕獲

deque

用雙端隊(duì)列演示上面的一些

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
void show(int & t)
{
    cout << t << " ";
}
int main()
{
    deque<int> a(10,5);
    a.push_front(10);
    a.push_back(20);
    for_each(a.begin(),a.end(),show);
    cout << endl;
    a.pop_front();
    a.pop_back();
    for_each(a.begin(),a.end(),show);
    a.push_back(999);
    cout << endl << a.at(10) << " " << a[10];
    try{
        cout << endl << a.at(100);
    }
    catch (out_of_range){
        cout << "越界訪問(wèn)";
    }
    return 0;
}

運(yùn)行結(jié)果

queue

一些queue的方法

priority_queue

可以用其進(jìn)行堆排序

int main()
{
    srand((unsigned)time(NULL));
    priority_queue<int> pq;
    for(int i=0;i<100;i++){
        int x = rand() %1000+1;
        pq.push(x);
    }
    for(int i=0;i<100;i++){
        cout << pq.top() << " ";
        if(i%10 == 0)
            cout << endl;
        pq.pop();
    }
    return 0;
}

運(yùn)行結(jié)果

時(shí)間復(fù)雜度O(nlogn)，因?yàn)槭腔跇?shù)形結(jié)構(gòu)，每次pop時(shí)間復(fù)雜度O(logn)，進(jìn)行n次。

一些方法

list

list的一些基本成員函數(shù)

void merge(list<T, Alloc> & X)

鏈表x與調(diào)用鏈表合并，在合并之前必須進(jìn)行排序。合并后的鏈表存儲(chǔ)在調(diào)用鏈表中，x變?yōu)榭真湵怼＞€性時(shí)間復(fù)雜度

void remove(const T &val)

刪除表中的所有val，線性時(shí)間復(fù)雜讀。

void sort()

因?yàn)?list 不支持隨機(jī)訪問(wèn)，不能使用 std::sort()，但是可以使用自帶的 sotr，時(shí)間復(fù)雜度 O（nlogn）

void (iterator pos, list <T, Alloc> x)

將x鏈表插入到pos的前面，x變?yōu)榭?。固定時(shí)間復(fù)雜度。

void unique() 將連續(xù)的相同元素壓縮為單個(gè)元素。線性時(shí)間復(fù)雜度

示例

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
void show(int & t)
{
    cout << t << " ";
}
 
ostream & operator<<(ostream & os, list<int> & s)
{
    for_each(s.begin(),s.end(),show);
    return os;
}
int main()
{
    list <int> one (5,2);
    list <int> two (5,3);
    list <int> three;
    int num[5] = {1,6,3,5,2};
    three.insert(three.begin(),num,num+5);
    cout << "list one is " << one << endl;
    cout << "list two is " << two << endl;
    cout << "list three is(use insert) " << three << endl;
    three.sort();
    cout << "list three use sort " << three << endl;
    three.merge(two);
    cout << "list three use merge to list two \n" << "now list two is empty: ";
    cout << "list two is " << two << endl;
    cout << "now list three is " << three << endl;
    three.splice(three.begin(),one);
    cout << "three use splice to one \n" << "now list one is empty: ";
    cout << "now list one is " << one << endl;
    cout << "now list three is " << three << endl;
    three.unique();
    cout << "three use unique is " << three << endl;
    three.sort();
    cout << "list three use sort and unique: " << three << endl;
    three.remove(3);
    cout << "now use remove delete 3: " << three;
    return 0;
}

運(yùn)行結(jié)果

注意merge()，不是簡(jiǎn)單的拼接，是有順序的合并。而spille()才是拼接（插入）。

forwarrd_list

一些方法

stack

一些方法

關(guān)聯(lián)容器

關(guān)聯(lián)容器是隊(duì)容器概念的另一個(gè)改進(jìn)，關(guān)聯(lián)容器將數(shù)據(jù)和關(guān)鍵字（key）存放在一起，用關(guān)鍵字來(lái)快速的查找數(shù)據(jù)。
STL提供了四種關(guān)聯(lián)容器，set, multiset, map, multimap。

set(關(guān)聯(lián)集合)

可翻轉(zhuǎn)，可排序，并且存儲(chǔ)進(jìn)去的時(shí)候自動(dòng)排好序。關(guān)鍵字唯一即一個(gè)數(shù)據(jù)有且只有一個(gè)關(guān)鍵字并且與存儲(chǔ)類型相同。

#include <iostream>
#include <algorithm>
#include <set>
#include <iterator>
using namespace std;
 
int main()
{
    const int n =6;
    string str[n] = {"hello", "world", "i am", "set use","C++","union"};
    //構(gòu)造函數(shù)接受兩個(gè)迭代器表示區(qū)間，初始化為區(qū)間內(nèi)的內(nèi)容
    set<string> A(str,str+6);
    ostream_iterator<string,char> out(cout,"\n");
    copy(A.begin(),A.end(),out);
    return 0;
}

運(yùn)行結(jié)果

可以看見(jiàn)其已經(jīng)自動(dòng)排序

一些set的類方法

lower_bound()——接受一個(gè)關(guān)鍵字參數(shù)，返回一個(gè)迭代器，該迭代器指向第一個(gè)不小于關(guān)鍵字成員的參數(shù)（可能以關(guān)鍵字對(duì)應(yīng)數(shù)開(kāi)頭，也可能不是）。

upper_bound()——同上，該迭代器指向第一個(gè)大于關(guān)鍵詞的成員（類似超尾）。

演示

#include <iostream>
#include <algorithm>
#include <set>
#include <iterator>
using namespace std;
 
int main()
{
    const int n =6;
    string str[n] = {"hello", "world", "i am", "set use","C++","union"};
    set<string> A(str,str+6);
    ostream_iterator<string,char> out(cout,"\n");
    //find string from b to r
    copy(A.lower_bound("b"),A.upper_bound("s"),out);
    return 0;
}

運(yùn)行結(jié)果

因?yàn)閡pper_bound()返回的是類似超尾迭代器的迭代器，所以不包括以‘s’開(kāi)頭的字符串

因?yàn)榈讓右詷?shù)形結(jié)構(gòu)實(shí)現(xiàn)得以快速查找，所以用戶不能指定插入位置。并且插入后自動(dòng)排序。

multimap(多關(guān)聯(lián)圖)

可反轉(zhuǎn)，自動(dòng)排序，關(guān)鍵字可與數(shù)據(jù)類型不同，一個(gè)關(guān)鍵字可與多個(gè)數(shù)據(jù)關(guān)聯(lián)。

//<const key,type_name>
mutimap <int,string> mp;

為了將信息結(jié)合在一起，數(shù)據(jù)與關(guān)鍵字用一個(gè)pair存儲(chǔ)，所以插入等操作要插入pair
一些方法

count()——接受一個(gè)關(guān)鍵字參數(shù)，返回該關(guān)鍵字所對(duì)應(yīng)得數(shù)據(jù)個(gè)數(shù)。

lower_bound()， upper_bound()，同set。

equal_range()——接受一個(gè)關(guān)鍵字參數(shù)，返回兩個(gè)迭代器，表示與該關(guān)鍵字所對(duì)應(yīng)的區(qū)間，并且用一個(gè)二元組封裝。

演示

#include <iostream>
#include <iterator>
#include <map>
using namespace std;
typedef pair<int,string> Pair;
int main()
{
    Pair p[6]={{6,"啤酒"},
               {10,"炒飯"},
               {80,"烤豬頭"},
               {10,"冷面"},
               {5,"早餐"},
               {80,"給你一錘子"}};
    multimap<int,string> mulmap;
    // no operator <
    cout << "現(xiàn)在圖中存儲(chǔ)的關(guān)鍵字和數(shù)據(jù)是：" << endl;
    multimap<int,string> ::iterator i;
    for(int i =0;i<6;i++){
        mulmap.insert(p[i]);
    }
    for(auto i=mulmap.begin(); i!=mulmap.end(); i++){
        cout << i->first << " " << i->second << endl;
    }
    cout << "使用count函數(shù)找到價(jià)格為80的菜品個(gè)數(shù)為：" << mulmap.count(80) << endl;
    pair<multimap<int,string>::iterator,multimap<int,string>::iterator> temp;
    cout << "使用equal_range函數(shù)找到價(jià)格為80的菜品" << endl;
    temp = mulmap.equal_range(80);
    for(auto i = temp.first;i!=temp.second;i++){
        cout << i->second;
    }
    return 0;
}

運(yùn)行結(jié)果