C++容器/迭代器

桃扇骨 2022-08-07 08:58 193阅读 0赞

# C++容器 #

## 简介 ##

vector用来代替数组（动态数组），顺序存储

list是链表，多用表经常使用插入删除的地方，每个对象都有前向指针和后象指针，在内存里也不一定是连续存储

map是图（哈希表），底层采用的是树型结构,多数使用平衡二叉树实现

queue很少用，比如排队买火车票的队列，就是这种结构

set更少用，指的是一个无序集合

--------------------

## 详解 ##

[浅谈C++容器 ][C_]  
STL 对定义的通用容器分三类：*顺序性容器、关联式容器和容器适配器*。  
***顺序性容器*** 是 一种各元素之间有顺序关系的线性表，是一种线性结构的可序群集。顺序性容器中的每个元素均有固定的位置，除非用删除或插入的操作改变这个位置。这个位置和 元素本身无关，而和操作的时间和地点有关，顺序性容器不会根据元素的特点排序而是直接保存了元素操作时的逻辑顺序。比如我们一次性对一个顺序性容器追加三 个元素，这三个元素在容器中的相对位置和追加时的逻辑次序是一致的。

***关联式容器*** 和 顺序性容器不一样，关联式容器是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系，也就是说元素在容器中并没有保存元素置 入容器时的逻辑顺序。但是关联式容器提供了另一种根据元素特点排序的功能，这样迭代器就能根据元素的特点“顺序地”获取元素。

关联式容器另一个显著的特点是它是以键值的方式来保存数据，就是说它能把关键字和值关联起来保存，而顺序性容器只能保存一种（可以认为它只保存关键字，也可以认为它只保存值）。这在下面具体的容器类中可以说明这一点。

***容器适配器*** 是一个比较抽象的概念， C++的 解释是：适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器是让一种已存在的容器类型采用另一种不同的抽象类型的工作方式来实现的一种机 制。其实仅是发生了接口转换。那么你可以把它理解为容器的容器，它实质还是一个容器，只是他不依赖于具体的标准容器类型，可以理解是容器的模版。或者把它 理解为容器的接口，而适配器具体采用哪种容器类型去实现，在定义适配器的时候可以由你决定。

![这里写图片描述][20150327210954467]

[vector用法介绍][vector]  
![这里写图片描述][20150327212438130]  
![这里写图片描述][20150327212421208]

[deque双向队列][deque]  
![这里写图片描述][20150327212457259]

[list用法][list]  
![这里写图片描述][20150327212755596]

[ set用法][set]  
![这里写图片描述][20150327213003672]

[map的基本操作和使用][map]  
![这里写图片描述][20150327213126043]

[ stack用法][stack]  
![这里写图片描述][20150327213355519]

[queue用法][queue]  
![这里写图片描述][20150327213620709]

[priority\_queue的使用 ][priority_queue_]  
![这里写图片描述][20150327220115410]  
注：输出的是排序后的第一个值

--------------------

## 部分示例代码 ##

### Vector ###

#include <iostream>
    #include <vector>
    using namespace std;
    
    int main()
    {
    vector<int> iVec;
    cout << "容器 大小为: " << iVec.size() << endl;
    cout << "容器 容量为: " << iVec.capacity() << endl; //1个元素， 容器容量为1
    
    iVec.push_back(1);
    cout << "容器 大小为: " << iVec.size() << endl;
    cout << "容器 容量为: " << iVec.capacity() << endl; //2个元素， 容器容量为2
    
    /* 测试effective stl中的特殊的交换 swap() */
    cout << "当前vector 的大小为: " << iVec.size() << endl;
    cout << "当前vector 的容量为: " << iVec.capacity() << endl;
    vector<int> iVec1;
    iVec1.push_back(2);
    iVec1.push_back(3);
    iVec1.swap(iVec);
    
    cout << "临时的vector<int>对象 的大小为: " << (vector<int>(iVec)).size() << endl;
    cout << "临时的vector<int>对象 的容量为: " << (vector<int>(iVec)).capacity() << endl;
    cout << "交换后，当前vector 的大小为: " << iVec1.size() << endl;
    cout << "交换后，当前vector 的容量为: " << iVec1.capacity() << endl;
    
    return 0;
    }

### priority\_queue ###

#include <iostream>
    #include <queue>
    using namespace std ;
    
    int main()
    {
        priority_queue<float> q;
    
        // insert three elements into the priority queue
        q.push (66.6);
        q.push (22.2);
        q.push (44.4);
    
        // read and print two elements
        cout << q.top () << ' ';
        q.pop ();
        cout << q.top () << endl;
        q.pop ();
    
        // insert three more elements
        q.push (11.1);
        q.push (55.5);
        q.push (33.3);
    
        // skip one element
        q.pop ();
    
        // pop and print remaining elements
        while (!q.empty ()) {
            cout << q.top () << ' ';
            q.pop ();
        }
        cout << endl ;
    }

--------------------

# C++迭代器 #

迭代器(iterator)是一中检查容器内元素并遍历元素的数据类型，一般迭代器定义为只读模式（const）.

根据STL中的分类，iterator包括：  
***Input Iterator***：只能单步向前迭代元素，不允许修改由该类迭代器引用的元素。  
***Output Iterator***：该类迭代器和Input Iterator极其相似，也只能单步向前迭代元素，不同的是该类迭代器对元素只有写的权力。  
***Forward Iterator***：该类迭代器可以在一个正确的区间中进行读写操作，它拥有Input Iterator的所有特性，和Output Iterator的部分特性，以及单步向前迭代元素的能力。  
***Bidirectional Iterator***：该类迭代器是在Forward Iterator的基础上提供了单步向后迭代元素的能力。  
***Random Access Iterator***：该类迭代器能完成上面所有迭代器的工作，它自己独有的特性就是可以像指针那样进行算术计算，而不是仅仅只有单步向前或向后迭代。

**容器** **支持的迭代器类别**  
vector 随机访问  
set 双向  
multimap 双向  
deque 随机访问  
multiset 双向  
stack 不支持  
list 双向  
map 双向  
queue 不支持  
priority\_queue 不支持

## 示例代码 ##

#include <iostream> 
    #include <vector> 
    using namespace std;int main()  
    {   
    //定义并赋值输出 
    vector<int> ivec;   
    cout<<"Befort *2 the elements are:"<<endl;   
    for(vector<int>::size_type ix=0;  
    ix!=10;++ix){ ivec.push_back(ix);   
    cout<<ivec[ix]<<'/t';   
    }   
    //把每个值乘以2并输出 
    cout<<endl<<"After *2 the elements are:"<<endl;   
    for(vector<int>::iterator iter=ivec.begin();  
    iter!=ivec.end();++iter)  
    {   
    *iter*=2; cout<<*iter<<'/t';   
    }   
    return 0;  
    }

详见：[官方文档][Link 1]

[C_]: http://www.cnblogs.com/xkfz007/articles/2534249.html%20%E6%B5%85%E8%B0%88C++%E5%AE%B9%E5%99%A8
[20150327210954467]: /images/20220805/590a60df53f14867bb4fdea0d277f855.png
[vector]: http://blog.csdn.net/phoebin/article/details/3864590
[20150327212438130]: /images/20220805/d52ec4d757a94828a018ef2bc4f5ad8e.png
[20150327212421208]: /images/20220805/f69993f0ee954876974d9aff1f685f59.png
[deque]: http://blog.csdn.net/morewindows/article/details/6946811
[20150327212457259]: /images/20220805/802782e00b994cd18a2221899759d33c.png
[list]: http://blog.csdn.net/lskyne/article/details/10418823
[20150327212755596]: /images/20220805/d0d5025f26e847648a664ec7cebe6fd2.png
[set]: http://blog.sina.com.cn/s/blog_779cf3410101389s.html
[20150327213003672]: /images/20220805/80306646d5c24539b05d591c28240af9.png
[map]: http://blog.sina.com.cn/s/blog_61533c9b0100fa7w.html
[20150327213126043]: /images/20220805/144f4bb4638a4c8fa5e8ae5e7ac413d1.png
[stack]: http://blog.csdn.net/chao_xun/article/details/8037420
[20150327213355519]: /images/20220805/9979797933c4471ca37e7a884183ce22.png
[queue]: http://blog.csdn.net/chao_xun/article/details/8037438
[20150327213620709]: /images/20220805/792f9d13b75c476ca71aff52264db922.png
[priority_queue_]: http://blog.csdn.net/sup_heaven/article/details/8036982
[20150327220115410]: /images/20220805/086d670b4f184030826457e92e713f72.png
[Link 1]: http://www.cplusplus.com/reference/iterator/ForwardIterator/