文章目录
- 1.set的原型
- 2.set的成员函数
- 1.构造函数
- 2.代码演示
- 3.map的原型
- 4.map的成员函数
- 1.构造函数
- 2.代码演示
- 5.OJ练习
- 1.前K个高频单词
- 2.两个数组的交集
- 3.随即链表的复制
1.set的原型
template <class T, //set::key_typeclass Compare = less<T>, //set::key_compareclass Alloc = allocator<T> //set::allocator_type >
class set;
2.set的成员函数
1.构造函数
//全缺省构造
explicit set(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
//迭代器区间构造
template <class InputIterator>
set(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
//拷贝构造
set(const set& x);
2.代码演示
//插入、迭代器、范围for
void test_set1()
{//初始化1.0set<int> s;s.insert(3);s.insert(1);s.insert(4);s.insert(2);s.insert(1);s.insert(2);//初始化2.0//set<int> s = { 1,2,1 }; //set<int,greater<int> s = { 1,2,1 }; //显式传compare//初始化3.0//int a[] = { 1,2,1 };//set<int> s(a, a + sizeof(a) / sizeof(int));set<int>::iterator it = s.begin();while (it != s.end()){// 二叉搜索树不允许修改key--破坏二叉搜索树的原则cout << *it << " ";++it;}cout << endl;// 范围forfor (auto e : s){cout << e << " ";}cout << endl;//set遍历后数据变成有序的 -- 搜索二叉树中序遍历 -- 有序数据
}
//erase 查找是否存在:find/count 删除某个范围的值
void test_set2()
{set<int> s;s.insert(3);s.insert(1);s.insert(4);s.insert(2);s.insert(1);s.insert(2);s.erase(30);//erase的底层auto pos = s.find(30);if (pos != s.end()){s.erase(pos);}int x;while (cin >> x){/* auto ret = s.find(x);if (ret != s.end()){cout << "yes" << endl;}else{cout << "no" << endl;}*///count在set里的取值: 1 0if (s.count(x)){cout << "yes" << endl;}else{cout << "no" << endl;}}set<int> s1;set<int>::iterator itlow, itup;for (int i = 1; i < 10; i++)s1.insert(i * 10); //10 20 30 40 50 60 70 80 90itlow = s1.lower_bound(25); //记录25或25后一个元素 itup = s1.upper_bound(60); //记录55后一个元素的位置 s1.erase(itlow, itup); //[ , ) cout << "s1 contains:";for (auto it = s1.begin(); it != s1.end(); ++it)cout << ' ' << *it;cout << '\n';
}//多重set:multiset 允许键值冗余[重复]
void test_set3()
{multiset<int> ms;ms.insert(3);ms.insert(1);ms.insert(4);ms.insert(2);ms.insert(1);ms.insert(1);ms.insert(1);ms.insert(2);multiset<int>::iterator mit = ms.begin();while (mit != ms.end()){cout << *mit << " ";++mit;}cout << endl;//中序遍历的第一个xauto pos = ms.find(1);while (pos != ms.end() && *pos == 1){cout << *pos << " ";++pos;}cout << endl;cout << "1的个数" << ms.count(1) << endl;ms.erase(1); //删除所有的1cout << "1的个数" << ms.count(1) << endl;cout << "2的个数" << ms.count(2) << endl;//删除第1个3auto pos = ms.find(3);if (pos != ms.end()){ms.erase(pos);}//删除第2个3++pos;if (pos != ms.end()){ms.erase(pos);}
}
3.map的原型
template < class Key, // key_type class T, // mapped_type class Compare = less<Key>, //key_compareclass Alloc = allocator<pair<const Key,T> > // allocator_type>
class map;
4.map的成员函数
1.构造函数
//全缺省默认构造
explicit map(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
//迭代器区间构造
template <class InputIterator>
map(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
//拷贝构造
map(const map& x);
2.代码演示
/*
template <class T1, class T2>
struct pair
{T1 _key;T2 _value;pair(): _key(T1()), _value(T2()){}pair(const T1& a, const T2& b): _key(a), _value(b){}
};
*//*template <class T1,class T2>inline pair<Tl,T2> make_pair (Tl x, T2 y){return ( pair<T1, T2>(x, y) ); }
*///插入、迭代器、make_pair
void test_map1()
{map<string, string> m;//创建pair -- 传参pair<string, string> p("Kevin", "凯文");m.insert(p);//匿名对象m.insert(pair<string, string>("Kevin", "凯文"));//make_pairm.insert(make_pair("Eddie", "彭于晏"));m.insert(make_pair("Tom", "汤姆"));m.insert(make_pair("Jerry", "杰瑞"));//map<string, string>::iterator auto it = m.begin();while (it != m.end()){//cout << (*it).first << "-" << (*it).second << endl;cout << it->first << "-" << it->second << endl;++it;}cout << endl;for (const auto& e : m){cout << e.first << "-" << e.second << endl;}cout << endl;
}//count的功能[初识at]
/*
pair(const T1& a, const T2& b): _key(a), _value(b)
{}
1.查找
查找key是否存在
存在返回value的引用
不存在插入 pair( key, V() ) 返回value的引用
2.查找 + 修改
查找key 存在 返回value的引用 将其赋值成新值--修改
3.查找 + 插入
查找key 不存在 插入key 分配value 返回value引用
*//*
V& at(const K& key);
查找key是否存在
存在返回value的引用
不存在抛异常
*/void test_map2()
{map<string, string> m;m.insert(make_pair("Eddie", "彭于晏"));m.insert(make_pair("Tom", "汤姆"));m.insert(make_pair("Jerry", "杰瑞"));//m.insert(make_pair("Eddie", "(彭于晏)")); // 插入失败:已经有了string:key不能重复m["abc"]; // 查找+插入: m中没有abc 插入abc并调用默认构造为其分配一个映射值即value 返回value的引用m["ABC"] = "牛顿"; // 查找+插入+赋值: m中没有ABC 插入ABC并调用默认构造为其分配一个映射值即value 返回value的引用 将value赋值为"牛顿" m["Eddie"] = "埃迪"; // 查找+修改: m中有Eddie 返回与其匹配的value的引用 将其修改为埃迪cout << m["string"] << endl; // 查找输出string对应的value值
}//统计玩具次数
void test_map3()
{string s[] = { "陀螺", "陀螺", "洋娃娃", "陀螺", "洋娃娃", "洋娃娃", "陀螺", "洋娃娃", "悠悠球", "洋娃娃", "悠悠球", "乐高" };//法一://map<string, int> count;// for (auto& key : s)//{// auto pos = count.find(key);// if (pos == count.end()) //没找到 map里没有此元素 插入// {// count.insert(make_pair(key, 1));// }// else// {// pos->second++;// }//}//法二:map<string, int> count;for (auto& key : s){/*template<class K,class V>class map{K _key;V _value;};template <class T1, class T2>struct pair{T1 first;T2 second;pair(): first(T1()), second(T2()){}pair(const T1& a, const T2& b): first(a) , second(b){}};insert函数调用 pair<iterator,bool> insert(const pair<K,V>& p); iterator insert(iterator pos, const pair<K,V>& p); //在pos处 插入一个键值对 返回pos迭代器template <class InputIterator> void insert(InputIterator first, InputIterator last); //迭代器区间构造 返回值为voidV& operator[](const K& key){pair<iterator, bool> it = insert( make_pair( key, V() ) );//插入一个键值对 返回键值对类型return it.first->second; //返回value的引用//it是一个键值对类型 //it.first: 访问类pair的first成员变量 在此pair里first类型为iterator 即it.first为指向key的迭代器[结构体指针类型]//访问value: (*it.first).second == it.first->second}*///key不在count 插入pair( key, int() ) iterator指向key bool-true//key在count iterator指向原有key bool-falsecount[key]++;}for (auto& toy : count){cout << toy.first << ":" << toy.second << endl;}
}
5.OJ练习
1.前K个高频单词
前K个高频单词
2.两个数组的交集
两个数组的交集
3.随即链表的复制
随机链表的复制