題目：1分鐘內(nèi)用戶上線的數(shù)目是60萬，如果用戶在5分鐘內(nèi)重復(fù)上線，就給他發(fā)警告，問如何設(shè)計(jì)？
考慮：要判斷用戶是否在5分內(nèi)重復(fù)上線，那么至少要（也只需要）保存距當(dāng)前時(shí)刻5分鐘內(nèi)的登錄用戶的信息（只要簡單的ID）
從這個(gè)開始出發(fā)，需要考慮的問題為2個(gè)：
1.如何在迅速判斷用戶是否在保存的數(shù)據(jù)中 （這個(gè)理所當(dāng)然想道用hash）
2. 如果把過期的數(shù)據(jù)刪掉 （這個(gè)就想到維護(hù)一個(gè)時(shí)間鏈表，把到期的通過鏈表來刪除）
這個(gè)是半年前騰訊面試的時(shí)候碰到的題目，當(dāng)時(shí)覺得很難，今天走在路上突然想起，想了想，突然想到這種方法，也許不是最好，但至少解決了，也了解了一件事
static的作用有2個(gè)，一個(gè)是控制名字的可見性，一個(gè)是控制生存期
1.控制名字的可見性
這時(shí)候是跟extern相對(duì)應(yīng)的，作用與文件作用域（file scope)內(nèi)的所有名字（變量名或函數(shù)名），其它定義在函數(shù)內(nèi)或類內(nèi)的變量名或函數(shù)名都不具有文件作用域。
一般情況下，當(dāng)你定義了一個(gè)全局范圍內(nèi)變量或函數(shù)名的時(shí)候，默認(rèn)的是extern，如在下面的file1.cpp
//file1.cpp
int a=1; //完整的應(yīng)該是extern int a=1;但extern是缺省的
void f() //同上一樣，這里也是定義
{
}那么在file2.cpp中你不能再聲明a跟f，否則會(huì)引起名字沖突，當(dāng)你想要使用file1.cpp中的a跟f時(shí)，可以如下
extern int a; //不運(yùn)行賦值，這里只是聲明,不可以省去extern，否則編譯器會(huì)認(rèn)為是重定義
void f(); //同樣是聲明，而且對(duì)函數(shù)而言，可以省去extern
extern int b＝1；//這里是定義
這樣就可以在file2.cpp中使用a跟f了
反過來，你在文件作用域范圍內(nèi)定義了一個(gè)名字，你不希望被其它文件引用，這時(shí)候就要在前面加上static，此時(shí)這個(gè)變量具有internal linkage，它不能被其它文件引用，同時(shí)在其它文件中聲明同名變量不會(huì)認(rèn)為有沖突（因?yàn)閟tatic 使得名字只在本文件內(nèi)可見）。
2.控制生存期
static 變量同global 變量一樣，放在static存儲(chǔ)區(qū)，只有當(dāng)程序運(yùn)行結(jié)束時(shí)，這些變量才會(huì)消失
當(dāng)static變量定義在函數(shù)中時(shí)，它僅在該函數(shù)內(nèi)可見，當(dāng)每次函數(shù)調(diào)用完，這個(gè)變量的值都會(huì)保留下來
當(dāng)static變量定義在類當(dāng)中時(shí)，這個(gè)變量就同類的對(duì)象無關(guān)，真?zhèn)€類只有一個(gè)該變量的副本，不過它定義了多少個(gè)對(duì)象，而且對(duì)改變量的改變可以只通過類來改變，該變量的變化對(duì)所有同類的對(duì)象是可見的
1. const常量，如const int max = 100;
優(yōu)點(diǎn)：const常量有數(shù)據(jù)類型，而宏常量沒有數(shù)據(jù)類型。編譯器可以對(duì)前者進(jìn)行類型安全檢查，而對(duì)后者只進(jìn)行字符替換，沒有類型安全檢查，并且在字符替換時(shí)可能會(huì)產(chǎn)生意料不到的錯(cuò)誤（邊際效應(yīng)）
2. const 修飾類的數(shù)據(jù)成員。如：
class A
{
const int size;
…
}
const數(shù)據(jù)成員只在某個(gè)對(duì)象生存期內(nèi)是常量，而對(duì)于整個(gè)類而言卻是可變的。因?yàn)轭惪梢詣?chuàng)建多個(gè)對(duì)象，不同的對(duì)象其const數(shù)據(jù)成員的值可以不同。所以不能在類聲明中初始化const數(shù)據(jù)成員，因?yàn)轭惖膶?duì)象未被創(chuàng)建時(shí)，編譯器不知道const 數(shù)據(jù)成員的值是什么。如
class A
{
const int size = 100; //錯(cuò)誤
int array[size]; //錯(cuò)誤，未知的size
}
const數(shù)據(jù)成員的初始化只能在類的構(gòu)造函數(shù)的初始化表中進(jìn)行。要想建立在整個(gè)類中都恒定的常量，應(yīng)該用類中的枚舉常量來實(shí)現(xiàn)。如
class A
{…
enum {size1=100, size2 = 200 };
int array1[size1];
int array2[size2];
}
枚舉常量不會(huì)占用對(duì)象的存儲(chǔ)空間，他們?cè)诰幾g時(shí)被全部求值。但是枚舉常量的隱含數(shù)據(jù)類型是整數(shù)，其最大值有限，且不能表示浮點(diǎn)數(shù)。
3. const修飾指針的情況，見下式：
int b = 500;
const int* a = & [1]
int const *a = & [2]
int* const a = & [3]
const int* const a = & [4]
如果你能區(qū)分出上述四種情況，那么，恭喜你，你已經(jīng)邁出了可喜的一步。不知道，也沒關(guān)系，我們可以參考《Effective c++》Item21上的做法，如果const位于星號(hào)的左側(cè)，則const就是用來修飾指針?biāo)赶虻淖兞浚粗羔樦赶驗(yàn)槌Ａ?；如果const位于星號(hào)的右側(cè)，const就是修飾指針本身，即指針本身是常量。因此，[1]和[2]的情況相同，都是指針?biāo)赶虻膬?nèi)容為常量（const放在變量聲明符的位置無關(guān)），這種情況下不允許對(duì)內(nèi)容進(jìn)行更改操作，如不能*a = 3 ；[3]為指針本身是常量，而指針?biāo)赶虻膬?nèi)容不是常量，這種情況下不能對(duì)指針本身進(jìn)行更改操作，如a++是錯(cuò)誤的；[4]為指針本身和指向的內(nèi)容均為常量。
4. const的初始化
先看一下const變量初始化的情況
1) 非指針const常量初始化的情況：A b;
const A a = b;
2) 指針const常量初始化的情況：
A* d = new A();
const A* c = d;
或者：const A* c = new A();
3）引用const常量初始化的情況：
A f;
const A& e = f; // 這樣作e只能訪問聲明為const的函數(shù)，而不能訪問一
般的成員函數(shù)；
[思考1]： 以下的這種賦值方法正確嗎？
const A* c=new A();
A* e = c;
[思考2]： 以下的這種賦值方法正確嗎？
A* const c = new A();
A* b = c;
5. 另外const 的一些強(qiáng)大的功能在于它在函數(shù)聲明中的應(yīng)用。在一個(gè)函數(shù)聲明中，const 可以修飾函數(shù)的返回值，或某個(gè)參數(shù)；對(duì)于成員函數(shù)，還可以修飾是整個(gè)函數(shù)。有如下幾種情況，以下會(huì)逐漸的說明用法：A& operator=(const A& a);
void fun0(const A* a );
void fun1( ) const; // fun1( ) 為類成員函數(shù)
const A fun2( );
1） 修飾參數(shù)的const，如 void fun0(const A* a ); void fun1(const A& a);
調(diào)用函數(shù)的時(shí)候，用相應(yīng)的變量初始化const常量，則在函數(shù)體中，按照const所修飾的部分進(jìn)行常量化，如形參為const A* a，則不能對(duì)傳遞進(jìn)來的指針的內(nèi)容進(jìn)行改變，保護(hù)了原指針?biāo)赶虻膬?nèi)容；如形參為const A& a，則不能對(duì)傳遞進(jìn)來的引用對(duì)象進(jìn)行改變，保護(hù)了原對(duì)象的屬性。
[注意]：參數(shù)const通常用于參數(shù)為指針或引用的情況，且只能修飾輸入?yún)?shù);若輸入?yún)?shù)采用“值傳遞”方式，由于函數(shù)將自動(dòng)產(chǎn)生臨時(shí)變量用于復(fù)制該參數(shù)，該參數(shù)本就不需要保護(hù)，所以不用const修飾。
[總結(jié)]對(duì)于非內(nèi)部數(shù)據(jù)類型的輸入?yún)?shù)，因該將“值傳遞”的方式改為“const引用傳遞”，目的是為了提高效率。例如，將void Func(A a)改為void Func(const A &a)
對(duì)于內(nèi)部數(shù)據(jù)類型的輸入?yún)?shù)，不要將“值傳遞”的方式改為“const引用傳遞”。否則既達(dá)不到提高效率的目的，又降低了函數(shù)的可理解性。例如void Func(int x)不應(yīng)該改為void Func(const int &x)
2） 修飾返回值的const，如const A fun2( ); const A* fun3( );
這樣聲明了返回值后，const按照"修飾原則"進(jìn)行修飾，起到相應(yīng)的保護(hù)作用。const Rational operator*(const Rational& lhs, const Rational& rhs)
{
return Rational(lhs.numerator() * rhs.numerator(),
lhs.denominator() * rhs.denominator());
}
返回值用const修飾可以防止允許這樣的操作發(fā)生:Rational a,b;
Radional c;
(a*B) = c;
一般用const修飾返回值為對(duì)象本身（非引用和指針）的情況多用于二目操作符重載函數(shù)并產(chǎn)生新對(duì)象的時(shí)候。
[總結(jié)]
1. 一般情況下，函數(shù)的返回值為某個(gè)對(duì)象時(shí)，如果將其聲明為const時(shí)，多用于操作符的重載。通常，不建議用const修飾函數(shù)的返回值類型為某個(gè)對(duì)象或?qū)δ硞€(gè)對(duì)象引用的情況。原因如下：如果返回值為某個(gè)對(duì)象為const（const A test = A 實(shí)例）或某個(gè)對(duì)象的引用為const（const A& test = A實(shí)例） ，則返回值具有const屬性，則返回實(shí)例只能訪問類A中的公有（保護(hù)）數(shù)據(jù)成員和const成員函數(shù)，并且不允許對(duì)其進(jìn)行賦值操作，這在一般情況下很少用到。
2. 如果給采用“指針傳遞”方式的函數(shù)返回值加const修飾，那么函數(shù)返回值（即指針）的內(nèi)容不能被修改，該返回值只能被賦給加const 修飾的同類型指針。如：
const char * GetString(void);
如下語句將出現(xiàn)編譯錯(cuò)誤：
char *str=GetString();
正確的用法是：
const char *str=GetString();
3. 函數(shù)返回值采用“引用傳遞”的場合不多，這種方式一般只出現(xiàn)在類的賻值函數(shù)中，目的是為了實(shí)現(xiàn)鏈?zhǔn)奖磉_(dá)。如：
class A
{…
A &operate = (const A &other); //賦值函數(shù)
}
A a,b,c; //a,b,c為A的對(duì)象
…
a=b=c; //正常
(a=B)=c; //不正常，但是合法
若負(fù)值函數(shù)的返回值加const修飾，那么該返回值的內(nèi)容不允許修改，上例中a=b=c依然正確。(a=B)=c就不正確了。
[思考3]： 這樣定義賦值操作符重載函數(shù)可以嗎？
const A& operator=(const A& a);
6. 類成員函數(shù)中const的使用
一般放在函數(shù)體后，形如：void fun() const;
任何不會(huì)修改數(shù)據(jù)成員的函數(shù)都因該聲明為const類型。如果在編寫const成員函數(shù)時(shí)，不慎修改了數(shù)據(jù)成員，或者調(diào)用了其他非const成員函數(shù)，編譯器將報(bào)錯(cuò)，這大大提高了程序的健壯性。如：
class Stack
{
public:
void Push(int elem);
int Pop(void);
int GetCount(void) const; //const 成員函數(shù)
private:
int m_num;
int m_data[100];
};
int Stack::GetCount(void) const
{
++m_num; //編譯錯(cuò)誤，企圖修改數(shù)據(jù)成員m_num
Pop(); //編譯錯(cuò)誤，企圖調(diào)用非const函數(shù)
Return m_num;
}
7. 使用const的一些建議
1 要大膽的使用const，這將給你帶來無盡的益處，但前提是你必須搞清楚原委；
2 要避免最一般的賦值操作錯(cuò)誤，如將const變量賦值，具體可見思考題；
3 在參數(shù)中使用const應(yīng)該使用引用或指針，而不是一般的對(duì)象實(shí)例，原因同上；
4 const在成員函數(shù)中的三種用法（參數(shù)、返回值、函數(shù)）要很好的使用；
5 不要輕易的將函數(shù)的返回值類型定為const;
6除了重載操作符外一般不要將返回值類型定為對(duì)某個(gè)對(duì)象的const引用;
[思考題答案]
1 這種方法不正確，因?yàn)槁暶髦羔樀哪康氖菫榱藢?duì)其指向的內(nèi)容進(jìn)行改變，而聲明的指針e指向的是一個(gè)常量，所以不正確；
2 這種方法正確，因?yàn)槁暶髦羔標(biāo)赶虻膬?nèi)容可變；
3 這種做法不正確；
在const A::operator=(const A& a)中，參數(shù)列表中的const的用法正確，而當(dāng)這樣連續(xù)賦值的時(shí)侯，問題就出現(xiàn)了：
A a,b,c:
(a=B)=c;
因?yàn)閍.operator=(B)的返回值是對(duì)a的const引用，不能再將c賦值給const常量。
給定 P=a1×a2×a3×……×an，依據(jù)乘法結(jié)合律，不改變其順序，只用括號(hào)表示成對(duì)的乘積，試問有幾種括號(hào)化的方案
n=4的例子如下
假設(shè)這個(gè)數(shù)是h(n-1), （這里之所以是n-1，是因?yàn)閷?shí)際上n指的是元素個(gè)數(shù)，每2個(gè)元素乘一次，只要n-1次就可以乘完)
那么顯然h(n-1)=h(0)h(n-2)+h(1)h(n-3)+...+h(n-2)h(0)
對(duì)應(yīng)的例子則是
a(b(cd)) a((bc)d) h(0)h(n-2) (只要先對(duì)右邊的n-2個(gè)元素進(jìn)行乘積，接著再跟最左邊的元素相乘，h(0)=1）
(ab)(cd) h(1)h(n-3) (先乘最左邊的2個(gè)元素，再乘最右邊的n-3個(gè)元素，之后再把這2個(gè)元素相乘）
(a(bc))d ((ab)c)d h(n-2)h(0)
從括號(hào)化展開的應(yīng)用
1. 進(jìn)出棧
對(duì)括號(hào)進(jìn)行進(jìn)出棧的模擬，左括號(hào)代表進(jìn)棧，右括號(hào)代表進(jìn)行出棧，那么進(jìn)出棧的順序就相當(dāng)于括號(hào)化的方案
2.三角剖分
三角剖分就是從距陣乘法類比過來的，而距陣乘法就是括號(hào)化的問題