- 浏览: 508711 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
jkxydp:
算法运行的结果根本就不对。
BM算法. -
soarwindzhang:
感谢博主的分享,我今天看了您的UFSET非递归的路径压缩时感觉 ...
并查集 -
zhangning290:
楼主好像只考虑了坏字符规则,。没有考虑好后缀
BM算法. -
lsm0622:
文字描述有错误 误导新学者
求有向图的强连通分量(scc):Tarjan算法 -
knightchen:
博主,你太强了!这篇文章对我学习C++多线程很有帮助!谢谢
并发学习之一_windows下ZThread在CodeBlocks上的安装与配置
1,deque特点:
(1)将元素放在多个连续的存储块.
(2)允许在序列两端快速地插入元素,并且在扩展存储区的时候不需要拷贝和析构原来的对象.
(3)deque支持随机访问[],但是速度没有vector快.
2,deque和vector的区别:微不足道.
deque有接口push_front()和pop_front(),而vector没有.
3,序列容器间的转换
4,
5,at比索引操作符[]代价更大.
(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; }
发表评论
-
关于priority_queue
2010-06-18 15:11 36201,关于STL中的priority_queue:确定用top( ... -
深入理解模板4
2010-03-15 12:28 8991,函数模板的半有序: 生成模板函数的时候,编译器将从这些模板 ... -
通用容器3_vector
2010-03-12 16:52 7861,vector特点: (1)将内容放在一段连续的存储区域,索 ... -
深入理解模板3
2010-03-12 09:57 7781,类模板和函数模板的 ... -
通用容器2
2010-03-11 11:15 6321,所有基本序列容器(vect ... -
深入理解模板2
2010-03-11 10:41 7271,typename关键字: (1)若一个模板代码内部的某个类 ... -
通用容器1
2010-03-10 12:19 7951,一个容器描述了一个持有其他对象的对象. 2,c++处理容器 ... -
深入理解模板1
2010-03-10 11:38 8801,模版参数可以有三种类型:(1)类型;(2)编译时常量;(3 ... -
设计模式之观察者模式
2010-03-04 11:54 8781,解决的问题: 当某些其他对象改变状态时,如果一组对象需要进 ... -
STL算法合集
2010-03-04 10:14 23681,简要描述迭代器的各种形式: (1)InputIterato ... -
通用算法之可调整的函数对象
2010-03-02 16:51 8741,实例代码: #include <algorith ... -
通用算法笔记4
2010-03-02 10:15 6031,generate_n(序列起点,个数,函数发生器) 2,t ... -
设计模式之构建器模式
2010-03-01 11:08 7191,目标:将对象的创建和它的表示法分开. 2,实例代码: ... -
设计模式之虚构造函数模式
2010-02-27 19:39 10901,虚构造函数模式:"现在还不知道需要什么类型的对象 ... -
设计模式之工厂模式
2010-02-22 23:26 786特征:封装对象的创建. 1,给一个对象添加新类型时,类的创建必 ... -
设计模式之职责链模式
2010-02-20 22:31 10741,职责链的本质:尝试多个解决方法,直到找到一个起作用的方法. ... -
设计模式之策略模式
2010-02-20 21:52 7301,策略(strategy)模式特征:运行时选择算法,可以用多 ... -
设计模式之模板方法模式
2010-02-20 21:41 7671,模板方法模式的重要特征:它的定义在基类中,并且不能改动. ... -
设计模式之代理模式和状态模式
2010-02-20 19:37 11351,代理(Proxy)模式基本思 ... -
设计模式之命令模式
2010-02-19 19:36 7071,命令(command)模式最大的特点:允许向一个函数或者对 ...
相关推荐
4. **set/multiset**:这些是关联容器,内部使用红黑树实现,存储的是排序的唯一元素(set)或重复元素(multiset)。查找、插入和删除的时间复杂度都是O(log n)。 5. **map/multimap**:与set类似,但每个元素都是...
4. **访问元素**:deque的元素可以通过下标访问,如`deque[索引]`,也可以通过迭代器访问。deque的迭代器提供了对元素的前向遍历。 5. **大小和容量**: - 获取deque的元素数量:`deque.size();` - 获取deque的...
STL中的通用算法是一系列独立于容器的函数,可以用于处理各种容器内的元素。常见的通用算法有: 1. `std::sort`:对容器内的元素进行排序。 2. `std::find`:查找容器中是否存在特定元素。 3. `std::count`:统计...
本文将详细介绍几种常见的顺序容器,包括`vector`、`string`、`list`、`forward_list`、`deque`以及`array`,并且探讨这些容器的初始化、赋值、大小调整、元素添加与删除等基本操作。 #### 二、顺序容器详解 ##### ...
本资源包含对STL中多种关键容器的详细讲解,包括Vector、Deque、sort、set、map等,这些都是C++程序员在实际开发中不可或缺的工具。 1. **Vector**:Vector是一个动态数组,它允许在任何位置插入和删除元素。其底层...
4. **deque**:deque(双端队列)是一种可以同时在两端进行插入和删除的容器,它提供了类似于vector的随机访问能力,但插入和删除效率通常高于vector,尤其是在容器的两端操作时。 5. **string**:string并不是传统...
这个名为"cpp_primer4_src"的压缩包文件,包含了该书配套的源代码,是学习和理解C++编程语言的一个宝贵资源。下面我们将对其中的知识点进行深入探讨。 1. **C++基础语法** - 变量与数据类型:包括基本类型(如int...
- 尽管可以尝试编写通用的代码,但不同容器有不同的性能特征和使用场景。例如,vector适合顺序访问,set适合快速查找,list适合频繁插入/删除。 3. **确保对象拷贝正确且高效**: - 如果容器包含对象而非指针,...
所有标准库容器都具有一定的通用功能。例如,它们都有默认构造函数来初始化容器,复制构造函数用于创建容器副本,析构函数用于释放内存。此外,还有一系列比较操作符如==、!=、<、>等,以及成员函数如empty、size、...
顺序容器按照元素在内存中的排列顺序来访问和操作这些元素,包括vector、deque、list、forward_list以及array和string。这些容器各自有不同的特点和性能表现。 **vector** 是一个可变大小的数组,支持快速的随机...
主要有四大类容器:顺序容器(如vector、deque、list)、关联容器(如set、map)、容器适配器(如stack、queue、priority_queue)以及未分类容器(如unordered_set、unordered_map)。这些容器各自有不同的特性和...
C++标准库中的容器提供了一系列通用的操作接口,使得学习和使用这些容器变得简单易懂。以下是所有容器共有的操作: - **Iterator**:迭代器允许开发者遍历容器中的元素。 - **Size**:返回容器中元素的数量。 - **...
STL,全称为Standard Template Library,是C++标准库的核心部分,它提供了一组高效、通用的容器、迭代器、算法和函数对象。在【STL源代码】中,我们可以深入学习并理解这些组件的实现细节,从而提高编程技能和效率。...
STL不仅提供容器,还有一系列通用算法,如`sort`, `find`, `copy`, `transform`等,这些算法可以作用于任何满足一定要求的序列上,极大提高了编程效率和代码的可读性。例如: - `sort`: 对容器进行排序。 - `find`: ...
尽管尝试编写通用代码是一种好习惯,但在C++中,不同容器的特点差异显著。因此,应该针对特定容器编写代码以利用其优势。 #### 三、确保容器中的对象拷贝正确而高效 - **拷贝机制**:了解容器如何处理对象拷贝非常...
vector和deque在插入元素到容器前端、插入元素到容器末端、删除容器前端元素这三种操作的接口上有所不同。 6. STL vector的capacity是指什么? 正确答案是(a) maximum number of elements the vector could ...
通过阅读源代码,你可以了解各种算法如何与容器和迭代器协同工作,以及如何实现通用性和效率。 5. **stl_rope.h, ropeimpl.h**:Rope是一种特殊的数据结构,用于高效处理大字符串的拼接和切分操作。它通过将字符串...
此外,`Collections`工具类提供了对容器的通用操作,如排序、翻转、填充等。`CopyOnWriteArrayList`和`CopyOnWriteArraySet`是线程安全的容器,适用于多线程环境,它们在读多写少的场景下表现优秀。 `Vector`类是...
4. deque(双端队列):可以高效地在两端进行插入和删除操作,但随机访问性能介于vector和list之间。它由多个固定大小的块组成,适合需要频繁在两端操作的场景。 5. set和multiset:这两种容器基于红黑树实现,用于...
1. **算法(algorithm)**:这个目录下的源代码包含了C++ STL中的各种通用算法,如排序、查找、交换、拷贝等。这些算法都是模板化的,能够适用于不同类型的容器,如vector、list或set。通过阅读这些源码,我们可以...