vector模板類

STL(標(biāo)準(zhǔn)模板庫(kù))提供了容器、迭代器、函數(shù)對(duì)象、算法的模板。容器是類似于數(shù)組的東西,它可以存儲(chǔ)若干值,STL容器是同質(zhì)的,即存儲(chǔ)的值的類型相同;迭代器是用來(lái)遍歷容器的,它和能遍歷數(shù)組的指針類似,是廣義指針;函數(shù)對(duì)象是類似于函數(shù)的對(duì)象,可以是類對(duì)象和函數(shù)指針;算法就是一些能完成特定任務(wù)的處方。

我們來(lái)看最簡(jiǎn)單的容器:vector模板類。

1. vector模板類

1.1 創(chuàng)建模板類

在頭文件vector中定義了vector模板,我們稱之為矢量,它就像是加強(qiáng)版的數(shù)組。

創(chuàng)建vector模板對(duì)象:

std::vector<int> first;                                // empty vector of ints
std::vector<int> myadd(5);                             //vector of five ints
std::vector<int> second (4,100);                       // four ints with value 100
std::vector<int> third (second.begin(),second.end());  // iterating through second
std::vector<int> fourth (third);                       // a copy of third

一般來(lái)說(shuō),我們使用前三種方式初始化vector對(duì)象,創(chuàng)建好了后數(shù)組可以做的它都可以,例如我們可以使用[]隨機(jī)訪問(wèn)數(shù)據(jù)。

矢量模板類還支持列表初始化語(yǔ)句

std::vector<int> a{1,2,3,4,5};

1.2 STL容器都提供的成員方法

• size():返回容器中元素?cái)?shù)目
• swap():交換兩個(gè)容器的內(nèi)容
• begin():返回一個(gè)指向容器第一個(gè)元素的迭代器
• end():返回一個(gè)表示超過(guò)容器尾的迭代器

什么是迭代器?它是一個(gè)廣義指針。它可以是指針,也可以是一個(gè)可對(duì)其執(zhí)行–解除引用operator*()和遞增operator++()–的對(duì)象。每一個(gè)容器類都定義了一個(gè)合適的迭代器,它的類型是一個(gè)名為iterator的typedef,其作用域是整個(gè)類。

我們可以這樣聲明一個(gè)迭代器:
vector<double>::iterator pd;
也可以使用auto關(guān)鍵字:
auto pd=scores.begin();
我們可以使用迭代器pd進(jìn)行如下操作:

pd=scores.begin();
*pd=22.3;
++pd;
pd++;
--pd;
pd--;

總之迭代器就相當(dāng)于是指向容器中元素的指針。

什么是超過(guò)結(jié)尾(past-the-end)?它是一種迭代器,指向容器中最后一個(gè)元素后面那個(gè)元素。例如在C風(fēng)格字符串中,字符串的末尾的\0就是超過(guò)結(jié)尾指向的元素。end()成員函數(shù)會(huì)返回超過(guò)結(jié)尾迭代器。
那么我們的遍歷可以這樣寫:

for(pd=scores.begin();pd!=scores.end(),pd++)
    cout<<*pd;

#include<vector>
#include<iostream>
int main()
{
    using std::cout;
    using std::endl;
    using std::vector;
    vector<double> a{1,2,3,4,5};
    vector<double> b{6,7,8};
    cout<<"a size: "<<a.size()<<endl;
    cout<<"b size: "<<b.size()<<endl;
    cout<<"a :";
    for(vector<double>::iterator i=a.begin();i!=a.end();i++)
        cout<<*i<<" ";
    cout<<"\nb :";
    for(vector<double>::iterator i=b.begin();i!=b.end();i++)
        cout<<*i<<" ";
    a.swap(b);
    cout<<"\nafter swap:"<<endl;
    cout<<"a :";
    for(vector<double>::iterator i=a.begin();i!=a.end();i++)
        cout<<*i<<" ";
    cout<<"\nb :";
    for(vector<double>::iterator i=b.begin();i!=b.end();i++)
        cout<<*i<<" ";
}

a size: 5
b size: 3
a :1 2 3 4 5
b :6 7 8
after swap:
a :6 7 8
b :1 2 3 4 5

以上代碼是測(cè)試了,矢量類的一些接口

實(shí)際上還有很多接口:例如empty,front,back;可以直接看cplusplus

1.3 vector特有的成員方法

• push_back():將元素添加到矢量末尾,而且矢量長(zhǎng)度會(huì)自動(dòng)增大
• erase():刪除給定區(qū)間內(nèi)的元素
• insert():插入指定區(qū)間內(nèi)的元素

push_back()接受一個(gè)元素類型的參數(shù),它相當(dāng)于在矢量的超過(guò)末尾的地方加個(gè)元素:

vector<double> scores;
double temp=1.23;
scores.push_back(temp);

erase()接受兩個(gè)迭代器參數(shù),這兩個(gè)迭代器定義了要?jiǎng)h除的區(qū)間,第一個(gè)迭代器是區(qū)間起始處,第二個(gè)迭代器是區(qū)間終止后的第一個(gè)位置,例如a.erase(start,end);是指刪除區(qū)間[start,end)左開(kāi)右閉中的元素,而C++中所說(shuō)的區(qū)間都是這種左開(kāi)右閉的區(qū)間。

scores.erase(scores.begin(),scores.begin()+2);

上面這句代碼就會(huì)刪除矢量對(duì)象中前兩個(gè)元素。

insert()會(huì)把指定區(qū)間里的元素插到一個(gè)位置前面。它接受三個(gè)迭代器參數(shù),第一個(gè)參數(shù)指出新元素的插入位置,第二第三就是區(qū)間;

vector<int> old_v;
vector<int> new_v;
...
old_v.insert(old_v.begin(),new_v.begin()+1,new_v.end());

上面這段代碼會(huì)把new_v中除了第一個(gè)元素外的所有元素插到old_v的第一個(gè)元素的前面。

超尾元素的存在,使得在最后一個(gè)元素后面插入元素變得簡(jiǎn)單:

old_v.insert(old_v.end(),new_v.begin()+1,new_v.end());

#include<vector>
#include<iostream>
int main()
{
    using namespace std;
    vector<int> a;
    a.push_back(1);
    a.push_back(2);
    cout<<"a: ";
    for(auto i=a.begin();i!=a.end();i++)
    cout<<*i;
    cout<<endl;
    vector<int>b{3,4,5,6,7};
    a.insert(a.end(),b.begin(),b.begin()+3);
    cout<<"after insert: ";
    cout<<"a: ";
    for(auto i=a.begin();i!=a.end();i++)
    cout<<*i;
    cout<<endl;
    a.erase(a.begin()+1,a.begin()+3);
    cout<<"after erase: ";
    cout<<"a: ";
    for(auto i=a.begin();i!=a.end();i++)
    cout<<*i;
    cout<<endl;
}

a: 12
after insert: a: 12345
after erase: a: 145 ??

1.4 STL容器的非成員方法

我們會(huì)對(duì)容器做很多操作,例如搜索,排序。但是這些功能不會(huì)放在成員方法中,因?yàn)椴煌娜萜黝惖呐判蚧蛘咚阉鞣椒ǘ际穷愃频?所以我們?yōu)榱斯?jié)省代碼,就不會(huì)為每個(gè)容器單獨(dú)寫這種成員方法。但是,即使存在執(zhí)行相同任務(wù)的非成員函數(shù),STL容器可能也會(huì)定義相同的成員方法,例如vector的swap()成員方法比swap()非成員方法效率高,但是非成員函數(shù)讓您可以交換兩個(gè)不同類型的容器的內(nèi)容。

• for_each():遍歷
• random_shuffle():隨機(jī)排列
• sort():排序

這些方法都定義在頭文件algorithm中,這就是我們所說(shuō)的算法。
for_each()接受3個(gè)參數(shù),前兩個(gè)是定義區(qū)間的迭代器,最后一個(gè)是指向函數(shù)的指針(或者說(shuō)是函數(shù)對(duì)象)。for_each()將被指向的函數(shù)應(yīng)用于容器間的各個(gè)元素。但是for_each()不能修改容器的元素值。我們可以使用它來(lái)代替for循環(huán)。

for_each(books.begin(),books.end(),foo);//foo是函數(shù)名,即函數(shù)地址

這個(gè)語(yǔ)法很熟悉,很像基于范圍的for循環(huán):

double prices[5]={4.99,10.99,6.87,7.99,8.49};
for(double x:prices)
    cout<<x<<endl;

for_each(books.begin(),books.end(),foo);//foo是函數(shù)名,即函數(shù)地址
//等價(jià)于
for(auto x:books) foo(x);

但是基于范圍的for循環(huán)可以改變?nèi)萜鞯膬?nèi)容,我們只需要函數(shù)的參數(shù)是引用參數(shù)foo(int &);
然后我們的代碼:

for(auto &x:books) foo(x);

random_shuffle()接受兩個(gè)指定區(qū)間的迭代器,并隨機(jī)排列區(qū)間中的元素,但是random_shuffle()要求容器允許隨機(jī)訪問(wèn)(即使用books[i]可以直接訪問(wèn)元素)

random_shuffle(books.begin(),books.end());

sort()也要求容器支持隨機(jī)訪問(wèn)。
第一個(gè)版本的sort()接受兩個(gè)指定區(qū)間的迭代器,并且使用<運(yùn)算符對(duì)容器中的元素進(jìn)行升序排列:

vector<int> coolstuff;
...
sort(coolstuff.begin(),coolstuff.end());

這就意味著,如果容器中的元素的類型必須定義operator<()。

第二個(gè)版本的sort()接受三個(gè)參數(shù),它更實(shí)用,前兩個(gè)參數(shù)是指定區(qū)間的迭代器,第三個(gè)參數(shù)是函數(shù)指針(或函數(shù)對(duì)象)。這個(gè)函數(shù)指針指向一個(gè)返回bool值,接受兩個(gè)元素的函數(shù),如果true就說(shuō)明排序正確,如果false就說(shuō)明排序錯(cuò)誤。

例如我們希望采用降序排列:

bool compare(double db1,double db2)
{
    if(db1<db2)
        return false;
    else 
        return true;
}
int main(){
vector<double> a{4.99,10.99,6.87,7.99,8.49};
sort(a.begin(),a.end(),compare);
}

或者直接使用函數(shù)對(duì)象:

sort(a.begin(),a.end(),greater<double>());

這里使用的greater<double>()就是函數(shù)對(duì)象,它返回了double類型的大于運(yùn)算。

#include<vector>
#include<iostream>
#include<algorithm>
void show(const int &a)
{
    std::cout<<a<<" ";
}
bool greater(const int &x,const int &y)
{
    return x>y;
}
int main()
{
    using std::vector;
    using std::random_shuffle;
    using std::sort;
    using std::for_each;
    using std::cout;
    vector<int> a;
    for(int i=0;i<20;i++)
        a.push_back(i);
    cout<<"initial: ";
    for_each(a.begin(),a.end(),show);
    random_shuffle(a.begin(),a.end());
    cout<<"\nafter shaking: ";
    for_each(a.begin(),a.end(),show);
    sort(a.begin(),a.end());
    cout<<"\nAscending: ";
    for_each(a.begin(),a.end(),show);
    sort(a.begin(),a.end(),greater);
    cout<<"\nDescending: ";
    for_each(a.begin(),a.end(),show);
}

initial: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ? ? ??
after shaking: 12 1 9 2 0 11 7 19 4 15 18 5 14 13 10 16 6 3 8 17?
Ascending: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ? ??
Descending: 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 ?