目錄
概述
算法
源碼
Iterator.h
RBTree.h
Map.h
Set.h
test.cpp
概述
map和set都是STL中的關(guān)聯(lián)式容器，而vector、list、deque是序列式容器。
map是映像，set是集合，map元素的數(shù)據(jù)類型是std::pair<K,V>格式(key/value形成映像)，set元素的數(shù)據(jù)類型只有key值。
map和set的實現(xiàn)是對紅黑樹的封裝，map根據(jù)key值進行排序，map和set的key值都是不可修改的，但是map的value值可以修改。
map和set支持迭代器、反向迭代器、常量迭代器，并且通過精妙的泛型設(shè)計，大大簡化了代碼，但是完成兩個STL容器的基本功能封裝，依舊需要千行代碼左右。
算法
本文里面的紅黑樹模塊相較于上一篇博客，做了部分修改，設(shè)計了紅黑樹的迭代器，并將迭代器單獨作為一個模塊，通過普通迭代器構(gòu)造出反向迭代器，這里采用的設(shè)計思路與之前 list 容器的迭代器設(shè)計思路是相同的。
紅黑樹在普通迭代器類中，設(shè)計出通過普通迭代器拷貝出const迭代器，這樣解決了set模塊的insert函數(shù)的返回值由紅黑樹的iterator轉(zhuǎn)換為const_iterator問題。
紅黑樹迭代器的自增、自減都有其獨特的算法，但是本文中的紅黑樹結(jié)構(gòu)，與stl標準庫中的紅黑樹略有不同，本文的紅黑樹沒有一個空的頭結(jié)點，即：當?shù)鞯絜nd()，即迭代器指向nullptr。而在stl標準庫中，迭代器走到end()時，迭代器指向空的頭結(jié)點。
紅黑樹的構(gòu)造可以通過元素插入構(gòu)造或者拷貝構(gòu)造，拷貝構(gòu)造設(shè)計了迭代器構(gòu)造，這也是拷貝構(gòu)造的核心。map和set的迭代器構(gòu)造、拷貝構(gòu)造、賦值構(gòu)造本質(zhì)都是調(diào)用紅黑樹的迭代器構(gòu)造。
紅黑樹的泛型設(shè)計十分精妙（紅黑樹自身并不知道自己是要構(gòu)造出一個map還是set，但是他必須兼容這兩種容器的所有特性），并通過仿函數(shù)KofT設(shè)計，實現(xiàn)了從傳入的元素數(shù)據(jù)(key值或key/value鍵值對)之中提取到key值進行排序
set模塊的迭代器設(shè)計十分精妙，因為set里面元素都是key值，而紅黑樹的key值是不允許修改的，所以無論是set的普通迭代器iterator還是const_iterator，其本質(zhì)都是const_iterator，所以set在設(shè)計時用const_iterator來重命名iterator，在普通迭代器的構(gòu)造函數(shù)時加上了const修飾，而省略了const_iterator的構(gòu)造函數(shù)，使iterator的構(gòu)造函數(shù)能夠?qū)onst_iterator構(gòu)成重載。文章來源：http://www.zghlxwxcb.cn/news/detail-434741.html
map的 "[ ]" 運算符有特殊功能，即可以通過 "[ ] " 來進行數(shù)據(jù)插入、查找、統(tǒng)計，原理是：若 "[ ]" 里面數(shù)據(jù)的key值已經(jīng)存在的話，則插入失敗，insert函數(shù)返回已有節(jié)點的迭代器和一個bool值false，然后 "[ ] " 運算符返回這個迭代器(pair<key, value>)的第二個數(shù)據(jù)(value)；若 "[ ]"? 里面數(shù)據(jù)的key不存在，則插入成功，insert函數(shù)返回新插入節(jié)點的迭代器和bool值true，然后 "[ ]" 運算符返回這個鍵值對迭代器的value值。因此我們可以通過這個原理對鍵值對的第二個數(shù)據(jù)為整型類型的數(shù)據(jù)進行計數(shù)操作。文章來源地址http://www.zghlxwxcb.cn/news/detail-434741.html
源碼
Iterator.h
#pragma once
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
RBTreeNode(const T data)
: _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED)
{}
};
template<class T, class Ref, class Ptr>
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)
{}
// 普通迭代器構(gòu)造const迭代器
RBTreeIterator(const iterator& it)
{
_node = it._node;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self operator++(int)
{
Self tmp(*this);
++(*this);
return tmp;
}
Self& operator--()
{
if (_node->_left)
{
Node* max = _node->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
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--(int)
{
Self tmp(*this);
--(*this);
return tmp;
}
bool operator!=(const Self& s)const
{
return _node != s._node;
}
bool operator==(const Self& s)const
{
return _node == s._node;
}
};
template<class Iterator, class Ref, class Ptr>
struct RBTreeReverseIterator
{
typedef RBTreeReverseIterator<Iterator, Ref, Ptr> Self;
Iterator _it;
RBTreeReverseIterator(Iterator it)
: _it(it)
{}
Ref operator*()
{
Iterator tmp = _it;
return *tmp;
}
Ptr operator->()
{
return &(operator*());
}
Self& operator++()
{
--_it;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
--_it;
return tmp;
}
Self& operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
++_it;
return tmp;
}
bool operator!=(const Self& s)const
{
return _it != s._it;
}
bool operator==(const Self& s)const
{
return _it == s._it;
}
};RBTree.h
#pragma once
#include "Iterator.h"
template<class K, class T, class KofT>
class RBTree
{
// 私有
typedef RBTreeNode<T> Node;
public:
typedef RBTreeIterator<T, T&, T*> iterator;
typedef RBTreeIterator<T, const T&, const T*> const_iterator;
typedef RBTreeReverseIterator<iterator, T&, T*> reverse_iterator;
typedef RBTreeReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
iterator begin()
{
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
return iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin()const
{
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
return const_iterator(left);
}
const_iterator end()const
{
return const_iterator(nullptr);
}
reverse_iterator rbegin()
{
Node* right = _root;
while (right && right->_right)
{
right = right->_right;
}
return reverse_iterator(iterator(right));
}
reverse_iterator rend()
{
return reverse_iterator(iterator(nullptr));
}
const_reverse_iterator rbegin()const
{
Node* right = _root;
while (right && right->_right)
{
right = right->_right;
}
return const_reverse_iterator(const_iterator(right));
}
const_reverse_iterator rend()const
{
return const_reverse_iterator(const_iterator(nullptr));
}
// 迭代器構(gòu)造
template<class Iterator>
RBTree(Iterator first, Iterator last)
{
_root = nullptr;
while (first != last)
{
insert(*first);
++first;
}
}
RBTree()
: _root(nullptr)
{}
std::pair<iterator, bool> insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return std::make_pair(iterator(_root), true);
}
KofT 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 std::make_pair(iterator(cur), false);
}
}
cur = new Node(data);
Node* newNode = cur;
cur->_col = RED;
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
// 變色、旋轉(zhuǎn)
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
// 情況1：叔叔存在且為紅
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
// 情況2: 右單旋
rotate_right(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// 情況3: 左右雙旋
rotate_left(parent);
rotate_right(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle&& uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
// 情況2: 左單旋
rotate_left(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// 情況3: 右左雙旋
rotate_right(parent);
rotate_left(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return std::make_pair(iterator(newNode), true);
}
void rotate_right(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
Node* ppNode = parent->_parent;
parent->_parent = subL;
if (ppNode == nullptr)
{
subL->_parent = nullptr;
_root = subL;
}
else
{
if (parent == ppNode->_left)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
void rotate_left(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
Node* ppNode = parent->_parent;
parent->_parent = subR;
if (ppNode == nullptr)
{
subR->_parent = nullptr;
_root = subR;
}
else
{
if (parent == ppNode->_left)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
void in_order()
{
_in_order(_root);
std::cout << std::endl;
}
bool is_balance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col != BLACK)
{
return false;
}
int ref = 0;
Node* left = _root;
while (left)
{
if (left->_col == BLACK)
{
++ref;
}
left = left->_left;
}
return _is_balance(_root, 0, ref);
}
private:
void _in_order(Node* root)
{
if (root == nullptr)
{
return;
}
_in_order(root->_left);
std::cout << root->_data << std::endl;
_in_order(root->_right);
}
// 檢查是否有聯(lián)系的紅節(jié)點
bool _is_balance(Node* root, int blackNum, const int ref)
{
if (root == nullptr)
{
if (blackNum != ref)
{
std::cout << "路徑黑色節(jié)點跟最左路徑不相等" << std::endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
std::cout << "出現(xiàn)連續(xù)紅節(jié)點: " << root->_data.first << ", " << root->_parent->_data.first << std::endl;
return false;
}
if (root->_col == BLACK)
{
++blackNum;
}
return _is_balance(root->_left, blackNum, ref)
&& _is_balance(root->_right, blackNum, ref);
}
private:
Node* _root = nullptr;
};Map.h
#pragma once
#include "RBTree.h"
template<class K, class V>
class Map
{
struct MapKofT
{
const K& operator()(const std::pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, std::pair<const K, V>, MapKofT>::iterator iterator;
typedef typename RBTree<K, std::pair<const K, V>, MapKofT>::const_iterator const_iterator;
typedef typename RBTree<K, std::pair<const K, V>, MapKofT>::reverse_iterator reverse_iterator;
typedef typename RBTree<K, std::pair<const K, V>, MapKofT>::const_reverse_iterator const_reverse_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();
}
reverse_iterator rbegin()
{
return _t.rbegin();
}
reverse_iterator rend()
{
return _t.rend();
}
const_reverse_iterator rbegin()const
{
return _t.rbegin();
}
const_reverse_iterator rend()const
{
return _t.rend();
}
template<class Iterator>
Map(Iterator first, Iterator last)
{
_t = RBTree<K, std::pair<const K, V>, MapKofT>(first, last);
}
void swap(Map<K, V>& m)
{
std::swap(_t, m._t);
}
Map()
: _t(RBTree<K, std::pair<const K, V>, MapKofT>())
{}
Map(const Map<K, V>& m)
{
Map<K, V> tmp(m._t.begin(), m._t.end());
swap(tmp);
}
Map<K, V>& operator=(const Map<K, V> m)
{
swap(m);
return *this;
}
std::pair<iterator, bool> insert(const std::pair<const K, V>& kv)
{
return _t.insert(kv);
}
V& operator[](const K& key)
{
std::pair<iterator, bool> ret = insert(std::make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, std::pair<const K, V>, MapKofT> _t;
};Set.h
#pragma once
#include "RBTree.h"
template<class K>
class Set
{
struct SetKofT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKofT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKofT>::const_iterator const_iterator;
typedef typename RBTree<K, K, SetKofT>::const_reverse_iterator reverse_iterator;
typedef typename RBTree<K, K, SetKofT>::const_reverse_iterator const_reverse_iterator;
iterator begin()const
{
return _t.begin();
}
iterator end()const
{
return _t.end();
}
reverse_iterator rbegin()const
{
return _t.rbegin();
}
reverse_iterator rend()const
{
return _t.rend();
}
template<class Iterator>
Set(Iterator first, Iterator last)
{
_t = RBTree<K, K, SetKofT>(first, last);
}
void swap(Set<K>& s)
{
std::swap(_t, s._t);
}
Set()
: _t(RBTree<K, K, SetKofT>())
{}
Set(const Set<K>& s)
{
Set<K> tmp(s.begin(), s.end());
swap(tmp);
}
Set<K>& operator=(const Set<K> s)
{
swap(s);
return *this;
}
std::pair<iterator, bool> insert(const K& k)
{
std::pair<typename RBTree<K, K, SetKofT>::iterator, bool> ret = _t.insert(k);
return std::pair<iterator, bool>(ret.first, ret.second);
}
private:
RBTree<K, K, SetKofT> _t;
};test.cpp
#include <iostream>
#include <string>
#include <vector>
#include "Map.h"
#include "Set.h"
void test_map()
{
int a[] = { 8, 4, 12, 2, 6, 10, 30, 14, 32, 28 };
Map<int, int> m;
for (auto e : a)
{
m.insert(std::make_pair(e, e));
}
Map<int, int>::iterator it = m.begin();
while (it != m.end())
{
std::cout << (*it).first << ": " << (*it).second << std::endl;
//++it;
it++;
}
std::cout << std::endl;
for (auto e : m)
{
std::cout << e.first << ": " << e.second << std::endl;
}
std::cout << std::endl;
Map<int, int>::reverse_iterator rit = m.rbegin();
while (rit != m.rend())
{
std::cout << rit->first << ": " << rit->second << std::endl;
rit++;
}
std::cout << std::endl;
const Map<int, int> m1(m.begin(), m.end());
Map<int, int>::const_iterator cit = m1.begin();
while (cit != m1.end())
{
std::cout << cit->first << ": " << cit->second << std::endl;
cit++;
}
std::cout << std::endl;
const Map<int, int> m2(m1);
Map<int, int>::const_reverse_iterator crit = m2.rbegin();
while (crit != m2.rend())
{
std::cout << crit->first << ": " << crit->second << std::endl;
++crit;
}
std::cout << std::endl;
Map<int, int> m3 = m2;
for (auto& e : m3)
{
// map的key不可修改，value可改
//e.first += 1;
e.second /= 2;
std::cout << e.first << ": " << e.second << std::endl;
}
std::cout << std::endl;
std::vector<std::string> food = {
"蛋糕", "西瓜", "啤酒", "蘋果", "香蕉", "蛋糕", "牛肉",
"西瓜", "蘋果", "啤酒", "西瓜", "牛肉", "蛋糕", "蛋糕",
"西瓜", "西瓜", "牛肉", "蘋果", "香蕉", "蛋糕", "西瓜"
};
Map<std::string, int> foodMap;
for (auto& e : food)
{
foodMap[e]++;
}
for (auto& e : foodMap)
{
std::cout << e.first << ": " << e.second << std::endl;
}
std::cout << std::endl;
}
void test_set()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
Set<int> s;
for (auto e: a)
{
s.insert(e);
}
Set<int>::iterator it = s.begin();
while (it != s.end())
{
std::cout << *it << ' ';
++it;
}
std::cout << std::endl;
for (const auto& e : s)
{
std::cout << e << ' ';
}
std::cout << std::endl;
Set<int>::reverse_iterator rit = s.rbegin();
while (rit != s.rend())
{
std::cout << *rit << ' ';
++rit;
}
std::cout << std::endl;
const Set<int> s1(s.begin(), s.end());
Set<int>::const_iterator cit = s1.begin();
while (cit != s1.end())
{
std::cout << *cit << ' ';
++cit;
}
std::cout << std::endl;
const Set<int> s2(s1);
Set<int>::const_reverse_iterator crit = s2.rbegin();
while (crit != s2.rend())
{
std::cout << *crit << ' ';
++crit;
}
std::cout << std::endl;
const Set<int> s3 = s2;
for (auto& e : s3)
{
// set的值不可修改
// e++;
std::cout << e << ' ';
}
std::cout << std::endl;
}
int main()
{
test_map();
test_set();
return 0;
}到了這里，關(guān)于【C++】STL之map、set類源碼剖析的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![【C++入門到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入門 ]](https://imgs.yssmx.com/Uploads/2024/02/714971-1.jpeg)
