`
kmplayer
  • 浏览: 508711 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

通用容器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;
}
分享到:
评论

相关推荐

    cPP.rar_c++ 容器使用_容器

    4. **set/multiset**:这些是关联容器,内部使用红黑树实现,存储的是排序的唯一元素(set)或重复元素(multiset)。查找、插入和删除的时间复杂度都是O(log n)。 5. **map/multimap**:与set类似,但每个元素都是...

    每天学点C++(C++实例教程:教程+源码)01deque容器.zip

    4. **访问元素**:deque的元素可以通过下标访问,如`deque[索引]`,也可以通过迭代器访问。deque的迭代器提供了对元素的前向遍历。 5. **大小和容量**: - 获取deque的元素数量:`deque.size();` - 获取deque的...

    容器通用算法和迭代器

    STL中的通用算法是一系列独立于容器的函数,可以用于处理各种容器内的元素。常见的通用算法有: 1. `std::sort`:对容器内的元素进行排序。 2. `std::find`:查找容器中是否存在特定元素。 3. `std::count`:统计...

    C++顺序容器,容器适配器,关联容器的操作

    本文将详细介绍几种常见的顺序容器,包括`vector`、`string`、`list`、`forward_list`、`deque`以及`array`,并且探讨这些容器的初始化、赋值、大小调整、元素添加与删除等基本操作。 #### 二、顺序容器详解 ##### ...

    STL容器 内容全,讲解详细 包括Vector、Deque、sort、set、map等

    本资源包含对STL中多种关键容器的详细讲解,包括Vector、Deque、sort、set、map等,这些都是C++程序员在实际开发中不可或缺的工具。 1. **Vector**:Vector是一个动态数组,它允许在任何位置插入和删除元素。其底层...

    标准库STL_第1节_顺序容器

    4. **deque**:deque(双端队列)是一种可以同时在两端进行插入和删除的容器,它提供了类似于vector的随机访问能力,但插入和删除效率通常高于vector,尤其是在容器的两端操作时。 5. **string**:string并不是传统...

    cpp_primer4_src

    这个名为"cpp_primer4_src"的压缩包文件,包含了该书配套的源代码,是学习和理解C++编程语言的一个宝贵资源。下面我们将对其中的知识点进行深入探讨。 1. **C++基础语法** - 变量与数据类型:包括基本类型(如int...

    使用经验总结(c++容器)

    - 尽管可以尝试编写通用的代码,但不同容器有不同的性能特征和使用场景。例如,vector适合顺序访问,set适合快速查找,list适合频繁插入/删除。 3. **确保对象拷贝正确且高效**: - 如果容器包含对象而非指针,...

    C++容器类的简单介绍.doc

    所有标准库容器都具有一定的通用功能。例如,它们都有默认构造函数来初始化容器,复制构造函数用于创建容器副本,析构函数用于释放内存。此外,还有一系列比较操作符如==、!=、&lt;、&gt;等,以及成员函数如empty、size、...

    第9章 顺序容器1

    顺序容器按照元素在内存中的排列顺序来访问和操作这些元素,包括vector、deque、list、forward_list以及array和string。这些容器各自有不同的特点和性能表现。 **vector** 是一个可变大小的数组,支持快速的随机...

    c++STL容器讲义与演示

    主要有四大类容器:顺序容器(如vector、deque、list)、关联容器(如set、map)、容器适配器(如stack、queue、priority_queue)以及未分类容器(如unordered_set、unordered_map)。这些容器各自有不同的特性和...

    《C++ Primer》学习笔记(27)顺序容器

    C++标准库中的容器提供了一系列通用的操作接口,使得学习和使用这些容器变得简单易懂。以下是所有容器共有的操作: - **Iterator**:迭代器允许开发者遍历容器中的元素。 - **Size**:返回容器中元素的数量。 - **...

    【STL源代码】C++标准库STL源代码下载

    STL,全称为Standard Template Library,是C++标准库的核心部分,它提供了一组高效、通用的容器、迭代器、算法和函数对象。在【STL源代码】中,我们可以深入学习并理解这些组件的实现细节,从而提高编程技能和效率。...

    STL容器和算法函数表

    STL不仅提供容器,还有一系列通用算法,如`sort`, `find`, `copy`, `transform`等,这些算法可以作用于任何满足一定要求的序列上,极大提高了编程效率和代码的可读性。例如: - `sort`: 对容器进行排序。 - `find`: ...

    c++容器使用经验总结.docx

    尽管尝试编写通用代码是一种好习惯,但在C++中,不同容器的特点差异显著。因此,应该针对特定容器编写代码以利用其优势。 #### 三、确保容器中的对象拷贝正确而高效 - **拷贝机制**:了解容器如何处理对象拷贝非常...

    ssd5 multiple choice4

    vector和deque在插入元素到容器前端、插入元素到容器末端、删除容器前端元素这三种操作的接口上有所不同。 6. STL vector的capacity是指什么? 正确答案是(a) maximum number of elements the vector could ...

    C++ STL库源代码(SGI版本)

    通过阅读源代码,你可以了解各种算法如何与容器和迭代器协同工作,以及如何实现通用性和效率。 5. **stl_rope.h, ropeimpl.h**:Rope是一种特殊的数据结构,用于高效处理大字符串的拼接和切分操作。它通过将字符串...

    JAVA 容器类应用

    此外,`Collections`工具类提供了对容器的通用操作,如排序、翻转、填充等。`CopyOnWriteArrayList`和`CopyOnWriteArraySet`是线程安全的容器,适用于多线程环境,它们在读多写少的场景下表现优秀。 `Vector`类是...

    STL容器(一)(附件STL帮助手册)

    4. deque(双端队列):可以高效地在两端进行插入和删除操作,但随机访问性能介于vector和list之间。它由多个固定大小的块组成,适合需要频繁在两端操作的场景。 5. set和multiset:这两种容器基于红黑树实现,用于...

    STL3.0源码

    1. **算法(algorithm)**:这个目录下的源代码包含了C++ STL中的各种通用算法,如排序、查找、交换、拷贝等。这些算法都是模板化的,能够适用于不同类型的容器,如vector、list或set。通过阅读这些源码,我们可以...

Global site tag (gtag.js) - Google Analytics