通用容器4_deque

1,deque特点:
(1)将元素放在多个连续的存储块.
(2)允许在序列两端快速地插入元素,并且在扩展存储区的时候不需要拷贝和析构原来的对象.
(3)deque支持随机访问[],但是速度没有vector快.
2,deque和vector的区别:微不足道.
deque有接口push_front()和pop_front(),而vector没有.

#include <cstddef>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    ifstream in("happy.in");
    vector<string> vstrings;
    deque<string> dstrings;
    string line;
    // Time reading into vector:
    clock_t ticks = clock();
    while(getline(in, line))
        vstrings.push_back(line);
    ticks = clock() - ticks;
    cout << "Read into vector: " << ticks << endl;

    // Repeat for deque:
    ifstream in2("happy.in");
    ticks = clock();
    while(getline(in2, line))
        dstrings.push_back(line);
    ticks = clock() - ticks;
    cout << "Read into deque: " << ticks << endl;
    //deque插入的速度更快

    // Now compare indexing: 加入行号
    ticks = clock();
    for(size_t i = 0; i < vstrings.size(); i++)
    {
        ostringstream ss;
        ss << i;
        vstrings[i] = ss.str() + ": " + vstrings[i];
    }
    ticks = clock() - ticks;
    cout << "Indexing vector: " << ticks << endl;

    ticks = clock();
    for(size_t j = 0; j < dstrings.size(); j++)
    {
        ostringstream ss;
        ss << j;
        dstrings[j] = ss.str() + ": " + dstrings[j];
    }
    ticks = clock() - ticks;
    cout << "Indexing deque: " << ticks << endl;
    //vector索引的速度更快

    // Compare iteration
    ofstream tmp1("tmp1.tmp"), tmp2("tmp2.tmp");
    ticks = clock();
    copy(vstrings.begin(), vstrings.end(), ostream_iterator<string>(tmp1, "\n"));
    ticks = clock() - ticks;
    cout << "Iterating vector: " << ticks << endl;
    ticks = clock();
    copy(dstrings.begin(), dstrings.end(), ostream_iterator<string>(tmp2, "\n"));
    ticks = clock() - ticks;
    cout << "Iterating deque: " << ticks << endl;
    //vector使用迭代器更快
}

3,序列容器间的转换

#include <algorithm>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

//读入deque,然后转化为vector
class Noisy
{
    static long create, assign, copycons, destroy;
    long id;
public:
    Noisy() : id(create++) //create:记录构造函数执行的次数
    {
        cout << "d[" << id << "]" << endl;
    }
    Noisy(const Noisy& rv) : id(rv.id) //copycons:记录拷贝函数执行的次数.
    {
        cout << "c[" << id << "]" << endl;
        ++copycons;
    }
    Noisy& operator=(const Noisy& rv) //assign:记录赋值操作执行的次数.
    {
        cout << "(" << id << ")=[" << rv.id << "]" << endl;
        id = rv.id;
        ++assign;
        return *this;
    }
    //容器对象,必须提供比较操作符
    friend bool operator<(const Noisy& lv, const Noisy& rv)
    {
        return lv.id < rv.id;
    }
    friend bool operator==(const Noisy& lv,const Noisy& rv)
    {
        return lv.id == rv.id;
    }
    ~Noisy() //destroy:记录析构函数调用的次数
    {
        cout << "~[" << id << "]" << endl;
        ++destroy;
    }
    friend ostream& operator<<(ostream& os, const Noisy& n)
    {
        return os << n.id;
    }
    friend class NoisyReport;
};

struct NoisyGen
{
    Noisy operator()()
    {
        return Noisy();
    }
};

//单件类,报告类的统计信息.
class NoisyReport
{
    static NoisyReport nr;
    NoisyReport() {} // Private constructor
    NoisyReport & operator=(NoisyReport &);  // Disallowed
    NoisyReport(const NoisyReport&);         // Disallowed
public:
    ~NoisyReport()
    {
        cout << "\n-------------------\n"
             << "Noisy creations: " << Noisy::create
             << "\nCopy-Constructions: " << Noisy::copycons
             << "\nAssignments: " << Noisy::assign
             << "\nDestructions: " << Noisy::destroy << endl;
    }
};
long Noisy::create = 0, Noisy::assign = 0,Noisy::copycons = 0, Noisy::destroy = 0;
NoisyReport NoisyReport::nr;


int main()
{
    int size = 25;
    deque<Noisy> d;
    generate_n(back_inserter(d), size, NoisyGen());

    cout << "\n Converting to a vector(1)" << endl;
    vector<Noisy> v1(d.begin(), d.end());//v1不会导致多次内存分配.

    cout << "\n Converting to a vector(2)" << endl;
    vector<Noisy> v2;
    v2.reserve(d.size());//先预先分配好大小,实际上和v1完全一致.
    v2.assign(d.begin(), d.end());

    cout << "\n Cleanup" << endl;
}

4,

#include <cstdlib>
#include <deque>
#include <iostream>
using namespace std;

//读入deque,然后转化为vector
class Noisy
{
    static long create, assign, copycons, destroy;
    long id;
public:
    Noisy() : id(create++) //create:记录构造函数执行的次数
    {
        cout << "d[" << id << "]" << endl;
    }
    Noisy(const Noisy& rv) : id(rv.id) //copycons:记录拷贝函数执行的次数.
    {
        cout << "c[" << id << "]" << endl;
        ++copycons;
    }
    Noisy& operator=(const Noisy& rv) //assign:记录赋值操作执行的次数.
    {
        cout << "(" << id << ")=[" << rv.id << "]" << endl;
        id = rv.id;
        ++assign;
        return *this;
    }
    //容器对象,必须提供比较操作符
    friend bool operator<(const Noisy& lv, const Noisy& rv)
    {
        return lv.id < rv.id;
    }
    friend bool operator==(const Noisy& lv,const Noisy& rv)
    {
        return lv.id == rv.id;
    }
    ~Noisy() //destroy:记录析构函数调用的次数
    {
        cout << "~[" << id << "]" << endl;
        ++destroy;
    }
    friend ostream& operator<<(ostream& os, const Noisy& n)
    {
        return os << n.id;
    }
    friend class NoisyReport;
};

struct NoisyGen
{
    Noisy operator()()
    {
        return Noisy();
    }
};

//单件类,报告类的统计信息.
class NoisyReport
{
    static NoisyReport nr;
    NoisyReport() {} // Private constructor
    NoisyReport & operator=(NoisyReport &);  // Disallowed
    NoisyReport(const NoisyReport&);         // Disallowed
public:
    ~NoisyReport()
    {
        cout << "\n-------------------\n"
             << "Noisy creations: " << Noisy::create
             << "\nCopy-Constructions: " << Noisy::copycons
             << "\nAssignments: " << Noisy::assign
             << "\nDestructions: " << Noisy::destroy << endl;
    }
};
long Noisy::create = 0, Noisy::assign = 0,Noisy::copycons = 0, Noisy::destroy = 0;
NoisyReport NoisyReport::nr;

int main()
{
    int size = 100;
    deque<Noisy> dn;
    Noisy n;
    for(int i = 0; i < size; i++)
        dn.push_back(n);
    cout << "\n cleaning up "<< endl;
    return 0;
}

5,at比索引操作符[]代价更大.

#include <ctime>
#include <deque>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    long count = 1000;
    int sz = 1000;

    vector<int> vi(sz);
    clock_t ticks = clock();
    for(int i1 = 0; i1 < count; i1++)
        for(int j = 0; j < sz; j++)
            vi[j];
    cout << "vector[] " << clock() - ticks << endl;

    ticks = clock();
    for(int i2 = 0; i2 < count; i2++)
        for(int j = 0; j < sz; j++)
            vi.at(j);
    cout << "vector::at() " << clock()-ticks <<endl;

    deque<int> di(sz);
    ticks = clock();
    for(int i3 = 0; i3 < count; i3++)
        for(int j = 0; j < sz; j++)
            di[j];
    cout << "deque[] " << clock() - ticks << endl;

    ticks = clock();
    for(int i4 = 0; i4 < count; i4++)
        for(int j = 0; j < sz; j++)
            di.at(j);
    cout << "deque::at() " << clock()-ticks <<endl;

    try
    {
        di.at(vi.size() + 1);
    } catch(...) { //捕捉所有异常
        cerr << "Exception thrown" << endl;
    }
    return 0;
}