程序地带

map要点



定义排序规则元素查找根据key值查找根据value查找
元素排序元素修改元素移除安插元素获取map与multimapmap与unordered_map


  map是以平衡二叉树完成,其元素是 key/value pair;   map的是定义在std内的class templates:


template <class Key,class T,class Compare = less<key>,
class Allocator = allocator<pair<cosnt key,T>>>
class map;

  其中:


第一个参数为key第二个参数为value第三个参数为排序准则第四个参数为内存模型

  map根据key自动进行排序,因此,根据某个已知key来搜寻某个元素,就有很好的性能;而根据已知value搜寻元素,性能就很糟糕。但是这也使得:不能直接改变元素key,因为这会改变元素的正确次序;所以,正如前面代码片段,key为const类型,而value则是常数可改;


  与vector、list不同的是,我们可以定义map的排序准则,一般默认为less<>;相同的是,key/value也必须可赋值、可复制,对于排序准则而言,必须可比较;


定义排序规则

  我们可以template参数定义排序规则:


std::map<folat,std::string,std::gerater<float> > coll;

  但map也支持运行时修改排序规则,如下:


map c(op) //以op为排序准则,产生一个空的map/multimap

  其中,op是一个函数对象,需要我们定义排序规则,在c++标准程序库一书中,提供了下面这个示例,以作参考:


#include <iostream>
#include <iomanip>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
class RuntimeStringCmp{
public:
enum cmp_mode{normal,nocase};
private:
const cmp_mode mode;
static bool nocase_compare(char c1,char c2)
{
return toupper(c1) < toupper(c2);
}
public:
RuntimeStringCmp (cmp_mode m = normal) : mode(m){
}
bool operator()(const string& s1,const string& s2) const
{
if(mode == normal)
return s1 < s2;
else
return lexicographical_compare(s1.begin(),s1.end(),s2.begin(),s2.end(),nocase_compare);
}
};
typedef map<string,string,RuntimeStringCmp> StringStringMap;
void fillTheMap(StringStringMap coll);
int main()
{
StringStringMap coll;
fillTheMap(coll);
RuntimeStringCmp ignorecase(RuntimeStringCmp::nocase);
StringStringMap coll2(ignorecase);
}

  代码并不难懂,唯一可能需要注意的可能是函数对象这个概念,不太理解的同学可以补补;


  排序规则不同,但是pair类型相同,可以视作同一类型的map,可进行赋值,拷贝,互换,互换时排序规则也会互换;但是,不能用于比较;例如:


std::map<float,std::string> c1;
std::map<float,std::string,std::greater<float> > c2;
if(c1 == c2) { // ERROR :differenent types
...
}
元素查找
根据key值查找

  我们可以使用STL提供的find()函数来进行根据key值得查找,但是为了更好的性能,map提供了成员函数find(),如下表所示: 在这里插入图片描述


根据value查找

  正如前文所述,根据vale查找并没有根据value查找的良好性能,但是也无法避免存在这种使用的特殊场景,这种情况下,主要有两种方式:


遍历map,根据value进行符合条件的判断;使用find_if,提供一个函数对象,根据value进行符合条件的判断。
元素排序

  和list相同,map是双向迭代器,所以无法使用STL中用于随机存取迭代器(vector随机存取迭代器)中的算法;


元素修改

  我们可以很轻易的修改value,无论是通过迭代器或者下标(返回引用)都可以,但是key值是const类型,该如何修改呢?   我们可以像下面这样修改key值:


std::map<std::string,float> coll;
coll['new _key"] = coll["old_key'];
coll.erase("olg_key");

  上述过程可表述为:


#mermaid-svg-0vqaBExovMJ4dvss .label{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-0vqaBExovMJ4dvss .label text{fill:#333}#mermaid-svg-0vqaBExovMJ4dvss .node rect,#mermaid-svg-0vqaBExovMJ4dvss .node circle,#mermaid-svg-0vqaBExovMJ4dvss .node ellipse,#mermaid-svg-0vqaBExovMJ4dvss .node polygon,#mermaid-svg-0vqaBExovMJ4dvss .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-0vqaBExovMJ4dvss .node .label{text-align:center;fill:#333}#mermaid-svg-0vqaBExovMJ4dvss .node.clickable{cursor:pointer}#mermaid-svg-0vqaBExovMJ4dvss .arrowheadPath{fill:#333}#mermaid-svg-0vqaBExovMJ4dvss .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-0vqaBExovMJ4dvss .flowchart-link{stroke:#333;fill:none}#mermaid-svg-0vqaBExovMJ4dvss .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-0vqaBExovMJ4dvss .edgeLabel rect{opacity:0.9}#mermaid-svg-0vqaBExovMJ4dvss .edgeLabel span{color:#333}#mermaid-svg-0vqaBExovMJ4dvss .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-0vqaBExovMJ4dvss .cluster text{fill:#333}#mermaid-svg-0vqaBExovMJ4dvss div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-0vqaBExovMJ4dvss .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-0vqaBExovMJ4dvss text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-0vqaBExovMJ4dvss .actor-line{stroke:grey}#mermaid-svg-0vqaBExovMJ4dvss .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-0vqaBExovMJ4dvss .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-0vqaBExovMJ4dvss #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-0vqaBExovMJ4dvss .sequenceNumber{fill:#fff}#mermaid-svg-0vqaBExovMJ4dvss #sequencenumber{fill:#333}#mermaid-svg-0vqaBExovMJ4dvss #crosshead path{fill:#333;stroke:#333}#mermaid-svg-0vqaBExovMJ4dvss .messageText{fill:#333;stroke:#333}#mermaid-svg-0vqaBExovMJ4dvss .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-0vqaBExovMJ4dvss .labelText,#mermaid-svg-0vqaBExovMJ4dvss .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-0vqaBExovMJ4dvss .loopText,#mermaid-svg-0vqaBExovMJ4dvss .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-0vqaBExovMJ4dvss .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-0vqaBExovMJ4dvss .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-0vqaBExovMJ4dvss .noteText,#mermaid-svg-0vqaBExovMJ4dvss .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-0vqaBExovMJ4dvss .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-0vqaBExovMJ4dvss .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-0vqaBExovMJ4dvss .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-0vqaBExovMJ4dvss .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-0vqaBExovMJ4dvss .section{stroke:none;opacity:0.2}#mermaid-svg-0vqaBExovMJ4dvss .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-0vqaBExovMJ4dvss .section2{fill:#fff400}#mermaid-svg-0vqaBExovMJ4dvss .section1,#mermaid-svg-0vqaBExovMJ4dvss .section3{fill:#fff;opacity:0.2}#mermaid-svg-0vqaBExovMJ4dvss .sectionTitle0{fill:#333}#mermaid-svg-0vqaBExovMJ4dvss .sectionTitle1{fill:#333}#mermaid-svg-0vqaBExovMJ4dvss .sectionTitle2{fill:#333}#mermaid-svg-0vqaBExovMJ4dvss .sectionTitle3{fill:#333}#mermaid-svg-0vqaBExovMJ4dvss .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-0vqaBExovMJ4dvss .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-0vqaBExovMJ4dvss .grid .tick text{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-0vqaBExovMJ4dvss .grid path{stroke-width:0}#mermaid-svg-0vqaBExovMJ4dvss .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-0vqaBExovMJ4dvss .task{stroke-width:2}#mermaid-svg-0vqaBExovMJ4dvss .taskText{text-anchor:middle;font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-0vqaBExovMJ4dvss .taskText:not([font-size]){font-size:11px}#mermaid-svg-0vqaBExovMJ4dvss .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-0vqaBExovMJ4dvss .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-0vqaBExovMJ4dvss .task.clickable{cursor:pointer}#mermaid-svg-0vqaBExovMJ4dvss .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-0vqaBExovMJ4dvss .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-0vqaBExovMJ4dvss .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-0vqaBExovMJ4dvss .taskText0,#mermaid-svg-0vqaBExovMJ4dvss .taskText1,#mermaid-svg-0vqaBExovMJ4dvss .taskText2,#mermaid-svg-0vqaBExovMJ4dvss .taskText3{fill:#fff}#mermaid-svg-0vqaBExovMJ4dvss .task0,#mermaid-svg-0vqaBExovMJ4dvss .task1,#mermaid-svg-0vqaBExovMJ4dvss .task2,#mermaid-svg-0vqaBExovMJ4dvss .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-0vqaBExovMJ4dvss .taskTextOutside0,#mermaid-svg-0vqaBExovMJ4dvss .taskTextOutside2{fill:#000}#mermaid-svg-0vqaBExovMJ4dvss .taskTextOutside1,#mermaid-svg-0vqaBExovMJ4dvss .taskTextOutside3{fill:#000}#mermaid-svg-0vqaBExovMJ4dvss .active0,#mermaid-svg-0vqaBExovMJ4dvss .active1,#mermaid-svg-0vqaBExovMJ4dvss .active2,#mermaid-svg-0vqaBExovMJ4dvss .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-0vqaBExovMJ4dvss .activeText0,#mermaid-svg-0vqaBExovMJ4dvss .activeText1,#mermaid-svg-0vqaBExovMJ4dvss .activeText2,#mermaid-svg-0vqaBExovMJ4dvss .activeText3{fill:#000 !important}#mermaid-svg-0vqaBExovMJ4dvss .done0,#mermaid-svg-0vqaBExovMJ4dvss .done1,#mermaid-svg-0vqaBExovMJ4dvss .done2,#mermaid-svg-0vqaBExovMJ4dvss .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-0vqaBExovMJ4dvss .doneText0,#mermaid-svg-0vqaBExovMJ4dvss .doneText1,#mermaid-svg-0vqaBExovMJ4dvss .doneText2,#mermaid-svg-0vqaBExovMJ4dvss .doneText3{fill:#000 !important}#mermaid-svg-0vqaBExovMJ4dvss .crit0,#mermaid-svg-0vqaBExovMJ4dvss .crit1,#mermaid-svg-0vqaBExovMJ4dvss .crit2,#mermaid-svg-0vqaBExovMJ4dvss .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-0vqaBExovMJ4dvss .activeCrit0,#mermaid-svg-0vqaBExovMJ4dvss .activeCrit1,#mermaid-svg-0vqaBExovMJ4dvss .activeCrit2,#mermaid-svg-0vqaBExovMJ4dvss .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-0vqaBExovMJ4dvss .doneCrit0,#mermaid-svg-0vqaBExovMJ4dvss .doneCrit1,#mermaid-svg-0vqaBExovMJ4dvss .doneCrit2,#mermaid-svg-0vqaBExovMJ4dvss .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-0vqaBExovMJ4dvss .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-0vqaBExovMJ4dvss .milestoneText{font-style:italic}#mermaid-svg-0vqaBExovMJ4dvss .doneCritText0,#mermaid-svg-0vqaBExovMJ4dvss .doneCritText1,#mermaid-svg-0vqaBExovMJ4dvss .doneCritText2,#mermaid-svg-0vqaBExovMJ4dvss .doneCritText3{fill:#000 !important}#mermaid-svg-0vqaBExovMJ4dvss .activeCritText0,#mermaid-svg-0vqaBExovMJ4dvss .activeCritText1,#mermaid-svg-0vqaBExovMJ4dvss .activeCritText2,#mermaid-svg-0vqaBExovMJ4dvss .activeCritText3{fill:#000 !important}#mermaid-svg-0vqaBExovMJ4dvss .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-0vqaBExovMJ4dvss g.classGroup text{fill:#9370db;stroke:none;font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-0vqaBExovMJ4dvss g.classGroup text .title{font-weight:bolder}#mermaid-svg-0vqaBExovMJ4dvss g.clickable{cursor:pointer}#mermaid-svg-0vqaBExovMJ4dvss g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-0vqaBExovMJ4dvss g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-0vqaBExovMJ4dvss .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-0vqaBExovMJ4dvss .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-0vqaBExovMJ4dvss .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-0vqaBExovMJ4dvss .dashed-line{stroke-dasharray:3}#mermaid-svg-0vqaBExovMJ4dvss #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-0vqaBExovMJ4dvss #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-0vqaBExovMJ4dvss #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-0vqaBExovMJ4dvss #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-0vqaBExovMJ4dvss #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-0vqaBExovMJ4dvss #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-0vqaBExovMJ4dvss #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-0vqaBExovMJ4dvss #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-0vqaBExovMJ4dvss .commit-id,#mermaid-svg-0vqaBExovMJ4dvss .commit-msg,#mermaid-svg-0vqaBExovMJ4dvss .branch-label{fill:lightgrey;color:lightgrey;font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-0vqaBExovMJ4dvss .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-0vqaBExovMJ4dvss .slice{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-0vqaBExovMJ4dvss g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-0vqaBExovMJ4dvss g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-0vqaBExovMJ4dvss g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-0vqaBExovMJ4dvss g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-0vqaBExovMJ4dvss g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-0vqaBExovMJ4dvss g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-0vqaBExovMJ4dvss .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-0vqaBExovMJ4dvss .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-0vqaBExovMJ4dvss .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-0vqaBExovMJ4dvss .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-0vqaBExovMJ4dvss .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-0vqaBExovMJ4dvss .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-0vqaBExovMJ4dvss .edgeLabel text{fill:#333}#mermaid-svg-0vqaBExovMJ4dvss .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-0vqaBExovMJ4dvss .node circle.state-start{fill:black;stroke:black}#mermaid-svg-0vqaBExovMJ4dvss .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-0vqaBExovMJ4dvss #statediagram-barbEnd{fill:#9370db}#mermaid-svg-0vqaBExovMJ4dvss .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-0vqaBExovMJ4dvss .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-0vqaBExovMJ4dvss .statediagram-state .divider{stroke:#9370db}#mermaid-svg-0vqaBExovMJ4dvss .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-0vqaBExovMJ4dvss .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-0vqaBExovMJ4dvss .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-0vqaBExovMJ4dvss .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-0vqaBExovMJ4dvss .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-0vqaBExovMJ4dvss .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-0vqaBExovMJ4dvss .note-edge{stroke-dasharray:5}#mermaid-svg-0vqaBExovMJ4dvss .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: ""trebuchet ms", verdana, arial";--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-0vqaBExovMJ4dvss .error-icon{fill:#522}#mermaid-svg-0vqaBExovMJ4dvss .error-text{fill:#522;stroke:#522}#mermaid-svg-0vqaBExovMJ4dvss .edge-thickness-normal{stroke-width:2px}#mermaid-svg-0vqaBExovMJ4dvss .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-0vqaBExovMJ4dvss .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-0vqaBExovMJ4dvss .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-0vqaBExovMJ4dvss .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-0vqaBExovMJ4dvss .marker{fill:#333}#mermaid-svg-0vqaBExovMJ4dvss .marker.cross{stroke:#333}
:root { --mermaid-font-family: "trebuchet ms", verdana, arial;}
#mermaid-svg-0vqaBExovMJ4dvss {
color: rgba(0, 0, 0, 0.75);
font: ;
}
创建新key
新key赋值
移除旧key
元素移除安插

  前文已知,map的key为const,这是因为map自动排序,而修改key值会打破这种排序,也因此,不能针对map调用任何变动性算法,如STL中的remove(),因为其实际是以一个参数覆盖被移除的元素;但我们可使用它们所提供的成员函数,例如erase()函数; 在这里插入图片描述   在这里,我们需要注意erase使用方式与list、vector的不同,这里的erase并不会返回下一个元素的迭代器位置,这是因为,这个过程对于map而言将会耗时,所以STL设计时就否决了这种设计,那么我们该如何使用迭代器移除元素呢?正确做法如下:


for(pos = coll.begin() ; pos != coll.end();)
{
if(pos->second == value )
coll.erase(pos++);
else
+pos;
}

  pos++会移向下一元素,但返回其原始值的一个副本,因为erase被调用,但是pos已经不再指向那个即将被移除的元素了;


  至于安插,我们可以使用insert函数,也可以使用map[key] = value直接进行赋值,但是需要注意的是,后者效率较低,因为其实际完成两个过程:新元素先用default构造函数将实值初始化,然后这个初值又马上被真正的value给覆盖了;


元素获取

  map支持使用[]重载来获取元素,但需要注意的是,不是通过索引,而是key值;   其次,这种方式获取元素也存在一定风险,很多时候,我们在该key值已经存在的情况下可以直接获取,但是如果不存在呢?则会安插新元素,这在有时候可能会导致一些我们意象之外的问题;例如:


std::cout << coll[”otto“] ;

  不知不觉间,我们已经为map新安插了一个键值为"otto",而value为0的元素;


map与multimap

  map与multimap的唯一区别在于,multimap允许元素重复,map不允许。


map与unordered_map
map内部实现了一个红黑树,红黑树具有自动排序的功能,因此map是有序的。unordered_map内部实现是哈希表,其元素排列是无序的。map内部实现红黑树,所以黑多操作在lgn的时间复杂度下就可以实现,因此效率非常高。unordered_map内部实现哈希表,因此其查找速度非常快,可达到O(1)。map空间占用率高,因为其每一个节点都需要额外保存父节点、子节点和红黑性质,使得每一个节点都占用大量空间。unordered_map中的哈希表建立比较费时。

  对于那些对顺序有要求的问题,使用map更高效;而如果不关注有序,对查找效率要求比较高,那么应该使用unordered_map。至于其他操作,二者基本相同,这里不再赘述。


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/wdl20170204/article/details/109757264

随机推荐

网络基础、HCIA(一)

网络基础、HCIA(一)

一、7层模型—OSI参考模型:应用层:抽象语言—>编码表示层:编码—>二进制会话层:提供会话层地址传输层:TCP/UD...

二十四万里归程 阅读(106)

iOS底层探索--内存管理(下)

iOS底层探索--内存管理(下)

iOS内存管理(上)简单的说了下retain、release和dealloc。不过关于内存管理还有个比较重要的东西autoreleasepool,也是兄弟们常说的自动释放池...

iOS发呆君 阅读(691)

基于check-point机制的任务状态回滚和数据分块任务

基于check-point机制的任务状态回滚和数据分块任务问题背景节点TASK关系TASK资料备注问题背景基于check-point实现图数据构建任务针对这篇文章提出的方案增加了数据分块操作与任务状态...

Tnoy.Ma 阅读(743)

JavaScript中的offset、client和scroll

JavaScript中的offset、client和scroll元素偏移量offsetoffset就是元素偏移量,使用offset系列相关属性可以动态的得到该元素的位置(偏...

我是Dreamer啊 阅读(590)