中央人民政府网电话_免费行情软件app下载安装_营销技巧和营销方法培训_有没有购买链接

        一、关联式容器

        在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、 forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面 存储的是元素本身。

        关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高。

二、键值对（key，value）

键值对就是用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。

比如：现在要建立一个英汉互译的字典，那该字典中必然 有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应 该单词，在词典中就可以找到与其对应的中文含义。

SGI-STL中关于键值对的定义：

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){}};

三、树形结构的关联式容器

        根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。

        树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使 用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一 个容器。

四、set

4.1set的介绍

1. set是按照一定次序存储元素的容器

2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。 set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。

3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行 排序。

4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对 子集进行直接迭代。

5. set在底层是用二叉搜索树(红黑树)实现的。

注意：

1. 与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放 value，但在底层实际存放的是由构成的键值对。

2. set中插入元素时，只需要插入value即可，不需要构造键值对。

3. set中的元素不可以重复(因此可以使用set进行去重)。

4. 使用set的迭代器遍历set中的元素，可以得到有序序列

5. set中的元素默认按照小于来比较

6. set中查找某个元素，时间复杂度为：logN

7. set中的元素不允许修改(为什么?)

8. set中的底层使用二叉搜索树(红黑树)来实现。

4.2set函数讲解

T: set中存放元素的类型，实际在底层存储的键值对。

Compare：set中元素默认按照小于来比较

Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

1、set的构造

2、set的迭代器

3、set的容量

4、set修改操作

count和find的作用一样，都是用于查找set中是否存在某个元素。

其实count是为了容器multiset设计的，该容器允许插入重复的元素，此时count会返回红黑树中被搜索元素的个数。

#include <iostream>
#include <set>int main ()
{std::set<int> myset;// set some initial values:for (int i=1; i<5; ++i) myset.insert(i*3);    // set: 3 6 9 12for (int i=0; i<10; ++i){std::cout << i;if (myset.count(i)!=0)std::cout << " is an element of myset.\n";elsestd::cout << " is not an element of myset.\n";}return 0;
}

 5、在set中用于返回目标值的迭代器

iterator lower_bound (const value_type& val) const;

iterator upper_bound (const value_type& val) const;

pair<iterator,iterator> equal_range 
(const value_type& val) const;

他们可以找到两个边界的迭代器，然后使用erase对数据进行删除

#include <iostream>
#include <map>int main ()
{std::map<char,int> mymap;std::map<char,int>::iterator itlow,itup;mymap['a']=20;mymap['b']=40;mymap['c']=60;mymap['d']=80;mymap['e']=100;itlow=mymap.lower_bound ('b');  // itlow points to bitup=mymap.upper_bound ('d');   // itup points to e (not d!)mymap.erase(itlow,itup);        // a => 20  e => 100// print content:for (std::map<char,int>::iterator it=mymap.begin(); it!=mymap.end(); ++it)std::cout << it->first << " => " << it->second << '\n';return 0;
}

4.3set使用举例

#include <set>void TestSet(){// 用数组array中的元素构造setint array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };set<int> s(array, array+sizeof(array)/sizeof(array[0]));cout << s.size() << endl;// 正向打印set中的元素，从打印结果中可以看出：set可去重for (auto& e : s)cout << e << " ";cout << endl;// 使用迭代器逆向打印set中的元素for (auto it = s.rbegin(); it != s.rend(); ++it)cout << *it << " ";cout << endl;// set中值为3的元素出现了几次cout << s.count(3) << endl;}

五、map

5.1map的介绍

1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。

2. 在map中，键值key通常用于排序和查找唯一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair: typedef pair value_type;

3. 在内部，map中的元素总是按照键值key进行比较排序的。

4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序 对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。

5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。

6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

5.2map函数讲解

key: 键值对中key的类型

T： 键值对中value的类型

Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比 较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户 自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的 空间配置器

注意：在使用map时，需要包含头文件。

1、map的构造

2、map的迭代器

3、map的容量与元素访问

std::map::operator[ ] 详细分析

​

分析可知，operator[ ]从内部调用insert函数得到ret = pair<key的迭代器，bool>，然后通过key的迭代器去访问pair<key，value>中的value，即 ret.first->second。所以可以通过operator[ ]对value进行插入和修改。

调用insert函数主要是为了得到key的迭代器。而value存不存在都不重要，value存在bool为false，operator[ ]函数返回的是已经存在的value；value不存在则用默认value构造pair去插入，bool为true，operator[ ]函数返回默认的value。

元素访问时，还有和其相类似的不常用函数map::at。如果key存在时，返回value，否则抛异常。

4、map中的元素修改

int main()
{map<string, string> m;pair<string, string> p("string", "字符串");m.insert(p);m.insert(make_pair("insert", "插入"));m["left"] = "左";m["right"] = "右";map<string, string>::iterator it = m.begin();while (it != m.end()){cout << it->first << " : " << it->second << endl;++it;}return 0;
}

 5、在map中用于返回目标值的迭代器

​

此几种函数和对应的set函数的功能一样，不多赘述。

5.3map总结

1. map中的的元素是键值对

2. map中的key是唯一的，并且不能修改

3. 默认按照小于的方式对key进行比较

4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列

5. map的底层为平衡搜索树(红黑树)，查找效率比较高O(logN)

6. 支持[ ]操作符，operator[]中实际进行插入查找。

六、multiset

multiset中的接口可以参考set，功能都是类似的。

1. multiset中在底层中存储的是的键值对

2. multiset的插入接口中只需要插入即可

3. 与set的区别是，multiset中的元素可以重复，set是中value是唯一的

4. 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列

5. multiset中的元素不能修改

6. 在multiset中找某个元素，时间复杂度为O(logN)

7. multiset的作用：可以对元素进行排序

七、multimap

multimap中的接口可以参考map，功能都是类似的。

1. multimap中的key是可以重复的。

2. multimap中的元素默认将key按照小于来比较

3. multimap中没有重载operator[ ]操作。

4. 使用时与map包含的头文件相同：

注意：multimap和map的唯一不同就是：

map中的key是唯一的，而multimap中key是可以重复的。

八、模拟实现map和set

8.1、set/map的底层结构

        STL库中set和map底层结构都是红黑树，且均为key/value模型。他们都用自身第二个模板参数value去实例化红黑树，所以实例化出的红黑树类型并不相同。

set的key/value使用key/key填充，而map的key/value使用key/pair<const key，value>填充。

而此时的红黑树结构为：

enum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}
};

因为T不同，set的T为key，map的T为pair<const key，value>，所以实例化出的红黑树不同。

8.2利用仿函数控制比较大小

        我们会发现红黑树的插入等接口会对key值进行比较大小，像set直接对key进行比较，这没问题，但是map中的节点装的是pair<K,V>,pair的比较规则是first比完之后可能会再去比较second（而我们仅仅想要比较first，该比较规则不适用）。

        通过源码启发，我们可以对红黑树新增一个模板参数：仿函数KeyOfT，在set和map类中完善该仿函数的比较对象，用于区分set和map的比较：

template <class K>
class set
{//仿函数用于比较大小struct SetKeyOfT{const K& operator()(const K& key)//传入节点的值{return key;//返回key}};
private:RBTree<K, K, SetKeyOfT> _t;
};
class map
{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv)//传入节点的值{return kv.first;//返回kv.first}};
private:RBTree<const K, pair<K,V>, MapKeyOfT> _t;
};
//利用模板确定传入对象是set还是map
template <class K, class T,class KeyOfT>
class RBTree//红黑树
{};

 利用仿函数，传入节点的值，set将会返回key值，map将会的返回pair的first。这样就解决了比较大小的规则问题。

Node* Find(const K& key)
{Node* cur = _root;KeyOfT kot;while (cur){//得到map中的key进行比较if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return cur;}}return nullptr;
}

8.3、set/map的迭代器（红黑树的迭代器）

        因为红黑树的中序遍历是有序的，可以根据中序遍历作为迭代器++--的依据。

        STL源码采用下图结构，多搞了一个头结点。迭代器begin()可以指向header的左，迭代器end()指向header。

但本文采用无头结点的常规红黑树仿写红黑树的迭代器。

8.3.1、红黑树的begin、end迭代器

iterator begin()
{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return iterator(leftMin);
}iterator end()
{return iterator(nullptr);
}

8.3.2、红黑树迭代器的operator++

        1、如果当前节点的右不为空，迭代器++返回右子树的最左节点

        2、如果当前节点的右为空，迭代器++返回祖先（当前节点是父亲的左）(end()-1迭代器++

返回nullptr即end())

template <class T>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T> Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}//1、右不为空，下一个节点是右树的最小节点//2、右为空，去找右是父亲左的最近祖先Self& operator++()//找中序的下一个节点,即根的右树的最左节点,返回值是一个迭代器的对象{if (_node->_right != nullptr){Node* min = _node->_right;while (min->_left != nullptr){min = min->_left;}_node = min;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent != nullptr && cur == parent->_right){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}bool operator!=(const Self& s){return _node != s._node;}
};

8.3.3、红黑树迭代器的operator--

        1、如果当前节点的左不为空，迭代器--返回左子树的最右节点

        2、如果当前节点的左为空，迭代器--返回祖先（当前节点是父亲的右）

template <class T>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T> Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}Self& operator--(){if (_node->_left!=nullptr){Node* max = _node;while (max->_right){max = max->_right;}_node = max;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent != nullptr && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}
};

8.4、set的const迭代器

        对于set和map，它们的key都是不能改的。set的value不能修改，map的value可以修改。

        因为set的value是不能改的，所以它的底层将普通迭代器和const迭代器全部封装成const迭代器来“解决”：

//自己实现的，不代表STL
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

        封装之后又会出现新问题，set使用迭代器其实都是在使用const迭代器，但是自己实现的红黑树的迭代器接口返回普通类型的迭代器，在Set.h中对this加上const“解决”：

iterator begin()const
{return _t.begin();
}
iterator end()const
{return _t.end();
}

        这时使用迭代器调用上方函数会发现红黑树返回了普通迭代器类型的迭代器，类型不匹配。在红黑树中补齐const版本的迭代器函数解决：

const_iterator begin()const//找红黑树最左节点
{Node* left = _root;while (left != nullptr && left->_left != nullptr){left = left->_left;}return const_iterator(left);
}
const_iterator end()const
{return const_iterator(nullptr);
}

8.5、map的const迭代器

map的value是可以改的，所以要分别设计普通迭代器和const迭代器。

typedef typename RBTree<const K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<const K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
iterator begin()
{return _t.begin();
}
iterator end()
{return _t.end();
}
const_iterator begin()const
{return _t.begin();
}
const_iterator end()const
{return _t.end();
}

8.6、迭代器类的拷贝构造

STL库中的普通迭代器都可以转换为const迭代器，这是迭代器类的拷贝构造所支持的。

这个拷贝构造有点特殊：

//红黑树的迭代器
template <class T,class Ref,class Ptr>//key/value、T&、T*
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ref, Ptr> Self;typedef __RBTreeIterator<T, T&, T*> iterator;Node* _node;__RBTreeIterator(Node* node):_node(node){}__RBTreeIterator(const iterator& it)//const iterator本质还是普通迭代器:_node(it._node){}
};

        1、当这个模板的的Ref和Ptr被实例化为T&和T*时，__RBTreeIterator(const iterator& it)就是一个拷贝构造(没啥意义)

        2、当这个模板的的Ref和Ptr被实例化为const T&和const T*时，__RBTreeIterator(const iterator& it)就是一个构造函数，支持用普通迭代器去构造const迭代器。此时const迭代器的拷贝构造函数则由编译器自动生成，刚好满足迭代器值拷贝的特点。

九、模拟实现代码

1、RBTree.h

#pragma once
#include<iostream>
using namespace std;enum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};template<class T, class Ptr, class Ref>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ptr, Ref> Self;typedef __TreeIterator<T, T*, T&> Iterator;__TreeIterator(const Iterator& it):_node(it._node){}Node* _node;__TreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node != s._node;}Self& operator--(){if (_node->_left){Node* subRight = _node->_left;while (subRight->_right){subRight = subRight->_right;}_node = subRight;}else{// 孩子是父亲的右的那个节点Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator++(){if (_node->_right){// 右树的最左节点(最小节点)Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else{Node* cur = _node;Node* parent = cur->_parent;// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点while (parent && cur == parent->_right){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}
};// set->RBTree<K, K, SetKeyOfT> _t;
// map->RBTree<K, pair<K, V>, MapKeyOfT> _t;
template<class K, class T, class KeyOfT>
struct RBTree
{typedef RBTreeNode<T> Node;
public:// 同一个类模板，传的不同的参数实例化出的不同类型typedef __TreeIterator<T, T*, T&> iterator;typedef __TreeIterator<T, const T*, const T&> const_iterator;iterator begin(){Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return iterator(leftMin);}iterator end(){return iterator(nullptr);}const_iterator begin() const{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return const_iterator(leftMin);}const_iterator end() const{return const_iterator(nullptr);}Node* Find(const K& key){Node* cur = _root;KeyOfT kot;while (cur){//得到map中的key进行比较if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return cur;}}return nullptr;}pair<iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}Node* parent = nullptr;Node* cur = _root;KeyOfT kot;while (cur){if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);}}cur = new Node(data);cur->_col = RED;Node* newnode = cur;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;// u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else // u不存在 或 存在且为黑{if (cur == parent->_left){//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else // parent == grandfather->_right{Node* uncle = grandfather->_left;// u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){// g//	  p//       cRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g//	  p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}void RotateL(Node* parent){++_rotateCount;Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){++_rotateCount;Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK){return false;}// 基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);}int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr)return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}private:Node* _root = nullptr;public:int _rotateCount = 0;
};

2、Set.h

#pragma once
#include"RBTree.h"
namespace a
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:public:typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}// iterator RBTree::const_iteratorpair<iterator, bool> insert(const K& key){// pair<RBTree::iterator, bool>pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);return pair<iterator, bool>(ret.first, ret.second);}private:RBTree<K, K, SetKeyOfT> _t;};
}

3、Map.h

#pragma once
#include"RBTree.h"
namespace a
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};
}