c++ map set 详解

map 是c++ key value [pair<key,value>]存储容器，底层使用红黑树， 结构具有自动排序功能， 1key对应1value， 查找O(logN)

unordered_map 是c++ 另外一种 key value 存储容器，底层使用哈希表，不具备排序功能，1key对应1value 查找O(1)

multimap 是c++ key value 存储容器，底层使用红黑树， 结构具有自动排序功能，允许一个key对应多个value 查找O(logN)

set 是c++ key 存储容器，底层使用红黑树， 结构具有自动排序功能， 不予许key重复 查找O(logN)

unordered_set 是c++ 另外一种 key存储容器，底层使用哈希表，不具备排序功能，不予许key重复 查找O(1)

multiset 是c++ 另外一种 key存储容器，底层使用哈希表，具备排序功能，予许key重复 查找O(logN)

map操作

begin() 返回指向第一个元素的迭代器 
clear() 删除所有元素 
count() 返回一个元素出现的次数 
empty() 如果multimap为空则返回真 
end() 返回一个指向multimap末尾的迭代器 
equal_range() 返回指向元素的key为指定值的迭代器对 
erase() 删除元素 
find() 查找元素 
get_allocator() 返回multimap的配置器 
insert() 插入元素 
key_comp() 返回比较key的函数 
lower_bound() 返回键值>=给定元素的第一个位置 
max_size() 返回可以容纳的最大元素个数 
rbegin() 返回一个指向mulitmap尾部的逆向迭代器 
rend() 返回一个指向multimap头部的逆向迭代器 
size() 返回multimap中元素的个数 
swap() 交换两个multimaps 
upper_bound() 返回键值>给定元素的第一个位置 
value_comp() 返回比较元素value的函数 

map 类别 用法 map ,unordered_map插入重复key会将原来值覆盖, multiple_map允许重复值

int main(int argc, char **argv) {
    //unordered_map 与map的增删改查
    unordered_map<int, int > tmap;
    tmap[0] =1;
    tmap.insert(make_pair<int, int>(2,3));
    tmap.insert({3,3});
    std::unordered_map<int, int>::iterator it;
    for (it = tmap.begin(); it!=tmap.end(); it++){
        cout<<it->first<<it->second<<endl;
     }
     cout<<(tmap.find(3)!=tmap.end())<<endl;


    //multimap 的增删改查
    multimap<int, int > mmap;
    //multimap 不包含[ ]操作
    //mmap[0] =1;
    mmap.insert(make_pair<int, int>(2,3));
    mmap.insert({2,4});
    multimap<int, int>::iterator it;
    cout<<(tmap.find(2)!=tmap.end())<<endl;
    it = tmap.find(2);
    int count = tmap.count(2);
    for (int i = 0; i<count; i++,it++){
        cout << it->first << " " << it->second << endl;
    }
     return 0;
}

set操作

begin() 返回指向第一个元素的迭代器 
clear() 删除所有元素 
count() 返回一个元素出现的次数 
empty() 如果set为空则返回真 
end() 返回一个指向set末尾的迭代器 
equal_range() 返回指向元素的key为指定值的迭代器对 
erase() 删除元素 
find() 查找元素 
insert() 插入元素 
size() 返回set中元素的个数 
swap() 交换两个set

int main(int argc, char **argv) {
    //unordered_set 与set的增删改查
    set< int > tset;
    tset.insert(3);
    tset.insert(3);
    tset.insert(4);
    tset.insert(3);
    set<int>::iterator it;
    cout<<(tset.find(3)!=tset.end())<<endl;
    it = tset.find(3);
    int count = tset.count(3);
    cout<<tset.size()<<endl;    

    multiset< int > mset;
    mset.insert(3);
    mset.insert(3);
    mset.insert(4);
    mset.insert(3);
    multiset<int>::iterator it;
    cout<<(mset.find(3)!=mset.end())<<endl;
    it = mset.find(3);
    cout<<mset.count(3)<<endl;
    cout<<mset.size()<<endl;
   
     return 0;
}

set的自动排序可以用于Astar算法中作openSet选点， 定义如下

struct node{
    int x; 
    int y;
    float f_score;
    float h_score;
    float g_score;
    node * parent;
}
struct Fop{
    bool operator() (const node* c1, const node* c2){
        return c1->h_score < c2->h_score;
    }
}
multiset<node*, Fop> openSet;
//将搜索节点加入openSet中，选openSet排序第一即h值最小的
node * node1 = new node();
openSet.insert(node1);
openSet.begin();