3.13. Hello STL 列表篇

vector是一種容器。我們還知道，vector其實(shí)是一個(gè)“類模板”，具體使用前，必須通過以下語法指定將要存儲的元素類型：

vector<元素類型>

這就是決定了vector是一個(gè)“通用”的容器，如果元素類型是“Beauty”，那么它就是一個(gè)裝美女的容器，如果元素類型是“Money”，那么它就是裝錢的容器。

“列表/list” 也是一種容器，同樣，list也是一個(gè)“類模板”，具體使用前，必須通過以下語法指定將要存儲的元素類型：

list <元素類型>

看來list也是一種通用容器——或許你想問：既生vector，何生list呢？

3.13.1. vector VS. list

最簡單的回答是：list和vector的結(jié)構(gòu)不同，因此決定了它們在能力分工上的不同。且先說說生活中的容器。桶是圓柱體，柜子是立方體，這就叫“結(jié)構(gòu)不同的容器”。在設(shè)計(jì)上，圓柱體的桶，有利于用最少的材質(zhì)，制造出最大容量的桶，而柜子正好相反，如果家里所有衣柜、書柜等等全部是圓柱體，那么它們將憑空浪費(fèi)掉屋子的很多空間。

因此，雖然容器的功能粗一看就是“存放元素”，但是，由于要存放的元素自身結(jié)構(gòu)不同，或者外部對容器的遍歷方式不同等原因，我們不得不需要有多種“功能傾向”明顯不同的容器。比如vector和list。

vector最大的結(jié)構(gòu)特點(diǎn)是：它開辟連續(xù)的內(nèi)存空間用以存儲元素。而list正好相反，它允許使用不連續(xù)內(nèi)存空間。

假設(shè)你想在熱鬧的市區(qū)蓋5間房子，有兩種方案，第一種方案把5間房連續(xù)蓋在一起，這會讓你生活很方便，但你需要一大塊地皮，可能市政府不會滿足你，為了你這一塊地，可能要拆牽別人許多房；第二種方案你同意把五間房分開蓋，這會給生活帶來一定不便，但現(xiàn)在你只需在市區(qū)見縫插針地找到5塊小地皮，就可以動工了。

第一種方案正是vector分配內(nèi)存的策略，第二種方案則是list分配內(nèi)存的策略。由此，我們可以得出第一個(gè)“猜想”：如果我們有一大堆對象，并且這些對象個(gè)頭都很大，那么我們就必須考慮是否放棄采用vector直接存儲？

作為代替方案，有兩種，其一是仍然采用vector存儲，但存放的元素改成是“堆對象”，也就是說將每個(gè)對象創(chuàng)建在“堆內(nèi)存區(qū)”中，而容器中僅僅保存對象在“堆內(nèi)存”中的地址。這個(gè)方案不足之處是：由于“堆對象”我們必須手工“殺死它們”，所以會帶來額外的內(nèi)存管理工作。其二，我們可以采用list容器進(jìn)行管理。list允許我們?nèi)匀粚?shù)據(jù)保存在“棧內(nèi)存區(qū)”中，不過必須將每個(gè)元素分開保存，從而有利于分配出足夠的內(nèi)存。

當(dāng)然，“內(nèi)存分配”并不是我們考慮是否采用list的唯一因素——如果非要找一個(gè)vector的代替方案，STL中的deque容器可能更適合——更為重要的考慮對元素的訪問，包括讀取元素、添加元素、插入元素、刪除元素的方式，及其代價(jià)。

比如“插入元素”：在vector模式下：你有三間緊密蓋在一起的房子，現(xiàn)在你想在第1、2間房子中插入一間新房子——老天，這在現(xiàn)實(shí)中幾乎難以實(shí)現(xiàn)。聽說有一種“樓房平移”技術(shù)，允許在地基下安裝輪子，然后以極慢的，比如一天1厘米的速度，將樓房不知不覺地挪開數(shù)米……

vector采用連續(xù)內(nèi)存保存元素，因此當(dāng)需要在中間插入元素時(shí)，同樣需要將插入點(diǎn)之后的所有元素往后“平移”，有時(shí)甚至需要將整個(gè)內(nèi)存摧毀重建。類似的，在vector中刪除元素的代價(jià)也非常之大。由此我們得出第二個(gè)“猜想”：如果你在存儲對象的同時(shí)，還需要經(jīng)常插入、刪除位于中部的元素，那么采用vector也是不合適的。這時(shí)候又可以考慮list，因?yàn)閘ist中的元素，東一個(gè)西一個(gè)，元素之間存在不是“物理”的，而是“邏輯”上的次序關(guān)系。要在所謂“中間位置”插入一個(gè)元素，易如反掌。

“猜想”到此結(jié)束，還是直接了解一下list的結(jié)構(gòu)吧。

3.13.2. 基礎(chǔ)

(圖 39 list 內(nèi)存結(jié)構(gòu)示意)

• 每個(gè)方格表示一塊內(nèi)存區(qū)域，其中黑色部分表示已經(jīng)被其它數(shù)據(jù)占用的內(nèi)存塊（釘子戶）。
• A、B、C三個(gè)元素依次加入list中，分別“見縫插針”地占用三塊地盤，從圖示可看，這三塊內(nèi)存并不連續(xù)，甚至連次序也沒有保證。
• 每個(gè)數(shù)據(jù)加入list時(shí)，不僅要占用自身需要的影子，而且要額外占用兩塊小內(nèi)存，分別用來保存“前一元素的地址”和“后一元素的地址”，即圖示中的“前”、“后”。
• 圖中箭頭表示：A的后一元素是B，B的后一元素是C；C的前一元素是B；B的前一元素是A。
• A沒有前一元素，C沒有后一元素，但為了使用方便，分別將它們的“前一元素地址”和“后一元素地址”設(shè)置一個(gè)虛擬值（具體實(shí)現(xiàn)方式并無標(biāo)準(zhǔn)）。訪問這兩個(gè)虛擬值，將會導(dǎo)致未定義的行為。

現(xiàn)在，假設(shè)B左邊的那位“釘子戶”搬走，而我們正好在此時(shí)在A和B之間插入A’元素，這引起的變化是什么呢？

(圖 40 A與B之間插入A''元素)

• 原有的A、B、C三個(gè)元素不必“搬家”，仍然位于原來的位置。換句話說，往list中插入新元素（刪除也一樣），不需要移動任何原有的元素。所以速度很快。
• 變化的只是A、B中“前一元素地址”和“后一元素地址”的值，在上圖用箭頭表示，即：A的“后一元素”改為指向A’，B的“前一元素”改為指向A’。而A’則把“前一元素”指向A，“后一元素”指向B。

list可以實(shí)現(xiàn)高速地插入、刪除元素，這一點(diǎn)讓vector望塵莫及。vector僅當(dāng)在尾部“追加”元素時(shí)，才有可能因?yàn)椴槐剡w移前面元素而獲得較高速度。然而，list卻沒有vector的“隨機(jī)訪問”能力。我們無法采用“[N]”來直接訪問list中第N個(gè)元素，相反，我們只能直接訪問到第一個(gè)，或最后一個(gè)元素，然后依據(jù)“后一元素地址”，不斷往后， 或者依據(jù)“前一元素地址”不斷往前，從而遍歷每個(gè)元素。

如果你不太理解，那么想象一隊(duì)士兵，我們被規(guī)定只允許“接觸”正副班長，但卻要將球傳給中間的某個(gè)士兵時(shí)該如何辦？（提示：一隊(duì)士兵中，通常班長排頭，副班長壓尾）。

3.13.3. 迭代器/iterator概念

由于在訪問某一元素時(shí)，必須同時(shí)得到“前一元素地址”和“后一元素地址”等相關(guān)信息，因此，當(dāng)我們在訪問list時(shí)，并不是直接得到當(dāng)初存入list的裸數(shù)據(jù)（如上圖中的A、B、C），而是得到另外一種類型的數(shù)據(jù)，稱為“迭代器/Iterator”。這不僅僅是list的策略，而是STL中常規(guī)容器共有的特點(diǎn)。對于list，“迭代器”包裝了裸數(shù)據(jù)，同時(shí)又新增了用于前往“前一元素”和“后一元素”的信息。

有關(guān)迭代器的實(shí)現(xiàn)，需要觸及許多們尚未學(xué)習(xí)的C++知識。在今天，你暫時(shí)可以把迭代器當(dāng)作是對“裸數(shù)據(jù)”的一層封裝，比如一個(gè)list<Beauty>的迭代器，暫時(shí)可以理解為這樣一個(gè)結(jié)構(gòu)：

struct iterator
            {
            Beauty *ptr; //指向我們保存的“美女”元素
               iterator* next; //后一個(gè)美女的位置
               iterator* prior; //前一個(gè)美女的位置
            };
            

struct list< Beauty >
            {
            //…
            };
            

struct list< Beauty >
            {
            struct iteraotr
            {
            //…
              };
            //…
            };
            

001 #include <iostream>
            002 #include <list>
            

006 int main()
            {
            008    list<int> lst;
            ......
            

list <int> lst;
            lst.push_back(1);
            lst.push_back(2);
            list<int>::iterator  iter = lst.begin();
            int a = *iter;
            cout << a << endl; //輸出 1
            cout << *iter << endl; //同樣輸出1
            *iter = 1000;
            cout << *iter << endl; //輸出1000
            cout << a << endl; //輸出1；
            int b = *iter;
            cout << b << endl; //輸出1000;
            

lst<int>::iterator iter2 = lst.end();
            int a = *iter2; //災(zāi)難發(fā)生
            *iter2 = 100;   //災(zāi)難發(fā)生
            

lst.clear();
            lst.push_back(10);
            lst.push_back(100);
            list<int>::iterator  iter = lst.begin();
            ++iter; //iter前進(jìn)1步，指向第二個(gè)元素
            lst.insert(iter, 1); //在第二個(gè)元素的位置上，插入新元素
            

lst.clear();
            lst.push_back(10);
            lst.push_back(100);
            list<int>::iterator  iter = lst.begin();
            ++iter;
            lst.erase(iter);
            

list<int>::const_iterator  c_iter = lst.begin();  //此時(shí)調(diào)用的是常量版
            int a = *c_iter; //正確
            *c_iter = 1000;  //錯(cuò)誤！c_iter是只讀版迭代器，不允許修改它綁定的元素
            

001 for (list<int>::const_iterator c_iter = lst.begin();
            002       c_iter != lst.end();
            003       ++c_iter)
            {
            005    cout << *c_iter << endl;
            }
            

001 for (list<int>::const_reverse_iterator c_iter = lst.rbegin();
            002     c_iter  !=  (list<int>::const_reverse_iterator) lst.rend();
            ++c_iter)
            {
            cout << *c_iter << endl;
            }
            

//學(xué)生
            struct Student
            {
            unsigned int number; //學(xué)號
              string name;
            };
            //成績
            struct Score
            {
            unsigned int number; //學(xué)號
               float mark; //分?jǐn)?shù)
            };
            

#include <iostream>
            #include <list>
            #include <vector>
            #include <string>
            
            using namespace std;
            //學(xué)生
            struct Student
            {
            unsigned int number; //學(xué)號
              string name;
            };
            //成績
            struct Score
            {
            unsigned int number; //學(xué)號
               float mark; //分?jǐn)?shù)
            };
            //此處是 main() 函數(shù)的默認(rèn)實(shí)現(xiàn)，略……
            
            

//學(xué)生成績管理類
            class StudentScoreManager
            {
            public:
            void InputStudents();
            void InputScores();
            void OutputScores() const;
            private:
            vector<Student> students;
            list<Score> scores;
            };
            

void StudentScoreManager::InputStudents()
            {
            037    int number = 1; //學(xué)號從1開始
            
            while(true)
            {
            041        cout << "請輸入" << number << "號學(xué)生姓名(輸入x表示結(jié)束)：";
            string name;
            getline(cin, name);
            047        if (name == "x")
            {
            break;
            }
            052        Student student;
            053        student.number = number;
            054        student.name = name;
            056        students.push_back(student);
            058        ++number;
            }
            }
            

void StudentScoreManager::InputScores()
            {
            while(true)
            {
            unsigned int number;
            cout << "請輸入學(xué)號（輸入0表示結(jié)束）：";
            cin >> number;
            if (number == 0)
            {
            break;
            }
            //簡單判斷學(xué)號是否正確：
            078        if (number > students.size())
            {
            cout << "錯(cuò)誤：學(xué)號必須位于: 1 ~ " << students.size() << " 之間。" << endl;
            081            continue;
            }
            float mark;
            cout << "請輸入該學(xué)員成績：";
            cin >> mark;
            Score score;
            score.number = number;
            score.mark = mark;
            092        scores.push_back(score); //直接加在尾部
                }
            }
            

void StudentScoreManager::OutputScores() const
            {
            120    for (unsigned int i=0; i<students.size(); ++i)
            {
            122        unsigned int number = students[i].number; //學(xué)號
            
            cout << "學(xué)號：" << number << endl;
            cout << "姓名：" << students[i].name << endl;
            //查找成績:
            128        bool found = false;
            130        for (list<Score>::const_iterator iter = scores.begin();
            iter != scores.end();
            ++iter)
            {
            if (iter->number == number)
            {
            found = true; //找到了
            
            cout << "成績：" << iter->mark << endl;
            break;
            }
            }
            144        if (found ==false) //沒找到??
                    {
            cout << "成績：" << "查無成績。" << endl;
            }
            }
            }