STL-Set&map

前言

大家好,我是jiantaoyab,我们将进入到C++STL 的学习。STL在各各C++的头文件中,以源代码的形式出现,不仅要会用,还要了解底层的实现。源码之前,了无秘密。

STL六大组件

image-20240323151905853

Container通过Allocator取得数据储存空间,Algorithm通过Iterator存取Container内容,Functor可以协助Algorithm完成不同的策略变化,Adapter可以修饰或者套接Functor。

关联式容器associative containers

Set

image-20240428231352539

  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中存储的是真正的键值对<key, value>,set中只放value,但在底层实际存放的是由<value, value>构成的键值对。

  2. set中的元素不可以重复(因此可以使用set进行去重)。multiset能插入重复的值,如果查找的话找的第一个节点是中序遍历的第一个节点

  3. set中的元素默认按照小于来比较,使用set的迭代器遍历set中的元素,可以得到有序序列

set的基本使用

//构造
void const()
{
   std::set<int> first;                           // empty set of ints
   int myints[]= {10,20,30,40,50};
   std::set<int> second (myints,myints+5);        // range
   std::set<int> third (second);                  // a copy of second
   std::set<int> fourth (second.begin(), second.end());  // iterator ctor.
   std::set<int,classcomp> fifth;                 // class as Compare
}

//插入
void insert()
{
    std::set<int> myset;
    std::set<int>::iterator it;
    std::pair<std::set<int>::iterator, bool> ret;
    
    for(int i = 1; i <= 5; i++) myset.insert(i);
    ret = myset.insert(2); //插入失败
    if(ret.second == false) it = ret.first; //指向20
    myset.insert(it, 9);
    
    for(it = myset.begin(); it != myset.end(); it++)
    {
        cout << *it <<" ";
	}
}


//查找
void find()
{
    std::set<int> myset;
    std::set<int>::iterator it;
    for(int i = 1; i <= 5; i++) myset.insert(i);
    it = myset.find(3);
    myset.erase(it);
}

Map

image-20240428233232502

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

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

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

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

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

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

    image-20240428233831725

在正式使用Map之前先看看pair和make_pair

image-20240428233452384

make_pair在pair的基础上做了一个自动推导

image-20240428234502828

可以看到pair是一个结构体里面有2个值,第一个叫first,第二个值叫second。在map中first的值就是key,second的值是value。

Map的使用

//pair<iterator,bool> insert (const value_type& val);
//返回值是一个pair
void  insert()
{
    map<string, string> dict;
    //假设插入失败
    auto it = dict.insert(make_pair("peach","桃子"));
    cout<< it.first->second <<end; //false
}
int main()
{
    pair<string, string> kv("apple", "苹果");
    map<string, string> dict;
    dict.insert(kv);   
    dict.insert(pair<string, string>("banana", "香蕉"); //匿名对象
    dict.inset(make_pair("grape", "葡萄"));
    map<string, string>::iterator it = dict.begin();
	while(it != dict.end())
    {
       // cout << *(it).first << ":" << *(it).second << " ";
   cout << it->first << ":" << it->second <<" " ; // map里面->进行了重载 ->->
	}
}

map中的[]

在C++中,可以通过下标操作符[]来访问和修改Map中的值。如果要修改一个键对应的值,可以直接用下标操作符访问该键然后赋予新值。如果该键不存在,则会在Map中创建一个新键,并赋予默认初始化的值。

image-20240506200301855

image-20240506200623063

调用完inset返回的是一个pair,.first取出iterator,iterator是指向插入的或者是已近存在的那个元素,*(iterator).first得到pair<const Key, T>,再.second得到T。

红黑树

image-20240506195546485

红黑树的性质:

  1. 每个节点要么是红色,要么是黑色。
  2. 根节点是黑色。
  3. 每个叶子节点(NIL节点或空节点)是黑色。注意,这里的叶子节点指的是NIL节点或空节点。(NIL节点在红黑树中通常指的是空节点或叶子节点的占位符。在红黑树的实现中,为了简化逻辑和保证性质,通常假设每个节点都有两个子节点,即使这些子节点实际上并不存在。这些不存在的子节点由NIL节点(或称为空节点、哑节点、哨兵节点)来表示。)
  4. 如果一个节点是红色的,则它的两个子节点都是黑色的。这一性质保证了不会出现连续的红色节点,有助于维护树的平衡性。
  5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。这一性质被称为“黑色节点路径长度相等”,它确保了红黑树的高度始终在对数级别。

模拟实现红黑树

红黑树节点

enum Color
	{
		RED,
		BLACK
	};

	template<class K, class V>
	struct RBTreeNode
	{
		RBTreeNode<K, V>* _left;
		RBTreeNode<K, V>* _parent;
		RBTreeNode<K, V>* _right;
		Color _col;
		pair<K, V> _kv;
		RBTreeNode(const pair<K, V>& kv)
			:_left(nullptr)
			, _parent(nullptr)
			, _right(nullptr)
			, _col(RED) //默认给红色
			, _kv(kv)
		{}
	};

红黑树

//插入
bool insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;

	while (cur)
	{
		if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			return false;
		}

	}
	cur = new Node(kv);
	cur->_col = RED;
	if (parent->_kv.first > kv.first)
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_right = cur;
		cur->_parent = parent;
	}


	//控制平衡
	while (parent && parent->_col == RED)
	{
		Node* g = parent->_parent;
		if (parent == g->_left)
		{
			Node* u = g->_right;
			//1.u存在且为红
			if (u && u->_col == RED)
			{
				//变色
				parent->_col = BLACK;
				u->_col = BLACK;
				g->_col = RED;
				// 向上处理
				cur = g;
				parent = cur->_parent;
			}

			//u不存在/u存在且为黑
			else
			{
				//          g
				//       p
				//  cur
				//右单旋
				if (cur == parent->_left)
				{
					RotateR(g);
			   	 	g->_col = RED;
					parent->_col = BLACK;
				}
				//      g
				//   p
				//      cur
				//左右双旋
				else
				{
					RotateL(parent);
					RotateR(g);
					cur->_col = BLACK;
					g->_col = RED;
				}
					break;
			}
		}
		//(parent == g->_right)
		else
		{
			Node* u = g->_left;
			//1.u存在且为红
			if (u&& u->_col == RED)
			{
				//变色
				parent->_col = BLACK;
				u->_col = BLACK;
				g->_col = RED;
				// 向上处理
				cur = g;
				parent = cur->_parent;
			}
			//u不存在 /u存在且为黑
			else
			{
				//    g
				//       p
				//          cur
			     if (parent->_right = cur)
				{
					RotateL(g);
					g->_col = RED;
					parent->_col = BLACK;
				}
				//    g
				//        p
				//   cur
				else
				{
					RotateR(parent);
					RotateL(g);
					cur->_col = BLACK;
					g->_col = RED;
				}
						break;
			}
		   }
			}
			_root->_col = BLACK;
			return true;
}

//判断平衡

bool _IsBalance(Node* root, const int refernum, int actualnum)
{
	if (root == nullptr)
	{
		if (refernum != actualnum)
		{
			cout << "实际值的黑色节点数目和参考值不一样" << endl;
			return false;
		}
		else return true;
	}

	if (root->_col == RED && root->_parent->_col == RED)
	{
		cout << "parent和cur都为红,出现连续的红节点" << endl;
		return false;
	}

	if (root->_col == BLACK)
		++actualnum;

	return _IsBalance(root->_left, refernum, actualnum)
				&& _IsBalance(root->_right, refernum, actualnum);

}
bool IsBalance()
{
	if (_root && _root->_col == RED)
	{
		cout << "根节点为红色" << endl;
		return false;
	}
		//选择一条路径记录黑色节点的数量做参考值
		int refernum = 0;
		Node* left = _root;
	while (left)
	{
	    if(left->_col == BLACK)
        {
           refernum++;
		  left = left->_left;
        }
			
	}
	int actualnum = 0;
	return _IsBalance(_root, refernum, actualnum);
}

红黑树模拟实现STL中的map和set

由于想要红黑树即能存k也能存pair,所以对上面的代码进行改造

红黑树部分

enum Color
{
	RED,
	BLACK
};

//T 代表  K或者是 pair<K,V>
template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _parent;
	RBTreeNode<T>* _right;
	Color _col;
	T _date; //用date,因为值是什么类型的并不知道
	RBTreeNode(const T& date)
		:_left(nullptr)
		, _parent(nullptr)
		, _right(nullptr)
		, _col(RED) //默认给红色
		, _date(date)
	{}
};

//map <class k,class V,MapKeyOfT>
//set <class k,class k,SetKeyOfT>
//通过KeyOfT返回值来用 
template < class K, class T, class KeyOfT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, T&, T*> iterator;
	typedef RBTreeIterator<T, const T&, const T*> const_iterator;

	//开始就是中序最小的值
	iterator begin() 
	{
		Node* cur = _root;
		while (cur&& cur->_left)
			cur = cur->_left;
		return iterator(cur);
	}

	iterator end()
	{
		return iterator(nullptr);
	}


	RBTree()
		:_root(nullptr)
	{}

	RBTree(const RBTree<K, T, KeyOfT>& tree)
	{
		_root = Copy(tree._root);
	}

	RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
	{
		swap(_root, t);
		return *this;
	}

	~RBTree()
	{
		Destroy(_root);
		_root = nullptr;
	}
private:

	void Destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}

	Node * Copy(Node* root)
	{

		if (root == nullptr)
			return nullptr;

		//生成一个新根+换颜色
		Node* newtree = new Node(root->_date);
		newtree->_col = root->_col;

		newtree->_left = Copy(root->_left);
		newtree->_right = Copy(root->_right);

		//处理newtree的parent
		if (newtree->_left)
			newtree->_left->_parent = newtree;
		else
		{
			newtree->_right->_parent = newtree;			
		}

		return newtree; 
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* parentparent = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		//parent是别人的子树
		else
		{
			if (parentparent->_left == parent)
				parentparent->_left = subL;
			else
				parentparent->_right = subL;

			subL->_parent = parentparent;
		}

		parent->_left = subLR;
		//subLR 可能不存在
		if (subLR)
		{
			subLR->_parent = parent;
		}


	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		Node* parentparent = parent->_parent;
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentparent->_left == parent)
				parentparent->_left = subR;
			else
				parentparent->_right = subR;
			subR->_parent = parentparent;
		}
		subR->_left = parent;
		parent->_parent = subR;
		parent->_right = subRL;
	}


public:
	pair<iterator, bool> insert(const T& date)
	{

		if (_root == nullptr)
		{
			_root = new Node(date);
			_root->_col = BLACK;
			return make_pair(iterator(_root),true);
		}

		Node* cur = _root;
		Node* parent = nullptr;
		KeyOfT key;
		while (cur)
		{
			if (key(cur->_date) > key(date))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (key(cur->_date) < key(date))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(iterator(cur), false);
			}

		}

		cur = new Node(date);
		Node* newnode = cur;
		cur->_col = RED;//新增给红,只影响新增所在的路径
		if (key(parent->_date) > key(date))
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}


		//控制平衡
		while (parent && parent->_col == RED)
		{
			Node* g = parent->_parent;
			if (parent == g->_left)
			{
				Node*u = g->_right;
				//1.u存在且为红
				if (u&& u->_col == RED)
				{
					//变色
					parent->_col = BLACK;
					u->_col = BLACK;
					g->_col = RED;
					// 向上处理
					cur = g;
					parent = cur->_parent;
				}

				//u不存在/u存在且为黑
				else
				{
					//          g
					//       p
					//  cur
					//右单旋
					if (cur == parent->_left)
					{
						RotateR(g);
						g->_col = RED;
						parent->_col = BLACK;
					}
					//      g
					//   p
					//      cur
					//左右双旋
					else
					{
						RotateL(parent);
						RotateR(g);
						cur->_col = BLACK;
						g->_col = RED;
					}

					break;
				}

			}
			//(parent == g->_right)
			else
			{
				Node* u = g->_left;
				//1.u存在且为红
				if (u&& u->_col == RED)
				{
					//变色
					parent->_col = BLACK;
					u->_col = BLACK;
					g->_col = RED;
					// 向上处理
					cur = g;
					parent = cur->_parent;
				}
				//u不存在 /u存在且为黑
				else
				{
					//    g
					//       p
					//          cur
					if (parent->_right = cur)
					{
						RotateL(g);
						g->_col = RED;
						parent->_col = BLACK;
					}
					//    g
					//        p
					//   cur
					else
					{
						RotateR(parent);
						RotateL(g);
						cur->_col = BLACK;
						g->_col = RED;
					}

					break;
				}
			}
		}
		
		_root->_col = BLACK;
		return make_pair(iterator(newnode), true);
	}

	
private:
	Node* _root;

};

红黑树迭代器

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr>Self;
	Node* _node;

	//节点来构造迭代器
	RBTreeIterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_date;
	}

	Ptr operator->()
	{
		return &_node->_date;//返回date的地址 ->优先级高
	}

	//中序
	Self& operator++(){
		// 1.如果右树不为空就访问右树最左节点
		if (_node->_right){
			Node* min = _node->_right;
			while (min->_left){
				min = min->_left;
			}
			_node = min;
		}
		//2.右树为空,说明所在子树访问完了
		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--(){

		//1.访问左子树最右节点
		if (_node->_left){
			Node* max= _node->_left;
			while (max->_right){
				max = max->_right;
			}

			_node = max;
		}
		//2.左为空说明访问完了
		else{
			Node* cur = _node;
			Node* parent = cur->_parent;
			//沿着到根路径往上走
			while (parent &&cur==parent->left){
				cur = cur->_parent;
				parent = parent->_parent;
			}
			//找右孩子是父亲的祖父节点,继续更新直到父亲为空
			_node = parent;

		}
		return *this;
	}
	
	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}

	bool operator==(const Self& s)  const
	{
		return _node == s._node;
	}

};

map.h

#pragma once
namespace jt
{
	template<class K,class V>
	class map
	{
	public:
		struct MapKeyOfT
		{
			const K& operator()(const pair<K,V>& kv)
			{
				return kv.first;
			}
		};

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

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

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _t.insert(kv);
		}
		
		V& operator[](const K& key)
		{
			auto ret = _t.insert(make_pair(key, V()));
			return ret.first->second;
		}
	private:
		RBTree<K, pair<K, V>, MapKeyOfT> _t;
	};

}

set.h

namespace jt
{
	template<class K>
	class set
	{
	public:

		struct SetKeyOfT
		{
			const K& operator()(const K& k)
			{
				return k;
			}
		};

		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;

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

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

		pair<iterator, bool> insert(const K& key)
		{
			return _t.insert(key);
		}

	private:
		RBTree<K, K, SetKeyOfT> _t;
	};

}

map和set是适配器吗?

容器:容器是存储数据的对象,这些对象提供了对它们所包含元素的访问。C++ 标准库提供了多种容器,如 vector, list, deque, map, set, unordered_map, unordered_set 等。

适配器:适配器是设计模式中的一种,它允许将一个类的接口转换为客户端所期望的另一个接口。在 C++ 标准库中,适配器通常是指那些不直接存储数据,但提供对数据的访问或修改操作的类。常见的适配器包括 stack, queue, priority_queue 等,它们通常基于其他容器(如 deque)来实现。

mapset 是直接存储数据的容器。它们内部有自己的数据结构(通常是红黑树)来存储和管理元素。与此不同,适配器通常不直接存储数据,而是基于其他容器来提供特定的接口或行为。

例如,stack 是一个适配器,它基于一个底层容器(如 deque)来提供栈的行为(如 push, pop, top 等)。但 stack 本身并不存储数据,它只是将 deque 的接口转换为栈的接口。

另一方面,map 提供了键值对的存储和查找,而 set 提供了唯一元素的存储和查找。这些功能是通过它们自己的数据结构和算法来实现的,而不是通过适配其他容器的接口。因此,mapset 被归类为容器,而不是适配器。

红黑树与AVL树对比

红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O(log2N),红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数,红黑树的设计确保了任何不平衡都可以在三次旋转之内解决。所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红黑树更多。

相关推荐

  1. STLstd::map使用小结

    2024-05-14 16:18:03       27 阅读
  2. STL-string

    2024-05-14 16:18:03       22 阅读
  3. c++ STL

    2024-05-14 16:18:03       26 阅读
  4. STL-deque

    2024-05-14 16:18:03       25 阅读
  5. <span style='color:red;'>STL</span>_list

    STL_list

    2024-05-14 16:18:03      29 阅读
  6. STL - list

    2024-05-14 16:18:03       23 阅读
  7. <span style='color:red;'>STL</span>简介

    STL简介

    2024-05-14 16:18:03      18 阅读
  8. STL简介

    2024-05-14 16:18:03       19 阅读

最近更新

  1. .Net Core WebAPI参数的传递方式

    2024-05-14 16:18:03       0 阅读
  2. QT--气泡框的实现

    2024-05-14 16:18:03       1 阅读
  3. LeetCode 968.监控二叉树 (hard)

    2024-05-14 16:18:03       0 阅读
  4. leetcode热题100.完全平方数(动态规划进阶)

    2024-05-14 16:18:03       0 阅读
  5. leetcode328-Odd Even Linked List

    2024-05-14 16:18:03       0 阅读
  6. C 语言设计模式(结构型)

    2024-05-14 16:18:03       0 阅读
  7. v-if 与 v-show(vue3条件渲染)

    2024-05-14 16:18:03       0 阅读
  8. kafka防止消息丢失配置

    2024-05-14 16:18:03       0 阅读

热门阅读

  1. Mysql 锁

    Mysql 锁

    2024-05-14 16:18:03      2 阅读
  2. 图书管理数据库

    2024-05-14 16:18:03       2 阅读
  3. Android 桌面小组件 AppWidgetProvider(2)

    2024-05-14 16:18:03       2 阅读
  4. 什么是跨境物流管理系统,它有什么功能

    2024-05-14 16:18:03       1 阅读
  5. Spring redis工具类

    2024-05-14 16:18:03       2 阅读
  6. 算法打卡day45

    2024-05-14 16:18:03       3 阅读
  7. 二级和三级城市插件

    2024-05-14 16:18:03       3 阅读
  8. MYSQL 存储过程 函数

    2024-05-14 16:18:03       3 阅读
  9. js怎么判断视频链接是否能播放

    2024-05-14 16:18:03       2 阅读