C++基础（10. map_set 的使用）

• set的声明如上，T就是set底层关键字的类型
• set默认要求T⽀持⼩于⽐较，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现仿函数传给第⼆个模版参数
• set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第三个参数。
• ⼀般情况下，我们都不需要传后两个模版参数。
• set底层是⽤红⿊树实现，增删查效率是O(logN) ，迭代器遍历是⾛的搜索树的中序，所以是有序的。
• 前⾯部分我们已经学习了vector/list等容器的使⽤，STL容器接⼝设计，⾼度相似。

set的基本使用：

set的构造：

set的构造我们关注以下⼏个接⼝即可。

• set的⽀持正向和反向迭代遍历，遍历默认按升序顺序
• 因为底层是⼆叉搜索树，迭代器遍历⾛的中序
• ⽀持迭代器就意味着⽀持范围for
• set的iterator和const_iterator都不⽀持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。

set<int> mySet;                 // 创建一个空的set
set<int> mySet2 = {1, 2, 3, 4}; // 使用初始化列表创建set
set (const set& x);             // 拷⻉构造 

set (InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& = allocator_type() );        //迭代器区间构造

set的增删查

// 单个数据插⼊，如果已经存在则插⼊失败
pair<iterator,bool> 
insert(const value_type& val);

// 列表插⼊，已经在容器中存在的值不会插⼊
void insert (initializer_list<value_type> il);

// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert (InputIterator first, InputIterator last);

// 查找val，返回val所在的迭代器，没有找到返回end()
iterator find (const value_type& val);

// 查找val，返回Val的个数（如果是set那么只为0或1）
size_type count (const value_type& val) const;

// 删除⼀个迭代器位置的值
iterator erase (const_iterator position);

// 删除val，val不存在返回0，存在返回1
size_type erase (const value_type& val);

// 删除⼀段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);

// 返回⼤于等val位置的迭代器
iterator lower_bound (const value_type& val) const;

// 返回⼤于val位置的迭代器
iterator upper_bound (const value_type& val) const;

迭代器：iterator

// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

检查元素是否存在：count()

由于集容器中的所有元素都是唯一的，因此该函数只能返回 1（如果找到元素）或 0（没找到）。

if (mySet.count(5) > 0)  
{
    std::cout << "5 is in the set." << std::endl;
}

遍历元素：范围for

for (const auto it: mySet) 
{
    std::cout << it << " ";
}

大小和清空：size（），clear（）

std::cout << "Size: " << mySet.size() << std::endl;
mySet.clear(); // 清空set

自定义排序：

可以通过提供自定义比较函数来改变元素的排序方式。

• way1:

struct CustomCompare
{
    bool operator()(int a, int b) const
    {
        return a > b; // 降序排列
    }
};

set<int, CustomCompare> mySet; // 创建一个降序排列的set

typedef pair<const Key, T> value_type;
template <class T1, class T2>
struct pair
{
    typedef T1 first_type;
    typedef T2 second_type;

    T1 first;
    T2 second;

    pair(): first(T1()), second(T2())
    {}

    pair(const T1& a, const T2& b): first(a), second(b)
    {}

    template<class U, class V>
    pair (const pair<U,V>& pr): first(pr.first), second(pr.second)
    {}

};

template <class T1,class T2>

inline pair<T1,T2> make_pair (T1 x, T2 y)
{
    return ( pair<T1,T2>(x,y) );
}

功能

• 唯一键：map中的每个键都是唯一的。
• 自动排序：键会根据升序自动排序。
• 高效操作：插入、删除和查找操作的时间复杂度为 O(log⁡n)O(logn)。

map的基本使用：

map的构造：

• map的⽀持正向和反向迭代遍历，遍历默认按key的升序顺序
• 因为底层是⼆叉搜索树，迭代器遍历⾛的中序
• ⽀持迭代器就意味着⽀持范围for
• map⽀持修改value数据，不⽀持修改key数据，修改关键字数据，破坏了底层搜索树的结构

// empty (1) ⽆参默认构造
explicit map (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());

map<int, std::string> myMap; // 创建一个空的map

// range (2) 迭代器区间构造
template <class InputIterator>
map (InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& = allocator_type());

// copy (3) 拷⻉构造
map (const map& x);

// initializer list (5) initializer 列表构造
map (initializer_list<value_type> il,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());

map<int, std::string> myMap2 = {{1, "one"}, {2, "two"}, {3, "three"}}; // 使用初始化列表创建map

map的增删查：

• map增接⼝，插⼊的pair键值对数据，跟set所有不同
• 查和删的接⼝只⽤关键字key跟set是完全类似的，不过find返回iterator，不仅仅可以确认key在不在，还找到key映射的value，同时通过迭代还可以修改value

// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
pair<iterator,bool> insert (const value_type& val);

// 列表插⼊，已经在容器中存在的值不会插⼊
void insert (initializer_list<value_type> il);

// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert (InputIterator first, InputIterator last);

// 查找k，返回k所在的迭代器，没有找到返回end()
iterator find (const key_type& k);

// 查找k，返回k的个数
size_type count (const key_type& k) const;

// 删除⼀个迭代器位置的值
iterator erase (const_iterator position);

// 删除k，k存在返回0，存在返回1
size_type erase (const key_type& k);

// 删除⼀段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);

// 返回⼤于等k位置的迭代器
iterator lower_bound (const key_type& k);

// 返回⼤于k位置的迭代器
const_iterator lower_bound (const key_type& k) const;