目录

一. set和map的简介

1.1 set的简介

1.2 map的简介 

二. set的主要接口函数及使用方法

2.1 构造及赋值相关接口函数

2.2 通过迭代器遍历set

2.3 结构修改相关接口函数

2.4 其他主要接口函数

三. map的主要接口函数及使用方法 

3.1 构造和赋值相关接口函数

3.2 通过迭代器遍历map

3.3 结构修改相关接口函数

3.3 查找和访问相关接口函数

---

一. set和map的简介

1.1 set的简介

• set是按照一定的次序顺序存储数据的容器。
• set的底层是通过二叉搜索树（红黑树）来实现的。
• 在默认情况下，set底层的二叉树遵循左子节点小于根节点、右子节点大于根节点且不能有相同节点的结构要求。
• 每个节点的值key具有const属性，不能被修改。
• 在set中查找某个特定数据的时间复杂度是O(NlogN)。
• 默认情况下，使用正向迭代器遍历set，是按照中序遍历进行的，也就是说会得到一组升序的数据。
• set不可以存储相同的节点，但是multiset可以，multiset与set唯一的不同就是可以存储相同值的节点。

1.2 map的简介 

• map是关联式容器。其结构与set类似，底层都是通过红黑树来实现的。
• map和set的不同在于，map存储的数据类型是以Key和Value组成的键值对<Key, Value>，通过比较Key的值来使map满足搜索树的结构要求，而Value只是与Key进行配对的数据，不参数比较。
• map中不允许存储两个Key相同的节点，但是multimap允许。

二. set的主要接口函数及使用方法

2.1 构造及赋值相关接口函数

接口函数	功能
set(const compare& comp = compare)	默认构造，创建空树
set(InputIterator first, InputIterator last, ...)	使用迭代器区间初始化
set(const set& x)	拷贝构造
set& operator=(const set& x)	赋值运算符重载函数

代码2.1：（构造和赋值） 

int main()
{int arr[5] = { 5,2,3,4,1 };std::set<int> st1;   //默认构造std::set<int> st2(arr, arr + 5);   //迭代器区间构造std::set<int> st3(st2);  //拷贝构造std::set<int, std::greater<int>> st4;   //创建右子节点大于根节点左子节点小于根节点的setst1 = st3;  //赋值return 0;
}

2.2 通过迭代器遍历set

默认情况下，使用正向迭代器遍历set是进行中序遍历，得到一组升序的数据。

代码2.2：（set遍历的直接实现） 

int main()
{int arr[5] = { 5,2,3,4,1 };std::set<int> st1(arr, arr + 5);std::set<int, std::greater<int>> st2(arr, arr + 5);//给定迭代器std::set<int>::iterator it1 = st1.begin();std::set<int, std::greater<int>>::iterator it2 = st2.begin();//正向迭代器遍历st1，得到一组升序数据while (it1 != st1.end()){std::cout << *it1++ << " ";}std::cout << std::endl;//正向迭代器遍历st2，得到一组降序数据while (it2 != st2.end()){std::cout << *it2++ << " ";}std::cout << std::endl;return 0;
}

代码2.3：（set遍历的函数模板实现）

template<class T, class Compare = std::less<T>>
void SetPrint(const std::set<T, Compare>& st)
{typename std::set<T, Compare>::const_iterator it = st.begin();while (it != st.end()){std::cout << *it++ << " ";}std::cout << std::endl;
}

2.3 结构修改相关接口函数

接口函数	功能
pair<iterator,bool> insert(const Type& x)	在插入值为x的节点
void insert(InputIterator first, InputIterator last)	插入位于一段迭代器区间的数据集
size_t erase(const Type& x)	删除指定值
void erase(iterator pos)	通过给定迭代器位置删除特定节点
void clear()	清空所有节点

• 这里需要注意insert函数的返回值：insert函数返回一键值对，pair中的first数据为iterator类型，如果成功插入节点（set中没有x），则返回新插入节点的位置的迭代器，如果插入节点失败，则返回与x值相同的节点的迭代器。pair中的second数据类型为bool，插入成功返回true，失败返回false。
• erase返回被删除的节点的个数，因为set不允许有相同的节点，因此erase返回值只能是1或0，而multiset中erase的返回值则可以大于1，因为multiset中允许相同节点的存在。
• 当调用erase函数给定值不存在或迭代器位置不合法时：如果使用给定值x的方法删除set的节点且x不存在，那么函数不进行任何工作，直接返回。如果给定不合法的迭代器位置调用erase，那么程序会崩溃。

代码2.4：（插入、删除和清空操作） 

int main()
{std::set<int> st;st.insert(7);st.insert(1);st.insert(0);st.insert(4);st.insert(5);   //插入数据SetPrint(st);   //set正向遍历打印函数st.erase(7);st.erase(10);st.erase(0);SetPrint(st);st.clear();   //清空元素SetPrint(st);return 0;
}

2.4 其他主要接口函数

接口函数	功能
iterator find(const Type& x) const	查找特定数据x函数
size_t  count(const Type& x) const	统计set中x出现的次数
iterator lower_bound (const Type& x) const	返回大于或等于x的最小节点
iterator upper_bound (const Type& x) const	返回大于x的最小节点
pair<iterator,iterator> equal_range (const Type& x) const	返回包含x的区间

• find函数如果没有找到值为x的节点，就返回end()的迭代器位置，如果要使用find函数的返回值，保险起见，应当检查 st.find(x) != st.end() 是否成立。
• 由于set中不允许有相同的节点，count的返回值只能是0或1。
• equal返回的区间只包含一个数：[first, second) -- 左开右闭区间，*first = x。

代码2.5：

int main()
{std::set<int> st = { 10,10,20,30,40,40,50,60,70,80,90 };//查找数据20 -- 找得到std::set<int>::iterator pos1 = st.find(20);  if (pos1 != st.end()){std::cout << "找到了" << std::endl;}else{std::cout << "没找到" << std::endl;}//查找数据100 -- 找不到std::set<int>::iterator pos2 = st.find(100);if (pos2 != st.end()){std::cout << "找到了" << std::endl;}else{std::cout << "没找到" << std::endl;}std::set<int>::iterator it1 = st.lower_bound(30);std::set<int>::iterator it2 = st.lower_bound(40);std::set<int>::iterator it3 = st.upper_bound(40);std::set<int>::iterator it4 = st.upper_bound(45);std::cout << "*it1 = " << *it1 << std::endl;std::cout << "*it2 = " << *it2 << std::endl;std::cout << "*it3 = " << *it3 << std::endl;std::cout << "*it4 = " << *it4 << std::endl;std::pair<std::set<int>::iterator, std::set<int>::iterator> pa = st.equal_range(50);std::cout << "first=" << *pa.first << ", " << "second=" << *pa.second << std::endl;return 0;
}

三. map的主要接口函数及使用方法 

3.1 构造和赋值相关接口函数

接口函数	功能
map(const compare& comp = compare)	默认构造，创建空树
map(InputIterator first, InputIterator last, ...)	使用迭代器区间初始化
map(const map& x)	拷贝构造
map& operator=(const map& x)	赋值运算符重载函数

代码3.1：（构造和赋值）

int main()
{std::map<int, int> mp1;  //默认构造std::map<int, int> rmp;rmp[1] = 1;rmp[3] = 3;rmp[2] = 2;std::map<int, int> mp2(rmp.begin(), rmp.end());  //通过迭代器区间构造std::map<int, int> mp3(mp2);  //拷贝构造mp1 = mp2;  //赋值return 0;
}

3.2 通过迭代器遍历map

注意：由于map存储的是键值对，对于map的迭代器it，不能直接对it解引用，*it会报错。如果想获取键值对中的数据，应当使用(*it).first/second 或it->first/second。

代码3.1：（迭代器遍历map）

int main()
{std::map<int, int> mp;mp[1] = 1;mp[3] = 3;mp[2] = 2;std::map<int, int>::iterator it = mp.begin();while (it != mp.end()){//std::cout << (*it).first << "=>" << (*it).second << " ";std::cout << it->first << "=>" << it->second << " ";++it;}std::cout << std::endl;return 0;
}

3.3 结构修改相关接口函数

接口函数	功能
pair<iterator,bool> insert(const pair<T1,T2>& x)	数据插入函数
void insert(InputIterator first, InputIterator second)	插入某段迭代器区间的数据
size_t erase(const Type_Key& x)	删除键值对中Key为x的数据
void erase(iterator pos)	删除特定迭代器位置的节点
void erase(iterator first, iterator second)	删除特定迭代器区间的节点
void clear()	清空元素

• make_pair(const Type1& key, const Type2& value) -- 键值对创建函数，给定参数为键值对的key和value，返回键值对pair<Type1,Type2>

代码3.2：（结构修改）

int main()
{std::map<int, int> mp;mp.insert(std::make_pair(5, 5));mp.insert(std::make_pair(7, 7));mp.insert(std::make_pair(3, 3));mp.insert(std::make_pair(1, 1));mp.insert(std::make_pair(9, 9));   //插入数据std::map<int, int>::iterator it = mp.begin();while (it != mp.end()){std::cout << it->first << "=>" << it->second << " ";++it;}std::cout << std::endl;mp.erase(1);mp.erase(9);  //给定值删除mp.erase(mp.begin());  //给定迭代器位置删除it = mp.begin();while (it != mp.end()){std::cout << it->first << "=>" << it->second << " ";++it;}std::cout << std::endl;mp.clear();  //清空元素return 0;
}

3.3 查找和访问相关接口函数

接口函数	功能
iterator find(const Key_Type x)	查找键值对Key为x的节点
Value_Type& operator[](const Key_Type x)	通过指定的Key的值x访问与之配对的Value值 / 创建Key值为x的新节点

• operator[]函数：如果在二叉map中找到了x，那么就直接返回与之配对的Value值的引用。如果没有找到x，那么就会以x为Key插入新的节点，但是Value的值就只能调用的类型的默认构造来给初值，无法保证新插入的节点的Value初值是需要的。

代码3.3：（查找和访问）

int main()
{std::map<int, int> mp;mp.insert(std::make_pair(5, 5));mp.insert(std::make_pair(7, 7));mp.insert(std::make_pair(3, 3));mp.insert(std::make_pair(1, 1));mp.insert(std::make_pair(9, 9));   std::map<int, int>::iterator it = mp.find(3);std::cout << it->first << "=>" << it->second << std::endl;mp[3] = 5;  //3存在std::cout << "mp[3] = " << mp[3] << std::endl;mp[10] = 10;   //10不存在std::cout << "mp[10] = " << mp[10] << std::endl;return 0;
}