惠山网站建设,网站开发项目报价,网站建设空间是否续费,中国核工业第二二建设有限公司待遇#x1fa90;#x1fa90;#x1fa90;欢迎来到程序员餐厅#x1f4ab;#x1f4ab;#x1f4ab; 主厨#xff1a;邪王真眼
主厨的主页#xff1a;Chef‘s blog 所属专栏#xff1a;c大冒险 总有光环在陨落#xff0c;总有新星在闪烁 一、 关联式容器 在初阶阶…
欢迎来到程序员餐厅 主厨邪王真眼
主厨的主页Chef‘s blog 所属专栏c大冒险 总有光环在陨落总有新星在闪烁 一、 关联式容器 在初阶阶段我们已经接触过 STL 中的部分容器比如 vector 、 list 、 deque 等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。那什么是关联式容器它与序列式容器有什么区别 关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是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。这四种容器的共同点是 使用红黑树作为其底层结果 容器中的元素是一个有序的序列。 3.1 set 1. set是按照一定次序存储元素的容器 2. 在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。 set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们。 3. 在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行 排序。 4. set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对 子集进行直接迭代。 注意事项 1. 与map/multimap不同map/multimap中存储的是真正的键值对key, valueset中只放 value但在底层实际存放的是由value, value构成的键值对。 2. set中插入元素时只需要插入value即可不需要构造键值对。 3. set中的元素不可以重复(因此可以使用set进行去重)。 4. 使用set的迭代器遍历set中的元素可以得到有序序列 5. set中的元素默认按照小于来比较 6. set中查找某个元素时间复杂度为log n 3.2 map的介绍 1. map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。 2. 在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的 内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员value_type绑定在一起为其取别名称为pair: typedef pairconst key, T value_type; 3. 在内部map中的元素总是按照键值key进行比较排序的。 4. map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序 对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。 5. map支持下标访问符即在[]中放入key就可以找到与key对应的value。
3.3 multiset
1. multiset是按照特定顺序存储元素的容器其中元素是可以重复的。 2. 在multiset中元素的value也会识别它(因为multiset中本身存储的就是value, value组成 的键值对因此value本身就是keykey就是value类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)但可以从容器中插入或删除。 3. 在内部multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。 4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢但当使用迭 代器遍历时会得到一个有序序列。 注意事项 1. multiset中再底层中存储的是value, value的键值对 2. mtltiset的插入接口中只需要插入即可 3. 与set的区别是multiset中的元素可以重复set是中value是唯一的 4. 使用迭代器对multiset中的元素进行遍历可以得到有序的序列 5. multiset中的元素不能修改 6. 在multiset中找某个元素时间复杂度为O(log 2N)7. multiset的作用可以对元素进行排序
3.4 multimap的介绍
1. Multimaps是关联式容器它按照特定的顺序存储由key和value映射成的键值对key, value其中多个键值对之间的key是可以重复的。 2. 在multimap中通常按照key排序和惟一地标识元素而映射的value存储与key关联的内 容。key和value的类型可能不同通过multimap内部的成员类型value_type组合在一起 value_type是组合key和value的键值对:typedef pairconst Key, T value_type; 3. 在内部multimap中的元素总是通过其内部比较对象按照指定的特定严格弱排序标准对 key进行排序的。 4. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢但是使用迭代 器直接遍历multimap中的元素可以得到关于key有序的序列。 multimap和map的唯一不同就是map中的key是唯一的而multimap中key是可以重复的。 四、改造红黑树 我们现在知道了这些树形容器都是对红黑树进行了封装但是如果直接用之前写的红黑树会导致set和map分别要建一颗红黑树为了提高代码的复用率我们要对红黑树改造使得map和set可以共用一颗进行封装。
4.1红黑树节点 注意事项 在红黑树里存的值类型是T而不是之前的pairK,V,这是为了使之可以同时满足set存键值map存键值对
enum Color
{RED,BLACK
};templateclass T
struct RBTreeNode
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Color _col;RBTreeNode(const T data): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};4.2 迭代器 之前的红黑树没有迭代器我们要设计出双向的迭代器要求是向后遍历等同于中序以最左节点为begin,最右节点为end
templateclass T, class Ref, class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT, T, T* Iterator;typedef RBTreeIteratorT, Ref, Ptr Self;Node* _node;RBTreeIterator(Node* node): _node(node){}RBTreeIterator(const Iterator it): _node(it._node){}Ref operator*(){return _node-_data;}Ptr operator-(){return (operator*());}bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}
};注意事项
1.看过我之前写的迭代器博客的老铁应该直到为什么要有三个模板参数这是为了使iterator和const迭代器都能调用同一个函数而不用分别设计一个2.红黑树是二叉搜索树它存的键值不能修改因为你不能保证修改后还是搜索树所以对*的重载返回值是Refconst T3.-的返回值不应被修改所以是Ptrconst T*;4.迭代器的拷贝构造函数在普通迭代器调用时以普通迭代器拷贝出普通迭代器在const迭代器调用时以普通迭代器拷贝出const迭代器
4.2.1 operator
前置 右不为空找右子树的最左结点右为空向上找孩子是父亲左的那个父亲返回引用后置复用前置返回临时对象返回值而非引用
Self operator()
{if (_node-right)//右不为空找右子树的最左结点{_node _node-right;while (_node-_left)_node _node-_left;}else//右为空向上找孩子是父亲左的那个父亲{while (_node-_parent _node-_parent-right _node){_node _node-_parent;}}return *this;
}
Self operator(int)
{Iterator news this;this:return *news;
} 4.2.2 operator- -
前置- -的思路 左不为空找左子树的最右结点左为空向上找孩子是父亲右的那个父亲后置- -复用前置- -返回临时对象
Self operator--()//左不为空找左子树的最右结点
{if (_node-left){_node_node-_leftwhile (_node-_right)_node _node-right;}else//左为空向上找孩子是父亲右的那个父亲{while (_node-_parent node-_parent-_left _node)_node _node-_parent;_node _node-parent;}
}
Self operator--(int)
{Self tmp *this;--*this;return tmp;
} 4.3 RBTree的修改
4.3.1 成员变量
注意事项
直接给缺省值为nullptr不必写构造函数模板参数第一个为K是键值类型模板参数第二个为T同时适用set存储键值和map存储键值对模板参数第三个为KeyOfT仿函数类型用于获取不同数据T的键值key
templateclass K, class T, class KeyOfT
class RBTree
{
protected:typedef RBTreeNodeT Node;
public:
protected:Node* _root nullptr;
};4.3.2 begin和end
注意事项 begin返回最左节点的迭代器end返回空迭代器不是最右节点的迭代器
typedef RBTreeIteratorT, T, T*iterator;
typedef RBTreeIteratorT, const T, const T *const_iterator;
iterator begin()
{Node* cur _root;if (cur nullptr)return iterator(nullptr);while (cur-_left)cur cur-_leftreturn iterator(cur);
}
const_iterator begin()const
{Node* cur _root;if (cur nullptr)return const_iterator(nullptr);while (cur-_left)cur cur-_left;return const_iterator(cur);
}
iterator end()
{return iterator(nullptr);
}
const_iterator end()const
{return const_iterator(nullptr);
}
4.3.3 Find
思路
返回迭代器运用仿函数进行键值比较从而适配map和set
iterator Find(const K key)
{if (_root nullptr){return iterator(nullptr);}KeyOfT kot;Node* cur _root;while (cur){if (kot(cur-_data) key){cur cur-_right;}else if (kot(cur-_data) key){cur cur-_left;}else{return iterator(cur);}}return iterator(nullptr);
}4.3.4 Insert
思路
返回pair第一个参数为迭代器第二个参数为布尔值记录是否插入成功运用仿函数进行键值比较从而适配map和set
pairiterator, bool Insert(const T data)
{if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(iterator(_root), true);}KeyOfT kot;Node* parent nullptr;Node* cur _root;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);}}Node* newnode new Node(data);cur newnode;if (kot(parent-_data) kot(data)){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandparent parent-_parent;if (grandparent-_right parent)//uncle在左parent在右{Node* uncle grandparent-_left;if (uncle uncle-_col RED)//uncle为红变色向上调整{parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent cur-_parent;}else//uncle为空或为黑变色旋转{if (parent-_right cur)//左单旋{RotateL(grandparent);parent-_col BLACK;grandparent-_col RED;}else//右左旋{RotateR(parent);RotateL(grandparent);cur-_col BLACK;grandparent-_col RED;}}}else//parent在左uncle在右{Node* uncle grandparent-_right;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent cur-_parent;}else{if (parent-_left cur)//右单旋{RotateR(grandparent);parent-_col BLACK;grandparent-_col RED;}else//左右旋{RotateL(parent);RotateR(grandparent);cur-_col BLACK;grandparent-_col RED;}}}}_root-_col BLACK;return make_pair(iterator(newnode), true);
}五、set
5.1 成员变量与仿函数
细节
set类仿函数直接返回参数key成员变量的第二个模板参数为K第三个模板参数为SetKeyOfT
templateclass K
class set
{struct SetKeyOfT{const K operator()(const K key){return key;}};
public:
protected:RBTreeK, K, SetKeyOfT _t;
};5.2 begin和end
细节 1.set中存储的键值key均不允许修改所以其普通迭代器和const迭代器均为红黑树的const迭代器。 2.set调用普通begin()时begin函数所调用的begin的返回值是普通迭代器可要求返回值是const迭代器便有从普通迭代器到const迭代器的转换产生临时变量用到了之前写的拷贝构造以普通迭代器拷贝构造const迭代器
typedef RBTreeK,K,SetKeyOfT::const_iterator iterator;
typedef RBTreeK, K, SetKeyOfT::const_iterator const_iterator;
iterator begin()
{return _t.begin();
}
const_iterator begin()const
{return _t.begin();
}
iterator end()
{return _t.end();
}
const_iterator end()const
{return _t.end();
}5.3 find
iterator find(const K key)
{return _t.Find(key);
}5.4 insert
pairiterator, bool insert(const K key)
{return _t.Insert(key);
}细节
插入参数类型为K键值此时也有从普通迭代器到const迭代器的转换
六、map
6.1 成员变量与仿函数
templateclass K, class V
class map
{struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};
public:
protected:RBTreeK, pairconst K, V, MapKeyOfT _t;
};细节
map类仿函数返回参数pair的first成员变量的第二个模板参数为pair第三个模板参数为MapKeyOfT
6.2 begin和end
typedef RBTreeK, pairconst K,V, MapKeyOfT::const_iterator iterator;
typedef RBTreeK, pairconst K,V, MapKeyOfT::const_iterator const_iterator;
iterator begin()
{return _t.begin();
}
const_iterator begin()const
{return _t.begin();
}
iterator end()
{return _t.end();
}
const_iterator end()const
{return _t.end();
}
注意事项 map不允许修改key所以除了迭代器都是const迭代器之外还要对键值对里的key进行const修饰。
6.3 find
iterator find(const K key)
{return _t.Find(key);
}6.4 insert
pairiterator, bool Insert(pairconst K, Vkv)
{return _t.Insert(kv);
}
6.5 operator[ ]
在插入和修改使用[ ]会很方便。
V operator[](const K key)
{pairconst K, V kv(key,V());return _t.Insert(kv).first-second;
}
注意事项 返回值可以帮我们直接修改键值对中的V
总结、
今日份学习内容如下
1.了解了关联性容器和键值对的概念2.了解了以红黑树为基础的四大容器的作用3.重写了红黑树4.模拟了map和set并分析了种种设置的原因 赠人一赞日行一善
