Dijkstra(迪杰斯特拉)算法是典型的最短路徑路由算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。
Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低。
Dijkstra算法是很有代表性的最短路算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運籌學等等。
其基本思想是，設置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。
初始時，S中僅含有源。設u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。
例如，對下圖中的有向圖，應用Dijkstra算法計算從源頂點1到其它頂點間最短路徑的過程列在下表中。
Dijkstra算法的迭代過程：
主題好好理解上圖！
以下是具體的實現(xiàn)(C/C++):
1 #include <iostream>
2 using namespace std;
3
4 const int maxnum = 100;
5 const int maxint = 999999;
6
7 // 各數(shù)組都從下標1開始
8 int dist[maxnum]; // 表示當前點到源點的最短路徑長度
9 int prev[maxnum]; // 記錄當前點的前一個結(jié)點
10 int c[maxnum][maxnum]; // 記錄圖的兩點間路徑長度
11 int n, line; // 圖的結(jié)點數(shù)和路徑數(shù)
12
13 // n -- n nodes
14 // v -- the source node
15 // dist[] -- the distance from the ith node to the source node
16 // prev[] -- the previous node of the ith node
17 // c[][] -- every two nodes' distance
18 void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
19 {
20 bool s[maxnum]; // 判斷是否已存入該點到S集合中
21 for(int i=1; i<=n; ++i)
22 {
23 dist[i] = c[v][i];
24 s[i] = 0; // 初始都未用過該點
25 if(dist[i] == maxint)
26 prev[i] = 0;
27 else
28 prev[i] = v;
29 }
30 dist[v] = 0;
31 s[v] = 1;
32
33 // 依次將未放入S集合的結(jié)點中，取dist[]最小值的結(jié)點，放入結(jié)合S中
34 // 一旦S包含了所有V中頂點，dist就記錄了從源點到所有其他頂點之間的最短路徑長度
35 // 注意是從第二個節(jié)點開始，第一個為源點
36 for(int i=2; i<=n; ++i)
37 {
38 int tmp = maxint;
39 int u = v;
40 // 找出當前未使用的點j的dist[j]最小值
41 for(int j=1; j<=n; ++j)
42 if((!s[j]) && dist[j]<tmp)
43 {
44 u = j; // u保存當前鄰接點中距離最小的點的號碼
45 tmp = dist[j];
46 }
47 s[u] = 1; // 表示u點已存入S集合中
48
49 // 更新dist
50 for(int j=1; j<=n; ++j)
51 if((!s[j]) && c[u][j]<maxint)
52 {
53 int newdist = dist[u] + c[u][j];
54 if(newdist < dist[j])
55 {
56 dist[j] = newdist;
57 prev[j] = u;
58 }
59 }
60 }
61 }
62
63 // 查找從源點v到終點u的路徑，并輸出
64 void searchPath(int *prev,int v, int u)
65 {
66 int que[maxnum];
67 int tot = 1;
68 que[tot] = u;
69 tot++;
70 int tmp = prev[u];
71 while(tmp != v)
72 {
73 que[tot] = tmp;
74 tot++;
75 tmp = prev[tmp];
76 }
77 que[tot] = v;
78 for(int i=tot; i>=1; --i)
79 if(i != 1)
80 cout << que[i] << " -> ";
81 else
82 cout << que[i] << endl;
83 }
84
85 int main()
86 {
87 freopen("input.txt", "r", stdin);
88 // 各數(shù)組都從下標1開始
89
90 // 輸入結(jié)點數(shù)
91 cin >> n;
92 // 輸入路徑數(shù)
93 cin >> line;
94 int p, q, len; // 輸入p, q兩點及其路徑長度
95
96 // 初始化c[][]為maxint
97 for(int i=1; i<=n; ++i)
98 for(int j=1; j<=n; ++j)
99 c[i][j] = maxint;
100
101 for(int i=1; i<=line; ++i)
102 {
103 cin >> p >> q >> len;
104 if(len < c[p][q]) // 有重邊
105 {
106 c[p][q] = len; // p指向q
107 c[q][p] = len; // q指向p，這樣表示無向圖
108 }
109 }
110
111 for(int i=1; i<=n; ++i)
112 dist[i] = maxint;
113 for(int i=1; i<=n; ++i)
114 {
115 for(int j=1; j<=n; ++j)
116 printf("%8d", c[i][j]);
117 printf("\n");
118 }
119
120 Dijkstra(n, 1, dist, prev, c);
121
122 // 最短路徑長度
123 cout << "源點到最后一個頂點的最短路徑長度: " << dist[n] << endl;
124
125 // 路徑
126 cout << "源點到最后一個頂點的路徑為: ";
127 searchPath(prev, 1, n);
128 }
輸入數(shù)據(jù):
5
7
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
輸出數(shù)據(jù):
999999 10 999999 30 100
10 999999 50 999999 999999
999999 50 999999 20 10
30 999999 20 999999 60
100 999999 10 60 999999
源點到最后一個頂點的最短路徑長度: 60
源點到最后一個頂點的路徑為: 1 -> 4 -> 3 -> 5
本文轉(zhuǎn)自：http://www.wutianqi.com/?p=1890
其他連接：http://2728green-rock.blog.163.com/blog/static/43636790200901211848284/
posted @
2012-06-30 16:12 王海光 閱讀(569) |
評論 (0) |
編輯 收藏一．貪心算法的基本概念
當一個問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)時，我們會想到用動態(tài)規(guī)劃法去解它。但有時會有更簡單有效的算法。我們來看一個找硬幣的例子。假設有四種硬幣，它們的面值分別為二角五分、一角、五分和一分?，F(xiàn)在要找給某顧客六角三分錢。這時，我們會不假思索地拿出2個二角五分的硬幣，1個一角的硬幣和3個一分的硬幣交給顧客。這種找硬幣方法與其他的找法相比，所拿出的硬幣個數(shù)是最少的。這里，我們下意識地使用了這樣的找硬幣算法：首先選出一個面值不超過六角三分的最大硬幣，即二角五分；然后從六角三分中減去二角五分，剩下三角八分；再選出一個面值不超過三角八分的最大硬幣，即又一個二角五分，如此一直做下去。這個找硬幣的方法實際上就是貪心算法。顧名思義，貪心算法總是作出在當前看來是最好的選擇。也就是說貪心算法并不從整體最優(yōu)上加以考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當然，我們希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。上面所說的找硬幣算法得到的結(jié)果就是一個整體最優(yōu)解。找硬幣問題本身具有最優(yōu)子結(jié)構(gòu)性質(zhì)，它可以用動態(tài)規(guī)劃算法來解。但我們看到，用貪心算法更簡單，更直接且解題效率更高。這利用了問題本身的一些特性。例如，上述找硬幣的算法利用了硬幣面值的特殊性。如果硬幣的面值改為一分、五分和一角一分3種，而要找給顧客的是一角五分錢。還用貪心算法，我們將找給顧客1個一角一分的硬幣和4個一分的硬幣。然而3個五分的硬幣顯然是最好的找法。雖然貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當廣的許多問題它能產(chǎn)生整體最優(yōu)解。如圖的單源最短路徑問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，但其最終結(jié)果卻是最優(yōu)解的很好的近似解。
二．求解活動安排問題算法
活動安排問題是可以用貪心算法有效求解的一個很好的例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。
設有n個活動的集合e={1，2，…，n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si<fi。如果選擇了活動i，則它在半開時間區(qū)間[si，fi]內(nèi)占用資源。若區(qū)間[si，fi]與區(qū)間[sj，fj]不相交，則稱活動i與活動j是相容的。也就是說，當si≥fi或sj≥fj時，活動i與活動j相容。活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合。
在下面所給出的解活動安排問題的貪心算法gpeedyselector中，各活動的起始時間和結(jié)束時間存儲于數(shù)組s和f{中且按結(jié)束時間的非減序：．f1≤f2≤…≤fn排列。如果所給出的活動未按此序排列，我們可以用o(nlogn)的時間將它重排。
1 template< class type>
2
3 void greedyselector(int n, type s[ 1, type f[ ], bool a[ ] ]
4
5 {
6 a[ 1 ] = true;
7
8 int j = 1;
9
10 for (int i=2;i< =n;i+ + )
11 {
12
13 if (s[i]>=f[j])
14 {
15
16 a[i] = true;
17
18 j=i;
19 }
20 else
21 a[i]= false;
22 }
23 }
算法greedyselector中用集合a來存儲所選擇的活動?；顒觟在集合a中，當且僅當a[i]的值為true。變量j用以記錄最近一次加入到a中的活動。由于輸入的活動是按其結(jié)束時間的非減序排列的，fj總是當前集合a中所有活動的最大結(jié)束時間，即：
貪心算法greedyselector一開始選擇活動1，并將j初始化為1。然后依次檢查活動i是否與當前已選擇的所有活動相容。若相容則將活動i加人到已選擇活動的集合a中，否則不選擇活動i，而繼續(xù)檢查下一活動與集合a中活動的相容性。由于fi
總是當前集合a中所有活動的最大結(jié)束時間，故活動i與當前集合a中所有活動相容的充分且必要的條件是其開始時間s 不早于最近加入集合a中的活動j的結(jié)束時間fj，si≥fj。若活動i與之相容，則i成為最近加人集合a中的活動，因而取代活動j的位置。由于輸人的活動是以其完成時間的非減序排列的，所以算法greedyselector每次總是選擇具有最早完成時間的相容活動加入集合a中。直觀上按這種方法選擇相容活動就為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。算法greedyselector的效率極高。當輸人的活動已按結(jié)束時間的非減序排列，算法只需g(n)的時間來安排n個活動，使最多的活動能相容地使用公共資源。
例：設待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
s[i] |
1 |
3 |
0 |
5 |
3 |
5 |
6 |
8 |
8 |
2 |
12 |
|
f[i] |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
算法greedyselector的計算過程如圖所示。
圖中每行相應于算法的一次迭代。陰影長條表示的活動是已選人集合a中的活動，而空白長條表示的活動是當前正在檢查其相容性的活動。
若被檢查的活動i的開始時間si小于最近選擇的活動了的結(jié)束時間fj，則不選擇活動i，否則選擇活動i加入集合a中。
三．算法分析
貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法greedyse—1ector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合a的規(guī)模最大。我們可以用數(shù)學歸納法來證明這個結(jié)論。
事實上，設e={1，2，…，n}為所給的活動集合。由于正中活動按結(jié)束時間的非減序排列，故活動1具有最早的完成時間。首先我們要證明活動安排問題有一個最優(yōu)解以貪心選擇開始，即該最優(yōu)解中包含活動1。設 是所給的活動安排問題的一個最優(yōu)解，且a中活動也按結(jié)束時間非減序排列，a中的第一個活動是活動k。若k=1，則a就是一個以貪心選擇開始的最優(yōu)解。若k>1，則我們設 。由于f1≤fk，且a中活動是互為相容的，故b中的活動也是互為相容的。又由于b中活動個數(shù)與a中活動個數(shù)相同，且a是最優(yōu)的，故b也是最優(yōu)的。也就是說b是一個以貪心選擇活動1開始的最優(yōu)活動安排。因此，我們證明了總存在一個以貪心選擇開始的最優(yōu)活動安排方案。
進一步，在作了貪心選擇，即選擇了活動1后，原問題就簡化為對e中所有與活動1相容的活動進行活動安排的子問題。即若a是原問題的一個最優(yōu)解，則a’=a—{i}是活動安排問題 的一個最優(yōu)解。事實上，如果我們能找到e’的一個解b’，它包含比a’更多的活動，則將活動1加入到b’中將產(chǎn)生e的一個解b，它包含比a更多的活動。這與a的最優(yōu)性矛盾。因此，每一步所作的貪心選擇都將問題簡化為一個更小的與原問題具有相同形式的子問題。對貪心選擇次數(shù)用數(shù)學歸納法即知，貪心算法greedyselector最終產(chǎn)生原問題的一個最優(yōu)解。
四．貪心算法的基本要素
貪心算法通過一系列的選擇來得到一個問題的解。它所作的每一個選擇都是當前狀態(tài)下某種意義的最好選擇，即貪心選擇。希望通過每次所作的貪心選擇導致最終結(jié)果是問題的一個最優(yōu)解。這種啟發(fā)式的策略并不總能奏效，然而在許多情況下確能達到預期的目的。解活動安排問題的貪心算法就是一個例子。下面我們著重討論可以用貪心算法求解的問題的一般特征。
對于一個具體的問題，我們怎么知道是否可用貪心算法來解此問題，以及能否得到問題的一個最優(yōu)解呢?這個問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中
我們看到它們一般具有兩個重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。
1．貪心選擇性質(zhì)
所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。在動態(tài)規(guī)劃算法中，每步所作的選擇往往依賴于相關子問題的解。因而只有在解出相關子問題后，才能作出選擇。而在貪心算法中，僅在當前狀態(tài)下作出最好選擇，即局部最優(yōu)選擇。然后再去解作出這個選擇后產(chǎn)生的相應的子問題。貪心算法所作的貪心選擇可以依賴于以往所作過的選擇，但決不依賴于將來所作的選擇，也不依賴于子問題的解。正是由于這種差別，動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行,以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題。
對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，我們必須證明每一步所作的貪心選擇最終導致問題的一個整體最優(yōu)解。通?？梢杂梦覀冊谧C明活動安排問題的貪心選擇性質(zhì)時所采用的方法來證明。首先考察問題的一個整體最優(yōu)解，并證明可修改這個最優(yōu)解，使其以貪心選擇開始。而且作了貪心選擇后，原問題簡化為一個規(guī)模更小的類似子問題。然后，用數(shù)學歸納法證明，通過每一步作貪心選擇，最終可得到問題的一個整體最優(yōu)解。其中，證明貪心選擇后的問題簡化為規(guī)模更小的類似子問題的關鍵在于利用該問題的最優(yōu)子結(jié)構(gòu)性質(zhì)。
2．最優(yōu)子結(jié)構(gòu)性質(zhì)
當一個問題的最優(yōu)解包含著它的子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題所具有的這個性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的一個關鍵特征。在活動安排問題中，其最優(yōu)子結(jié)構(gòu)性質(zhì)表現(xiàn)為：若a是對于正的活動安排問題包含活動1的一個最優(yōu)解,則相容活動集合a’=a—{1}是對于e’={i∈e:si≥f1}的活動安排問題的一個最優(yōu)解。
3．貪心算法與動態(tài)規(guī)劃算法的差異
貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是兩類算法的一個共同點。但是，對于一個具有最優(yōu)子結(jié)構(gòu)的問題應該選用貪心算法還是動態(tài)規(guī)劃算法來求解?是不是能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法來求解?下面我們來研究兩個經(jīng)典的組合優(yōu)化問題，并以此來說明貪心算法與動態(tài)規(guī)劃算法的主要差別。
五． ０－背包問題
給定n種物品和一個背包。物品i的重量是w ，其價值為v ，背包的容量為c.問應如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大? 在選擇裝入背包的物品時，對每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。
此問題的形式化描述是，給定c>0，wi>0，vi>0，1≤i≤n，要求找出一個n元0—1向
量(xl，x2，…，xn)， ，使得 ≤c，而且 達到最大。
背包問題：與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包。
此問題的形式化描述是，給定c>0，wi>0，vi>0，1≤i≤n，要求找出一個n元向量
(x1,x2,...xn)，0≤xi≤1，1≤i≤n 使得 ≤c，而且 達到最大。
這兩類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)。對于0—1背包問題，設a是能夠裝入容量為c的背包的具有最大價值的物品集合，則aj=a-{j}是n-1個物品1，2，…，j—1，j+1，…，n可裝入容量為c-wi叫的背包的具有最大價值的物品集合。對于背包問題，類似地，若它的一個最優(yōu)解包含物品j，則從該最優(yōu)解中拿出所含的物品j的那部分重量wi，剩余的將是n-1個原重物品1，2，…，j-1，j+1，…，n以及重為wj-wi的物品j中可裝入容量為c-w的背包且具有最大價值的物品。
雖然這兩個問題極為相似，但背包問題可以用貪心算法求解，而0·1背包問題卻不能用貪心算法求解。用貪心算法解背包問題的基本步驟是，首先計算每種物品單位重量的價值
vj／wi然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過c，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直進行下去直到背包裝滿為止。具體算法可描述如下：
void knapsack(int n, float m, float v[ ], float w[ ], float x[ ] )
sort(n,v,w);
int i;
for(i= 1;i<= n;i++) x[i] = o;
float c = m;
for (i = 1;i < = n;i ++) {
if (w[i] > c) break;
x[i] = 1;
c-= w[i];
}
if (i < = n) x[i] = c/w[i];
}
算法knapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為o(nlogn)。當然，為了證明算法的正確性，我們還必須證明背包問題具有貪心選擇性質(zhì)。
這種貪心選擇策略對0—1背包問題就不適用了。看圖2(a)中的例子，背包的容量為50千克；物品1重10千克；價值60元；物品2重20千克，價值100元；物品3重30千克；價值120元。因此，物品1每千克價值6元，物品2每千克價值5元，物品3每千克價值4元。若依貪心選擇策略，應首選物品1裝入背包，然而從圖4—2(b)的各種情況可以看出，最優(yōu)的選擇方案是選擇物品2和物品3裝入背包。首選物品1的兩種方案都不是最優(yōu)的。對于背包問題，貪心選擇最終可得到最優(yōu)解，其選擇方案如圖2(c)所示。
對于0—1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為它無法保證最終能將背包裝滿，部分背包空間的閑置使每千克背包空間所具有的價值降低了。事實上，在考慮0—1背包問題的物品選擇時，應比較選擇該物品和不選擇該物品所導致的最終結(jié)果，然后再作出最好選擇。由此就導出許多互相重疊的于問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。動態(tài)規(guī)劃算法的確可以有效地解0—1背包問題。
本文轉(zhuǎn)自：http://m.shnenglu.com/3522021224/archive/2007/06/16/26429.aspx
其他鏈接：http://www.cnblogs.com/chinazhangjie/archive/2010/11/23/1885330.html
posted @
2012-06-30 15:55 王海光 閱讀(411) |
評論 (0) |
編輯 收藏Select * From user Limit 3 Offset 5;
以上語句表示從Account表獲取數(shù)據(jù)，跳過5行，取3行
用法一
SELECT `keyword_rank`.* FROM `keyword_rank` WHERE (advertiserid='59') LIMIT 2 OFFSET 1;
比如這個SQL ，limit后面跟的是2條數(shù)據(jù)，offset后面是從第1條開始讀取。
用法二
SELECT `keyword_rank`.* FROM `keyword_rank` WHERE (advertiserid='59') LIMIT 2,1;
而這個SQL，limit后面是從第2條開始讀，讀取1條信息。
這兩個千萬別搞混哦。
用法三
select * from tablename <條件語句> limit 100,-1
從第100條后開始-最后一條的記錄
用法四
select * from tablename <條件語句> limit 15
相當于limit 0,15 .查詢結(jié)果取前15條數(shù)據(jù)
用法五mysql低版本不支持limit offset
limit offset 在mysql 4.0以上的版本中都可以正常運行，在舊版本的mysql 3.23中無效
limit m offset n 等價于 limit m,n
limit 的優(yōu)化mysql的limit給分頁帶來了極大的方便，但數(shù)據(jù)量一大的時候，limit的性能就急劇下降
來源：一畝三分地博客
MYSQL的優(yōu)化是非常重要的。其他最常用也最需要優(yōu)化的就是limit。mysql的limit給分頁帶來了極大的方便，但數(shù)據(jù)量一大的時候，limit的性能就急劇下降。
同樣是取10條數(shù)據(jù)
select * from yanxue8_visit limit 10000,10 和
select * from yanxue8_visit limit 0,10
就不是一個數(shù)量級別的。
網(wǎng)上也很多關于limit的五條優(yōu)化準則，都是翻譯自mysql手冊，雖然正確但不實用。今天發(fā)現(xiàn)一篇文章寫了些關于limit優(yōu)化的，很不錯。
文中不是直接使用limit，而是首先獲取到offset的id然后直接使用limit size來獲取數(shù)據(jù)。根據(jù)他的數(shù)據(jù)，明顯要好于直接使用limit。這里我具體使用數(shù)據(jù)分兩種情況進行測試。（測試環(huán)境win2033+p4雙核 (3GHZ) +4G內(nèi)存 mysql 5.0.19）
1、offset比較小的時候。
select * from yanxue8_visit limit 10,10
多次運行，時間保持在0.0004-0.0005之間
Select * From yanxue8_visit Where vid ＞=(
Select vid From yanxue8_visit Order By vid limit 10,1
) limit 10
多次運行，時間保持在0.0005-0.0006之間，主要是0.0006
結(jié)論：偏移offset較小的時候，直接使用limit較優(yōu)。這個顯然是子查詢的原因。
2、offset大的時候。
select * from yanxue8_visit limit 10000,10
多次運行，時間保持在0.0187左右
Select * From yanxue8_visit Where vid ＞=(
Select vid From yanxue8_visit Order By vid limit 10000,1
) limit 10
多次運行，時間保持在0.0061左右，只有前者的1/3。可以預計offset越大，后者越優(yōu)
本文轉(zhuǎn)自：
http://blog.csdn.net/lvwz2008/article/details/7558285
posted @
2012-06-21 12:40 王海光 閱讀(1276) |
評論 (0) |
編輯 收藏
摘要: 1.批處理文件是一個“.bat”結(jié)尾的文本文件，這個文件的每一行都是一條DOS命令。可以使用任何文本文件編輯工具創(chuàng)建和修改。 2.批處理是一種簡單的程序，可以用 if 和 goto 來控制流程，也可以使用 for 循環(huán)。 3.批處理的編程能力遠不如C語言等編程語言，也十分不規(guī)范。 4.每個編寫好的批處理文件都相當于一個DOS的外部命令，把它所在的目錄放到DOS搜索路徑(path)中，即可在任意位置運行。 5.C:\AUTOEXEC.BAT 是每次系統(tǒng)啟動時都會自動運行的，可以將每次啟動時都要運行的命令放入該文件中。 6.大小寫不敏感(命令符忽略大小寫) 7.批處理的文件擴展名為 .bat 或 .cmd。
閱讀全文
posted @
2012-06-21 12:30 王海光 閱讀(3187) |
評論 (0) |
編輯 收藏【按鈕添加圖標】
方法一:
1.添加圖標資源IDI_ICON1;
2 使用函數(shù) LoadIcon() 載入圖標。因為LoadIcon() 是類 CWinApp 的成員函數(shù)，同時函數(shù) LoadIcon() 返回所載入圖標的句柄。所以我們采用以下方法來調(diào)用函數(shù) LoadIcon():
HICON m_hicn1=AfxGetApp()->LoadIcon(IDI_ICON1);
3 為按鈕設置圖標了，這通過調(diào)用函數(shù) SetIcon() 來實現(xiàn):
m_button1.SetIcon(m_hicn1); // m_button1是按鈕變量
方法二:
前兩步和上方法一樣;
3 先由函數(shù) GetDlgItem() 獲得一個指向 CWnd 對象的指針，再通過強制類型轉(zhuǎn)換將該指針轉(zhuǎn)換為一個指向 CButton 類對象的指針。進而通過該指針來調(diào)用函數(shù) SetIcon()。具體實現(xiàn)代碼如下：
CWnd *pWnd = GetDlgItem(IDC_BUTTON1);
CButton *Button= (CButton *) pWnd;
Button-> SetIcon(m_hicn1);
【按鈕添加位圖】
1 添加位圖資源BMP1;
2 利用函數(shù) LoadBitmap() 從資源中載入位圖.
HBITMAP LoadBitmap(
HINSTANCE hInstance, // handle of application instance
LPCTSTR lpBitmapName // address of bitmap resource name
);
所以，為達到載入位圖的目的，不僅要定義一個位圖句柄 hBitmap，而且還要定義一個應用程序?qū)嵗浔?hInstance，
并調(diào)用函數(shù) AfxGetInstanceHandle() 以獲得當前的應用程序?qū)嵗浔?，代碼如下：
HBITMAP hBitmap;
HINSTANCE hInstance = ::AfxGetInstanceHandle();
只有在聲明并獲得了當前的應用程序句柄后，才能使用以下語句載入位圖：
hBitmap = ::LoadBitmap(hInstance,"BMP1"); //BMP1是資源文件名
3 用SetBitmap()添加位圖;
m_button1.SetBitmap(hBitmap);
或
pWnd = GetDlgItem(IDC_BUTTON1);
Button= (CButton *) pWnd;
Button-> SetBitmap(hBitmap);
___________________________________________________
位圖按鈕的實現(xiàn)方法：
首先，我們創(chuàng)建一個基于對話框的應用程序CmyDialog ；
Ι．MFC的CBitmapButton類，這也是最簡單的功能最強的位圖按鈕。我們可以采取如下的步驟：
1． 為按鈕指定唯一的按鈕標題（此例子為OK按鈕，這里設置按鈕標題為OK）并選中Ownerdraw屬性，然后在項目中加一些位圖資源，并用名字標示這些資源而不要用數(shù)字ID，其ID分別為”OKU”、”OKD”、”OKF”、”OKX”（一定要加雙引號），分別對應于按鈕的“松開(Up)”、“按下(Down)”、“獲得輸入焦點(focused)”和“禁止(Disable)”狀態(tài)。
2． 我們還要在對話框類中加入CBitmapButton m_aBmpBtn;數(shù)據(jù)成員。
3． 在初始化中為這個成員調(diào)用：
…
m_aBmpBtn. AutoLoad(IDOK,this);
…
點擊編譯按鈕，成功后運行程序，我們的位圖按鈕已經(jīng)建立了。
改變CANCLE按鈕的標題，可以設置其標題為ICON或者BITMAP ：（這里我們演示了bitmap的用法，Icon按鈕讀者可以按照下面的代碼處理）
CBitmapButton的使用
CBitmapButton作為MFC的控件類，并不為很多人所使用，因為現(xiàn)在網(wǎng)上遍布著從CButton派生的各種各樣的按鈕類，其中最為著名的就是CButtonST類了。但是最近在CSDN上看到幾個問題都是使用CBitmapButton類，但是由于使用錯誤、不當而造成程序崩潰或者錯誤的。所以總結(jié)一下CBitmapButton類的使用，希望能幫助一些初學者。
可以參考MSDN自帶的例子“CTRLTEST”學習CBitmapButton的用法。個人總結(jié)如下：
1、在資源編輯的時候選中按鈕的Owner draw即可，不需要選擇Bitmap屬性！
2、在程序中定義一個CBitmapButton成員變量。不能使用ClassWizard為按鈕映射一個CButton變量，然后改為CBitmapButton，這么做并不能將按鈕直接映射為CBitmapButton類的對象，反而會出現(xiàn)初始化錯誤。也不能兩種變量同時存在,會造成程序崩潰。
3-1、使用CBitmapButton::LoadBitmaps裝載各種狀態(tài)的圖片,使用SubclassDlgItem關聯(lián)到想要的按鈕，使用CBitmapButton::SizeToContent函數(shù)使按鈕適合圖片大小。。注意Loadbitmaps一定要在關聯(lián)到按鈕之前進行！
3-2、或者是使用CBitmapButton::AutoLoad函數(shù)關聯(lián)到想要的按鈕。需要注意：
A、之前不能使用CBitmapButton::LoadBitmaps裝載各種狀態(tài)的圖片，否則會出錯。
B、AutoLoad函數(shù)完成的關聯(lián)和改變按鈕大小的CBitmapButton::SizeToContent函數(shù)的功能。
C、CBitmapButton::AutoLoad使用的位圖是默認資源ID的，即它會自動裝載相關資源位圖。位圖的資源ID格式為："按鈕Caption+U"、"按鈕Caption+D"、"按鈕Caption+F"、"按鈕Caption+X"，分別代表Up、Down、Focus、Disable狀態(tài)。如資源編輯時，希望關聯(lián)的按鈕的Caption為Test，那么其默認裝載的位圖資源的ID為："TestU"/"TestD"/"TestF"/"TestX"，注意分號""也是其ID的一部分。
Ⅱ．使用圖標制作按鈕
1． 打開ICON按鈕的屬性頁，在Style中選中Icon
2． 在對話框類的頭文件中定義成員變量（使用ClassWizard加入這個成員變量）
CButton m_IconBtn；//對應于圖標按鈕
3． 創(chuàng)建相應的圖標或者位圖資源：
圖標資源：IDI_ICONBUTTON
4．在初始化中加入如下代碼：
…
//對應于圖標按鈕
HICON hIcon=AfxGetApp()->LoadIcon(IDI_ICONBUTTON);
m_IconBtn.SetIcon(hIcon);
…
重新編譯運行我們的程序，奇妙的圖像按鈕呈現(xiàn)在我們的眼前了。
Ⅲ．使用位圖制作按鈕
1． 打開BITMAP按鈕的屬性頁，在Style中選中Bitmap。
2． 對話框類的頭文件中定義成員變量（使用ClassWizard加入這個成員變量）
CButton m_IconBtn；
3．創(chuàng)建位圖資源：
位圖資源：IDB_BITMAPBUTTON
4．在初始化中加入如下代碼：
//對應于位圖按鈕
…
HBITMAP hBmp=::LoadBitmap(AfxGetInstanceHandle(),
MAKEINTRESOURCE(IDB_ BITMAPBUTTON));
m_BmpBtn.SetBitmap(hBmp);
本文轉(zhuǎn)自：http://hi.baidu.com/lechie/item/dcbca9f4ee98a3d742c36ad4
posted @
2012-06-18 17:32 王海光 閱讀(1801) |
評論 (0) |
編輯 收藏
摘要: 本文轉(zhuǎn)自：http://www.vckbase.com/document/viewdoc/?id=212 本文的目的是為剛剛接觸COM的程序員提供編程指南，并幫助他們理解COM的基本概念。內(nèi)容包括COM規(guī)范簡介，重要的COM術語以及如何重用現(xiàn)有的COM組件。本文不包括如何編寫自己的COM對象和接口?！ OM即組件對象模型，是Compone...
閱讀全文
posted @
2012-06-11 14:58 王海光 閱讀(752) |
評論 (0) |
編輯 收藏
使用ATL編寫一個簡單的COM服務器
本文的對象是COM編程初學者，其目的旨在描述如何用ATL創(chuàng)建COM服務器，以及如何在VC或VB編寫的客戶端應用程序中調(diào)用COM服務器。為了不給初學者增加負擔，本文不打算深入討論COM和IDL的細節(jié)，而是展示用ATL創(chuàng)建簡單的COM對象所需要的步驟。希望通過這篇文章能刺激你學習COM編程的欲望。
第一步：運行ATL COM向?qū)?br /> 你要做的第一件事情是啟動VS2008創(chuàng)建一個新的工程。選擇“File->New Project”。彈出創(chuàng)建工程對話框，選擇"Visual C++->ATL->ATL Project"，在下面輸入工程名稱和路徑,注意這個向?qū)?chuàng)建的工程并沒有包含任何初始的COM對象，在完成這個向?qū)е螅獜?#8220;ClassView”中用“New ATL Object”命令來指定你想要增加到這個工程中的對象類型。然后單擊"OK"按鈕。
第一部分單選按鈕選項是要創(chuàng)建的服務器類型“Server Type”。因為我們要創(chuàng)建一個進程內(nèi)服務器（Server DLL），所以應該選擇的類型是動態(tài)鏈接庫“Dynamic Link Library——DLL”，注意所有進程內(nèi)服務器都是DLL。下面是三個復選框不用去管它，它和我們創(chuàng)建的這個工程沒關系。單擊“Finish”按鈕。
第二步：創(chuàng)建新的ATL對象
為你的ATL項目（容器）添加供外部使用的Class (ATL Simple Object)。選項頁 “ C++”的“Short name”輸入欄中輸入你的Class名稱，其它輸入框會自動更新。
“Threading model”選“Apartment”;“Interface”選“Dual”;“Aggregation”選“No”;“Support”選“Connection points”和“I Object With Site(IE objects support)”。
在“Short Name”文本編輯框中輸入“First_ATL”。注意向?qū)詣犹顚懫溆嗟奈谋揪庉嬁颉螕?#8220;Attributes”標簽。其中有幾組單選按鈕選項和幾個復選框。第一組單選按鈕是線程模型“Threading Model”，我們?nèi)∪笔≈?#8220;Apartment Model”。第二組單選按鈕是接口“Interface”，單擊“Dual”，也就是雙接口。最后，第三組單選按鈕是聚合“Aggregation”，因為我們不想涉及接口的聚合，所以在此選擇“No”。至于底下的三個復選框，我們不用管它，單擊OK按鈕讓向?qū)?chuàng)建新的“ATL Simple Object”
第三步：添加方法
如果你單擊工作間的“ClassView”標簽，你會注意到向?qū)г诶锩嫣砑恿艘恍﹥?nèi)容。添加一個方法很容易，選中“IFirst_ATL”后單擊右鍵并選擇“Add Method”。
單擊“Add Method”后，你會看到“Add Method to Interface”對話框。
在“Return Type”編輯框中（已成灰色）這個方法的返回值已經(jīng)缺省為 “HRESULT”。大多數(shù)情況下都應該是這個值類型。下一個編輯框是方法名“Method Name”，輸入方法名“AddNumbers”。最后一個編輯框是要你輸入希望使用的參數(shù)“Parameters”。由于我們打算將兩個數(shù)字相加，然后返回相加結(jié)果，所以要使用三個參數(shù)。最后一個參數(shù)是一個指針?，F(xiàn)在你不用去關心繁雜的接口定義語言IDL，只要在這個參數(shù)編輯框中輸入如下內(nèi)容：
[in] long Num1, [in] long Num2, [out] long *ReturnVal
它的意思是聲明兩個long類型輸入[in]參數(shù)和一個指針返回值[out]（剛開始可能會不習慣這樣怪怪的寫法，但等你閱讀了一兩本關于COM的書之后，會慢慢接收它的）。單擊OK按鈕。展開所有“ClassView”的節(jié)點“+”號。從這個視圖可以清楚地了解Simple_ATL各個類之間的層次關系。雙擊最上面“IFirst_ATL”（接口）節(jié)點下的“AddNumbers”（方法）節(jié)點，右邊屏幕將會顯示這個方法的實現(xiàn)代碼。添加如下的代碼：
1 STDMETHODIMP CFirst_ATL::AddNumbers(long Num1, long Num2, long *ReturnVal)
2 {
3 // TODO: Add your implementation code here
4 *ReturnVal = Num1 + Num2;
5
6 return S_OK;
7 }
第四步：編譯這個DLL
不管你想不相信，到目前為止，我們用ATL所創(chuàng)建的COM服務器已經(jīng)完全能運行！當然，還需要編譯它才行。按下“F7”功能鍵，幾秒鐘之后，VC++便會完成編譯并注冊你所創(chuàng)建的DLL服務器。這樣其它的應用程序就可以使用這個COM服務器了。試一試吧！
第五步：用VC測試這個服務器
保存并關閉Simple_ATL工程，然后創(chuàng)建一個新的Win32 控制臺應用程序。選擇“Win32 Console Application”并取名為“Test_ATL”。單擊OK按鈕并接受對話框中的缺省設置（空的工程）。單擊“Finish”按鈕，然后再按OK按鈕。這樣就創(chuàng)建好了一個空的工程。按下“Control+N”鍵向工程中添加一個文件。從彈出的窗口中選擇“C++ Source File”并為它取名為“Test_ATL.cpp”。按下OK按鈕。這樣工程中就有了一個空的.CPP文件。我們要在這個文件中添加一些測試COM服務器的代碼：
// 將頭文件的目錄指到Simple_ATL工程所在的目錄
1 #include "stdafx.h"
2 #include "..\..\Simple_ATL\Simple_ATL\Simple_ATL_i.h"
3 #include "..\..\Simple_ATL\Simple_ATL\Simple_ATL_i.c"
4 #include <iostream>
5 using namespace std;
6 // 從Simple_ATL 工程所在目錄的Simple_ATL_i.c 文件中拷貝以下內(nèi)容
7 // 注意: 你也可以不拷貝這些東西，而是把文件Simple_ATL_i.c包含進來。
8 // 我之所以將它拷進來，是想更清楚地展示這些敞亮來自什么地方一擊它們的代碼
9 // const IID IID_IFirst_ATL =
10 // {0x5AC2B2B7,0xBA06,0x4A4E,0x8D,0xED,0x78,0xDD,0x95,0x73,0x25,0x3B};
11 //
12 // const CLSID CLSID_First_ATL =
13 // {0x862DFA11,0x863B,0x4115,0xB7,0x39,0xB6,0x18,0x0E,0xBC,0x6B,0x66};
14
15 void main(void)
16 {
17 // 聲明HRESULT和Simple_ATL接口指針
18 HRESULT hr;
19 IFirst_ATL *IFirstATL = NULL;
20
21 // 初始化COM
22 hr = CoInitialize(0);
23
24 // 使用SUCCEEDED 宏并檢查我們是否能得到一個接口指針
25 if(SUCCEEDED(hr))
26 {
27 hr = CoCreateInstance( CLSID_First_ATL, NULL, CLSCTX_INPROC_SERVER,
28 IID_IFirst_ATL, (void**) &IFirstATL);
29
30 // 如果成功，則調(diào)用AddNumbers方法，否則顯示相應的出錯信息
31 if(SUCCEEDED(hr))
32 {
33 long ReturnValue;
34
35 IFirstATL->AddNumbers(5, 7, &ReturnValue);
36 cout << "The answer for 5 + 7 is: " << ReturnValue << endl;
37 IFirstATL->Release();
38 }
39 else
40 {
41 cout << "CoCreateInstance Failed." << endl;
42 }
43 }
44 // 釋放COM
45 CoUninitialize();
46 }
第七步：編譯并運行測試程序
按下“F5”功能鍵，編譯測試程序，然后按“Control+F5”功能組合鍵運行測試程序。在DOS窗口中，你應該能看到輸出的結(jié)果。
本文轉(zhuǎn)自：
http://andylin02.iteye.com/blog/453079。
posted @
2012-06-07 13:56 王海光 閱讀(1571) |
評論 (0) |
編輯 收藏本文轉(zhuǎn)自：
http://blog.csdn.net/lee353086/article/details/5864939
Linux下C++程序常用編譯命令
文中涉及的命令在Ubuntu8.04.1中測試通過，本文的目的是為了以后要用的時候，只要看一下本文就馬上能回憶起這此命令怎么用。
生成目標文件
#gcc –c <XXX.cpp>
可以有多個cpp文件
編譯靜態(tài)庫
#ar cr <libXXX.a> <XXX.o>
可以有多個o文件（目標文件）
靜態(tài)庫名的命名方式應該是libXXX.a 其中XXX是庫的名字。
編譯成動態(tài)庫
# gcc -shared -fPCI -o libmyhello.so hello.o
可以有多個o文件，若考慮到同個庫有多個版本，參考如下命令
#gcc -shared -Wl,-soname,libhello.so.1 -o libhello.so.1.0 hello.o
另外再建立兩個符號連接：
#ln -s libhello.so.1.0 libhello.so.1
#ln -s libhello.so.1 libhello.so 這樣一個libhello的動態(tài)連接庫就生成了。最重要的是傳gcc -shared 參數(shù)使其生成是動態(tài)庫而不是普通執(zhí)行程序。
-Wl 表示后面的參數(shù)也就是-soname,libhello.so.1直接傳給連接器ld進行處理。實際上，每一個庫都有一個soname，當連接器發(fā)現(xiàn)它正 在查找的程序庫中有這樣一個名稱，連接器便會將soname嵌入連結(jié)中的二進制文件內(nèi)，而不是它正在運行的實際文件名，在程序執(zhí)行期間，程序會查找擁有 soname名字的文件，而不是庫的文件名，換句話說，soname是庫的區(qū)分標志。 這樣做的目的主要是允許系統(tǒng)中多個版本的庫文件共存，習慣上在命名庫文件的時候通常與soname相同 libxxxx.so.major.minor 其中，xxxx是庫的名字，major是主版本號，minor 是次版本號
使用靜態(tài)庫
#gcc –o <輸出文件名> <目標文件名> <靜態(tài)庫文件名>
使用動態(tài)庫
#gcc <源文件名> -l<動態(tài)庫文件名> -L<動態(tài)庫所在路徑>
例如：
#gcc test.c -lhello -L.
把源test.c編譯為a.out可執(zhí)行文件，test.c所需要的函數(shù)在libhello.so文件中定義，libhello.so文件在當前目錄。
直接執(zhí)行a.out提示找不到動態(tài)庫文件，這時需要修改當前的動態(tài)庫搜索路徑。
如下：
# export LD_LIBRARY_PATH=.:$LD_LIBRARY_PATH
再執(zhí)行a.out，測試文件運行成功。
常用命令
[1]查看當前文件依賴于哪些庫
#ldd <庫文件或可執(zhí)行文件>
[2]查看文件類型
#file <可執(zhí)行文件名>
[3]查看庫中符號
#nm <庫文件名稱>
nm列出的符號有很多，常見的有 三種，一種是在庫中被調(diào)用，但并沒有在庫中定義(表明需要其他庫支持)，用U表示；一種是庫中定義的函數(shù)，用T表示，這是最常見的；另外一種是所謂的“弱 態(tài)”符號，它們雖然在庫中被定義，但是可能被其他庫中的同名符號覆蓋，用W表示。
通常和grep命令配合使用
可執(zhí)行程序在執(zhí)行的時候如何定位共享庫文件
采用以下順序
[搜索elf文件的 DT_RPATH段]=>
[ 環(huán)境變量LD_LIBRARY_PATH]=>
[/etc/ld.so.cache文件列表]=>
[/lib/,/usr/lib目錄]
如何讓執(zhí)行程序順利找到動態(tài)庫
[方法一]把庫文件copy到/usr/lib目錄或/lib目錄。
[方法二]修改當前終端的LD_LIBRARY_PATH環(huán)境變量，例如：
#export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/home/WhereIsMyLibLocation
此方法只能臨時改變搜索路徑
[方法三]修改/etc/ld.so.conf文件，把庫所在的路徑加到文件末尾，并執(zhí)行ldconfig刷新。這樣，加入的目錄下的所有庫文件都可見。
常用參數(shù)（速記）
-I<頭文件路徑> -L<庫文件路徑> -i<頭文件> -l<庫文件名>
-Wall 盡可能多的警告信息
-o 輸出可執(zhí)行文件名（起到重命名輸出文件名的作用）
比如說用gcc編譯C++文件需要加上-lstdc++參數(shù)，讓編譯器去找libstdc++.a靜態(tài)庫文件
posted @
2012-06-07 10:55 王海光 閱讀(565) |
評論 (0) |
編輯 收藏 迭代器是一種對象，它能夠用來遍歷STL容器中的部分或全部元素，每個迭代器對象代表容器中的確定的地址。迭代器修改了常規(guī)指針的接口，所謂迭代器是一種概念上的抽象：那些行為上象迭代器的東西都可以叫做迭代器。然而迭代器有很多不同的能力，它可以把抽象容器和通用算法有機的統(tǒng)一起來。
迭代器提供一些基本操作符：*、++、==、！=、=。這些操作和C/C++“操作array元素”時的指針接口一致。不同之處在于，迭代器是個所謂的smart pointers，具有遍歷復雜數(shù)據(jù)結(jié)構(gòu)的能力。其下層運行機制取決于其所遍歷的數(shù)據(jù)結(jié)構(gòu)。因此，每一種容器型別都必須提供自己的迭代器。事實上每一種容器都將其迭代器以嵌套的方式定義于內(nèi)部。因此各種迭代器的接口相同，型別卻不同。這直接導出了泛型程序設計的概念：所有操作行為都使用相同接口，雖然它們的型別不同。
功能特點 迭代器使開發(fā)人員不必整個實現(xiàn)類接口。只需提供一個迭代器，即可遍歷類中的數(shù)據(jù)結(jié)構(gòu)，可被用來訪問一個容器類的所包函的全部元素，其行為像一個指針，但是只可被進行增加(++)或減少(--)操作。舉一個例子，你可用一個迭代器來實現(xiàn)對vector容器中所含元素的遍歷。
如下代碼對vector容器對象生成和使用了迭代器：
1 vector<int> the_vector;
2 vector<int>::iterator the_iterator;
3 for( int i=0; i < 10; i++ )
4 the_vector.push_back(i);
5 int total = 0;
6 the_iterator = the_vector.begin();
7 while( the_iterator != the_vector.end() )
8 {
9 total += *the_iterator;
10 the_iterator++;
11 }
12 cout << "Total=" << total << endl;
提示：通過對一個迭代器的解引用操作（*），可以訪問到容器所包含的元素。
C++標準庫總結(jié)
容器
序列
vector=========================<vector>
list===========================<list>
deque==========================<deque>
序列適配器
stack:top,push,pop=============<stack>
queue:front,back,push,pop======<queue>
priority_queue:top,push,pop====<queue>
關聯(lián)容器
map============================<map>
multimap=======================<map>
set============================<set>
multiset=======================<set>
擬容器
string=========================<string>
valarray=======================<valarray>
bitset=========================<bitset>
算法http://www.cplusplus.com/reference/algorithm/ STL Algorithms 詳細說明。
非修改性序列操作
<algorithm>
for_each()=====================對序列中每個元素執(zhí)行操作
find()=========================在序列中找某個值的第一個出現(xiàn)
find_if()======================在序列中找符合某謂詞的第一個元素
find_first_of()================在序列中找另一序列里的值
adjust_find()==================找出相鄰的一對值
count()========================在序列中統(tǒng)計某個值出現(xiàn)的次數(shù)
count_if()=====================在序列中統(tǒng)計與某謂詞匹配的次數(shù)
mismatch()=====================找使兩序列相異的第一個元素
equal()========================如果兩個序列對應元素都相同則為真
search()=======================找出一序列作為子序列的第一個出現(xiàn)位置
find_end()=====================找出一序列作為子序列的最后一個出現(xiàn)位置
search_n()=====================找出一序列作為子序列的第n個出現(xiàn)位置
修改性的序列操作
<algorithm>
transform()====================將操作應用于序列中的每個元素
copy()=========================從序列的第一個元素起進行復制
copy_backward()================從序列的最后元素起進行復制
swap()=========================交換兩個元素
iter_swap()====================交換由迭代器所指的兩個元素
swap_ranges()==================交換兩個序列中的元素
replace()======================用一個給定值替換一些元素
replace_if()===================替換滿足謂詞的一些元素
replace_copy()=================復制序列時用一個給定值替換元素
replace_copy_if()==============復制序列時替換滿足謂詞的元素
fill()=========================用一個給定值取代所有元素
fill_n()=======================用一個給定值取代前n個元素
generate()=====================用一個操作的結(jié)果取代所有元素
generate_n()===================用一個操作的結(jié)果取代前n個元素
remove()=======================刪除具有給定值的元素
remove_if()====================刪除滿足謂詞的元素
remove_copy()==================復制序列時刪除給定值的元素
remove_copy_if()===============復制序列時刪除滿足謂詞的元素
unique()=======================刪除相鄰的重復元素
unique_copy()==================復制序列時刪除相鄰的重復元素
reexample()======================反轉(zhuǎn)元素的次序
reexample_copy()=================復制序列時反轉(zhuǎn)元素的次序
rotate()=======================循環(huán)移動元素
rotate_copy()==================復制序列時循環(huán)移動元素
random_shuffle()===============采用均勻分布隨機移動元素
序列排序
<algorithm>
sort()=========================以很好的平均次序排序
stable_sort()==================排序且維持相同元素原有的順序
partial_sort()=================將序列的前一部分排好序
partial_sort_copy()============復制的同時將序列的前一部分排好序
nth_element()==================將第n個元素放到它的正確位置
lower_bound()==================找到某個值的第一個出現(xiàn)
upper_bound()==================找到大于某個值的第一個出現(xiàn)
equal_range()==================找出具有給定值的一個子序列
binary_search()================在排好序的序列中確定給定元素是否存在
merge()========================歸并兩個排好序的序列
inplace_merge()================歸并兩個接續(xù)的排好序的序列
partition()====================將滿足某謂詞的元素都放到前面
stable_partition()=============將滿足某謂詞的元素都放到前面且維持原順序
集合算法
<algorithm>
include()======================如果一個序列是另一個的子序列則為真
set_union()====================構(gòu)造一個已排序的并集
set_intersection()=============構(gòu)造一個已排序的交集
set_difference()===============構(gòu)造一個已排序序列，包含在第一個序列但不在第二個序列的元素
set_symmetric_difference()=====構(gòu)造一個已排序序列，包括所有只在兩個序列之一中的元素
堆操作
<algorithm>
make_heap()====================將序列高速得能夠作為堆使用
push_heap()====================向堆中加入一個元素
pop_heap()=====================從堆中去除元素
sort_heap()====================對堆排序
最大和最小
<algorithm>
min()==========================兩個值中較小的
max()==========================兩個值中較大的
min_element()==================序列中的最小元素
max_element()==================序列中的最大元素
lexicographic_compare()========兩個序列中按字典序的第一個在前
排列
<algorithm>
next_permutation()=============按字典序的下一個排列
prev_permutation()=============按字典序的前一個排列
通用數(shù)值算法
<numeric>
accumulate()===================積累在一個序列中運算的結(jié)果(向量的元素求各的推廣)
inner_product()================積累在兩個序列中運算的結(jié)果(內(nèi)積)
partial_sum()==================通過在序列上的運算產(chǎn)生序列(增量變化)
adjacent_difference()==========通過在序列上的運算產(chǎn)生序列(與partial_sum相反)
C風格算法
<cstdlib>
qsort()========================快速排序，元素不能有用戶定義的構(gòu)造，拷貝賦值和析構(gòu)函數(shù)
bsearch()======================二分法查找，元素不能有用戶定義的構(gòu)造，拷貝賦值和析構(gòu)函數(shù)
函數(shù)對象
基類 template<class Arg, class Res> struct unary_function
template<class Arg, class Arg2, class Res> struct binary_function
謂詞
返回bool的函數(shù)對象。
<functional>
equal_to=======================二元，arg1 == arg2
not_equal_to===================二元，arg1 != arg2
greater========================二元，arg1 > arg2
less===========================二元，arg1 < arg2
greater_equal==================二元，arg1 >= arg2
less_equal=====================二元，arg1 <= arg2
logical_and====================二元，arg1 && arg2
logical_or=====================二元，arg1 || arg2
logical_not====================一元，!arg
算術函數(shù)對象
<functional>
plus===========================二元，arg1 + arg2
minus==========================二元，arg1 - arg2
multiplies=====================二元，arg1 * arg2
divides========================二元，arg1 / arg2
modulus========================二元，arg1 % arg2
negate=========================一元，-arg
約束器，適配器和否定器
<functional>
bind2nd(y)
binder2nd==================以y作為第二個參數(shù)調(diào)用二元函數(shù)
bind1st(x)
binder1st==================以x作為第一個參數(shù)調(diào)用二元函數(shù)
mem_fun()
mem_fun_t==================通過指針調(diào)用0元成員函數(shù)
mem_fun1_t=================通過指針調(diào)用一元成員函數(shù)
const_mem_fun_t============通過指針調(diào)用0元const成員函數(shù)
const_mem_fun1_t===========通過指針調(diào)用一元const成員函數(shù)
mem_fun_ref()
mem_fun_ref_t==============通過引用調(diào)用0元成員函數(shù)
mem_fun1_ref_t=============通過引用調(diào)用一元成員函數(shù)
const_mem_fun_ref_t========通過引用調(diào)用0元const成員函數(shù)
const_mem_fun1_ref_t=======通過引用調(diào)用一元const成員函數(shù)
ptr_fun()
pointer_to_unary_function==調(diào)用一元函數(shù)指針
ptr_fun()
pointer_to_binary_function=調(diào)用二元函數(shù)指針
not1()
unary_negate===============否定一元謂詞
not2()
binary_negate==============否定二元謂詞
迭代器
分類 Output: *p= , ++
Input: =*p , -> , ++ , == , !=
Forward: *p= , =*p , -> , ++ , == , !=
Bidirectional: *p= , =*p -> , [] , ++ , -- , == , !=
Random: += , -= , *p= , =*p -> , [] , ++ , -- , + , - , == , != , < , > , <= , >=
插入器
template<class Cont> back_insert_iterator<Cont> back_inserter(Cont& c);
template<class Cont> front_insert_iterator<Cont> front_inserter(Cont& c);
template<class Cont, class Out> insert_iterator<Cont> back_inserter(Cont& c, Out p);
反向迭代器
reexample_iterator===============rbegin(), rend()
流迭代器
ostream_iterator===============用于向ostream寫入
istream_iterator===============用于向istream讀出
ostreambuf_iterator============用于向流緩沖區(qū)寫入
istreambuf_iterator============用于向流緩沖區(qū)讀出
分配器
<memory>
template<class T> class std::allocator
數(shù)值
數(shù)值的限制
<limits>
numeric_limits<>
<climits>
CHAR_BIT
INT_MAX
...
<cfloat>
DBL_MIN_EXP
FLT_RADIX
LDBL_MAX
...
標準數(shù)學函數(shù)
<cmath>
double abs(double)=============絕對值(不在C中)，同fabs()
double fabs(double)============絕對值
double ceil(double d)==========不小于d的最小整數(shù)
double floor(double d)=========不大于d的最大整數(shù)
double sqrt(double d)==========d在平方根，d必須非負
double pow(double d, double e)=d的e次冪
double pow(double d, int i)====d的i次冪
double cos(double)=============余弦
double sin(double)=============正弦
double tan(double)=============正切
double acos(double)============反余弦
double asin(double)============反正弦
double atan(double)============反正切
double atan2(double x,double y) //atan(x/y)
double sinh(double)============雙曲正弦
double cosh(double)============雙曲余弦
double tanh(double)============雙曲正切
double exp(double)=============指數(shù)，以e為底
double log(double d)===========自動對數(shù)(以e為底),d必須大于0
double log10(double d)=========10底對數(shù)，d必須大于0
double modf(double d,double*p)=返回d的小數(shù)部分，整數(shù)部分存入*p
double frexp(double d, int* p)=找出[0.5,1)中的x,y,使d=x*pow(2,y),返回x并將y存入*p
double fmod(double d,double m)=浮點數(shù)余數(shù)，符號與d相同
double ldexp(double d, int i)==d*pow(2,i)
<cstdlib>
int abs(int)===================絕對值
long abs(long)=================絕對值(不在C中)
long labs(long)================絕對值
struct div_t { implementation_defined quot, rem; }
struct ldiv_t { implementation_defined quot, rem; }
div_t div(int n, int d)========用d除n，返回(商，余數(shù))
ldiv_t div(long n, long d)=====用d除n，返回(商，余數(shù))(不在C中)
ldiv_t ldiv(long n, long d)====用d除n，返回(商，余數(shù))
向量算術
<valarray>
valarray
復數(shù)算術
<complex>
template<class T> class std::complex;
posted @
2012-06-05 13:59 王海光 閱讀(1097) |
評論 (0) |
編輯 收藏C++隊列是一種容器適配器，它給予程序員一種先進先出(FIFO)的數(shù)據(jù)結(jié)構(gòu)。
1.back() 返回一個引用，指向最后一個元素
2.empty() 如果隊列空則返回真
3.front() 返回第一個元素
4.pop() 刪除第一個元素
5.push() 在末尾加入一個元素
6.size() 返回隊列中元素的個數(shù)
隊列可以用線性表(list)或雙向隊列(deque)來實現(xiàn)(注意vector container 不能用來實現(xiàn)queue，因為vector 沒有成員函數(shù)pop_front!)：
queue<list<int>> q1;
queue<deque<int>> q2;
其成員函數(shù)有“判空(empty)” 、“尺寸(Size)” 、“首元(front)” 、“尾元(backt)” 、“加入隊列(push)” 、“彈出隊列(pop)”等操作。
例：
1 int main()
2 {
3 queue<int> q;
4 q.push(4);
5 q.push(5);
6 printf("%d\n",q.front());
7 q.pop();
8 }
C++ Priority Queues(優(yōu)先隊列)
C++優(yōu)先隊列類似隊列，但是在這個數(shù)據(jù)結(jié)構(gòu)中的元素按照一定的斷言排列有序。
1.empty() 如果優(yōu)先隊列為空，則返回真
2.pop() 刪除第一個元素
3.push() 加入一個元素
4.size() 返回優(yōu)先隊列中擁有的元素的個數(shù)
5.top() 返回優(yōu)先隊列中有最高優(yōu)先級的元素
優(yōu)先級隊列可以用向量(vector)或雙向隊列(deque)來實現(xiàn)(注意list container 不能用來實現(xiàn)queue，因為list 的迭代器不是任意存取iterator，而pop 中用到堆排序時是要求randomaccess iterator 的!)：
priority_queue<vector<int>, less<int>> pq1; // 使用遞增less<int>函數(shù)對象排序
priority_queue<deque<int>, greater<int>> pq2; // 使用遞減greater<int>函數(shù)對象排序
其成員函數(shù)有“判空(empty)” 、“尺寸(Size)” 、“棧頂元素(top)” 、“壓棧(push)” 、“彈棧(pop)”等。
例：
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4
5 class T {
6 public:
7 int x, y, z;
8 T(int a, int b, int c):x(a), y(b), z(c)
9 {
10 }
11 };
12 bool operator < (const T &t1, const T &t2)
13 {
14 return t1.z < t2.z; // 按照z的順序來決定t1和t2的順序
15 }
16 main()
17 {
18 priority_queue<T> q;
19 q.push(T(4,4,3));
20 q.push(T(2,2,5));
21 q.push(T(1,5,4));
22 q.push(T(3,3,6));
23 while (!q.empty())
24 {
25 T t = q.top();
26 q.pop();
27 cout << t.x << " " << t.y << " " << t.z << endl;
28 }
29 return 1;
30 }
輸出結(jié)果為(注意是按照z的順序從大到小出隊的)：
3 3 6
2 2 5
1 5 4
4 4 3
再看一個按照z的順序從小到大出隊的例子：
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 class T
5 {
6 public:
7 int x, y, z;
8 T(int a, int b, int c):x(a), y(b), z(c)
9 {
10 }
11 };
12 bool operator > (const T &t1, const T &t2)
13 {
14 return t1.z > t2.z;
15 }
16 main()
17 {
18 priority_queue<T, vector<T>, greater<T> > q;
19 q.push(T(4,4,3));
20 q.push(T(2,2,5));
21 q.push(T(1,5,4));
22 q.push(T(3,3,6));
23 while (!q.empty())
24 {
25 T t = q.top();
26 q.pop();
27 cout << t.x << " " << t.y << " " << t.z << endl;
28 }
29 return 1;
30 }
輸出結(jié)果為：
4 4 3
1 5 4
2 2 5
3 3 6
如果我們把第一個例子中的比較運算符重載為： bool operator < (const T &t1, const T &t2) { return t1.z > t2.z; // 按照z的順序來決定t1和t2的順序} 則第一個例子的程序會得到和第二個例子的程序相同的輸出結(jié)果。
posted @
2012-06-05 13:21 王海光 閱讀(49390) |
評論 (0) |
編輯 收藏