关联容器

目录:

1.问题的来源
2.关联容器学习

1.问题来源

面试题:最小的k个树
借助容器来实现,使用红黑树保证删除，插入操作都能在O(logK)实现,STL中的模版直接使用
关于mulitset的迭代器及其定义存在问题

typedef multiset<int,greater<int>>                 intSet;      // 关键字可以重复出现的有序集合
typedef multiset<int,greater<int>>::iterator  setIterator;   // 上面这两个定义都存在问题？

void GetLastNumbers2(const vector<int>& data,intSet& leastNumbers,int k)
{
    leastNumbers.clear();                                         // 容器清空
    if(k<1 || data.size()<k)                                         // 错误判断
        return;
    vector<int>::const_iterator iter=data.begin();         // 定义迭代器
    // for(auto it=data.begin();it!=data.end();it++)       // 直接使用？觉得也可以
    for(;iter!=data.end();++iter)
    {
        if(leastNumbers.size()<k)                            // 容器中元素不足k，元素直接进入容器
        {
            leastNumbers.insert(*iter);                  // 必须是解引用
        }
        else
        {
            setIterator iterGreatest=leastNumbers.begin();      // 小于其最大元素
            if(*iter<*(leastNumbers.begin()))
            {
                leastNumbers.erase(iterGreatest);
                leastNumbers.insert(*iter);
            }
        }
    }
}

2.关联容器学习

关联容器预览

--------------------------------------

关联容器操作

• key_type

  容器的关键字类型

• mapped_type

  关键字关联的模型，map独有

• value_type

  对于set而言 value_type==key_type ; map 而言 value_type 为pair<const key_value,mapped_value>

set<string>::key_type v1           //v1 is string
set<string>::value_type v         // v  is string
map<string,int>::value_type v2  // v2 is pair<const string ,int >
map<string,int >::mapped_type v //v is int

set的迭代器是const的

添加元素:

map添加元素必须是pair

map.insert(value_type);
set.inesert(vector.cbegin(),vector.cend());

问题还是没有彻底解决

typedef multiset<int,greater<int>>                 intSet;      // 这个set的定义真的不理解  set不是只有key_type类型
typedef multiset<int,greater<int>>::iterator  setIterator;   

自己得出的结论是 greater<int> 表示的是 multiset 的顺序

// 这个set中的键 是按照从小到大的顺序进行有序排列的
typedef multiset<int,greater<int>>                 intSet;   

补充的知识点
less<type>,greater<type> 称之为比较仿函数 放在定义的结尾

这个也用来最大堆和最小堆的实现 - 剑指offer p216面试题41.数据流中的中位数