1.set和map是什么
set和map是 C++ STL 提供的容器，用于高效的查找数据，底层采用红黑树实现，其中set是Key模型，map是Key-Value模型
set和map的基本使用较为简单，这里不再叙述，直接进入实现环节
2.set和map的底层实现
2.1 节点的定义
既然set和map的底层采用红黑树，那就少不了我们之前实现过的红黑树，直接搬过来复用
但我们实现的红黑树是Key-Value模型，难道要针对Key模型再copy一份红黑树，将节点里面的值修改成Key吗？
STL 中采用模板的方式，只需要一份红黑树，就能完成Key和Key-Value模型的统一
既然如何，红黑树节点的定义中，数据就不能只是key或pair对象，而应当是泛型，外部传递什么类型，数据就是什么类型
template<typename T>
struct RBTreeNode
{
RBTreeNode(const T& data)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_data(data)
,_col(RED)
{}
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Color _col;
};
// set.h
template<typename K>
class set
{
private:
RBTree<K, K> _tree;
};
// map.h
template<typename K, typename V>
class map
{
private:
RBTree<K, std::pair<K, V>> _tree;
};
2.2 set和map的设计
同时，插入数据时，插入的值也应当为修改，此时，数据的比较就有问题了，之前的比较都是针对单一的key或pair进行比较，但红黑树这层并不知道外部传递给我的是一个什么类型的数据，只有set/map层知道传递的数据类型是什么，该如何进行数据的比较？
这里的解决方法是使用仿函数，在set/map层传递一个仿函数给红黑树层，该仿函数的功能用于取出key值，如果是set，那就直接取出key值，如果是map，那就取出pair中的first
// set.h
template<typename K>
class set
{
private:
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
private:
RBTree<K, K, SetKeyOfT> _tree;
};
// map.h
template<typename K, typename V>
class map
{
private:
struct MapKeyOfT
{
const K& operator()(const std::pair<K, V>& kv)
{
return kv.first;
}
};
private:
RBTree<K, std::pair<K, V>, MapKeyOfT> _tree;
};
// RBTree.h
template<typename K, typename T, typename KeyOfT>
class RBTree
{
public:
bool insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
KeyOfT kot;
Node* cur = _root, * parent = nullptr;
while (cur)
{
if (kot(data) < kot(cur->_data))
{
parent = cur;
cur = cur->_left;
}
else if (kot(data) > kot(cur->_data))
{
parent = cur;
cur = cur->_right;
}
else return false;
}
Node* newnode = new Node(data);
if (kot(data) < kot(parent->_data)) parent->_left = newnode;
else parent->_right = newnode;
newnode->_parent = parent;
// .......
return true;
}
private:
Node* _root = nullptr;
};
至此，set/map的整体框架建立完毕
set/map中，红黑树的定义时，还多传递了一个K类型，这样set有两个K类型，会不会很多余？
虽然插入数据不同的类型要采用不同的比较方式，但双方的查找操作都是根据key进行查找的，因此，多添加的K类型是为了方便map进行find操作的
2.3 迭代器
接下来，便是迭代器的设计了
在vector和list中，迭代器都是对指针的封装，再通过重载*和->运算符，达到屏蔽底层，上层统一遍历的效果
这里我们的设计思想也是一样的
template<typename T, typename Ref, typename Ptr>
struct __RBreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBreeIterator<T, Ref, Ptr> Self;
__RBreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
Node* _node;
};
唯一不同的是对于红黑树，++操作该如何实现？
红黑树的遍历要采用中序遍历才有意义，左子树 根 右子树
遍历到到某一节点时，如果左子树不为空，那么要一直遍历，直到左子树为空
左子树遍历完了，接下来访问根
根访问完了，如果右子树不为空，下一个应该访问右子树的最左节点
如果右子树为空，表明当前子树已经访问完了，此时，如果父亲是祖父的右子树，表明父亲的那颗子树也访问完了，要一直向上返回，直到当前节点是其父亲的左子树
template<typename T, typename Ref, typename Ptr>
struct __RBreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBreeIterator<T, Ref, Ptr> Self;
// ...
Self& operator++()
{
if (_node->_right != nullptr)
{
_node = _node->_right;
while (_node->_left) _node = _node->_left;
}
else
{
Node* parent = _node->_parent;
while (parent && _node == parent->_right)
{
_node = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Node* _node;
};
set和map在 STL 中是双向迭代器，意味着能迭代器不仅支持++操作，也支持–操作，而–操作无非反过来遍历
Self& operator--()
{
if (_node->_left != nullptr)
{
_node = _node->_left;
while (_node->_right) _node = _node->_right;
}
else
{
Node* parent = _node->_parent;
while (parent && _node == parent->_left)
{
_node = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
规定迭代器的begin为红黑树的最左节点，end为空
template<typename K, typename T, typename KeyOfT>
class RBTree
{
public:
typedef RBTreeNode<T> Node;
typedef __RBreeIterator<T, T&, T*> iterator;
iterator begin()
{
Node* left = _root;
while (left && left->_left) left = left->_left;
return iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
// ...
}
而set/map，无论是插入操作，还是迭代器，无非是对红黑树的接口的封装罢了
// set.h
template<typename K>
class set
{
private:
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;
bool insert(const K& key)
{
return _tree.insert(key);
}
iterator begin()
{
return _tree.begin();
}
iterator end()
{
return _tree.end();
}
private:
RBTree<K, const K, SetKeyOfT> _tree;
};
// map.h
template<typename K, typename V>
class map
{
private:
struct MapKeyOfT
{
const K& operator()(const std::pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT>::iterator iterator;
bool insert(const std::pair<K, V>& kv)
{
return _tree.insert(kv);
}
iterator begin()
{
return _tree.begin();
}
iterator end()
{
return _tree.end();
}
private:
RBTree<K, std::pair<const K, V>, MapKeyOfT> _tree;
};
2.4 map中operator[]
STL 中map支持使用[]运算符进行value的修改，使用起来相当方便
实际上，其内部设计利用了insert操作，将insert的返回值修改为std::pair<iterator, bool>
使用[]时，会传递一个key值，希望拿到key对应value的引用，这样就能方便修改value
因此，可以在[]内部调用insert，如果key不存在则插入成功，返回新节点的迭代器 + true的pair对象，否则返回值中的pair的second为false，表示插入失败
template<typename K, typename V>
class map
{
// ...
public:
typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT>::iterator iterator;
V& operator[](const K& key)
{
std::pair<iterator, bool> ret = this->insert(std::make_pair(key, V()));
return ret.first->second;
}
// ...
};
2.5 拷贝构造 + 赋值重载
set和map都只有RBTree一个成员，直接调用红黑树的拷贝构造和赋值重载即可
template<typename K, typename T, typename KeyOfT>
class RBTree
{
public:
typedef RBTreeNode<T> Node;
typedef __RBreeIterator<T, T&, T*> iterator;
typedef __RBreeIterator<T, const T&, const T*> const_iterator;
~RBTree()
{
this->destroy(_root);
_root = nullptr;
}
RBTree() = default;
RBTree(const RBTree<K, T, KeyOfT>& t)
{
_root = this->create(t._root);
_root->_parent = nullptr;
}
RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
{
std::swap(_root, t._root);
return *this;
}
// ...
private:
void destroy(Node* root)
{
if (root == nullptr) return;
destroy(root->_left);
destroy(root->_right);
delete root;
root = nullptr;
}
Node* create(Node* root)
{
if (root == nullptr) return nullptr;
Node* newnode = new Node(root->_data);
newnode->_col = root->_col;
newnode->_left = create(root->_left);
if (newnode->_left) newnode->_left->_parent = newnode;
newnode->_right = create(root->_right);
if (newnode->_right) newnode->_right->_parent = newnode;
return newnode;
}
private:
Node* _root = nullptr;
}
剩下的还有const迭代器和find的实现了，由于较为简单，不再详讲
**注意：**还有个细节，我们在传递红黑树的模板参数时，将第二个模板参数中的K加上了const
如果是set，那就是const K，如果是map，那就是pair<const K, V>，这是为了防止使用迭代器修改节点中的值，为什么不直接使用const迭代器呢？如果使用const迭代器，那么map中的Key和Value都不能修改，而map是要能支持修改Value的
2.6 测试
void Test_set()
{
set<int> s;
std::vector<int> v = { 1, 3, 2, 8, 11, 9, 4, 5, 7, 10, 6 };
for (auto& e : v) s.insert(e);
std::cout << "正向遍历: ";
for (auto& e : s) std::cout << e << " ";
std::cout << std::endl;
std::cout << "反向遍历: ";
set<int>::iterator it = s.find(11);
while (it != s.end())
{
std::cout << *it << " ";
--it;
}
std::cout << std::endl;
std::cout << "拷贝构造: s2->";
set<int> s2(s);
for (auto& e : s2) std::cout << e << " ";
std::cout << std::endl;
std::cout << "赋值重载: ";
set<int> s3(s);
s3.insert(1);
s3 = s;
std::cout << "s3->";
for (auto& e : s3) std::cout << e << " ";
std::cout << " s->";
for (auto& e : s) std::cout << e << " ";
}
void Test_map()
{
std::vector<std::string> v = { "apple", "tassel", "watermelon", "apple", "banana", "tassel", "orange", "apple" };
map<std::string, int> m;
for (auto& e : v) m[e] ++;
for (auto& it : m)
{
std::cout << it.first << " " << it.second << std::endl;
}
}
