vector、deque、stack、queue、list以及set的使用

注意：以下测试案例都要加上相应的头文件，必要时要加上algorithm文件。

1、vector

　　连续存储结构，每个元素在内存上是连续的；支持高效的随机访问和在尾端插入/删除操作，但其他位置的插入/删除操作效率低下；相当于一个数组，但是与数组的区别为：内存空间的扩展。vector的初始化操作

int main(){

    vector<int> v1;

    v1.push_back(1);

    v1.push_back(2);

    v1.push_back(3);

    vector<int> v2=v1;

    vector<int> v3(10);     //必须提前把内存大小写出(初始化元素默认值是0，即10个0）

    for (int i = 0; i < 10; i++) {

        v3[i]=(i+1);

    }

    printV(v3);

    cout<<endl;

    vector<int> v4{1,2,3,6};

    printV(v4);

    return 0;

}

元素的插入与删除

int main()

{

    vector<int> v1;

    cout<<"Initial size of vector: "<<v1.size()<<endl;

    //push_back操作是将一个元素插入vector的末尾。

    v1.push_back(1);

    v1.push_back(2);

    v1.push_back(3);

    cout<<"size of vector(push): "<<v1.size()<<endl;

    //获取头部元素

    cout<<"the head element of vector: "<<v1.front()<<endl;

    //循环打印尾部元素

    while (v1.size() > 0) {

        cout<<v1.back()<<" ";

        v1.pop_back();  //删除vector的尾部元素，此函数返回值为空(void)

    }

    return 0;

}

随机访问并修改元素

int main(){

    vector<int> v1;

    cout<<"Initial size of vector: "<<v1.size()<<endl;

    v1.push_back(1);

    v1.push_back(2);

    v1.push_back(3);

    //此时若想修改头部元素

    v1.front()=50;  //函数返回值当左值，应该返回一个引用，对此的理解参考下面的案例

    //2011/12/14/2286908.html

    v1.back()=20;

    printV(v1);

    return 0;

}

在以上案例中，函数返回值当左值的案例理解如下

int& abc(int a, int b, int c, int& result)

{

    result = a + b + c;

    return result;

}

int main(){

    int result=0;

    abc(1,2,3,result)=2;

    cout<<result<<endl;

    return 0;

}

顺向迭代与逆向迭代访问

int main(){

    vector<int> v(10);

    for (int i = 0; i < 10; ++i) {

        v[i]=i+1;

    }

    //利用顺向迭代器去遍历

    for(vector<int>::iterator it=v.begin();it!=v.end();it++){

     cout<<*it<<"  ";

    }

    cout<<endl;

    //利用迭代器逆向遍历

    for(vector<int>::reverse_iterator rit=v.rbegin(); rit != v.rend(); rit++){

        cout<<*rit<<"  ";

    }

    cout<<endl;

    return 0;

}

元素的删除和插入

int main(){

    vector<int> v(10);

    for (int i = 0; i < 10; ++i) {

        v[i]=i+1;

    }

    //vector的删除

    v.erase(v.begin(),v.begin()+3);

    printV(v);

    //删除指定元素

    v.erase(v.end()-1); //注意v.end()指向的位置在vector最后元素的下一个

    printV(v);

    v.insert(v.begin(),11);

    v[1]=2;

    v[3]=2;

    v[5]=2;

    printV(v);

    for(vector<int>::iterator it =v.begin(); it != v.end(); ){

        if(*it ==2 ){

            it=v.erase(it);    //删除某位值后，其后元素会自动前移

        }else{

            it++;

        }

    }

    printV(v);

    //插入

    v.insert(v.begin(),100);

    v.insert(v.end(),200);

    printV(v);

    return 0;

}

2、deque

　　连续存储结构，即其每个元素在内存上也是连续的，类似于vector，不同之处在于，deque提供了两级数组结构，第一级完全类似于vector，代表实际容器；另一级维护容器的首位地址。这样，deque除了具有vector的所有功能外，还支持高效的首/尾端插入/删除操作。

#include<iostream>

#include<deque>

#include<algorithm>

using namespace std;

void print(deque<int> &d){

    for(deque<int>::iterator it=d.begin();it !=d.end();it++){

        cout<<*it<<" ";

    }

    cout<<endl;

}

int main(){

    deque<int> d;

    d.push_back(1);

    d.push_back(3);

    d.push_back(5);

    d.push_back(100);

    //deque的动态数组头尾都开放，因此能在头尾两端进行快速安插和删除。

    d.push_front(0);

    print(d);

    //查找

    deque<int>::iterator it=find(d.begin(),d.end(),3);

    if(it!=d.end()){

        cout<<"已成功找到："<<*it<<"其下标地址是："<<distance(d.begin(),it)<<endl;　　//通过distance()可以获得相应的下标地址

    }else{

        cout<<"未找到！"<<endl;

    }

    return 0;

}

3、栈和队列

　　与数据结构的操作一样，较简单。

//测试程序

int main1(){

    stack<int> s;

    //入栈

    for (int i = 0; i < 10; ++i) {

        s.push(i+1);

    }

    //出栈

    while ( !s.empty()) {

        int tmp = s.top();

        cout<<tmp<<" ";

        s.pop();

    }

    cout<<endl;

    return 0;

}

int main2(){

    queue<int> q;

    q.push(1);

    q.push(2);

    q.push(3);

    cout<<"头元素: "<<q.front()<<endl;

    cout<<"尾元素: "<<q.back()<<endl;

    cout<<"队列大小: "<<q.size()<<endl;

    while ( ! q.empty() ) {

        int tmp=q.front();

        cout<<tmp<<" ";

        q.pop();

    }

    cout<<endl;

    return 0;

}

4、list

　　非连续存储结构，具有双链表结构，每个元素维护一对前向和后向指针，因此支持前向/后向遍历。支持高效的随机插入/删除操作，但随机访问效率低下，且由于需要额外维护指针，开销也比较大。每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。

void print(list<int> &l){

    for ( list<int>::iterator it = l.begin(); it != l.end(); it++) {

        cout<<*it<<" ";

    }

    cout<<endl;

}

int main(){

    list<int> l;

    cout<<"list的大小："<<l.size()<<endl;

    for (int i = 0; i < 10; ++i) {

        l.push_back(i+1);

    }

    cout<<"list的大小："<<l.size()<<endl;

    list<int>::iterator it=l.begin();

    while (it != l.end() ) {

        cout<<*it<<" ";

        it++;

    }

    cout<<endl;

    //list不能随机访问

    it=l.begin();

    it++;   //语法正确

    //it=it+2;    //编译不通过，即不支持访问

    //元素的插入

    l.insert(l.end(),100);

    l.insert(l.end(),100);

    l.insert(l.end(),100);

    print(l);

    //元素的删除

    list<int>::iterator left=l.begin();

    list<int>::iterator right=l.begin();

    right++;    //因为没有办法it=it+2,只能一个一个移动

    right++;

    l.erase(left,right);    //区间删除

    print(l);

    list<int>::iterator pos=l.begin();

    pos++;

    pos++;

    l.erase(pos);         //直接删除某个位置

    print(l);

    l.remove(100);        //删除值为100的元素

    print(l);

    l.clear();            //删除所有元素

    cout<<"list的大小："<<l.size()<<endl;

    return 0;

}

4、set

　　set也是STL中比较常见的容器。set集合容器实现了红黑树的平衡二叉检索树的数据结构，它会自动调整二叉树的排列，把元素放到适当的位置。set容器所包含的元素的值是唯一的，集合中的元素按一定的顺序排列。

　　set集合的常用操作如下（注意要引入set头文件）：

//集合测试

int main(){

    set<int> s;

    set<int,greater<int>> ss;   //从大到小存储

    int tmp;

    for (int i = 0; i < 5; ++i) {

        tmp=rand()/10000000;

        s.insert(tmp);  //往集合中插入元素

        ss.insert(tmp);

    }

    s.insert(100);

    s.insert(100);

    s.insert(100);  //set集合中的元素是唯一的，虽然插入这么多等值元素，但最终只会显示一个元素

    ss.insert(100);

    //打印输出

    for(set<int>::iterator it=s.begin(); it!=s.end(); it++){

        cout<<*it<<" "; //依次输出84 100 168 171 180 195

    }                   //即默认集合中的元素是从小到大排序的

    cout<<endl;

    for(set<int,greater<int>>::iterator it=ss.begin(); it!=ss.end(); it++){

        cout<<*it<<" "; //从大到小打印d

    }

    cout<<endl;

    set<int>::iterator ir=s.begin();

    //ir=ir+3; //错误，不支持随机访问

    //删除集合

    while ( !s.empty() ) {

        set<int>::iterator it=s.begin();

        s.erase(it);

    }

    cout<<endl;

    cout<<s.size()<<endl;

    return 0;

}

　　以上案例中set存放的是简单的整数，如果是复杂的对象，我们要指定集合中存放元素比较的依据属性，利用仿函数去实现（上述中的set集合ss的声明中的greater<int>也是用仿函数实现的），如下案例：

class Student{

public:

    Student(int age,char *name){

        this->age=age;

        strcpy(this->name,name);

    }

    /*

     * error: passing 'const Student' as 'this' argument discards qualifiers

     * getXXX()函数一般最好加上const，

     */

    const char* getName() const{

        return this->name;

    }

    const int getAge() const {

        return this->age;

    }

public:

    char name[20];

    int age;

};

//仿函数

struct FuncStudent

{

    bool operator()(const Student &left,const Student &right) const

    {

        if( left.getAge() < right.getAge() ){

            return true;    //如果左边的student的age小于右边，即从小到大排序

        }

        else{

            return false;

        }

    }

};

int main(){

    set<Student,FuncStudent> s;

    Student s1(20,"张三");

    Student s2(50,"李四");

    Student s3(24,"王五");

    Student s4(32,"老六");

    s.insert(s1);

    s.insert(s2);

    s.insert(s3);

    s.insert(s4);

    for(set<Student,FuncStudent>::iterator it=s.begin(); it !=s.end(); it++){

        cout<<it->getName()<<"\t"<<it->getAge()<<endl;

    }

    return 0;

}

此时又有一个问题，如果插入的元素是一个年龄相同，但姓名不同的对象的时候（测试可以通过，但结果中没有该元素），这个时候需要注意insert()的返回值了，可以用返回值来检测，具体操作如下：

int main(){

    set<Student,FuncStudent> s;

    Student s1(20,"张三");

    Student s2(50,"李四");

    Student s3(24,"王五");

    Student s4(32,"老六");

    //insert()函数的返回值 typedef pair<iterator,bool> _Pairib

    pair<set<Student,FuncStudent>::iterator,bool> pair1=s.insert(s1);

    //对插入检查是否成功

    if ( pair1.second ==true ) {

        cout<<"s1插入成功"<<endl;

    }else{

        cout<<"s1插入失败"<<endl;

    }

    s.insert(s2);

    s.insert(s3);

    s.insert(s4);

    //如果插入一个年龄相同的数据

    Student s5(20,"test");

    pair<set<Student,FuncStudent>::iterator,bool> pair2=s.insert(s5);   //插入不成功

    if ( pair2.second ==true ) {

        cout<<"s5插入成功"<<endl;

    }else{

        cout<<"s5插入失败"<<endl;

    }

    for(set<Student,FuncStudent>::iterator it=s.begin(); it !=s.end(); it++){

        cout<<it->getName()<<"\t"<<it->getAge()<<endl;

    }

    return 0;

}

结果如下所示：

s1插入成功
s5插入失败
张三   20
王五   24
老六   32
李四   50

　　set中还有其他一些便于查找元素的方法，如下：

int main(){

    set<int> s;

    for (int i = 0; i < 5; ++i) {

        s.insert(i+3);

    }

    for(set<int>::iterator it=s.begin(); it!=s.end(); it++ ){

        cout<<*it<<" ";

    }

    cout<<endl;

    //查找5的位置

    set<int>::iterator it0=s.find(6);

    cout<<"*it0 : "<<*it0<<endl;

    int count=s.count(5);

    cout<<"count "<<count<<endl;

    set<int>::iterator it1=s.lower_bound(6);    //返回小于等于6的元素的iterator位置

    cout<<"*it1 : "<<*it1<<endl;

    set<int>::iterator it2=s.upper_bound(6);    //返回大于6的元素的iterator位置

    cout<<"*it2 : "<<*it2<<endl;

    //如果想把iterator位置接过来

    /*

     * typedef pair<iterator,bool> _Pairib

     * typedef pair<iterator,iterator> _Pairii;

     * typedef pair<const_iterator,const_iterator> _Paircc;

     */

    pair<set<int>::iterator,set<int>::iterator> myPair=s.equal_range(6);

    set<int>::iterator ip0=myPair.first;

    cout<<"ip0 : "<<*ip0<<endl;

    set<int>::iterator ip1=myPair.second;

    cout<<"ip1 : "<<*ip1<<endl;

    return 0;

}

　　还有一个问题是如果确实想在set集合中插入具有被排序元素值相同的元素，这个时候就可以考虑使用multiset，如下：

int main(){

    multiset<int> s;

    //与set相比特点是可以放多个相同的元素

    s.insert(66);

    s.insert(21);

    s.insert(8);

    s.insert(21);

    s.insert(21);

    //打印元素

    for(multiset<int>::iterator it=s.begin(); it!=s.end(); it++){

        cout<<"\t"<<*it;

    }

    cout<<endl;

    //删除元素

    while( !s.empty() ){

        multiset<int>::iterator it=s.begin();

        cout<<"\t"<<*it;

        s.erase(it);

    }

    cout<<endl;

    return 0;

}

　　此时结果如下：

8 21 21 21 66
8 21 21 21 66

巴特西

vector、deque、stack、queue、list以及set的使用

最新文章

热门文章