【面向对象】顺序容器

71 阅读 0 评论 47 点赞

我是靠谱客的博主优美灰狼，最近开发中收集的这篇文章主要介绍【面向对象】顺序容器，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

顺序容器

容器：特定对象的集合
顺序容器：加入容器的位置；

关联容器：根据关键字的值
vector 可变大小数组，支持随机访问；尾部之外的位置插入很慢（string 特殊的）

deque 双端队列，快速随机访问，头尾操作很快

list 双向链表双向顺序访问；任意位置操作很快

forward_list 单向链表

确定使用哪种顺序容器

如果只有在读取输入时才需要在容器中间位置插入元素, 随后需要随机访问元素，则
— 首先，确定是否真的需要在容器中间位置添加元素。
当处理输入数据时，通常可以很容易地向vector追加数据，
然后再调用标准库的sort函数来重排容器中的元素，从而避免在中间位置添加元素。
— 如果必须在中间位置插入元素，考虑在输入阶段使用list，
一旦输入完成，将list中的内容拷贝到一个vector中。
如果既需要随机访问元素，又需要在容器中间位置插入元素
在list或forward_list中访问元素与vector或deque中插入/删除元素的相对性能。
一般来说，应用中占主导地位的操作（执行的访问操作更多还是插入/删除更多）
决定了容器类型的选择
在此情况下，对两种容器分别测试应用的性能可能就是必要的了。
如果你不确定应该使用哪种容器，那么可以在程序中只使用vector和list公共的操作：
使用迭代器，不使用下标操作，避免随机访问

迭代器：

左闭右开；第一个和最后一个之后
总是可以递增begin来达到end
list迭代器不支持<,只支持++ – == !=,因为链表中指针大小与顺序不一定吻合
当不需要写访问时，应使用 cbegin 和 cend

定义和初始化

list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a","an","the"};
//元素类型转换
forward_list<string> words(articles.begin(),articles.end());
//拷贝元素直到(但不包括)it指向的元素。it是迭代器，指向authors中一个元素
deque<string> authList(authors.begin(),it);

当将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型和元素类型都必须相同

array<int,10> a1; //10个默认初始化的int
array<int,10> a2={0,1,2,3,4,5,6,7,8,9}; //列表初始化
array<int,10> a3={12}; //a3[0]为12，其余为0
//普通数组不能拷贝，但是array可以，但是要求大小类型都相同

vector<int> vec; // 0
vector<int> vec(10); // 10个0
vector<int> vec(10, 1); // 10个1
vector<int> vec{ 1, 2, 3, 4, 5 }; // 1, 2, 3, 4, 5
vector<int> vec(other_vec); // 拷贝 other_vec 的元素
vector<int> vec(other_vec.begin(), other_vec.end()); // 拷贝other_vec的元素

c.assign(b, e) 将c中的元素替换成迭代器b和e表示范围中的元素，
b和e不能指向c中的元素
c.assign(il) 将c中的元素替换成初始化列表il中的元素
c.assign(n, t) 将c中的元素替换为n个值是t的元素
//赋值相关运算会导致指向左边容器的内部迭代器引用和指针失效。
//swap操作将容器内容交换不会导致指向容器的迭代器引用和指针失效

使用swap（头疼篇）

除array外，swap不对任何元素进行拷贝、删除或插入操作，
因此可以保证在常数时间内完成。
元素不会被移动的事实意味着，
除string外，指向容器的迭代器、引用和指针在swap操作之后都不会失效。
它们仍指向swap操作之前所指向的那些元素。
但是，在swap之后，这些元素已经属于不同的容器了。
对一个string调用swap会导致迭代器、引用和指针失效。
swap两个array会真正交换它们的元素
对于array，在swap操作之后，指针、引用和迭代器所绑定的元素保持不变，
但元素值已经与另一个array中对应元素的值进行了交换。

比较

比较一个list<int>中的元素和一个vector<int>中的元素。
std::list<int> li{ 1, 2, 3, 4, 5 };
std::vector<int> vec2{ 1, 2, 3, 4, 5 };
std::vector<int> vec3{ 1, 2, 3, 4 };
std::cout << (std::vector<int>(li.begin(), li.end()) == vec2 ?
"true" : "false") << std::endl;
std::cout << (std::vector<int>(li.begin(), li.end()) == vec3 ?
"true" : "false") << std::endl;

添加

向一个vector string deque 插入元素会使所有指向容器的迭代器、引用和指针失效。

//操作会改变大小，因此不适用于array。
//forward_list有自己专有版本的insert和emplace。
//forward_list不支持push_back和emplace_back。
c.push_back(t) //(除forward_list)在c尾部创建一个值为t的元素，返回void
c.emplace_back(args) //同上
c.push_front(t) //在c头部创建一个值为t的元素，返回void
c.emplace_front(args) //同上
c.insert(p, t) //在迭代器p指向的元素之前创建一个值是t的元素，返回指向新元素的迭代器
c.emplace(p, args) //同上
c.insert(p, n, t) //在迭代器p指向的元素之前插入n个值为t的元素，返回指向第一个新元素的迭代器；如果n是0，则返回p
c.insert(p, b, e) //将迭代器b和e范围内的元素，插入到p指向的元素之前；如果范围为空，则返回p
c.insert(p, il) //il是一个花括号包围中的元素值列表，将其插入到p指向的元素之前；如果il是空，则返回p

insert成员允许在容器中任意位置插入0个或多个元素。

vector、deque、list和string都支持insert成员。

forward_list提供了特殊版本的insert成员
insert函数都接受一个迭代器作为其第一个参数,指出在容器中什么位置放置新元素

vector<string> svec;
list<string> slist;
//等价于slist.push_front("Hello");
slist.insert(slist.begin(),"Hello");
//vector 不支持push_front, 插入末尾之外的位置都可能很慢
svec.insert(svec.begin(),"Hello!");

//将10个元素插入到svec的末尾，并将所有元素都初始化为string"Anna"。
svec.insert(svec.end(),10,"Anna");
vector<string> v = {"quasi","simba","frollo","scar"};
//将v的最后两个元素添加到slist开始位置
slist.insert(slist.begin(),v.end()-2,v.end());
slist.insert(slist.end(),{"these","words","will","go","at","the","end"});
//运行时错误 迭代器表示要拷贝的范围 不能指向与目的位置相同的容器
slist.insert(slist.begin(),slist.begin(),slist.end());

在新标准下，接受元素个数或范围的insert版本返回指向第一个新加入元素的迭代器。
在旧版本的标准库中，这些操作返回void。

如果范围为空，不插入任何元素，insert操作会将第一个参数返回。

list<string> lst;
auto iter=lst.begin();
while(cin>>word)
iter = lst.insert(iter,word);//等价于push_front
//每步while循环就会将一个新元素插入到iter之前
//并将iter改变为新加入元素的位置。
//这个循环等价于调用push_front

emplace

c.emplace_back("987",25,15.99);
//错误 没有接受三个参数的push_back
c.push_back("987",25,15.99);
//正确 创建临时对象 传递给push_back
c.push_back(Sales_data("987",25,15.99));
//其中对emplace_back的调用和第二个push_back调用都会创建新的Sales_data对象。
//在调用emplace_back时，会在容器管理的内存空间中直接创建对象。
//而调用push_back则会创建一个局部临时对象，并将其压入容器中。

访问

//判断非空
if(!c.empty()){
//val val2是c中第一个元素的拷贝
auto val = *c.begin(),val2=c.front();
//val3 val4 是c中最后一个元素的拷贝
auto last = c.end();
auto val3 = *(--last);//不能递减forward_list迭代器
auto val4 = c.back();//forward_list 不支持
}

if(!c.empty()){
c.front()=42;//42赋给第一个元素
auto &v = c.back();
v =1024;//改变c中的值
auto v2 = c.back();
v2 = 0; //未改变c中的值
}

#include <iostream>
#include <vector>
int main()
{
std::vector<int> v;
std::cout << v.at(0); // out_of_range
std::cout << v[0]; // Segmentation fault
std::cout << v.front(); // Segmentation fault
std::cout << *v.begin(); // Segmentation fault
return 0;
}