vector與map...怎麼選擇

平常我們在寫程式時,經常可以用很多方法來解決
不過寫到後來,可能會因為客戶要求, 程式品質, 或者挑戰自己
而想要用比較有效率的方法
這時候,什麼是有效率的,沒比較過是不會知道的
我們在寫C++程式時,一定都知道STL,常用的排序與尋找的方法
就是vector 搭配binary_search 以及map這二個較多了

以下的程式碼(BCB5),就把這2個做了一個比較(200萬筆)
//---------------------------------------------------------------------------

#include < vcl.h >
#pragma hdrstop
#include < iostream >
#include < vector >
#include < list >
#include < map >
#include < ctime >
#include < stdio.h >
#include < time.h >
//---------------------------------------------------------------------------
#pragma argsused

using namespace std;

int main(int argc, char* argv[])
{

//vector
        vector  v;
        vector ::iterator it;

        v.push_back( 10 );

        cout << "vector container " << endl << "================" << endl << endl;
        time_t t1; time(&t1);
        for(int i=0;i<2000000;i++)
                v.push_back(i);
//            v.insert( v.begin( ) , i );
        time_t t2; time(&t2);
        cout<<" vcetor insert data , the time it takes is " << t2-t1 << " sec." << endl;

        sort(v.begin(),v.end());

        int a;
        time_t t5; time(&t5);
        for(int i=0;i<2000000;i++)
        {
            srand(time(NULL));
            a=(rand() % 2000000) +1;
            bool b1 = binary_search(v.begin(),v.end(),a);
        }
        time_t t6; time(&t6);
        cout<<" vcetor search data , the time it takes is " << t6-t5 << " sec." << endl;


        time_t t3; time(&t3);
        v.erase (v.begin(),v.begin()+2000000);
        time_t t4; time(&t4);
        cout <<" vcetor erase data , the time it takes is " << t4-t3 << " sec." << endl ;
//map
      map< int,int > mymap;
      map< int,int >::iterator map_it;
      pair< map< int,int >::iterator,bool > ret;


      mymap.insert ( pair< int,int >(0,100) );

      cout << endl << "map container " << endl << "================"  << endl;
      time_t map_t1; time(&map_t1);
      for(int i=1;i<2000000;i++)
          mymap.insert ( pair(i,2000000+i) );
      time_t map_t2; time(&map_t2);
      cout << endl <<" map insert data , the time it takes is " << map_t2-map_t1 << " sec." << endl;


      int c;
      time_t map_t5; time(&map_t5);
      for(int i=0;i<2000000;i++)
      {
          srand(time(NULL));
          c=(rand() % 2000000) +1;
          map_it=mymap.find(c);
      }
      time_t map_t6; time(&map_t6);
      cout<<" map search data , the time it takes is " << map_t6-map_t5 << " sec." << endl;



      time_t map_t3; time(&map_t3);
      mymap.erase(mymap.begin(),mymap.end());
      time_t map_t4; time(&map_t4);
      cout  <<" map erase data , the time it takes is " << map_t4-map_t3 << " sec." << endl << endl;

      system("pause");
      return 0;
}
//---------------------------------------------------------------------------

以下是執行結果,可以明顯看出,vector與binary_search的組合是比較有效率的
你不禁會懷疑,是不是巧合(因為random),執行幾次後,還是一樣

vector container
================

 vcetor insert data , the time it takes is 0 sec.
 vcetor search data , the time it takes is 4 sec.
 vcetor erase data , the time it takes is 0 sec.

list container
================

 list insert data , the time it takes is 0 sec.

 list erase data , the time it takes is 1 sec.

map container
================

 map insert data , the time it takes is 8 sec.
 map search data , the time it takes is 5 sec.
 map erase data , the time it takes is 1 sec.

請按任意鍵繼續 . . .

從上面的比較可以得知,vector與binary_search的合作似乎都比較好
那為什麼還要用到map,答案隱藏在上面vector程式碼裡用雙斜線mark掉那行
如果我vector都一直insert在第1筆,那效率就很慘了(可以打開來試看看)
況且,如果你的情況,是要一邊insert , 排序, search
那猜測這樣的結果可能不見得會是vector跟binary_search會比較好了(因為不是push_back)
筆者試過,每push_back 1筆就排序一次,只要2萬筆,...就慢到不行

所以建議:
(1)如果資料一剛開始就確定範圍,可以用vector 與binary_search來處理
(2)如果資料使用中不斷變化,簡單方法可以用map
(3)承(2),如果一定要用vector,比較常遇到的解法是
   1)不要用sort,改用lower_bound或upper_bound來決定插入資料的位置
   2)因為sort資料會花時間,尤其是資料量大時,如果還是要用sort,那就原始資料一律用vector.push_back,
     另外建一個vector來與原始資料對應序號(KEY),針對這個KEY的vector進行SORT
     會有效率得多,不過在做erase時,請記得2方都要刪除
      (當然KEY的vector也可運用1)的技巧)

以下補充:以下參考(http://hi.baidu.com/litinglong2010/blog/item/6b55d23962cbabca9f3d6215.html)

vector中存儲資料 標準關聯容器(map)
概要：在有序vector中存儲資料很有可能比在標準關聯容器中保存相同的資料消耗更少的記憶體；
當頁面錯誤值得重視的時候，在有序vector中通過二分法查找可能比在一個標準關聯容器中查找更快。 

當然，有序vector的大缺點是它必須保持有序！當一個新元素插入時，大於這個新元素的所有東西都必須向上移一位。
它和聽起來一樣昂貴，如果vector必須重新分配它的內在記憶體（參見條款14），則會更昂貴，
因為vector中所有的元素都必須拷貝。同樣的，如果一個元素從vector中被刪除，所有大於它的元素都要向下移動。
vector的插入和刪除都很昂貴，但是關聯容器的插入和刪除則很輕量。這就是為什麼只有當你知道
你的資料結構使用的時候查找幾乎不和插入和刪除混合時，使用有序vector代替關聯容器才有意義。 

本條款有很多文字，但不幸的是只有很少的例子，所以我們來看看一個使用有序vector代替set的代碼骨架： 

vector < Widget > vw; // 代替set < Widget > 
... // 建立階段：很多插入， 
// 幾乎沒有查找 
sort(vw.begin(), vw.end()); // 結束建立階段。（當 
// 模擬一個multiset時，你 
// 可能更喜歡用stable_sort 
// 來代替；參見條款31。） 
Widget w; // 用於查找的值的對象 
... // 開始查找階段 
if (binary_search(vw.begin(), vw.end(), w))... // 通過binary_search查找 
vector < Widget > ::iterator i = 
lower_bound(vw.begin(), vw.end(), w); // 通過lower_bound查找 
if (i != vw.end() && !(w < *i))... // 條款19解釋了 
// “!(w < *i)”測試 
pair < vector < Widget > ::iterator, 
vector < Widget > ::iterator > range = 
equal_range(vw.begin(), vw.end(), w); // 通過equal_range查找 
if (range.first != range.second)... 
... // 結束查找階段，開始 
// 重組階段 
sort(vw.begin(), vw.end()); // 開始新的查找階段... 

就像你可以看到的，這非常直截了當。裏面最難的東西就是怎麼在搜索演算法中做出選擇（比如，binary_search、lower_bound等），條款45可以幫你做出選擇。 

當你決定用vector代替map或multimap時，事情會變得更有趣，因為vector必須容納pair物件。
畢竟，那是map和multimap所容納的。但是要注意，如果你聲明一個map < K, V > 的物件
（或者等價的multimap），保存在map中的元素類型是pair < const K, V > 。
如果要用vector模擬map或者multimap，你必須去掉const，因為當你對vector排序時，
它的元素的值將會通過賦值移動，那意味著pair的兩個元件都必須是可賦值的。
當使用vector來模擬map < K, V > 時，保存在vector中資料的類型將是pair < K, V > ，
而不是pair < const K, V > 。 

map和multimap以順序的方式保存他們的元素，但用於排序目的時它們只作用於元素的key部分
（pair的第一個元件），所以當排序vector時你必須做一樣的事情。你需要為你的pair寫一個
自定義比較函數，因為pair的operator < 作用於pair的兩個組件。 

有趣的是，你會需要第二個比較函數來進行查找。用來排序的比較函數將作用於兩個pair物件，
但是查找只用到key值。必須傳給用於查找的比較函數一個key類型的物件（要查找的值）和一個pair
（存儲在vector中的一個pair）——兩個不同的類型。還有一個附加的麻煩，你不會知道key還是pair
是作為第一個實參傳遞的，所以你真的需要兩個用於查找的比較函數：一個key值先傳遞，一個pair先傳遞。 

這個例子演示了怎麼把這些東西合在一起： 

typedef pair < string, int > Data; // 在這個例子裏 
// "map "容納的類型 
class DataCompare { // 用於比較的類 
public: 
bool operator()(const Data& lhs, // 用於排序的比較函數 
const Data& rhs) const 
{ 
return keyLess(lhs.first, rhs.first); // keyLess在下麵 
} 

bool operator()(const Data& Ihs, // 用於查找的比較函數 
const Data::first_type& k) const // （形式1） 
{ 
return keyLess(lhs.first, k); 
} 

bool operator()(const Data::first_type& k, // 用於查找的比較函數 
const Data& rhs) const // （形式2） 
{ 
return keyLessfk, rhs.first); 
} 

private: 
bool keyLess(const Data::first_type& k1, // “真的” 
const Data::first_type& k2) const // 比較函數 
{ 
return k1 < k2; 
} 
}; 

在這個例子中，我們假設有序vector將模擬map < string, int > 。
這段代碼幾乎是上面討論的字面轉換，除了存在成員函數keyLess。
那個函數的存在是用來保證幾個不同的operator()函數之間的一致性。
每個這樣的函數只是簡單地比較兩個key的值，所以我們把這個測試放在keyLess中並讓operator()
函數返回keyLess所做的事情，這比複製那個邏輯要好。
這個軟體工程中絕妙的動作增強了DataCompare的可維護性，但有一個小缺點，
它提供了有不同參數類型的operator()函數，這將導致函數物件無法適配（看見條款40）。
噢，好了。 

把有序vector用作map本質上和用作set一樣。唯一大的區別是必須把DataCompare物件用作比較函數： 

vector < Data > vd; // 代替map < string, int > 
... // 建立階段：很多插入， 
// 幾乎沒有查找 
sort(vd.begin(), vd.end(), DataCompare()); // 結束建立階段。（當 
// 模擬multimap時，你 
// 可能更喜歡用stable_sort 
// 來代替；參見條款31。） 
string s; // 用於查找的值的對象 
... // 開始查找階段 
if (binary_search(vd.begin(), vd.end(), s, 
DataCompare()))... // 通過binary_search查找 
vector  ::iterator i = 
lower_bound(vd.begin(), vd.end(), s, 
DataCompare()); // 在次通過lower_bound查找， 
if (i != vd.end() && !DataCompare()(s, *i))... // 條款45解釋了 
// “!DataCompare()(s, *i)”測試 
pair < vector < Data > ::iterator, 
vector < Data > ::iterator > range = 
equal_range(vd.begin(), vd.end(), s, 
DataCompare()); // 通過equal_range查找 
if (range.first != range.second)... 
... // 結束查找階段，開始 
// 重組階段 
sort(vd.begin(), vd.end(), DataCompare()); // 開始新的查找階段... 

正如你所見，一旦你寫了DataCompare，東西都很好的依序排列了。而一旦位置合適了，
只要你的程式按照101頁描述的階段方式使用資料結構，它們往往比相應的使用真的map的設計
運行得更快而且使用更少記憶體。如果你的程式不是按照階段的方式操作資料結構，
那麼使用有序vector代替標準關聯容器幾乎可以確定是在浪費時間。