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 王海光 閱讀(628) |
評論 (0) |
編輯 收藏
摘要: 本文轉自：http://blog.csdn.net/wangji163163/article/details/3539756。GetLastError()返回值意義總結 〖0〗-操作成功完成。〖1〗-功能錯誤?！?〗-系統找不到指定的文件?！?〗-系統找不到指定的路徑?！?〗-系統無法打開文件。〖5〗-拒絕訪問?！?〗-句柄無效。〖7〗-存儲控制塊被損壞?！?〗-存儲空間不足，無法處理此命令?！?〗-存儲控制塊地址無效?！?0〗-環境錯誤。
閱讀全文
posted @
2012-06-05 10:58 王海光 閱讀(468) |
評論 (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 王海光 閱讀(1199) |
評論 (0) |
編輯 收藏
摘要: C++ Maps & MultiMapsC++ Maps是一種關聯式容器，包含“關鍵字/值”對。
C++ Multimaps和maps很相似，但是MultiMaps允許重復的元素。
1.begin() 返回指向map頭部的迭代器
2.clear() 刪除所有元素
3.count() 返回指定元素出現的次數
語法...
閱讀全文
posted @
2012-06-04 16:57 王海光 閱讀(1858) |
評論 (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 王海光 閱讀(22840) |
評論 (1) |
編輯 收藏
摘要: List(雙向鏈表)介紹: List是一個線性鏈表結構，它的數據由若干個節點構成，每一個節點都包括一個信息塊（即實際存儲的數據）、一個前驅指針和一個后驅指針。它無需分配指定的內存大小且可以任意伸縮，這是因為它存儲在非連續的內存空間中，并且由指針將有序的元素鏈接起來。
&nbs...
閱讀全文
posted @
2012-06-04 15:50 王海光 閱讀(4115) |
評論 (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 王海光 閱讀(11060) |
評論 (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 王海光 閱讀(927) |
評論 (0) |
編輯 收藏
摘要: 本文轉自：http://www.cnblogs.com/zqrferrari/archive/2010/07/07/1773113.html
一、MFC對多線程編程的支持
MFC中有兩類線程，分別稱之為工作者線程和用戶界面線程。二者的主要區別在于工作者線程沒有消息循環，而用戶界面線程有自己的消息隊列和消息循環?！ 」ぷ髡呔€程沒有消息機制，通常用來執行后臺計算和維護任務，如冗長的計算過程...
閱讀全文
posted @
2012-05-31 14:34 王海光 閱讀(3073) |
評論 (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 王海光 閱讀(1339) |
評論 (0) |
編輯 收藏