基础知识

array与vector是连续存储空间，可以用指针的算术运算实现对容器的访问。list也是一个容器，不同的是，list的元素以一组指针相互链接(linked)：前向(forward)指针指向下一个(next)元素，后向(backward)指针指向上一个(preceding)元素。因此，指针的算术运算并不适用于list。解决这个问题的办法是，在底层指针的行为之上提供一层抽象，取代程序原本的“指针直接操作”方式。我们把底层指针的处理通通放在此抽象层中，让用户无须直接面对指针操作，iterator（泛型指针）应运而生。

泛型算法提供了许多可作用于容器类及类型上的操作。这些算法之所以称之为泛型(generic)，是因为它们和它们想要操作的元素类型无关。泛型算符系通过function template技术，达到“与操作对象的类型相互独立”的目的。

利用istream_iterator从标准输入设备读取字符串，我们需要一对iterator：first和last，用来标示元素范围。以下定义：

istream_iterator<string> is(cin);

为我们提供了一个first iterator，它将is定义为一个“绑至标准输入设备”的istream_iterator。我们还需要一个last_iterator，表示“要读取的最后一个元素的下一个位置”。对于不标准输入设备而言，end-of-file即代表last。只要在定义istream_iterator时不为它指定istream对象，它便代表了end-of-file，例如：

istream_iterator<string> eof;

所有容器的共通操作

equality（==）和inequality（!=）运算符，返回ture或false。

assignment（=）运算符，将某个容器复制给另一个容器。

empty()会在容器无任何元素时返回true，否则返回false。

size()返回容器内目前持有的元素个数。

clear()删除所有元素

每个容器都提供了begin()和end()两个函数，分别返回指向容器的第一个元素和最后一个元素的下一位置的iterator。通常我们在容器身上进行的迭代操作都是始于begin()而终于end()。

所有容器都提供insert ()用以插入元素，以及erase()用以删除元素。

insert()将单一或某个范围内的元素插入容器内。

erase()将容器内的单一元素或某个范围内的元素删除。

insert()和erase()的行为视容器本身为顺序性(sequential)容器或关联(associative)容器而有所不同。

顺序性容器

顺序性容器用来维护一组排列有序、类型相同的元素。这里介绍三种主要的顺序性容器vector、list和deque。

vector以一块连续内存来存放元素。对vector进行随机访问(random access)——例如先取其第5个元素，再取其第17个元素，然后取其第九个元素——颇有效率；vector内的每个元素都被储存在距离起始点的固定偏移位置上。如果将元素插入任意位置，而此位置不是vector的末端，那么效率将很低，因为插入位置右端的每个元素，都必须被复制一份，依次向右移动。同样道理，删除vector内最后一个元素以外的任意元素，同样缺乏效率。

list系以双向链接(double-linked)而非连续内存来存储内容，因此可以执行前进或后退操作。list中的每个元素都包含三个字段：value、back指针（指向前一个元素）、front指针（指向下一个元素）。在list的任意位置进行元素的插入或删除操作，都颇具效率，因为list本身只需适当设定back指针和front指针即可。但是如果要对list进行随机访问，则效率不彰。

第三种顺序性容器是所谓的deque(读作deck)。deque的行为和vector颇为相似——都以连续内存储存元素。和vector不同的是，deque对于最前端元素的插入和删除操作，效率更高；末端元素亦同。（标准库的queue便是以deque实现，也就是说，以deque作为底部储存元素。）

定义顺序性容器对象的方式有五种：

1. 产生空的容器：
list<string> slist;

vector<int> ivec;
2. 产生特定大小的容器。每个元素都以其默认值作为初值：
list<int> ilist(1024);

vector<string> svec(32);
3. 产生特定大小的容器，并为每个元素指定初值：
vector<int> ivec(10, -1);

list<string> slist(16, "unassigned");
4. 通过一对iterator产生容器，这对iterator用来标示一整组作为初值的元素的范围：
int ia[8] = { 1,1,2,3,5,8,13,21 };

vector<int> fib(ia, ia + 8);
5. 根据某个容器产生出新容器，复制原容器内的元素，作为新容器的初值：
list<string> slist;

list<string> slist2(slist);

有两个特别的操作函数，允许我们在容器的末尾进行插入和删除操作：push_back()和pop_back()。push_back()会在末端插入一个元素，pop_back()会删除最后一个元素。除此之外，list和deque（但不包括vector）还提供了push_front()和pop_front()，允许在容器前端进行插入和删除操作。

关联容器

关联容器可以让我们快速查找容器中的元素值。

map是一对对的key/value 组合。key用于查找，value用来标示我们要储存或取出的数据。举例来说，电话号码即可以用map轻松表示，电话用户名便是key，而value与电话号码产生关联。

set，仅包含有key。我们对它进行查询操作，为的是判断某值是否存在于其中。如果我们想要建立一组索引表，用来记录出现于新闻、故事中的字眼，我们可能会希望将一些中性字眼如the、an、but排除掉。在让某个字眼进入索引表之前，我们要先查询exclude_word这么一个set，如果这个字眼在里面，我们便忽略它不再计较；反之则将它加入索引表。

练习题答案

练习3.1 写一个读取文本文件的程序，将文件中的每个单字存入map。map的key便是刚才所说的单字，map的value则是该单字在文本文件中的出现次数。再定义一份由“排除字眼”组成的set，其中包含诸如a，an，or，the、and和but之类的单字。将某个单字放入map之前，先确定该单字并不在“排除字集”中。一旦文本文件读取完毕，请显示一份单字清单，并显示各单字的出现次数。你甚至可以再加以扩展，在显示单字之前，允许用户查询某个单字是否出现于文本文件中。

#include <map>

#include <set>

#include <string>

#include <iostream>

#include <fstream>

using namespace std;

void initialize_exclusion_set(set<string>&);

void process_file(map<string, int>&, const set<string>&, ifstream&);

void user_query(const map<string, int>&);

void display_word_count(const map<string, int>&, ofstream&);

int main()

{

    ifstream ifile("1.txt");

    ofstream ofile("2.txt");

    if (!ifile || !ofile)

    {

        cerr << "Unable to open file -- bailling out!\n";

        return -1;

    }

    set<string> exclude_set;

    initialize_exclusion_set(exclude_set);

    map<string, int> word_count;

    process_file(word_count, exclude_set, ifile);

    user_query(word_count);

    display_word_count(word_count, ofile);

    return 0;

}

void initialize_exclusion_set(set<string>& exs)

{

    static string _excluded_words[25] = {

        "the","and","but","that","then","are","been",

        "can","a","could","did","for","of",

        "had","have","him","his","her","its","is",

        "were","which","when","with","would"

    };

    exs.insert(_excluded_words, _excluded_words + 25);

}

void process_file(map<string, int>& word_count, const set<string>& exclude_set, ifstream& ifile)

{

    string word;

    while (ifile >> word)

    {

        if (exclude_set.count(word))

            continue;

        word_count[word]++;

    }

}

void user_query(const map<string, int>& word_map)

{

    string search_word;

    cout << "Please enter a word to search( q to quit ): ";

    cin >> search_word;

    while (search_word.size() && search_word != "q")

    {

        map<string, int>::const_iterator it;

        if ((it = word_map.find(search_word)) != word_map.end())

            cout << "Found! " << it->first

            << " occurs " << it->second

            << " times.\n";

        else cout << search_word

            << " was not fount in text.\n";

        cout << "\nAnother search?( q to quit) ";

        cin >> search_word;

    }

}

void display_word_count(const map<string, int>& word_map, ofstream& os)

{

    map<string, int>::const_iterator iter = word_map.begin(),

        end_it = word_map.end();

    while (iter != end_it)

    {

        os << iter->first << " ( "

            << iter->second << " ) " << endl;

        ++iter;

    }

    os << endl;

}

练习3.2 读取文本文件内容——和练习3.1一样——并将内容储存于vector。以字符串长度为依据，对vector进行排序。定义一个function object并传给sort()；这一function object接受两个字符串，当第一字符串的长度小于第二字符串的长度时，就返回true。最后，打印排序后的vector内容。

#include <iostream>

#include <vector>

#include <fstream>

#include <algorithm>

using namespace std;

class LessThan

{

public:

    bool operator()(const string& s1, const string& s2)

    {

        return s1.size() < s2.size();

    }

};

template <typename elemType>

void display_vector(const vector<elemType>& vec, ostream& os = cout, int len = 8)

{

    vector<elemType>::const_iterator iter = vec.begin(),

        end_it = vec.end();

    int elem_cnt = 1;

    while (iter != end_it)

    {

        os << *iter++

            << (!(elem_cnt ++ % len) ? '\n' : ' ');

    }

    os << endl;

}

int main()

{

    ifstream ifile("1.txt");

    ofstream ofile("2.txt");

    if (!ifile || !ifile)

    {

        cerr << "Unable to open file -- bailing out!\n";

        return -1;

    }

    vector<string> text;

    string word;

    while (ifile >> word)

        text.push_back(word);

    sort(text.begin(), text.end(), LessThan());

    display_vector(text, ofile);

    return 0;

}

练习3.3 定义一个map，以家庭姓氏为key，value则是家庭所有小孩的名字。另此map至少容纳六笔数据。允许用户根据姓氏来查询，并得以打印map内的每一笔数据。

#include <iostream>

#include <vector>

#include <map>

#include <fstream>

#include <string>

using namespace std;

typedef vector<string> vstring;

void populate_map(ifstream& nameFile, map<string, vstring>& families)

{

    string textline;

    while (getline(nameFile, textline))

    {

        string fam_name;

        vector<string> child;

        string::size_type pos = 0, prev_pos = 0,

            text_size = textline.size();

        //找出以空格分隔开来的所有单字

        while ((pos = textline.find_first_of(' ', pos)) != string::npos)    //string::npos表示直到字符串结束

        {

            //计算所有自字符串的终点

            string::size_type end_pos = pos - prev_pos;

            //倘若prev_pos并未设置（或说其值为0），那么读到的单字就是家庭姓氏，否则我们就一一读取孩子们的名字

            if (!prev_pos)

                fam_name = textline.substr(prev_pos, end_pos);

            else child.push_back(textline.substr(prev_pos, end_pos));

            prev_pos = ++pos;

        }

        //现在处理最后一个孩子的名字

        if (prev_pos < text_size)

            child.push_back(textline.substr(prev_pos, pos - prev_pos));

        if (!families.count(fam_name))

            families[fam_name] = child;

        else

            cerr << "Oops! We already hava a "

            << fam_name << " family in our map!\n";

    }

}

void display_map(const map<string, vstring>& families, ostream& os)

{

    map<string, vstring>::const_iterator it = families.begin(),

        end_it = families.end();

    while (it != end_it)

    {

        os << "The " << it->first << " family ";

        if (it->second.empty())

            os << "has no children\n";

        else

        {

            os << "has " << it->second.size() << " children: ";

            vector<string>::const_iterator iter = it->second.begin(),

                end_iter = it->second.end();

            while (iter != end_iter)

            {

                os << *iter << " ";

                ++iter;

            }

            os << endl;

        }

        ++it;

    }

}

void query_map(const string& family, const map<string, vstring>& families)

{

    map<string, vstring>::const_iterator it = families.find(family);

    if (it == families.end())

    {

        cout << "Sorry. The " << family

            << " is not currently entered.\n";

        return;

    }

    cout << "The " << family;

    if (!it->second.size())

        cout << " has no children.\n";

    else

    {

        cout << " has " << it->second.size() << " children: ";

        vector<string>::const_iterator iter = it->second.begin(),

            end_iter = it->second.end();

        while (iter != end_iter)

        {

            cout << *iter << " ";

            ++iter;

        }

        cout << endl;

    }

}

int main()

{

    map<string, vstring> families;

    ifstream nameFile("1.txt");

    if (!nameFile)

    {

        cerr << "Unable to find the file. bailling out!\n";

        return -1;

    }

    populate_map(nameFile, families);

    string family_name;

    while (1)

    {

        cout << "Please enter a family name or q to quit ";

        cin >> family_name;

        if (family_name == "q")

            break;

        query_map(family_name, families);

    }

    display_map(families, cout);

    return 0;

}

练习3.4 编写一个程序，利用istream_iterator从标准输入设备读取一连串整数。利用ostream_iterator将其中的奇数写至某个文件，每个数值皆以空格分隔。再利用ostream_iterator将偶数写到另一个文件，每个数值单独放在一行中。

#include <iterator>

#include <vector>

#include <iostream>

#include <algorithm>

#include <fstream>

using namespace std;

class even_elem

{

public:

    bool operator()(int elem)

    {

        return elem % 2 ? false : true;

    }

};

int main()

{

    vector<int> input;

    istream_iterator<int> in(cin), eos;

    ofstream even_file("even.file.txt"), odd_file("odd_file.txt");

    if (!even_file || !odd_file)

    {

        cerr << "arghh! unable to open the output files. bailling out!";

        return -1;

    }

    //将ostream_iterator绑定至相应的ofstream对象上，第二参数代表每个元素输出时的分隔符。

    ostream_iterator<int> even_iter(even_file, "\n"), odd_iter(odd_file, " ");

    copy(in, eos, back_inserter(input));

    vector<int>::iterator division = partition(input.begin(), input.end(), even_elem());

    copy(input.begin(), division, even_iter);

    copy(division, input.end(), odd_iter);

    return 0;

}

end。

“有志者，事竟成，破釜沉舟，百二秦关终属楚。”

巴特西

#《Essential C++》读书笔记# 第三章泛型编程风格

基础知识

所有容器的共通操作

顺序性容器

关联容器

练习题答案

最新文章

热门文章

巴特西

#《Essential C++》读书笔记# 第三章 泛型编程风格

基础知识

所有容器的共通操作

顺序性容器

关联容器

练习题答案

最新文章

热门文章

#《Essential C++》读书笔记# 第三章泛型编程风格