• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Focus on ACE

            訂閱 ace-china
            電子郵件:
            瀏覽存于 groups.google.com 上的所有帖子

            C++博客 首頁 新隨筆 聯系 聚合 管理
              64 Posts :: 3 Stories :: 22 Comments :: 0 Trackbacks

            STL中map與hash_map容器的選擇

            作者 alvin_lee @ 2005-06-21 17:43:38

              實際上這個問題不光C++會遇到,其他所有語言的標準容器的實現及選擇上都是要考慮的。做應用程序你可能覺得影響不大,但是寫算法或者核心代碼就要小心了。今天改進代碼,順便又來溫習基礎功課了。


              還記得Herb Sutter那極有味道的《C++對話系列》么,在其中《產生真正的hash對象》這個故事里就講了map的選擇。順便回顧一下,也講一下我在實用中的理解。

              選擇map容器,是為了更快的從關鍵字查找到相關的對象。與使用list這樣的線性表容器相比,一可以簡化查找的算法,二可以使任意的關鍵字做索引,并與目標對象配對,優化查找算法。在C++的STL中map是使用樹來做查找算法,這種算法差不多相當與list線性容器的折半查找的效率一樣,都是O(log2N),而list就沒有map這樣易定制和操作了。

              相比hash_map,hash_map使用hash表來排列配對,hash表是使用關鍵字來計算表位置。當這個表的大小合適,并且計算算法合適的情況下,hash表的算法復雜度為O(1)的,但是這是理想的情況下的,如果hash表的關鍵字計算與表位置存在沖突,那么最壞的復雜度為O(n)。

              那么有了這樣的認識,我們應該怎么樣選用算法呢?前兩天看Python文章的時候,不知道哪個小子說Python的map比c++的map快,如何如何的。但是他并不知道Python是默認使用的hash_map,而且這些語言特征本質上是使用c/c++寫出來的,問題在與算法和手段,而不是在于語言本身的優劣,你熟悉了各種算法,各種語言的細節、設計思想,還能在這偏激的嚷嚷孰好孰壞(片面與偏激的看待事物只能表明愚昧與無知,任何事物都有存在的價值,包括技術)。顯然C++的STL默認使用樹結構來實現map,是有考究的。

              樹查找,在總查找效率上比不上hash表,但是它很穩定,它的算法復雜度不會出現波動。在一次查找中,你可以斷定它最壞的情況下其復雜度不會超過O(log2N)。而hash表就不一樣,是O(1),還是O(N),或者在其之間,你并不能把握。假若你在開發一個供外部調用的接口,其內部有關鍵字的查找,但是這個接口調用并不頻繁,你是會希望其調用速度快、但不穩定呢,還是希望其調用時間平均、且穩定呢。反之假若你的程序需要查找一個關鍵字,這個操作非常頻繁,你希望這些操作在總體上的時間較短,那么hash表查詢在總時間上會比其他要短,平均操作時間也會短。這里就需要權衡了。

              這里總結一下,選用map還是hash_map,關鍵是看關鍵字查詢操作次數,以及你所需要保證的是查詢總體時間還是單個查詢的時間。如果是要很多次操作,要求其整體效率,那么使用hash_map,平均處理時間短。如果是少數次的操作,使用hash_map可能造成不確定的O(N),那么使用平均處理時間相對較慢、單次處理時間恒定的map,考慮整體穩定性應該要高于整體效率,因為前提在操作次數較少。如果在一次流程中,使用hash_map的少數操作產生一個最壞情況O(N),那么hash_map的優勢也因此喪盡了。

            posted on 2006-04-25 09:25 Stone Jiang 閱讀(1504) 評論(0)  編輯 收藏 引用 所屬分類: C++&OOPMiscellaneous
            欧美亚洲国产精品久久蜜芽| 7国产欧美日韩综合天堂中文久久久久 | 色综合久久久久无码专区| 精品国产青草久久久久福利| 婷婷五月深深久久精品| 久久久久国产一级毛片高清版| 亚洲国产精品久久久久网站| 精品国产乱码久久久久久呢| 久久97精品久久久久久久不卡| 久久综合偷偷噜噜噜色| 久久久久99精品成人片试看| 久久夜色精品国产www| 99久久国产热无码精品免费| 香蕉久久夜色精品国产2020| 国产三级观看久久| 国产成人无码久久久精品一| 欧美无乱码久久久免费午夜一区二区三区中文字幕 | 久久亚洲综合色一区二区三区| 亚洲七七久久精品中文国产| 国产一级持黄大片99久久| 久久无码国产专区精品| 久久久久亚洲AV成人网| 婷婷综合久久狠狠色99h| 无码人妻精品一区二区三区久久久| 久久精品国产亚洲AV不卡| 久久99久久99精品免视看动漫| 久久无码高潮喷水| 亚洲精品97久久中文字幕无码| 精品久久久久久无码国产| 狠狠色噜噜狠狠狠狠狠色综合久久| 日产精品久久久久久久| 亚洲精品无码久久久久去q| 亚洲欧美一级久久精品| 久久综合九色综合欧美就去吻| 94久久国产乱子伦精品免费| 久久噜噜电影你懂的| 精品九九久久国内精品| 91精品国产综合久久香蕉 | 亚洲欧美另类日本久久国产真实乱对白| 99热热久久这里只有精品68| 国产精品九九久久精品女同亚洲欧美日韩综合区 |