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