《C++Primer》复习——with C++11 [4]

时间:2022-07-18 09:09:51

考虑到STL的掌握主要靠的是练习,所以对于STL这部分,我把书中的练习都做一遍,加深印象。这些练习是第9、10、11、17章的,分别是顺序容器、泛型算法和关联容器等。

                                          ——10月22日

/*------------------------------------------------------------------------------------------------------------*/

STL中的顺序容器:vector--deque--list--forward_list--array--string

除了固定大小的array外,其他容器都提供高效、灵活的内存管理——添加删除更改访问元素、扩张收缩容器大小。string和vector支持快速的随机访问,但是其增删元素却会很耗时:在一次出入或删除操作后,需要移动插入和删除位置之后的所有元素,来保持连续的存储,而且,添加一个元素有事可能还要分配额外的存储空间。list和forward_list设计目的是另容器任何位置的添加和删除操作都很快速,作为代价,这两个容器不支持元素的随机访问,为了访问一个元素,必须便利整个容器,而且,与vector、deque和array相比,这两个容器的额外内存开销也很大。与string和vector类似,deque支持快速的随机访问,deque中间位置添加或删除元素的代价可能很高,但是在deque的两端添加或删除元素都是很快的,与list或forwa_list的添加删除元素的速度相当。forward_list和array是新C++标准增加的类型,与内置数组相比,array是一种更安全、更容易使用的数组类型。

确定使用容器的原则:

*除非你有很好的理由选择其他容器,否则使用vector

*如果你的程序有很多小的元素,且空间的额外开销很重要,则不要使用list或forward_list

*如果程序要求随机访问元素,应使用vector或deque

*如果程序要求在中间插入或删除元素,应使用list或forward_list

*如果程序要求在头围位置插入或删除元素,但不会在中间位置进行插入或删除操作,则使用deque

*如果程序只有在读取输入使才需要在容器中间位置插入元素,随后需要随机访问元素,则——首先,确定是否真的需要在容器中间位置添加元素,处理输入数据时,通常可以很容易的像vector追加元素,然后再调用标准库的sort函数来重拍容器中的元素,从而避免在中间位置添加元素。如果必须在中间插入元素,考虑在输入阶段使用list,一旦输入完成,将list中的内容拷贝到一个vector中。

如果程序即要求随机访问也要求在中间插入元素,取决于实际使用的相对性能,中间插入多的就list或forward_list,两端插入多的酒vector和deque。

/*-------------------------------------------习题start-------------------------------------------------*/

练习9.1:对于下面的程序任务,vector、deque和list哪种容器最为适合?解释你的选择理由,如果没有哪一种容器优于其他容器,也请解释理由。 a.读取固定数量的单词,讲他们按照字典顺序插入到容器中。b.读取未知数量的单词,总是讲新单词插入到末尾,删除操作在头部进行。c.从一个文件读取未知数量的整数,讲这些数排序,然后将他们打印到标准输出。1.list或者forward_lis,因为要按照字典顺序所以很大可能涉及到中间的插入,所以不用vector和deuqe 2.deque无疑,deque支持头尾的插入和删除,不在中间插入删除元素就不用list或forward_list可以节省空间。3.这些整数小而杂,应该使用数组类型的支持随机访问的容器,且要求排序,链表类容器的排序相对浪费时间和存储空间,所以使用vector或者deque。

/*--------------------------------------------习题end----------------------------------------------*/

                        今天写复习笔记优点浪费了时间,所以没写完这个-------10月25日        

练习9.2定义一个list对象,其元素类型是int的deque。list<deque<int>> mylist;

练习9.3构成迭代器范围的迭代器有何限制?两个迭代器分别指向同一个容器中的元素或者尾元素之后的位置。

练习9.4编写函数,接受一对指向vector<int>的迭代器和一个int 值,在两个迭代器指定的范围中查找给定的值,返回一个布尔值指出是否找到。

 bool findvar(vector<int>::iterator first, vector<int>::iterator last, int var)
{
for (vector<int>::iterator it = first; it != last; ++it)
{
if (*it == var)
return true;
}
return false;
}

练习9.5重写上一题的函数,返回一个迭代器指向找到的元素。注意,程序必须处理未找到给定值的情况。

 typedef vector<int>::iterator vit;
vit findvar(vit first, vit last, int var)
{
for (vit it = first; it != last; ++it)
{
if (*it == var)
return it;
}
return last;
}

练习9.6下面程序有何错误?如何改正?

 list<int> lst1;
list<int>::iterator iter1 = lst1.begin(), iter2 = lst1.end();
while (iter1 < iter2)
/*...*/
iter1 != iter2, iter1++

练习9.7为了索引int的vector中的元素,应该使用什么类型?

这个使用普通的const_iterator即可。

练习9.8为了读取string的list中的元素,应该使用什么类型?如果写入list,又应该使用什么类型?

为了读取而并不改变则使用const_iterator,若要写入则需要iterator类型。

练习9.9begin和cbegin两个函数有什么不同?

begin返回的是一个一般性的iterator,而cbegin返回的是一个const_iterator。

练习9.10下面4个对象分别是什么类型?

 vector<int>    v1;
const vector<int> v2;
auto it1 = v1.begin(), it2 = v2.begin();
auto it3 = v1.cbegin(), it4 = v2.cbegin();