# Good method to use map in c++

• I read some threads in discuss, found that most of you want to use map or unsorted_map to store the length information for each element in num. However you may miss an important feature about map:

map is based on red-black tree, so the key value is sorted in map, which is the great difference between map and unsorted_map, so we can exactly use the sorted key value to calculate the longest length

following is my code:

``````class Solution {
public:
int longestConsecutive(vector<int> &num) {
map<int, int> m;
for(int i=0;i<num.size();i++){
m[num[i]]++;
}

int ret=1;
int cur_len=1;

map<int, int>::iterator it;
int last=m.begin()->first;

for(it=m.begin();it!=m.end();it++){
int cur=it->first;

if(cur==last) continue;
else if(cur==last+1){
cur_len++;
ret=max(ret,cur_len);
last=cur;
}
else{
cur_len=1;
last=cur;
}
}

return ret;
}
};``````

• As you said, map is based on rb-tree, so the insert method of map is logn, then I think the code run time below is O(nlogn),not O(n), what do you say?
for(int i=0;i<num.size();i++){
m[num[i]]++;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.