6. STL容器(page143)

C++標準程序庫還提供了一些特殊容器類別——即 容器配接器(container adapter，包括stack副砍、queue修档、priority queue)赌髓，以及bitset和valarray咒锻。
這些容器都有特殊接口冷冗，不滿足STL容器的一般要求。

6.1 容器的共通性

8.1.1 容器的共通能力(page144)

所有STL容器三個核心能力：

1.所有容器提供的是value語意惑艇。
    進行插入操作時蒿辙，內(nèi)部是拷貝操作，故STL容器元素須能被拷貝敦捧。
    若要存放的對象沒有public copy構(gòu)造函數(shù)须板，
        或要存放的對象不是副本(eg是被多個容器共同容納的元素)，
        那容器元素只能是指針(指向?qū)ο?兢卵。

2.總體上所有元素形成一個次序，即可按相同次序一次或多次遍歷每個元素绪颖。
    所有容器都提供“可返回迭代器”的函數(shù)秽荤，運用這些迭代器可遍歷元素甜奄。

3.一般各項操作并非絕對安全。調(diào)用者須保證傳遞的函數(shù)參數(shù)符合要求窃款。

6.1.2 容器的共同操作(page145)

p145_t6-1.png

以下操作為所有容器共有课兄，但前提是滿足上述核心能力：

• 初始化(initialization)

每個容器類別都有一個default構(gòu)造函數(shù)、一個copy構(gòu)造函數(shù)和一個析構(gòu)函數(shù)晨继。
可用某已知區(qū)間的內(nèi)容作為容器初值烟阐，
   負責此工作的構(gòu)造函數(shù)從另一容器或數(shù)組或標準輸入裝置得到元素并構(gòu)造處容器。
   這些構(gòu)造函數(shù)是mumber template紊扬，故若提供了從“源端”到“目標端”的元素型別自動裝換蜒茄，
      那容器類別和元素型別都可不同。

eg1: 以另一容器元素為初值完成初始化操作
std::list<int> I;  // I is a linked list of ints
// ...
// copy all elements of the list as floats into a vector
std::vector<float> c(I.begin(), I.end());

eg2:以某數(shù)組元素為初值完成初始化操作
int array[] = { 2, 3, 17, 33, 45, 77 };
// ...
// copy all elements of the array into a set
std::set<int> c(array, array + sizeof(array)/sizeof(array[0] );

eg3:以標準輸入完成初始化操作
// read all integer elements of the deque from standard input
std::deque<int> c( ( std::istream_iterator<int>(std::cin) ),
                   ( std::istream_iterator<int>() ) );

note: eg3不能遺漏了“初始化參數(shù)”的那對多余的括號餐屎，否則該語句就會變成一個函數(shù)聲明：

若eg3不寫括號：
std::deque<int> c( std::istream_iterator<int>(std::cin),
                   std::istream_iterator<int>() );
會是一個返回值為deque<int>的函數(shù)檀葛，其第一參數(shù)型別為istream_iterator<int>參數(shù)名cin，
    其第二參數(shù)是型別為一個不接受參數(shù)腹缩、返回值型別為istream_iterator<int>的函數(shù)屿聋。
    據(jù)C++規(guī)則其被視為聲明。

• 與大小相關(guān)的函數(shù)操作(size operation)

1. size(): 返回當前容器的元素數(shù)量藏鹊。
2. empty(): 即size()==0表達式的快捷形式润讥。
          但empty()的實現(xiàn)可能比size()==0效率更高。
3. max_size(): 返回容器所能容納的最大元素數(shù)量盘寡。
       其值因具體實現(xiàn)版本而不同象对。
      如vector通常是一個內(nèi)存塊包含全部元素，故在PC上可能有相關(guān)限定宴抚。
    max_size()通常返回索引型別的最大值勒魔。

• 比較(comparison)
  含常用比較操作符==、!=菇曲、<冠绢、<=、>常潮、>=弟胀。它們的定義依據(jù)以下三條規(guī)則：

1. 比較操作的兩端(兩容器)須型別相同。
2. 若兩容器所有元素對應位置相等喊式，則這兩容器相等孵户。
3. 用字典式(lexicographical)順序比較原則來判斷某容器是否小于另一容器。(見page360)

• assignment and swap

對容器賦值元素岔留，源容器所有元素被拷貝到目標容器夏哭，后者所有元素被移除，故容器賦值操作代價高献联。

若兩容器類別相同竖配，且拷貝后源容器不再使用何址，則可使用一個優(yōu)化方法： 
    swap()。其時間復雜度為常數(shù)进胯。
    因為swap()事實上只交換某些內(nèi)部的指針(指向?qū)嶋H數(shù)據(jù)如元素用爪、配置器、排序準則)胁镐。

6.2 vector(page148)

vector是一個動態(tài)數(shù)組偎血。
因此，其本身是”將元素置于動態(tài)數(shù)組中加以管理“的一個抽象概念盯漂。

使用vector颇玷，須包含頭文件<vector>:#include <vector>
  其中型別vector是一個定義于namespace std內(nèi)的template：
namespace std
{
    template <class T, class Allocator = allocator<T> >
    class vector;
}

vector的元素可為任意型別T，但須能assignment和copyable兩個性質(zhì)宠能。
  第二個參數(shù)可有可無亚隙，用于定義內(nèi)存模型，缺省的內(nèi)存模型是C++標準程序庫提供的allocator违崇。

6.2.1 vector能力(page149)

vector支持隨機存劝⑵；vector迭代器是隨機存取迭代器羞延。
末端增刪元素渣淳，性能好。但首部或中部增刪元素性能低伴箩，
    由于增刪點后每個元素需移動入愧，而每次移動要調(diào)用assignment操作符。

大小(size)和容量(capacity)

vector優(yōu)異性能秘訣之一：配置比其所容納元素所需更多的內(nèi)存嗤谚。
capacity()：返回實際能容納的元素數(shù)量棺蛛。
          若超過這個數(shù)量，vector就須重新配置內(nèi)部存儲器巩步。

vector容量的重要性旁赊，原因如下：
1. 內(nèi)存重新配置會導致和vector元素有關(guān)的所有reference、pointer椅野、iterator都失效终畅。
2. 內(nèi)存重新配置時耗很高。

內(nèi)存重配(配置)方法：

1. reserve()保留適當容量竟闪，以避免一再重配內(nèi)存离福。
      如此只要保留的容量有余，就不會使reference失效炼蛤。eg:
std::vector<int> v;  // create an empty vector
v.reserve(80);  // reserve memory for 80 elements

2. 初始化期間向構(gòu)造函數(shù)傳遞附加參數(shù)妖爷，以構(gòu)造足夠空間。
      若該附加參數(shù)是數(shù)值鲸湃，該數(shù)則為vector的起始大小赠涮。
std::vector<T> v(5);  // create a vector and initializes it with five values
                      // calls five times the default constructor of type T

note:若用初始化方法配置內(nèi)存子寓，前提是容器的元素型別須有default構(gòu)造函數(shù)暗挑。
若型別很復雜笋除，就算提供了default ctor，初始化操作也很耗時炸裆。若只是為了保留足夠內(nèi)存垃它，不如使用reserve()。

但是烹看，vector不能使用reserve()來縮減內(nèi)存容量：

vector容量概念上和string類似国拇，vector不能用reserve()來縮減容量，這和string不同惯殊。
    若調(diào)用reserve()所給的參數(shù)比當前vector容量小酱吝，不會有任何反應。

如何達到時間和空間的最佳效率土思，由具體實現(xiàn)版本決定务热。

且vector內(nèi)存容量不會縮減，但有個間接縮減vector容量的方法：兩個vector交換內(nèi)容后己儒，兩者的容量也會互換崎岂。eg:

template <class T>
void shrinkCapacity (std::vector<T>& v)
{
    std::vector<T> tmp(v);    // copy elements into a new vector
    v.swap(tmp);  // swap internal vector data
}

或者使用如下語句直接縮減容量：
// shrink capacity of vector v for type T
std::vector<T>(v).swap(v);

swap()操作后原有reference、pointer闪湾、iterator都換了指向?qū)ο蟪甯剩磿А?/p>

6.2.2 vector的操作函數(shù)(page150)

• 構(gòu)造、拷貝和析構(gòu)

  
  
  p150_t6-2.png

• 非變動性操作(Nonmodifying Operation)

  
  
  p151_t6-3.png
  
  

  reserve()確實會modify vector途样，會使reference江醇、pointer、iterator失效何暇，但從邏輯內(nèi)容上容器沒變化陶夜，所以還是列在此處。

• 賦值(Assignment)
  

  p151_t6-4.png
  
  所有賦值操作都可能會調(diào)用元素型別的default ctor赖晶、copy ctor律适、assignment操作符以及可能析構(gòu)函數(shù)，視元素數(shù)量變化而定,eg：

std::list<Elem> l;
std::vector<Elem> col1;
// ...
// make col1 be a copy of the contents of l
col1.assign(l.begin(), l.end() );

• 元素存取(Element Access)(page152)

  
  
  p152_t6-5.png
  
  

  若發(fā)生越界遏插，沒有范圍檢查會引發(fā)未定義行為捂贿。

std::vector<Elem> col1;  // empty
col1[5] = elem;  // RUNTIME ERROR --> undefined behavior
std::cout << col1.front();  // RUNTIME ERROR --> undefined behavior

故調(diào)用operator[]時，確保索引有效：
std::vector<Elem> col1;  // empty
if(col1.size() >5)
{
    col1[5] = elem;  // OK
}
if (!col1.empty() )
{
    cout << col1.front();  // OK
}
col1.at(5) = elem;  // throws out_of_range exception

• 迭代器相關(guān)函數(shù)(Iterator Function)
  
  p153_t6-6.png
  
  迭代器的確切型別有實現(xiàn)版本決定胳嘲。對vector而言通常是一般指針厂僧。一般指針就是隨機存取迭代器。

vector迭代器持續(xù)有效了牛，除非發(fā)生如下兩種情況：
1. 在一個較小索引位置增刪元素颜屠。
2. 由于容量變化而致的內(nèi)存重配辰妙。

• 插入(insert)和刪除(remove)元素(page153)
  性能方面，以下情況稍好：

1. 容器尾部增刪元素
2. 容器容量起初就足夠大
3. 插入多個元素時甫窟，”調(diào)用一次“比”調(diào)用多次“要快

p154_t6-7.png

vector未提供函數(shù)用于直接移除”與某值相等“的所有元素密浑。則應使用算法了，如下語句可將值val的所有元素移除:

std::vector<Elem> col1;
// ...
// remove all elements with value val
col1.erase( remove(col1.begin(), col1.end(), val), col1.end() );

詳解可見page111
若只是移除”與某值相等“的第一個元素：

std::vector<Elem> col1;
// ...
// remove first element with value val
std::vector<Elem>::iterator pos;
pos = find(col1.begin(), col1.end(), val );
if (pos != col1.end() )
{
    col1.erase(pos);
}

6.2.3 將vector當做一般array使用

若需要一個動態(tài)數(shù)組粗井，即可用vector搜锰，但須確保vector大小能容納所有數(shù)據(jù)媳叨。
eg:使用C-String闻丑，記住最后有個'\0'十兢。
    即若需一個元素型別為T的數(shù)組，就vector<T>耘擂，然后傳遞第一元素的額地址給它胆剧。

note:不能把迭代器當做第一元素的地址來傳遞。vector迭代器由實現(xiàn)版本定義的醉冤，或許不是一個指針秩霍。

6.2.4 異常處理(page155)

使用vector調(diào)用的函數(shù)拋出異常，C++標準程序庫保證：

1.push_back()時發(fā)生異常冤灾，該函數(shù)不起作用前域。
2.若元素拷貝(包括copy ctor和assignment操作符)不拋出異常，要么insert()成功韵吨，要么不生效匿垄。
3.pop_back()不會拋出異常。
4.若元素拷貝(包括copy ctor和assignment操作符)不拋出異常归粉，則erase()和clear()不拋出異常椿疗。
5.swap()不拋出異常。
6.若元素拷貝(包括copy ctor和assignment操作符)不拋出異常糠悼，則所有操作要么成功届榄，要么無效。
    這類元素稱為POD(plain old data)倔喂。

POD泛指那些無C++特性的型別(如 C structure)铝条。
所有上述保證基于一個條件：析構(gòu)函數(shù)不拋出異常。

8.2.5 vector example

// 展示vector的簡單用法
// cont/vector1.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;

int main()
{
    // create empty vector fro strings
    vector<string> sentence;

    // reserve memory for five elements to avoid reallocation
    sentence.reserve(5);

    // append some elements
    sentence.push_back("Hello");
    sentence.push_back("how");
    sentence.push_back("are");
    sentence.push_back("you");
    sentence.push_back("?");

    // print elements separated with spaces
    copy (sentence.begin(), sentence.end(), ostream_iterator<string>(cout, " "));
    cout << endl;

    // print "technical data"
    cout << "max_size(): " << sentence.max_size() << endl;
    cout << "size(): " << sentence.size() << endl;
    cout << "capacity(): " << sentence.capacity() << endl;

    // swap second and fourth element
    swap (sentence[1], sentence[3]);

    // insert element "always" before element "?"
    sentence.insert(find(sentence.begin(), sentence.end(), "?"), "always");

    // assign "!" to the last element
    sentence.back() = "!";

    // print elements separated with space
    copy (sentence.begin(), sentence.end(), ostream_iterator<string>(cout, " "));
    cout << endl;

    // print "technical data" again
    cout << " max_size(): " << sentence.max_size() << endl;
    cout << " size(): " << sentence.size() << endl;
    cout << " capacity(): " << sentence.capacity() << endl;
}

輸出可能是：

vector1.png

6.2.6 class vector<bool>(page158)

C++標準程序庫對元素型別為bool的vector定制了特殊版本席噩，以獲取一個優(yōu)化的vector：
其耗用空間遠小于一般vector實現(xiàn)的bool vector班缰。
一般vector的實現(xiàn)會為每個元素至少分配一個byte空間，
而vector<bool>特殊版本只用1bit存儲一個元素悼枢。

由于vector<bool>大小可動態(tài)改變埠忘，故可當成動態(tài)大小的bitfield(位域)。
  如此可增刪bit。

若需要靜態(tài)大小的bitfield莹妒，應使用bitset名船。

p158_t6-8.png

namespace std
{
    class vector<bool>
    {
    public:
        // auxiliary type for subscript operator
        class reference
        {
        public:
            // automatic type conversion to bool
            operator bool() const;

            // assignments
            reference& operator= (const bool);
            reference& operator= (const reference&);

            // bit complement
            void flip();
        };
        // ...
        // operations for element access
        // - return types is reference instead of bool
        reference operator[] (size_type n);
        reference at(size_type n);
        reference front();
        reference back();
        // ...
    };
}

6.3 deque(page160)

與vector類似，采用動態(tài)數(shù)組管理元素旨怠，可隨機存取渠驼，并與vector有類似的接口。
但deque動態(tài)數(shù)組頭尾兩端都可增刪元素运吓。

同vector渴邦，deque型別定義與命名空間std內(nèi)的一個class template：
namespace std
{
    template <class T, class Allocator = allocator<T> >
    class deque;
}
與vector同疯趟，第一個template參數(shù)用于表明元素型別(只要assignable和copyable)拘哨。

6.3.1 deque能力

• 與vector相比，deque不同之處：

1. 兩端都可增刪元素信峻。
2. 存取元素時倦青，deque內(nèi)部會多一個間接過程，故元素存取及迭代器動作稍慢盹舞。
3. 迭代器需在不同區(qū)塊間跳轉(zhuǎn)产镐，故須是特殊的智能型指針。
4. 在對內(nèi)存塊有限制的系統(tǒng)中(如PC系統(tǒng))踢步，deque可內(nèi)含更多元素癣亚，
    因為它使用不止一塊內(nèi)存，故其max_size()可能更大获印。
5.不支持對容量和內(nèi)存重配的時機的控制述雾。
    除頭尾的其它位置增刪會導致deque的pointer、reference兼丰、iterator失效玻孟。
    但 deque的內(nèi)存重配優(yōu)于vector，
        因為deque在內(nèi)存重配時不必復制所有元素鳍征。
6.deque內(nèi)存區(qū)塊不再被使用時會被釋放黍翎。
      deque的內(nèi)存大小可縮減(不同版本實現(xiàn)方式不同)。

• 與vector相比艳丛，deque相似之處：

1. 中部增刪元素很慢匣掸，因為所有元素都需移動。
2. 迭代器是random access iterator氮双。

總之碰酝，以下情形優(yōu)選deque:
1. 需在兩端增刪元素。
2. 無需引用容器內(nèi)的元素眶蕉。
3. 要求容器釋放不再使用的元素砰粹。

6.3.2 deque操作(page162)

p162_t6-9.png

p162_t6-10.png

p163_t6-11.png

1. deque不提供容量操作(capacity()和reserve())。
2. deque直接提供函數(shù)用于頭部元素增刪(push_front()和pop_front())。

6.3.3 異常處理&&example(page164)

原則上deque提供的異常處理和vector一樣碱璃，因此C++標準程序庫保證：

1. 若push_back()或push_front()發(fā)生異常時弄痹，該操作不帶來任何影響。
2. pop_back()和pop_front()不會拋出異常嵌器。

// 展示deque的簡單運用

// cont/deque1.cpp

#include <iostream>
#include <deque>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;

int main()
{
    // create empty deque of strings
    deque<string> col1;

    // insert several elements
    col1.assign(3, string("string"));
    col1.push_back("last string");
    col1.push_front("first string");

    // print elements separated by newlines
    copy(col1.begin(), col1.end(), ostream_iterator<string>(cout, "\n"));
    cout << endl;

    // remove first and last elements
    col1.pop_front();
    col1.pop_back();

    // insert "another" into every element but the first
    for (int i = 1; i < col1.size(); ++i)
    {
        col1[i] = "another " + col1[i];
    }

    // change size to four elements
    col1.resize (4, "resized string");

    // print elements separated by newlines
    copy (col1.begin(), col1.end(), ostream_iterator<string>(cout, "\n"));
    cout << endl;
}

deque1.png

6.4 list(page166)

list是double linked list(雙向鏈表)肛真。
list型別定義于namespace std中，是class template：

namespace std
{
    template <class T, class Allocator = allocator<T> >
    class list;
}

6.4.1 list能力

list由于內(nèi)部結(jié)構(gòu)和vectror/deque不同爽航，故特性不同：

1. 不支持隨機存取蚓让。只能順序遍歷。
2. 任何位置增刪很快讥珍，無需移動元素历极。
      且增刪元素不會使pointer、reference衷佃、iterator失效趟卸。
3. list對于異常處理方式：操作要么成功，要么無效氏义。

list提供的成員函數(shù)反映它和vector/deque的不同：

1. 由于不支持隨機存取锄列，故不提供下標操作符和at()。
2. 各元素都有自己的內(nèi)存惯悠，被刪除前一直有效邻邮，故無容量、內(nèi)存重配操作克婶。
3. 提供了一些特殊成員函數(shù)以移動元素(調(diào)整指針)筒严。

6.4.2 list 操作(page167)

p167_t6-12.png

p168_t6-13.png

p168_t6-14.png

p168_t6-15.png

只有運用迭代器才能存取list中各個元素。

p169_t6-16.png

為移除元素鸠补，list配備了remove()的特殊版本萝风，該成員函數(shù)比remove()算法要快(只有指針操作，無需顧及元素)紫岩。
故移除元素應用成員函數(shù)remove()而不是像vector/deque調(diào)用STL算法的remove()规惰。

p170_t6-17.png

• splice 函數(shù)

  
  
  p171_t6-18.png

6.4.3 異常處理&&example(page172)

p172_t6-19.png

// 展示list特殊成員函數(shù)的用法
// cont/list1.cpp

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>
using namespace std;

void printLists (const list<int>& l1, const list<int>&l2)
{
    cout << "list: ";
    copy (l1.begin(), l1.end(), ostream_iterator<int>(cout, " "));
    cout << endl << "list2: ";
    copy (l2.begin(), l2.end(), ostream_iterator<int>(cout," "));
    cout << endl << endl;
}

int main()

{
     // create two empty lists
     list<int> list1, list2;

     // fill both lists with elements
     for (int i = 0; i < 6; ++i)
     {
        list1.push_back(i);
        list2.push_front(i);
     }
     printLists(list1, list2);

    // insert all elements of list1 before the first element with value 3 of list2
    // - find() returns an iterator to the first element with value 3
    list2.splice(find(list2.begin(), list2.end(), 3),   // destination positon
            list1); // source list
    printLists(list1, list2);

    // move first element to the end
    list2.splice(list2.end(),   // destination position
            list2,  // source list
            list2.end());   // source position
    printLists(list1, list2);

    // sort second list, assign to list1 and remove duplicates
    list2.sort();
    list1 = list2;
    list2.unique();
    printLists(list1, list2);

    // merge both sorted lists into the first list
    list1.merge(list2);
    printLists(list1, list2);
}

list1.png

6.5 set and multiset(page175)

6.5.1 set/multiset能力

set和multiset會根據(jù)特定排序準則自動對元素排序，set不允許重復值而multiset允許泉蝌。二者定于于namespace std中的class template：

namespace std
{
    template <class T, 
              class Compare = less<T>,
              class Allocator = allocator<T> > 
    class set;

    template <class T, 
              class Compare = less<T>,
              class Allocator = allocator<T> > 
    class set;
}

滿足assignable歇万、copyable、comparable(根據(jù)特定排序準則)的型別T勋陪，都可稱為set/multiset的元素型別贪磺。
仿函數(shù)less以operator<比較元素。

6.5.2 set和multiset操作(page177)

與所有標準關(guān)聯(lián)式容器類似诅愚，set/multiset通常以平衡二叉樹實現(xiàn)寒锚。
自動排序優(yōu)勢在于二叉樹查找的良好性能。
但自動排序?qū)et/multiset的限制：不能直接改變元素值(否則會打亂原本正確順序)，要易值須先刪除舊元素刹前，再插入新元素泳赋。提供的接口反映此行為：

set/multiset不提供直接存取元素的操作。
通過迭代器存取元素喇喉，有限制：從迭代器角度看祖今，元素值是常數(shù)。

p177_t6-20.png

p179_t6-21.png

// 展示使用 lower_bound()掸绞、upper_bound()泵三、equal_range()
// cont/set2.cpp

#include <iostream>
#include <set>
#include <iterator>
using namespace std;

int main()
{
    set<int> c;

    c.insert(1);
    c.insert(2);
    c.insert(4);
    c.insert(5);
    c.insert(6);

    cout << "lower_bound(3): " << *c.lower_bound(3) << endl;
    cout << "upper_bound(3): " << *c.upper_bound(3) << endl;
    cout << "equal_range(3): " << *c.equal_range(3).first << " "
                                << *c.equal_range(3).second << endl;

    cout << endl;
    cout << "lower_bound(5): " << *c.lower_bound(5) << endl;
    cout << "upper_bound(5): " << *c.upper_bound(5) << endl;
    cout << "equal_range(5): " << *c.equal_range(5).first << " "
                                << *c.equal_range(5).second << endl;
}

set2.png

若用multiset，輸出相同衔掸。

p182_t6-23.png

p182_t6-24.png

p183_t6-25.png

set:
pair<iterator,bool> insert(const value_type& elem);
iterator  insert(iterator pos_hint, const value_type& elem);

multiset:
iterator insert(const value_type& elem);
iterator insert(iterator pos_hint, const value_type& elem);

返回型別不同原因：multiset允許元素重復而set不允許侣颂，若insert一個元素到set中档桃，而set內(nèi)已存在該元素，則插入操作失敗憔晒，所以set返回pair型別藻肄，其second成員表插入成功否，first成員表新元素位置或現(xiàn)存同值元素位置拒担。
注：所有擁有“位置提示參數(shù)”的插入函數(shù)嘹屯，其返回型別都一樣即一個迭代器。

還用一個返回型別不一致的情況：作用于序列式容器和關(guān)聯(lián)式容器的erase()函數(shù)：

1.序列式容器erase()成員函數(shù)：
  iterator erase(iterator pos);
  iterator erase(iterator beg, iterator end);
2. 關(guān)聯(lián)式容器erase()成員函數(shù)：
  void erase(iterator pos);
  void erase(iterator beg, iterator end);

6.5.3 exception handling

set/multiset是“以節(jié)點為基礎(chǔ)”的容器从撼。若節(jié)點構(gòu)造失敗州弟，則容器保持原樣。
另，由于析構(gòu)函數(shù)通常不拋出異常婆翔，所以節(jié)點的移除不可能失敗桐经。
詳見page139 5.11.2和p248 6.10.10的“異常出現(xiàn)時的特殊保證”。

6.5.4 example(page186)

example of set:

// 展示set用法
// cont/set1.cpp

#include <iostream>
#include <set>
#include <iterator>
using namespace std;

int main()
{
    /* type of the collection:sets:
     * - no duplicates
     * - elements are integral values
     * - descending order
     */
    typedef set<int, greater<int> > IntSet;
    IntSet coll1;   // empty set container

    // insert elements in random order
    coll1.insert(4);
    coll1.insert(3);
    coll1.insert(5);
    coll1.insert(1);
    coll1.insert(6);
    coll1.insert(2);
    coll1.insert(5);

    // iterator over all elements and print them
    IntSet::iterator pos;
    for(pos = coll1.begin(); pos != coll1.end(); ++pos)
    {
        cout << *pos << " ";
    }
    cout << endl;

    // insert 4 again and process return value
    pair<IntSet::iterator, bool> status = coll1.insert(4);
    if (status.second)
    {
        cout << " 4 inserted as element "
            << distance(coll1.begin(), status.first) + 1
            << endl;        
    }
    else
    {
        cout << " 4 already exist " << endl;
    }

    // assign elements to another set with ascending order
    set<int> coll2(coll1.begin(), coll1.end());

    // print all elements of the copy
    copy (coll2.begin(), coll2.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    // remove all elements up to elements with value 3
    coll2.erase(coll2.begin(), coll2.find(3));

    // remove all elements with value 5
    int num;
    num = coll2.erase(5);
    cout << num << " element(s) removed " << endl;

    // print all elements 
    copy (coll2.begin(), coll2.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
}

set1.png

example of multiset:

// 相比較于set1.cpp浙滤，要做寫改變并得到不同結(jié)果
// cont/mset1.cpp

#include <iostream>
#include <set>
#include <iterator>
using namespace std;

int main()
{
    /* type of collection: sets
     * - duplicates allowed
     * - elements are integral values
     * - descending order
     */
    typedef multiset<int, greater<int> > IntSet;

    IntSet coll1;   // empty multiset container

    // insert elements in random order
    coll1.insert(4);
    coll1.insert(3);
    coll1.insert(5);
    coll1.insert(1);
    coll1.insert(6);
    coll1.insert(2);
    coll1.insert(5);

    // iterate over all elements and print them
    IntSet::iterator pos;
    for (pos = coll1.begin(); pos != coll1.end(); ++pos)
    {
        cout << *pos << " ";
    }
    cout << endl;

    // insert 4 again and process return value
    IntSet::iterator ipos = coll1.insert(4);
    cout << " 4 inserted as element "
        << distance(coll1.begin(), ipos) + 1 
        << endl;
    
    // assign elements to another multiset with ascending order
    multiset<int> coll2(coll1.begin(), coll1.end());

    // print all elements of the copy
    copy (coll2.begin(), coll2.end(), ostream_iterator<int>(cout," "));
    cout << endl;

    // remove all elements  up to element with value 3
    coll2.erase(coll2.begin(), coll2.find(3));

    // remove all element with value 5
    int num;
    num = coll2.erase(5);
    cout << num << " element(s) removed " << endl;

    // print all elements
    copy(coll2.begin(), coll2.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
}

mset1.png

6.5.5 運行時指定排序準則(page191)

有時需要在運行時處理排序準則阴挣，就需要一個“表示排序準則”的特殊型別，使能在運行時傳遞某準則纺腊，eg:

// 運行時處理排序準則
// cont/setcmp.cpp

#include <iostream>
#include <set>
#include <iterator>
#include "../stl/print.hpp"
using namespace std;

// type for sorting criterion
template <class T>
class RuntimeCmp
{
    public:
        enum cmp_mode{normal, reverse};

    private:
        cmp_mode mode;

    public:
        // constructor for sorting criterion
        // - default criterion uses value normal
        RuntimeCmp (cmp_mode m = normal) : mode(m){}

        // comparision of elements
        bool operator() (const T& t1, const T& t2) const 
        {
            return mode == normal ? t1 < t2 : t2 < t1;
        }

        // comparision of sorting criteria
        bool operator== (const RuntimeCmp& rc)
        {
            return mode == rc.mode;
        }
};

// type of a set that uses this sorting criterion
typedef set<int, RuntimeCmp<int> > IntSet;

// forward declaration
void fill (IntSet& set);

int main()
{
    // create, fill , and print set with normal element order
    // - uses default sorting criterion
    IntSet coll1;
    fill(coll1);
    PRINT_ELEMENTS(coll1,"coll1: ");

    // create sorting criterion with reverse element order
    RuntimeCmp<int> reverse_order(RuntimeCmp<int>::reverse);

    // create , fill , and print set with reverse element order
    IntSet coll2(reverse_order);
    fill(coll2);
    PRINT_ELEMENTS(coll2, "coll2: ");

    // assign elements and sorting criterion
    coll1 = coll2;
    coll1.insert(3);
    PRINT_ELEMENTS(coll1, "coll1: ");

    // just to make sure ...
    if (coll1.value_comp() == coll2.value_comp())
    {
        cout << "coll1 and coll2 have some sorting criterion" << endl;
    }
    else
    {
        cout << "coll1 and coll2 have different sorting criterion" << endl;
    }
}

void fill (IntSet& set)
{
    // fill insert elements in random order
    set.insert(4);
    set.insert(7);
    set.insert(5);
    set.insert(1);
    set.insert(6);
    set.insert(2);
    set.insert(5);
}

output:

setcmp.png