C++ Stack（堆栈） 是一个容器类的改编，为程序员提供了堆栈的全部功能，——也就是说实现了一个先进后出（FILO）的数据结构。
1.empty() 堆栈为空则返回真
2.pop() 移除栈顶元素
3.push() 在栈顶增加元素
4.size() 返回栈中元素数目
5.top() 返回栈顶元素
栈可以用向量(vector)、线性表(list)或双向队列(deque)来实现：
stack<vector<int>> s1;
stack<list<int> > s2;
stack<deque<int>> s3;
其成员函数有“判空(empty)” 、“尺寸(Size)” 、“栈顶元素(top)” 、“压栈(push)” 、“弹栈(pop)”等。
范例引自：
http://blog.csdn.net/morewindows/article/details/6950881
1 int main()
2 {
3 //可以使用list或vector作为栈的容器，默认是使用deque的。
4 stack<int, list<int>> a;
5 stack<int, vector<int>> b;
6 int i;
7
8 //压入数据
9 for (i = 0; i < 10; i++)
10 {
11 a.push(i);
12 b.push(i);
13 }
14
15 //栈的大小
16 printf("%d %d\n", a.size(), b.size());
17
18 //取栈项数据并将数据弹出栈
19 while (!a.empty())
20 {
21 printf("%d ", a.top());
22 a.pop();
23 }
24 putchar('\n');
25
26 while (!b.empty())
27 {
28 printf("%d ", b.top());
29 b.pop();
30 }
31 putchar('\n');
32 return 0;
33 }
34
posted @
2012-06-05 13:16 王海光 阅读(591) |
评论 (0) |
编辑 收藏
摘要: 本文转自：http://blog.csdn.net/wangji163163/article/details/3539756。GetLastError()返回值意义总结 〖0〗-操作成功完成。〖1〗-功能错误。〖2〗-系统找不到指定的文件。〖3〗-系统找不到指定的路径。〖4〗-系统无法打开文件。〖5〗-拒绝访问。〖6〗-句柄无效。〖7〗-存储控制块被损坏。〖8〗-存储空间不足，无法处理此命令。〖9〗-存储控制块地址无效。〖10〗-环境错误。
阅读全文
posted @
2012-06-05 10:58 王海光 阅读(456) |
评论 (0) |
编辑 收藏
集合(Set)是一种包含已排序对象的关联容器。多元集合(MultiSets)和集合(Sets)相像，只不过支持重复对象,其用法与set基本相同。
Set 又称集合，实际上就是一组元素的集合，但其中所包含的元素的值是唯一的，且是按一定顺序排列的，集合中的每个元素被称作集合中的实例。因为其内部是通过链表的方式来组织，所以在插入的时候比vector 快，但在查找和末尾添加上比vector 慢。
multiset 是多重集合，其实现方式和set 是相似的，只是它不要求集合中的元素是唯一的，也就是说集合中的同一个元素可以出现多次。
构造：
explicit set(const Compare&=compare());
如：set<int,less<int> > set1;
less<int>是一个标准类，用于形成升序排列函数对象。降序排列是用greater<int>。
Template<class InputIterator> set(InputIterator, InputIterator,\ const Compare&=compare());
如：set<int ,less<int> >set2(vector1.begin(),vector1.end());
通过指定某一预先定义的区间来初始化set对象的构造函数。
set（const set<Key,Compare&>）;
如：set<int ,less<int> >set3(set2);
方法：1.begin() 返回指向第一个元素的迭代器
2.clear() 清除所有元素
3.count() 返回某个值元素的个数
4.empty() 如果集合为空，返回true
5.end() 返回指向最后一个元素的迭代器
6.equal_range() 返回第一个>=关键字的迭代器和>关键字的迭代器
语法：
pair <iterator,iterator>equal_range( const key_type &key );
//key是用于排序的关键字
Set<int> ctr;
例如：
Pair<set<int>::iterator,set<int>::iterarot>p;
For(i=0;i<=5;i++) ctr.insert(i);
P=ctr.equal_range(2);
那么*p.first==2;*p.second==3;
7.erase() 删除集合中的元素
语法:
iterator erase( iterator i ); //删除i位置元素
iterator erase( iterator start, iterator end );
//删除从start开始到end(end为第一个不被删除的值)结束的元素
size_type erase( const key_type &key );
//删除等于key值的所有元素（返回被删除的元素的个数）
//前两个返回第一个不被删除的双向定位器,不存在返回末尾
//第三个返回删除个数
8.find() 返回一个指向被查找到元素的迭代器
语法:
iterator find( const key_type &key );
//查找等于key值的元素，并返回指向该元素的迭代器;
//如果没有找到,返回指向集合最后一个元素的迭代器
9.get_allocator() 返回集合的分配器
10.insert() 在集合中插入元素
语法:
iterator insert( iterator i, const TYPE &val ); //在迭代器i前插入val
void insert( input_iterator start, input_iterator end );
//将迭代器start开始到end（end不被插入）结束返回内的元素插入到集合中
pair insert( const TYPE &val );
//插入val元素，返回指向该元素的迭代器和一个布尔值来说明val是否成功被插入
//应该注意的是在集合(Sets中不能插入两个相同的元素)
11.lower_bound() 返回指向大于（或等于）某值的第一个元素的迭代器
语法:
iterator lower_bound( const key_type &key );
//返回一个指向大于或者等于key值的第一个元素的迭代器
12.key_comp() 返回一个用于元素间值比较的函数
语法:
key_compare key_comp();
//返回一个用于元素间值比较的函数对象
13.max_size() 返回集合能容纳的元素的最大限值
14.rbegin() 返回指向集合中最后一个元素的反向迭代器
示例：
Set<int> ctr;
Set<int>::reverse_iterator rcp;
For(rcp=ctr.rbegin();rcp!=ctr.rend();rcp++)
Cout<<*rcp<<” ”;
15.rend() 返回指向集合中第一个元素的反向迭代器
16.size() 集合中元素的数目
17.swap() 交换两个集合变量
语法:
void swap( set &object ); //交换当前集合和object集合中的元素
18.upper_bound() 返回大于某个值元素的迭代器
语法:
iterator upwer_bound( const key_type &key );
//返回一个指向大于key值的第一个元素的迭代器
19.value_comp() 返回一个用于比较元素间的值的函数
语法:
iterator upper_bound( const key_type &key );//返回一个用于比较元素间的值的函数对象
20.Set集合的并，交和差
set_union(a.begin(),a.end(),b.begin(),b.end(),insert_iterator<set<int> >(c,c.begin()));
set_intersection(a.begin(),a.end(),b.begin(),b.end(),insert_iterator<set<int> >(c,c.begin()));
set_difference(a.begin(),a.end(),b.begin(),b.end(),insert_iterator<set<int> >(c,c.begin()));
以下转自：
http://blog.csdn.net/wangji163163/article/details/3740948
Set是关联容器。其键值就是实值，实值就是键值，不可以有重复，所以我们不能通过set的迭代器来改变set的元素的值，set拥有和list相同的特性：当对他进行插入和删除操作的时候，操作之前的迭代器依然有效。当然删除了的那个就没效了。Set的底层结构是RB-tree，所以是有序的。
stl中特别提供了一种针对set的操作的算法：交集set_intersection，并集set_union，差集set_difference。对称差集set_symeetric_difference，这些算法稍后会讲到。
一：set模板类的声明。
1 template <
2 class Key,
3 class Traits=less<Key>,
4 class Allocator=allocator<Key>
5 >
6 class set。
其中个参数的意义如下：
key：要放入set里的数据类型，可以是任何类型的数据。
Traits：这是一个仿函数（关于仿函数是什么，我后面的文章会讲到）。提供了具有比较功能的仿函数，来觉得元素在set里的排列的顺序，这是一个可选的参数，默认的是std::less<key>，如果要自己提供这个参数，那么必须要遵循此规则：具有两个参数，返回类型为bool。
Allocator:空间配置器，这个参数是可选的，默认的是std::allocator<key>.
二：set里的基本操作
我们可以通过下面的方法来实例化一个set对象
std::set<int> s;那个s这个对象里面存贮的元素是从小到大排序的，(因为用std::less作为比较工具。)
如果要想在s里面插入数据，可以用inset函数（set没用重载[]操作，因为set本生的值和索引是相同的)
s.insert(3);s.insert(5).....
因为set是集合，那么集合本身就要求是唯一性，所以如果要像set里面插入数据和以前的数据有重合，那么插入不成功。
可以通过下面的方法来遍历set里面的元素
1 std::set<int>::iterator it = s.begin();
2 while(it!=s.end())
3 {
4 cout<<*it++<<endl;//迭代器依次后移，直到末尾。
5 }
如果要查找一个元素用find函数，it = s.find(3);这样it是指向3的那个元素的。可以通过rbegin，rend来逆向遍历
1 std::set<int>::reverse_iterator it = s.rbegin();
2
3 while(it!=s.rend())
4
5 {cout<<*it++<<endl;}
还有其他的一些操作在这就不一一列出了。
三：与set相关的一组算法
set_intersection() :这个函数是求两个集合的交集。下面是stl里的源代码
1 template<class _InIt1,
2 class _InIt2,
3 class _OutIt> inline
4 _OutIt set_intersection(_InIt1 _First1, _InIt1 _Last1,
5 _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
6 { // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
7 for (; _First1 != _Last1 && _First2 != _Last2; )
8 if (*_First1 < *_First2)
9 ++_First1;
10 else if (*_First2 < *_First1)
11 ++_First2;
12 else
13 *_Dest++ = *_First1++, ++_First2;
14 return (_Dest);
15 }
这是个模板函数，从上面的算法可以看出，传进去的两个容器必须是有序的。_Dest指向输出的容器，这个容器必须是预先分配好空间的，否则会出错的,返回值指向保存结果的容器的尾端的下一个位置。eg.
1 set_union() :求两个集合的并集，参数要求同上。
2
3 std::set_difference（）：差集
4
5 set_symmetric_difference（）：得到的结果是第一个迭代器相对于第二个的差集并上第二个相当于第一个的差集。代码：
6
7 struct compare
8 {
9 bool operator ()(string s1,string s2)
10 {
11 return s1>s2;
12 }///自定义一个仿函数
13 };
14 int main()
15 {
16 typedef std::set<string,compare> _SET;
17 _SET s;
18 s.insert(string("sfdsfd"));
19 s.insert(string("apple"));
20 s.insert(string("english"));
21 s.insert(string("dstd"));
22 cout<<"s1:"<<endl;
23 std::set<string,compare>::iterator it = s.begin();
24 while(it!=s.end())
25 cout<<*it++<<" ";
26 cout<<endl<<"s2:"<<endl;
27 _SET s2;
28 s2.insert(string("abc"));
29 s2.insert(string("apple"));
30 s2.insert(string("english"));
31 it = s2.begin();
32 while(it!=s2.end())
33 cout<<*it++<<" ";
34 cout<<endl<<endl;
35
36 string str[10];
37 string *end = set_intersection(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//求交集，返回值指向str最后一个元素的尾端
38 cout<<"result of set_intersection s1,s2:"<<endl;
39 string *first = str;
40 while(first<end)
41 cout <<*first++<<" ";
42 cout<<endl<<endl<<"result of set_union of s1,s2"<<endl;
43 end = std::set_union(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//并集
44 first = str;
45 while(first<end)
46 cout <<*first++<<" ";
47 cout<<endl<<endl<<"result of set_difference of s2 relative to s1"<<endl;
48 first = str;
49 end = std::set_difference(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//s2相对于s1的差集
50 while(first<end)
51 cout <<*first++<<" ";
52 cout<<endl<<endl<<"result of set_difference of s1 relative to s2"<<endl;
53 first = str;
54 end = std::set_difference(s2.begin(),s2.end(),s.begin(),s.end(),str,compare());//s1相对于s2的差集
55
56 while(first<end)
57 cout <<*first++<<" ";
58 cout<<endl<<endl;
59 first = str;
60 end = std::set_symmetric_difference(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//上面两个差集的并集
61 while(first<end)
62 cout <<*first++<<" ";
63 cout<<endl;
64 }
65
66 set<int> s3 ;
67 set<int>::iterator iter = s3.begin() ;
68 set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(s3,iter));
69 copy(s3.begin(),s3.end(), ostream_iterator<int>(cout," "));
posted @
2012-06-05 10:51 王海光 阅读(1146) |
评论 (0) |
编辑 收藏
摘要: C++ Maps & MultiMapsC++ Maps是一种关联式容器，包含“关键字/值”对。
C++ Multimaps和maps很相似，但是MultiMaps允许重复的元素。
1.begin() 返回指向map头部的迭代器
2.clear() 删除所有元素
3.count() 返回指定元素出现的次数
语法...
阅读全文
posted @
2012-06-04 16:57 王海光 阅读(1813) |
评论 (0) |
编辑 收藏C++ Deque(双向队列)
是一种优化了的、对序列两端元素进行添加和删除操作的基本序列容器。它允许较为快速地随机访问，但它不像vector 把所有的对象保存在一块连续的内存块，而是采用多个连续的存储块，并且在一个映射结构中保存对这些块及其顺序的跟踪。向deque 两端添加或删除元素的开销很小。它不需要重新分配空间，所以向末端增加元素比vector 更有效。
实际上，deque 是对vector 和list 优缺点的结合，它是处于两者之间的一种容器。
Deque 的特点：
(1) 随机访问方便，即支持[ ] 操作符和vector.at() ，但性能没有vector 好；
(2) 可以在内部进行插入和删除操作，但性能不及list ；
(3) 可以在两端进行push 、pop ；
(4) 相对于verctor 占用更多的内存。
双向队列和向量很相似，但是它允许在容器头部快速插入和删除（就像在尾部一样）。
1.Constructors 创建一个新双向队列
语法:
deque();//创建一个空双向队列
deque( size_type size );// 创建一个大小为size的双向队列
deque( size_type num, const TYPE &val ); //放置num个val的拷贝到队列中
deque( const deque &from );// 从from创建一个内容一样的双向队列
deque( input_iterator start, input_iterator end );
// start 和 end - 创建一个队列，保存从start到end的元素。
2.Operators 比较和赋值双向队列
//可以使用[]操作符访问双向队列中单个的元素
3.assign() 设置双向队列的值
语法:
void assign( input_iterator start, input_iterator end);
//start和end指示的范围为双向队列赋值
void assign( Size num, const TYPE &val );//设置成num个val。
4.at() 返回指定的元素
语法:
reference at( size_type pos ); 返回一个引用，指向双向队列中位置pos上的元素
5.back() 返回最后一个元素
语法:
reference back();//返回一个引用，指向双向队列中最后一个元素
6.begin() 返回指向第一个元素的迭代器
语法:
iterator begin();//返回一个迭代器，指向双向队列的第一个元素
7.clear() 删除所有元素
8.empty() 返回真如果双向队列为空
9.end() 返回指向尾部的迭代器
10.erase() 删除一个元素
语法:
iterator erase( iterator pos ); //删除pos位置上的元素
iterator erase( iterator start, iterator end ); //删除start和end之间的所有元素
//返回指向被删除元素的后一个元素
11.front() 返回第一个元素的引用
12.get_allocator() 返回双向队列的配置器
13.insert() 插入一个元素到双向队列中
语法:
iterator insert( iterator pos, size_type num, const TYPE &val ); //pos前插入num个val值
void insert( iterator pos, input_iterator start, input_iterator end );
//插入从start到end范围内的元素到pos前面
14.max_size() 返回双向队列能容纳的最大元素个数
15.pop_back() 删除尾部的元素
16.pop_front() 删除头部的元素
17.push_back() 在尾部加入一个元素
18.push_front() 在头部加入一个元素
19.rbegin() 返回指向尾部的逆向迭代器
20.rend() 返回指向头部的逆向迭代器
21.resize() 改变双向队列的大小
22.size() 返回双向队列中元素的个数
23.swap() 和另一个双向队列交换元素
语法：
void swap( deque &target );// 交换target和现双向队列中元素
posted @
2012-06-04 15:57 王海光 阅读(22750) |
评论 (1) |
编辑 收藏
摘要: List(双向链表)介绍: List是一个线性链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。
&nbs...
阅读全文
posted @
2012-06-04 15:50 王海光 阅读(4075) |
评论 (0) |
编辑 收藏
C++ Vector（向量容器）
是一个线性顺序结构。相当于数组，但其大小可以不预先指定，并且自动扩展。它可以像数组一样被操作，由于它的特性我们完全可以将vector 看作动态数组。
在创建一个vector 后，它会自动在内存中分配一块连续的内存空间进行数据存储，初始的空间大小可以预先指定也可以由vector 默认指定，这个大小即capacity （）函数的返回值。当存储的数据超过分配的空间时vector 会重新分配一块内存块，但这样的分配是很耗时的，在重新分配空间时它会做这样的动作：
首先，vector 会申请一块更大的内存块；
然后，将原来的数据拷贝到新的内存块中；
其次，销毁掉原内存块中的对象（调用对象的析构函数）；
最后，将原来的内存空间释放掉。
如果vector 保存的数据量很大时，这样的操作一定会导致糟糕的性能（这也是vector 被设计成比较容易拷贝的值类型的原因）。所以说vector 不是在什么情况下性能都好，只有在预先知道它大小的情况下vector 的性能才是最优的。
vector 的特点：
(1) 指定一块如同数组一样的连续存储，但空间可以动态扩展。即它可以像数组一样操作，并且可以进行动态操作。通常体现在push_back() pop_back() 。
(2) 随机访问方便，它像数组一样被访问，即支持[ ] 操作符和vector.at()
(3) 节省空间，因为它是连续存储，在存储数据的区域都是没有被浪费的，但是要明确一点vector 大多情况下并不是满存的，在未存储的区域实际是浪费的。
(4) 在内部进行插入、删除操作效率非常低，这样的操作基本上是被禁止的。Vector 被设计成只能在后端进行追加和删除操作，其原因是vector 内部的实现是按照顺序表的原理。
(5) 只能在vector 的最后进行push 和pop ，不能在vector 的头进行push 和pop 。
(6) 当动态添加的数据超过vector 默认分配的大小时要进行内存的重新分配、拷贝与释放，这个操作非常消耗性能。 所以要vector 达到最优的性能，最好在创建vector 时就指定其空间大小。
Vectors 包含着一系列连续存储的元素,其行为和数组类似。访问Vector中的任意元素或从末尾添加元素都可以在常量级时间复杂度内完成，而查找特定值的元素所处的位置或是在Vector中插入元素则是线性时间复杂度。
1.Constructors 构造函数
vector<int> v1; //构造一个空的vector
vector<int> v1( 5, 42 ); //构造了一个包含5个值为42的元素的Vector
2.Operators 对vector进行赋值或比较
C++ Vectors能够使用标准运算符: ==, !=, <=, >=, <, 和 >.
要访问vector中的某特定位置的元素可以使用 [] 操作符.
两个vectors被认为是相等的,如果:
1.它们具有相同的容量
2.所有相同位置的元素相等.
vectors之间大小的比较是按照词典规则.
3.assign() 对Vector中的元素赋值
语法：
void assign( input_iterator start, input_iterator end );
// 将区间[start, end)的元素赋到当前vector
void assign( size_type num, const TYPE &val );
// 赋num个值为val的元素到vector中,这个函数将会清除掉为vector赋值以前的内容。
4.at() 返回指定位置的元素
语法：
TYPE at( size_type loc );//差不多等同v[i];但比v[i]安全;
5.back() 返回最末一个元素
6.begin() 返回第一个元素的迭代器
7.capacity() 返回vector所能容纳的元素数量(在不重新分配内存的情况下）
8.clear() 清空所有元素
9.empty() 判断Vector是否为空（返回true时为空）
10.end() 返回最末元素的迭代器(译注:实指向最末元素的下一个位置)
11.erase() 删除指定元素
语法：
iterator erase( iterator loc );//删除loc处的元素
iterator erase( iterator start, iterator end );//删除start和end之间的元素
12.front() 返回第一个元素的引用
13.get_allocator() 返回vector的内存分配器
14.insert() 插入元素到Vector中
语法：
iterator insert( iterator loc, const TYPE &val );
//在指定位置loc前插入值为val的元素,返回指向这个元素的迭代器,
void insert( iterator loc, size_type num, const TYPE &val );
//在指定位置loc前插入num个值为val的元素
void insert( iterator loc, input_iterator start, input_iterator end );
//在指定位置loc前插入区间[start, end)的所有元素
15.max_size() 返回Vector所能容纳元素的最大数量（上限）
16.pop_back() 移除最后一个元素
17.push_back() 在Vector最后添加一个元素
18.rbegin() 返回Vector尾部的逆迭代器
19.rend() 返回Vector起始的逆迭代器
20.reserve() 设置Vector最小的元素容纳数量
//为当前vector预留至少共容纳size个元素的空间
21.resize() 改变Vector元素数量的大小
语法:
void resize( size_type size, TYPE val );
//改变当前vector的大小为size,且对新创建的元素赋值val
22.size() 返回Vector元素数量的大小
23.swap() 交换两个Vector
语法：
void swap( vector &from );
Vector用法 ：
1.声明：
一个vector类似于一个动态的一维数组。
vector<int> a; //声明一个元素为int类型的vector a
vectot<MyType> a; //声明一个元素为MyType类型的vector a
这里的声明的a包含0个元素，既a.size()的值为0，但它是动态的，其大小会随着数据的插入和删除改变而改变。
vector<int> a(100, 0); //这里声明的是一个已经存放了100个0的整数vector
你可以用以下的几种方法声明一个 vector 对象：
vector<float> v(5, 3.25); //初始化有5 个元素，其值都是3.25
vector<float> v_new1(v);
vector<float> v_new2 = v;
vector<float> v_new3(v.begin(), v.end());
这四个vector 对象是相等的，可以用operator==来判断。
2.向量操作
常用函数：
size_t size(); // 返回vector的大小，即包含的元素个数
void pop_back(); // 删除vector末尾的元素，vector大小相应减一
void push_back(); //用于在vector的末尾添加元素
T back(); // 返回vector末尾的元素
void clear(); // 将vector清空，vector大小变为0
其他访问方式：
cout<<a[5]<<endl;
cout<<a.at(5)<<endl;
以上区别在于后者在访问越界时会抛出异常，而前者不会。
3.遍历
(1). for(vector<datatype>::iterator it=a.begin(); it!=a.end();it++)
cout<<*it<<endl;
(2). for(int i=0;i<a.size;i++)
cout<<a[i]<<endl;
现在想得到容器中能保存的最大元素数量就可以用 vector 类的成员函数max_size()：
vector<shape>::size_type max_size = my_shapes.max_size();
当前容器的实际尺寸 --- 已有的元素个数用size()：
vector<shape>::size_type size = my_shapes.size();
就像size_type 描述了vector 尺寸的类型，value_type 说明了其中保存的对象的类型：
cout << “value type: “ << typeid(vector<float>::value_type).name();
输出：
value type: float
可以用capacity()来取得vector 中已分配内存的元素个数：
vector<int> v;
vector<int>::size_type capacity = v.capacity();
vector 类似于数组，可以使用下标[]访问：
vector<int> v(10);
v[0] = 101;
注意到这里预先给10 个元素分配了空间。你也可以使用vector 提供的插入函数来动态的扩
展容器。成员函数push_back()就在vector 的尾部添加了一个元素：
v.push_back(3);
也可以用insert()函数完成同样的工作：
v.insert(v.end(), 3);
这里insert()成员函数需要两个参数：一个指向容器中指定位置的迭代器(iterator)，一个待插
入的元素。insert()将元素插入到迭代器指定元素之前。
现在对迭代器(Iterator)做点解释。Iterator 是指针(pointer)的泛化，iterator 要求定义
operator*，它返回指定类型的值。Iterator 常常和容器联系在一起。例子：
vector<int> v(3);
v[0] = 5;
v[1] = 2;
v[2] = 7;
vector<int>::iterator first = v.begin();
vector<int>::iterator last = v.end();
while (first != last)
cout << *first++ << “ “;
上面代码的输出是：
5 2 7
begin()返回的是vector 中第一个元素的iterator，而end()返回的并不是最后一个元素的
iterator，而是past the last element。在STL 中叫past-the-end iterator。
组合查找
vector<int>::iterator result = find( v.begin( ), v.end( ), 2 ); //查找2
if ( result == v.end( ) ) //没找到
cout << "No" << endl;
else //找到
cout << "Yes" << endl;
posted @
2012-06-04 09:18 王海光 阅读(10994) |
评论 (0) |
编辑 收藏
STL介绍
C++ STL (Standard Template Library标准模板库) 是通用类模板和算法的集合，它提供给程序员一些标准的数据结构的实现如 queues(队列), lists(链表), 和 stacks(栈)等. 该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。提供了一个可扩展的应用框架，高度体现了软件的可复用性。从逻辑层次来看，在STL中体现了泛型化程序设计的思想（generic programming），引入了诸多新的名词，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。与OOP（object-oriented programming）中的多态（polymorphism）一样，泛型也是一种软件的复用技术。
从实现层次看，整个STL是以一种类型参数化（type parameterized）的方式实现的，这种方式基于一个在早先C++标准中没有出现的语言特性--模板（template）。
C++ STL 提供给程序员以下三类数据结构的实现：
标准容器类
顺序性容器
vector 从后面快速的插入与删除，直接访问任何元素
deque 从前面或后面快速的插入与删除，直接访问任何元素
list 双链表，从任何地方快速插入与删除
三者比较：
vector 是一段连续的内存块，而deque 是多个连续的内存块， list 是所有数据元素分开保存，可以是任何两个元素没有连续。vector 的查询性能最好，并且在末端增加数据也很好，除非它重新申请内存段；适合高效地随机存储。list 是一个链表，任何一个元素都可以是不连续的，但它都有两个指向上一元素和下一元素的指针。所以它对插入、删除元素性能是最好的，而查询性能非常差；适合大量地插入和删除操作而不关心随机存取的需求。deque 是介于两者之间，它兼顾了数组和链表的优点，它是分块的链表和多个数组的联合。所以它有被list好的查询性能，有被vector好的插入、删除性能。 如果你需要随即存取又关心两端数据的插入和删除，那么deque是最佳之选。
关联容器
set 快速查找，不允许重复值
multiset 快速查找，允许重复值
map 一对多映射，基于关键字快速查找，不允许重复值
multimap 一对多映射，基于关键字快速查找，允许重复值
关联容器(Associative Container)提供了快速检索基于关键词(Key)的数据的能力。和序列容器(vector、list、deque)一样，关联容器用来存储数据，而且设计关联容器时考虑到了优化数据检索的意图 --- 通过关键词(Key)作为标识把单一的数据记录组织到特定的结构中(如tree)。STL 提供了不同的关联容器：集合(set)、多元集合(multiset)、映射(map)、多元映射(multimap)。set 和map 支持唯一关键词(unique key)，就是对每个KEY，最多只保存一个元素(数据
记录)。multiset 和multimap 则支持相同关键词(equal key)，这样可有很多个元素可以用同一个KEY 进行存储。set(multiset)和map(multimap)之间的区别在于set(multiset)中的存储数据内含了KEY 表达式；而map(multimap)则将Key 表达式和对应的数据分开存放。
容器适配器
stack 后进先出
queue 先进先出
priority_queue 最高优先级元素总是第一个出列
STL 中包含三种适配器：栈stack 、队列queue 和优先级priority_queue 。适配器是容器的接口，它本身不能直接保存元素，它保存元素的机制是调用另一种顺序容器去实现，即可以把适配器看作“它保存一个容器，这个容器再保存所有元素”。
STL 中提供的三种适配器可以由某一种顺序容器去实现。默认下stack 和queue 基于deque 容器实现，priority_queue 则基于vector 容器实现。当然在创建一个适配器时也可以指定具体的实现容器，创建适配器时在第二个参数上指定具体的顺序容器可以覆盖适配器的默认实现。由于适配器的特点，一个适配器不是可以由任一个顺序容器都可以实现的。
栈stack 的特点是后进先出，所以它关联的基本容器可以是任意一种顺序容器，因为这些容器类型结构都可以提供栈的操作有求，它们都提供了push_back 、pop_back 和back 操作。
队列queue 的特点是先进先出，适配器要求其关联的基础容器必须提供pop_front 操作，因此其不能建立在vector 容器上。
posted @
2012-06-04 08:52 王海光 阅读(881) |
评论 (0) |
编辑 收藏
摘要: 本文转自：http://www.cnblogs.com/zqrferrari/archive/2010/07/07/1773113.html
一、MFC对多线程编程的支持
MFC中有两类线程，分别称之为工作者线程和用户界面线程。二者的主要区别在于工作者线程没有消息循环，而用户界面线程有自己的消息队列和消息循环。 工作者线程没有消息机制，通常用来执行后台计算和维护任务，如冗长的计算过程...
阅读全文
posted @
2012-05-31 14:34 王海光 阅读(3047) |
评论 (1) |
编辑 收藏本文转自：
http://www.cnblogs.com/jillzhang/archive/2006/11/02/547679.html
哈希表和哈希函数是大学数据结构中的课程，实际开发中我们经常用到Hashtable这种结构，当遇到键-值对存储，采用Hashtable比ArrayList查找的性能高。为什么呢？我们在享受高性能的同时，需要付出什么代价(这几天看红顶商人胡雪岩，经典台词：在你享受这之前，必须受别人吃不了的苦，忍受别人受不了的屈辱)，那么使用Hashtable是否就是一桩无本万利的买卖呢？就此疑问，做以下分析，希望能抛砖引玉。
1)hash它为什么对于键-值查找性能高
学过数据结构的，都应该晓得，线性表和树中，记录在结构中的相对位置是随机的，记录和关键字之间不存在明确的关系，因此在查找记录的时候，需要进行一系列的关键字比较，这种查找方式建立在比较的基础之上，在.net中(Array,ArrayList,List)这些集合结构采用了上面的存储方式。
比如，现在我们有一个班同学的数据，包括姓名，性别，年龄，学号等。假如数据有
| 姓名 |
性别 |
年龄 |
学号 |
| 张三 |
男 |
15 |
1 |
| 李四 |
女 |
14 |
2 |
| 王五 |
男 |
14 |
3 |
假如，我们按照姓名来查找，假设查找函数FindByName(string name);
1)查找“张三”
只需在第一行匹配一次。
2)查找"王五"
在第一行匹配，失败，
在第二行匹配，失败，
在第三行匹配，成功
上面两种情况，分别分析了最好的情况，和最坏的情况，那么平均查找次数应该为 (1+3)/2=2次，即平均查找次数为(记录总数+1)的1/2。
尽管有一些优化的算法，可以使查找排序效率增高，但是复杂度会保持在log2n的范围之内。
如何更更快的进行查找呢？我们所期望的效果是一下子就定位到要找记录的位置之上，这时候时间复杂度为1，查找最快。如果我们事先为每条记录编一个序号，然后让他们按号入位，我们又知道按照什么规则对这些记录进行编号的话，如果我们再次查找某个记录的时候，只需要先通过规则计算出该记录的编号，然后根据编号，在记录的线性队列中，就可以轻易的找到记录了 。
注意，上述的描述包含了两个概念，一个是用于对学生进行编号的规则，在数据结构中，称之为哈希函数，另外一个是按照规则为学生排列的顺序结构，称之为哈希表。
仍以上面的学生为例，假设学号就是规则，老师手上有一个规则表，在排座位的时候也按照这个规则来排序，查找李四，首先该教师会根据规则判断出，李四的编号为2，就是在座位中的2号位置，直接走过去，“李四，哈哈，你小子，就是在这！”
看看大体流程:
从上面的图中，可以看出哈希表可以描述为两个筒子，一个筒子用来装记录的位置编号，另外一个筒子用来装记录，另外存在一套规则，用来表述记录与编号之间的联系。这个规则通常是如何制定的呢？
a)直接定址法:
我在前一篇文章对GetHashCode()性能比较的问题中谈到，对于整形的数据GetHashCode()函数返回的就是整形 本身，其实就是基于直接定址的方法，比如有一组0-100的数据，用来表示人的年龄
那么，采用直接定址的方法构成的哈希表为:
| 0 |
1 |
2 |
3 |
4 |
5 |
| 0岁 |
１岁 |
２岁 |
３岁 |
４岁 |
５岁 |
.....
这样的一种定址方式，简单方便，适用于元数据能够用数字表述或者原数据具有鲜明顺序关系的情形。
b)数字分析法:
有这样一组数据，用于表述一些人的出生日期
| 年 |
月 |
日 |
| ７５ |
１０ |
１ |
| ７５ |
１２ |
１０ |
| ７５ |
０２ |
１４ |
分析一下，年和月的第一位数字基本相同，造成冲突的几率非常大，而后面三位差别比较大，所以采用后三位
c)平方取中法
取关键字平方后的中间几位作为哈希地址
d) 折叠法：
将关键字分割成位数相同的几部分，最后一部分位数可以不相同，然后去这几部分的叠加和（取出进位）作为哈希地址，比如有这样的数据20-1445-4547-3
可以
5473
+ 4454
+ 201
= 10128
取出进位1,取0128为哈希地址
e)取余法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。H(key)=key MOD p (p<=m)
f) 随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。
总之，哈希函数的规则是：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中。越分散，则以后查找的时间复杂度越小，空间复杂度越高。
２)使用hash，我们付出了什么？
hash是一种典型以空间换时间的算法，比如原来一个长度为100的数组，对其查找，只需要遍历且匹配相应记录即可，从空间复杂度上来看，假如数组存储的是byte类型数据，那么该数组占用100byte空间。现在我们采用hash算法，我们前面说的hash必须有一个规则，约束键与存储位置的关系，那么就需要一个固定长度的hash表，此时，仍然是100byte的数组，假设我们需要的100byte用来记录键与位置的关系，那么总的空间为200byte,而且用于记录规则的表大小会根据规则，大小可能是不定的，比如在lzw算法中，如果一个很长的用于记录像素的byte数组，用来记录位置与键关系的表空间，算法推荐为一个1２bit能表述的整数大小，那么足够长的像素数组，如何分散到这样定长的表中呢，lzw算法采用的是可变长编码，具体会在深入介绍lzw算法的时候介绍。
注:hash表最突出的问题在于冲突，就是两个键值经过哈希函数计算出来的索引位置很可能相同，这个问题，下篇文章会令作阐述。
注:之所以会简单得介绍了hash，是为了更好的学习lzw算法，学习lzw算法是为了更好的研究gif文件结构，最后，我将详细的阐述一下gif文件是如何构成的，如何高效操作此种类型文件。
HASH如何处理冲突：
1)冲突是如何产生的？
上文中谈到，哈希函数是指如何对关键字进行编址的规则，这里的关键字的范围很广，可视为无限集，如何保证无限集的原数据在编址的时候不会出现重复呢？规则本身无法实现这个目的。举一个例子，仍然用班级同学做比喻，现有如下同学数据
张三，李四，王五，赵刚，吴露.....
假如我们编址规则为取姓氏中姓的开头字母在字母表的相对位置作为地址，则会产生如下的哈希表
...
...
..
我们注意到，灰色背景标示的两行里面，关键字王五，吴露被编到了同一个位置，关键字张三，赵刚也被编到了同一个位置。老师再拿号来找张三，座位上有两个人，"你们俩谁是张三？"
2)如何解决冲突问题
既然不能避免冲突，那么如何解决冲突呢，显然需要附加的步骤。通过这些步骤，以制定更多的规则来管理关键字集合，通常的办法有:
a)开放地址法开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,...m-1，称线性探测再散列。
如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。仍然以学生排号作为例子，
现有两名同学，李四，吴用。李四与吴用事先已排好序，现新来一名同学，名字叫王五，对它进行编制
| 10.. |
.... |
22 |
.. |
.. |
25 |
| 李四.. |
.... |
吴用 |
.. |
.. |
25 |
赵刚未来之前
| 10.. |
.. |
22 |
23 |
25 |
| 李四.. |
|
吴用 |
王五 |
|
(a)线性探测再散列对赵刚进行编址，且di=1
| 10... |
20 |
22 |
.. |
25 |
| 李四.. |
王五 |
吴用 |
|
|
(b)二次探测再散列，且di=-2
| 1... |
10... |
22 |
.. |
25 |
| 王五.. |
李四.. |
吴用 |
|
|
(c)伪随机探测再散列,伪随机序列为:5,3,2 b)再哈希法 当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止
c)链地址法
将所有关键字为同义词的记录存储在同一线性链表中。如下：
因此这种方法，可以近似的认为是筒子里面套筒子
d.建立一个公共溢出区假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。
经过以上方法，基本可以解决掉hash算法冲突的问题。
posted @
2012-05-28 15:54 王海光 阅读(1308) |
评论 (0) |
编辑 收藏