C++ 数据结构-标准库的容器(上篇)

2019-09-22 本文已影响0人铁甲万能狗

C++中标准库已经内置了常用的数据结构,数据结构就是程序内部数据的组织形成和存储方法,而我们要讲述的数据结构类型是线性结构,只不过我们在C++的标准库中给了一个更生动的名称叫"容器"。特别是顺序容器，它为程序员提供控制元素存储和访问顺序的能力，如果你有过数据结构的基础，那么C++容器,自然很轻松掌握.

各种容器的特性一览表

如果你不确定使用哪种容器,那么使用vector是非常不错的选择.

容器公共API一览表

container.png

迭代器

你只要熟悉了一种容器的迭代器操作,其他容器的迭代器都带有相同的公共接口,比较特殊的容器就forward_list由于其数据结构属于单向链表的存储结构,不支持--iter的操作

2019-09-09 09-49-27屏幕截图.png

仅适用于vector和string的迭代器的运算

vector_iter.png

迭代器区间

任何的C++的容器都有两个特殊的迭代器

begin():指向容器中的第一个元素
end():指向容器中的末尾元素之后的位置(通常约定为NULL)

而这一对迭代器就构成了一个容器的迭代器区间(iterator range),而迭代器区间中就包含了遍历容器中的所有元素,但不包含end所指向的位置,就是一个左闭合区间 [begin,end)。

如果begin与end相等,即容器为空
如果begin不等于end,即容器至少包含一个元素,且begin始终指向区间中的第一个元素.
这也意味着我们遍历容器的一般逻辑的伪代码是这样的

Container<type> c={a1,a2,a3,....};
Container<type>::iterator iter =c.begin();
 >
  >while (iter != c.end())
  {
     cout << *iter << endl;
     iter++;
  }

又或者:

Container<type> obj={....};
Container<type>::size_type n=obj.size();

for(int i=0;i<n;i++){
    ....obj[i];....
}

容器的初始化

容器初始化就两种:直接初始化和赋值初始化.

其中容器的赋值初始化以列表初始化方式居多，并且要求列表中的数据类型要和和声明语句样板的Container<type>的type要一致.
拷贝对象的初始化都是要求已经存在的源对象的类型和需要初始化的容器的类型(包括容器的元素类型要相容)要一致.
construct.png
只有顺序容器的构造函数但不包括array才接受大小参数,关联容器不支持
construct2.png

vector<double> prices(0.0,10);

C++中的array容器

从上面的容器公共API列表,我们知道array容器是无法新增/删除它的元素,因此array容器适合那些加载临时数据而且元素个数确定的场景，并且在程序退出后C++自动回收内存.

初始化数组的指定元素类型和数组的大小.
列表初始化中的元素类型和array容器声明的元素类型要一致,并且列表中的初始值的个数小于或等于array容器声明的元素个数.

array<int,42> salesCnt={0,112,34,56};
array<string,10> person={"lisa","chary","mary"};

C++的array和C的array的比较

相同点:

C的array和C++的array声明和初始化的时候都要求明确元素类型。
- 较新的C编译器声明和初始化时不需要指定元素个数或用一个变量作为元素的个数,以下示例对C编译器都可以接受的.
  
  char a[]={'a','b','c','\0'};
  或
  int count=4;
  char a[count]={'a','b','c','0'};
- C++的array声明时必须明确元素个数,而C和C++的数组在列表初始化的个数可以小于或等于声明的个数.
C的array和C++的array的大小是固定的,无法向内部插入/删除元素

不同点:

新版本的C++编译器无法通过length的属性名获取C的array长度.基于这一点,不要在C++环境中使用C的array去初始化你的数组.

错误的示例:

char c[3]={'a','b','c'};
//C++ 编译器将c.length视为不合法的语法
for(int i=0;i<c.length;i++){
.....
}
C的array的初始化不允许执行对象赋值拷贝,而C++的array没有此限制,但C++的array在执行对象赋值必须确保元素的类型和个数都必须一致。

char c[]={'a','b','c'};
char d[]=c; //在C中对象赋值拷贝是非法的

array<char,3> c={'a','b','c'};
array<char,3> d=c; //在C++中,对象赋值拷贝是合法的
array<char,4> e=c; //在C++中这是非法的,因为元素个数不一致,对象赋值失败.

由于篇幅有限,剩下内容放到下一部分