原创 by zoe.zhang

 0.写在前面的话

　　我是在2011年学的C++，但是那一年恰好是C++11新标准的一年，但是大学上学的C++还是基于C++98的风格的，使用的编译器也是VC6.0，啊，插一句话，虽然VC6现在看起来有些简陋，而且也不支持C++新标准，但是因为它的轻便，以及有些年代感的编码界面，我自己感觉它就像是一柄钝剑，加上是我接触的第一个编译器，因此对它还是怀有敬意的。当然，现在用的VS2013，编程友好，功能强大，也是非常棒的了。它是支持C++11标准的。C++11相对C++98来说有了很多新变化，根据书上说，是为C++打磨了一套新的体系。当年的C++学习的基础现在想来真的很是浅显，不过语言真的很有趣啊，阅读C++ primer这本大厚书的时候，居然很多时候并不觉得枯燥，反而仿佛看到一扇新的大门一样，忍不住惊叹设计的巧妙，啊，不，美妙。

　　总的来说，自己在学习C++的路上还有许多事情和实践需要做。

　　这一篇文章是和C++中的容器相关，基本当年大一的时候是没有接触过的内容，如今捧卷来读，只觉自己知道得太少。好了，切入正题。

　　C++11的标准库得到了广泛的赞誉以及被众多程序员接受和使用。STL标准库中封装了许多复杂优秀的数据结构/容器，也提供了大量的基于迭代器的以及等常用的数据结构算法和操作，

　　在C++标准中，STL被组织为下面的17个头文件：<algorithm>、<deque>、<functional>、<iterator>、<array>、<vector>、<list>、<forward_list>、<map>、<unordered_map>、<memory>、<numeric>、<queue>、<set>、<unordered_set>、<stack>和<utility>等等。

　　这一章主要是关于容器的学习记录。容器主要分为顺序容器（如vector，list等），关联容器（map，set等），对于这些容器C++提供了插入、排序，删除、查找等等一系列通用或者部分特殊的常用操作。这里要稍微理解一些这些容器与我们在算法中经常见到的数据结构中的关系。

　　vector：类似于增强型数组结构的封装；list：链表式结构；

　　set/map：基于高效的平衡二叉树（红黑树），红黑树具有很好的统计特性，作为关联容器的内部结构。关于红黑树/AV-L树放到其他章节再讨论。

　　还有一点为什么容器类被称作容器，因为容器实际上是一种类模板，可以像容器一样存放大多数类型的对象。

 1.迭代器

　　迭代器是使用容器的基础，除掉数组、vector、string等对象可以使用下标运算符，迭代器（iterator）是一种更加通用的机制。在使用容器之前需要深刻理解迭代器的用法，STL提供的泛型算法是基于迭代器对象或者说是一对迭代器生成的范围之上的。此处指出一下：严格上string类型不属于容器，但是它支持很多与容器类型的操作，也支持迭代器。迭代器提供了对对象的间接访问，可以从一个元素移动到下一个元素，（在C++11里，对于对象的>/</++/--/==/!=等运算符的定义要注意理解。）迭代器某种意义上有点像更宽泛意义上的指针，在行为上也有点像，它有无效和有效之分，有效的迭代器指向某个元素或者指向尾后元素。

（1）获取迭代器：迭代器类型

　　有迭代器的容器类型都有拥有返回迭代器的成员。我们主要是使用迭代器，有时候并不关心迭代器的类型，所以可以由编译器决定，也可以显示指定。　

auto it_b = v.begin(), it_end = v.end(); // 由编译器决定 
auto cit_b = v.cbegin(), cit_end = v.cbegin(); // 返回常量迭代器
vector<int>::iterator it;        //显示定义
vector<int>::const_iterator cit;//显示定义，常量，能够读取但是不修改

 （2）检查容器是否为空

　　这里有一个特殊的迭代器，称为“尾后迭代器”，某种程度上类似于一个边界条件，（end iterator），用于构成迭代器范围。通常使用容器第一步需要判断容器是否为空，容器为空时，begin和end函数返回的是同一个迭代器，均为尾后迭代器。或者迭代器遍历容器完毕结束的条件，就是到达尾后迭代器。

if (v.begin() != v.end()){}

（3）迭代器的基本操作：

• *iter：解引用，返回迭代器所指向元素的引用；如果解引用所得到的对象是类，通过箭头运算符将解引用和成员访问结合到一起，iter->mem;
• ++iter,--iter:迭代器从一个元素移动下一个元素；几乎所有迭代器都支持++操作，++操作相对来说更通用，在反向迭代器时要注意理解。（注意：所有标准库容器都支持++递增运算的迭代器，一些容器的迭代器提供了额外的操作，比如vector和string，array，deque的迭代器运算相对丰富）（forward_list迭代器不支持--递减运算符操作）
• ==，！=：判断两个迭代器是否指向同一元素（包括尾后迭代器）

（4）迭代器范围：

　　迭代器范围的概念是标准库的基础。一个迭代器范围由一对迭代器表示，这里的迭代器区间是左闭合区间[begin，end）,从begin开始，但是不包含end。如果begin与end相等，那么范围为空，如果begin和end不等，那么范围至少包含一个元素。

（5）迭代器的种类

　　除了为容器提供的用于访问数据提供的迭代器之外，标准库还提供了其他几种迭代器。

　　插入迭代器：绑定在容器上，可以向容器内插入数据；它接受一个数据，生成一个迭代器，当通过insert iterator进行赋值的时候，迭代器调用容器操作来向容器指定位置插入一个元素。

　　流迭代器；绑定在输入或输出流上，用来遍历关联的的IO流；

　　反向迭代器：迭代器向后移动，虽然也使用++运算符，但是是向后移动的；（C++ primer 图10.2 ）

　　移动迭代器：顾名思义，用于移动元素。

 2.顺序容器

　　顺序容器中，元素的排放顺序是与其加入容器时的位置相对应的，这种顺序不依赖于元素的值，与元素加入容器时的位置县桂英。

　　关联容器中，元素的位置由相关联的关键字值决定的。也就是所关联容器中元素的位置与关键字关联。

（1）顺序容器的种类：顺序容器都提供了快速顺序访问元素的能力。

• vector：可变大小数组，支持快速随机访问，可快速增长，但是插入或删除元素可能很慢。
• deque：双端队列，支持快速随机访问，在首尾插入、删除速度很快。
• list：双向链表，双向顺序访问/遍历(链表不支持元素的随机访问），list在任何位置的插入和删除速度都很快，很方便。
• forward_list:单向链表，单向顺序访问。
• array：固定大小数组，支持随机快速访问，不能删除或填加元素。
• string：字符串容器。

　　关于顺序容器的使用有一些总结：

　　a. 除了array固定大小，其他顺序容器都提供高效、灵活的内存管理，可以添加、删除、扩张和收缩容器。

　　b. string 和vector等容器将元素保存在连续的内存空间中，即其元素的内存是连续存储的，可以支持下标操作。

　　c. 通常使用vector是很好的选择，除非你有更好的理由选择其他容器。

　　d. 如果在读取时需要插入元素，但是随后需要使用随机访问元素，根据情况可以选择sort重排vector，更通用情况是输入阶段使用list，输入完成后，将list中的内容放入到一个vector中。

（2）容器库的操作

　　容器型的操作可以看成包括3种类型：一种是通用的，一种各自针对顺序容器、关联容器、无序容器等，还有一种是针对特殊的容器类型。

　　容器通用操作包括：类型别名，构造函数（默认，拷贝，迭代器范围构造c（b,e）,列表初始化），赋值和swap，大小，添加和删除（insert，emplace,erase,clear）,关系运算符，获取迭代器.

（3）顺序容器的操作

（4）vector对象是如何增长的：关于内存空间分配的一些讨论；

（5）string库的额外操作

 3.关联容器

　　关联容器中的元素是根据关键字来保存和访问的，顺序中的容器元素按照它们在容器中的位置来顺序保存和访问。

　　关联容器支持的是高效的关键字查找和访问。、

（1）综述

　　关联容器的类型主要有map和set两种，根据有序无序，允许重复和不允许重复关键字分为8种关联容器。按照关键字有序保存元素的容器定义在map和set头文件中，无序容器保存在unordered_map和unordered_set中，有序容器实际上按顺序保存元素，通过比较运算符来组织元素。无序容器使用哈希（hash）函数和关键字类型==来组织元素。

　　举例：set——有序存储的不允许重复关键字的集合； unordered_multi_set——无序存储的通过哈希函数组织、允许关键字重复的集合。

　　对于有序容器而言，传入的关键字类型，需要定义元素的比较方法，标准库通过使用关键字的类型<运算符比较两个关键字，来组织元素。

（2）map

　　map是关键字—值对的集合，关键字起到索引的作用，可以被称为“关联数组”，因为它可以通过下标运算符来访问值，只不过下标运算符中传入的是关键字。在文本处理上，字典是一个map一个很好的使用例子。

　　a. map初始化：

　　当定义一个map时，需要指明关键字和值的类型，关联容器都定义了一个默认构造函数，创建一个指定类型的空容器。

　　如果需要对map或者set等容器进行初始化，可以使用列表初始化；将关联容器初始化为另一同类型容器的拷贝，或者使用一个值范围来进行初始化；（迭代器范围）；其中需要注意一下multimap或者multiset与map和set的不同。

//map 值初始化
map<string, string>authors = {  { "jocye", "1111" },
                                { "Austen", "2222"},
                                { "Dicken", "3333"} };

//ivec是一个包含重复元素的vector 
set<int> iset(ivec.cbegin(), ivec.cend());   //不包含重复元素
multiset<int> miset(ivec.cbegin(), ivec.cend());//包含重复元素

　　b.map的使用：

//统计出现次数——下标运算符
map<string, size_t> word_count;
string word;
while (cin >> word)
    ++word_count[word];
for (const auto &w : word_count)
cout << w.first << "occurs" << w.second
    << ((w.second > 1) ? "times" : "time") << endl;

 　　这里用到了下标运算符[]，下标运算符在map中的特点是，会根据传入的对象去寻找对应的key-value对，如果元素不在map中，会自动创建一个新元素，初始化value为0‘；

　　map中的元素为pair类型，pair的first成员保存关键字，second成员保存对应的值。

（3）set

　　set是关键字的简单集合，set支持的是高效的关键字查询操作，检查一个关键字是否在set中，set是最有用的，常见一个场景，定义set保存要忽略的元素，或者检查屏蔽等。

　　a. 定义一个set的时候，应当指明关键字类型，其初始化可参考上文map的初始化问题。

　　b.set的使用：   

//使用set忽略想忽略的单词
map<string, size_t> word_count;
set<string> exclude = { "the", "but", "and", "or", "an" };//列表初始化
string word；
while (cin >> word)
{
    if (exclude.find(word) == exclude.end())
        ++word_count[string];
}

　　这里是set一个最常见的用法，set.find(obj),调用返回一个迭代器，如果给定关键字在set中，就指向该关键字，如果不在，find返回尾后迭代器。

（4）关联容器迭代器

　　 map<string, int> word_count;
    auto map_it = word_count.begin(); //获取map迭代器
    //*map_it是pair类型；可以通过map_it->first;map_it->second 访问键值对
    // 注意：map_it->first 关键字是const 不可改变

    set<int> myset = { 0, 1, 2, 3, 5, 6, 7, 8 };
    set<int>::iterator set_it = myset.begin(); 
    //显式定义迭代器 不管是begin还是cbegin返回的都是const_iterator

（5）关联容器相关操作

• 遍历操作：递增迭代器遍历

auto map_it = word_count.cbegin();
    while (map_it != word_count.cend())
    {
        cout << i;
        cout<<(map_it->first)<<"occurs"<< (map_it->second) << endl;
        ++map_it;  
    }

• 添加元素

    //set 插入操作：不允许重复元素
    vector<int> vec = { 2, 4, 6, 8, 2, 4, 6, 8 };
    set<int> set2;
    set2.insert(vec.cbegin(), vec.cend()); //set2 有4个元素  重复元素不插入 接受一对迭代器
    set2.insert({ 1, 3, 5, 7, 1, 3, 5, 7 }); //再插入4个元素  接受一个初始化器列表

    //map 向map添加元素：所添加的元素类型是pair
    word_count.insert({ "word", 1 }); //{}花括号构造初始化一个pair
    word_count.insert(make_pair("word", 1));//make_pair显示构造  
    word_count.insert(pair<string, size_t>("word", 1));      

　　insert函数会返回值，对于不包含重复关键字的容器，添加单一元素的insert会返回一个pair，pair的的第一个元素是一个迭代器，指向给定关键字的元素，第二个元素second，是一个bool值，如果关键字已经在容器中，bool值为false，insert不做任何事。如果关键字不在，元素插入容器中，bool值为true。对于允许重复关键字的容器，接受单一元素的容器的insert会返回一个指向新元素的迭代器。

• 删除元素

    c.erase(k);//k是一个关键字，返回一个size_type的值，删除元素的数量；
    c.erase(it);//it是一个迭代器，删除迭代器it指向的元素
    c.erase(b, e);//一对迭代器所表示的范围元素    

• 访问元素

　　访问元素是很重要的一个方法，因为关联容器的一个意义所在就是提供了高效得对元素的访问。主要有find和count两个方法，find返回迭代器，count可以计算出元素出现的次数。

　　对于map和unordered_map(不允许重复）的类型中，下标运算符提供了最简单的访问和提取元素值的方法，但是下标运算符会将未在map中的元素添加到map中。因此如果不想改变map，所以应该使用find方法。

    set<int> myset = { 1, 2, 3, 4, 5, 6, 7, 8 };
    myset.find(1); //返回一个迭代器 指向key == 1; 如果未找到，返回set2.end();
    myset.count(1);//返回1；

    myset.lower_bound(2); //返回一个迭代器 指向第一个关键字不小于k ==2 的元素
    myset.upper_bound(2); //返回一个迭代器 指向第一个关键字大于k ==2 的元素  注意是大于；左闭合区间
    myset.equal_range(2); //返回一个pair，pair两个元素均是迭代器 表示关键字==k的元素范围----常用于multiset/multimap;

    // map 
    multimap<string, string> author;
    string search_item = "Alain";
    for (auto beg = author.lower_bound(search_item),
        end = author.upper_bound(search_item);
        beg != end; ++beg)
        cout << beg->second;   // 如果上限和下限返回相同迭代器，则给定关键字不在容器中

 （6）无序容器

　　无序容器使用hash function和关键字类型==运算符来组织元素，无序容器在存储组织上为一组桶，每个桶保存零个或者多个元素，无序容器使用哈希函数将元素将元素映射到桶。

　　访问元素的步骤：a、计算元素的哈希值，指出这个元素是放在哪一个桶中（具有相同哈希值的元素保存在相同的桶中）b、桶中存在多个元素时，通过顺序搜索这些元素来查找我们想要的那个。

　　哈希技术能够获得更好的平均性能。无序容器的性能依赖于哈希函数的质量和桶的数量和大小。

4.泛型算法

　　标准库容器提供了大量的泛型算法，这些算法独立于特定容器，这些算法是运行于迭代器之上的，不会去做容器的操作。这一概念一定要牢记在心理，也是泛型算法之所以通用的关键所在。

　　大多是算法都定义在头文件algorithm中，还有numeric中定义了数值的泛型算法。

　　泛型算法的知识还是相当多的，同时对迭代器的理解也要更深刻，这里我只列举一些基础和浅显的实例，更多知识应当参阅C++primer中。

　　此外还要注意一点，泛型算法很大一部分跟顺序容器的联系比较紧密，我们通常不对关联容器使用泛型算法，因为对于关联容器，关键字通常是const的，所以不能将关联容器传递给修改或者重排容器的算法。关联容器虽然可以使用读取元素的算法，比如说泛型算法中的find方法，但是其效率远远比不上关联容器自己定义的专用find方法，这一点要注意一下。

　　对于泛型算法而言，主要可以分为三类：读取元素、改变元素或者重排元素；

　　除了少数例外，标准库算法都是对一个范围内的元素进行操作，也就是所说的“输入范围”，该输入范围通常使用要处理的第一个元素和最后一个元素之后位置的两个迭代器表示。（再度表明左闭合区间）

（1）标准库find方法　　

    vector<int> vec = { 41, 42, 43, 44, 45, 46 };
    int val = 42;
    //find算法：参数表（迭代器1，迭代器2，要查找的值val）
    auto result = find(vec.cbegin(), vec.cend(), val);
    //如果找到，返回该元素的迭代器；如果找不到，返回vec.cend();
    cout << "the value" << val
        << (result == vec.cend() ? "is not present" :"is present") << endl;

    //find可以用在数组中查找值
    int ia[] = { 27, 20, 31, 34, 109, 11 };
    int *ib = ia;
    int ii = 27;
    int *result = find(begin(ia), end(ia), ii);  //传入位置指针
    auto result2 = find(ia, ia + 4, ii);  // 范围

 （2）accumulate：求和，接收三个参数，定义在头文件numeric中；

    //accumulate 的第三个参数类型决定函数使用哪个加法运算符 第三个参数是初值
    string sum = accumulate(v.cbegin(), v.cend(), string(""));

（3）重排容器元素的算法：sort unique；

　　void elim(vector<string> &words)
    {
        sort(words.begin(), words.end());//重排
        auto end_unique = unique(words.begin(), words.end());
        words.erase(end_unique, words.end())；
    }

C++ Primer 阅读笔记：迭代器和容器 小结