【总结】C++容器比较学习–待补充

Posted on Posted in 计算机1,338 views

注:文章来源是网上博客内容整理而来,具体见参考。

零、概述

0.1、容器

        实质上是一组相同类型对象的集合,但它不仅仅是数组那么简单,它实现了比数组更复杂的数据结构,能够实现更复杂的功能。C++标准模版库里提供了10种通用的容器,它基本可以解决程序中遇到的大部分问题。

        C++中容器的定义如下:数据存储上,有一种对象类型,它可以持有其他对象或指向其他对象的指针,这种对象类型叫容器。通俗的说容器就是保存其他对象的对象,这种“对象”还包含了一些列处理其他对象的方法,这也体现了容器类的一个好处,“容器类对特定代码重用问题的良好的解决方案”。

        容器另一个好处就是可以自行扩展,解决问题是我们不知道需要存储多少个对象,数组在这方面是个欠缺。容器可以为你申请内存、释放内存,并且使用最优的算法来执行你的命令。

0.2、分类

标准容器说明
顺序容器向量vector从后面快速的插入与删除,直接访问任何元素
列表list双链表,从任何地方快速插入与删除
队列deque从前面或后面快速的插入与删除,直接访问任何元素
关联容器集合map一对多映射,基于关键字快速查找,不允许重复
映射set快速查找,不允许重复值
多重集合multimap一对多映射,基于关键字快速查找,允许重复值
多重映射multiset快速查找,允许重复值
容器适配器stack后进先出
队列queue先进先出
优先级队列priority_queue最高优先级元素总是第一个出列

0.3、共有函数

1、所有标准库共有函数

默认构造函数提供容器默认初始化的构造函数。
复制构造函数将容器初始化为现有同类容器副本的构造函数
析构函数不再需要容器时进行内存整理的析构函数
empty容器中没有元素时返回true,否则返回false
max_size返回容器中最大元素个数
size返回容器中当前元素个数
operator=将一个容器赋给另一个容器
operator<如果第一个容器小于第二个容器,返回true,否则返回false,
operator<=如果第一个容器小于或等于第二个容器,返回true,否则返回false
operator>如果第一个容器大于第二个容器,返回true,否则返回false
operator>=如果第一个容器大于或等于第二个容器,返回true,否则返回false
operator==如果第一个容器等于第二个容器,返回true,否则返回false
operator!=如果第一个容器不等于第二个容器,返回true,否则返回false
swap交换两个容器的元素

2、顺序容器和关联容器共有函数

begin该函数两个版本返回iterator或const_iterator,引用容器第一个元素
end该函数两个版本返回iterator或const_iterator,引用容器最后一个元素后面一位
rbegin该函数两个版本返回reverse_iterator或const_reverse_iterator,引用容器最后一个元素
rend该函数两个版本返回reverse_iterator或const_reverse_iterator,引用容器第一个元素前面一位
erase从容器中清除一个或几个元素
clear清除容器中所有元素

3、顺序容器和关联容器中常用的typedef

value_type容器中存放元素的类型
reference容器中存放元素类型的引用
const_reference容器中存放元素类型的常量引用,这种引用只能读取容器中的元素和进行const操作
pointer容器中存放元素类型的指针
iterator指向容器中存放元素类型的迭代器
const_iterator指向容器中存放元素类型的常量迭代器,只能读取容器中的元素
reverse_iterator指向容器中存放元素类型的逆向迭代器,这种迭代器在容器中逆向迭代
const_reverse_iterator指向容器中存放元素类型的逆向迭代器,只能读取容器中的元素
difference_type引用相同容器的两个迭代器相减结果的类型(list和关联容器没有定义operator-)
size_type用于计算容器中项目数和检索顺序容器的类型(不能对list检索)

一、顺序性容器

1.0、概要

1、使用选择:

        如果你需要高效的随即存取,而不在乎插入和删除的效率,使用vector

        如果你需要大量的插入和删除,而不关心随机存取,则应使用list

        如果你需要随机存取,而且关心两端数据的插入和删除,则应使用deque

        若需要随机访问操作,则选择vector;

        若已经知道需要存储元素的数目, 则选择vector;

        若需要随机插入/删除(不仅仅在两端),则选择list

        只有需要在首端进行插入/删除操作的时候,才选择deque,否则都选择vector。

        若既需要随机插入/删除,又需要随机访问,则需要在vector与list间做个折中。

        当要存储的是大型负责类对象时,list要优于vector;当然这时候也可以用vector来存储指向对象的指针,同样会取得较高的效率,但是指针的维护非常容易出错,因此不推荐使用。

1.1、vector

1、基本概念

        vector向量相当于一个数组;

        在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时,首先分配一个非常大的内存空间预备进行存储,即capacity() 函数返回的大小,当超过此分配的空间时再整体重新放分配一块内存存储,这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。

2、优缺点

    优点:

        1) 不指定一块内存大小的数组的连续存储,即可以像数组一样操作,但可以对此数组进行动态操作。通常体现在push_back() pop_back()

        2) 随机访问方便,即支持[ ]操作符和vector.at()

        3) 节省空间。

    缺点:

        1) 在内部进行插入删除操作效率低。

        2) 只能在vector的最后进行push和pop,不能在vector的头进行push和pop。

        3) 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放。

3、使用

//1.定义和初始化
vector<int> vec1;            //默认初始化,vec1为空
vector<int> vec2(vec1);      //使用vec1初始化vec2
vector<int> vec3(vec1.begin(),vec1.end());//使用vec1初始化vec2
vector<int> vec4(10);        //10个值为的元素
vector<int> vec5(10,4);      //10个值为的元素
 
//2.常用操作方法
vec1.push_back(100);            //添加元素
int size = vec1.size();         //元素个数
bool isEmpty = vec1.empty();    //判断是否为空
cout<<vec1[0]<<vec1.at(0)<<endl;//取得第一个元素
vec1.insert(vec1.end(),5,3);    //从vec1.back位置插入个值为的元素
vec1.pop_back();                //删除末尾元素
vec1.erase(vec1.begin(),vec1.end());//删除之间的元素,其他元素前移
cout<<(vec1==vec2)?true:false;  //判断是否相等==、!=、>=、<=...
vector<int>::iterator iter = vec1.begin();    //获取迭代器首地址
vector<int>::const_iterator c_iter = vec1.begin();   //获取const类型迭代器
vec1.clear();                   //清空元素
 
//3.遍历
//下标法
int length = vec1.size();
for(int i=0;i<length;i++)
    cout<<vec1[i];
cout<<endl<<endl;
//迭代器法
vector<int>::const_iterator iterator = vec1.begin();
for(;iterator != vec1.end();iterator++)
    cout<<*iterator;

4、实现

1.2、list

1、基本概念

        

        具有双链表结构,每个元素维护一对前向和后向指针,因此支持前向/后向遍历。每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。

2、优缺点

     优点:

        1) 不使用连续内存完成动态操作。

        2) 在内部方便的进行插入和删除操作

        3) 可在两端进行push、pop

    缺点:

        1) 不能进行内部的随机访问,即不支持[ ]操作符和vector.at()

        2) 相对于verctor占用内存多

3、使用

//1.定义和初始化
list<int> lst1;          //创建空list
list<int> lst2(3);       //创建含有三个元素的list
list<int> lst3(3,2);     //创建含有三个元素的list
list<int> lst4(lst2);    //使用lst2初始化lst4
list<int> lst5(lst2.begin(),lst2.end());  //同lst4

//2.常用操作方法
lst1.assign(lst2.begin(),lst2.end());  //分配值
lst1.push_back(10);                    //添加值
lst1.pop_back();                       //删除末尾值
lst1.begin();                          //返回首值的迭代器
lst1.end();                            //返回尾值的迭代器
lst1.clear();                          //清空值
bool isEmpty1 = lst1.empty();          //判断为空
lst1.erase(lst1.begin(),lst1.end());   //删除元素
lst1.front();                          //返回第一个元素的引用
lst1.back();                           //返回最后一个元素的引用
lst1.insert(lst1.begin(),3,2);         //从指定位置插入个
lst1.rbegin();                         //返回第一个元素的前向指针
lst1.remove(2);                        //相同的元素全部删除
lst1.reverse();                        //反转
lst1.size();                           //含有元素个数
lst1.sort();                           //排序
lst1.unique();                         //删除相邻重复元素

//3.遍历
//迭代器法
for(list<int>::const_iterator iter = lst1.begin();iter != lst1.end();iter++)
   cout<<*iter;
cout<<endl;

4、实现

1.3、deque

1、基本概念

        deque是在功能上合并了vector和list。

        类似于vector,不同之处在于,deque提供了两级数组结构,第一级完全类似于vector,代表实际容器;另一级维护容器的首位地址。这样,deque除了具有vector的所有功能外,还支持高效的首端插入/删除操作。

2、优缺点

    优点:

        1) 随机访问方便,即支持[ ]操作符和vector.at()

        2) 在内部方便的进行插入和删除操作

        3) 可在两端进行push、pop

    缺点:

        1) 占用内存多

 

3、使用

4、实现

二、关联容器

2.0、概述

1、pair类型

        pair定义于头文件utility中,主要的作用是将两个数据组合成一个数据。pair实质上是一个结构体,其主要的两个成员变量是first和second。

        与容器一样,pair 也是一种模板类型。但又与之前介绍的容器不同,在创建 pair 对象时,必须提供两个类型名:pair 对象所包含的两个数据成员各自对应的类型名字,这两个类型必相同。

         pair<string, string> anon;       // holds two strings

         pair<string, int> word_count;    // holds a string and an int

         pair<string, vector<int> > line; // holds string and vector<int>

        如果在创建 pair 对象时不提供初始化式,则调用默认构造函数对其成员采用值初始化。于是,anon 是包含两空 string 类型成员的 pair 对象,line 则存储一个空的 string 类型对象和一个空的vector 类型对象。word_count 中的 int 成员获得 0 值,而 string 成员则初始化为空 string 对象。

2、

2.1、map

1、基本概念

    map 是键-值对的集合。map 类型通常可理解为关联数组(associative array):可使用键作为下标来获取一个值,正如内置数组类型一样。而关联的本质在于元素的值与某个特定的键相关联,而并非通过元素在数组中的位置来获取。

2、优缺点

3、使用

//1.定义和初始化
map<int,string> map1;                  //空map

//2.常用操作方法
map1[3] = "Saniya";                    //添加元素
map1.insert(map<int,string>::value_type(2,"Diyabi"));//插入元素
map1.insert(pair<int,string>(1,"Siqinsini"));
map1.insert(make_pair<int,string>(4,"V5"));
string str = map1[3];                  //根据key取得value,key不能修改
map<int,string>::iterator iter_map = map1.begin();//取得迭代器首地址
int key = iter_map->first;             //取得eky
string value = iter_map->second;       //取得value
map1.erase(iter_map);                  //删除迭代器数据
map1.erase(3);                         //根据key删除value
map1.size();                           //元素个数
map1.empty();                          //判断空
map1.clear();                          //清空所有元素

//3.遍历
for(map<int,string>::iterator iter = map1.begin();iter!=map1.end();iter++)
{
   int keyk = iter->first;
   string valuev = iter->second;
}

4、实现

2.2、set

1、基本概念

        set的含义是集合,它是一个有序的容器,里面的元素都是排序好的,支持插入,删除,查找等操作,就像一个集合一样。所有的操作的都是严格在logn时间之内完成,效率非常高。

        set和multiset的区别是:set插入的元素不能相同,但是multiset可以相同。Set默认自动排序。使用方法类似list。

        set 不支持下标操作符,而且没有定义 mapped_type 类型。

2、优缺点

3、使用

4、实现

2.3、multimap

2.4、multiset

三、容器适配器

3.0、概述

3.1、stack

1、基本概念

        它可以将任意类型的序列容器转换为一个堆栈,一般使用deque作为支持的序列容器。

        元素只能后进先出(LIFO)。

        不能遍历整个stack。

2、优缺点

3、使用

4、实现

3.2、queue

1、基本概念

        它可以将任意类型的序列容器转换为一个队列,一般使用deque作为支持的序列容器。

        元素只能先进先出(FIFO)。

        不能遍历整个queue。

2、优缺点

3、使用

4、实现

3.3、priority_queue

1、基本概念

        它可以将任意类型的序列容器转换为一个优先级队列,一般使用vector作为底层存储方式。

        只能访问第一个元素,不能遍历整个priority_queue。

        第一个元素始终是优先级最高的一个元素。

2、优缺点

3、使用

4、实现

参考:

1、http://www.360doc.com/content/14/0408/11/1317564_367203273.shtml

2、https://segmentfault.com/a/1190000000325549

3、http://blog.chinaunix.net/uid-21411227-id-1826905.html

4、http://blog.csdn.net/conanswp/article/details/23297441


转载标明出处:https://blog.evanxia.com/2016/03/274