【C++】用手搓的红黑树手搓set和map

蒋灵瑜的笔记本 2023-04-05 原文

本文相关往期内容，可按需查阅：
1、【C++】set/multiset、map/multimap的使用

2、【数据结构】二叉搜索树的实现

3、【数据结构】平衡二叉树

4、【数据结构】手撕红黑树

本文难点：使用红黑树封装set和map，必须保证两种数据结构复用同一棵红黑树；且满足set和map的性质，set的value不可被改变，而map的value可以被改变。

一、set/map的底层结构

1、set/map的源码

扒一扒STL库中set和map的底层结构，不难发现，set和map的底层用的都是红黑树且均为key/value模型。

只不过set的key/value均为key值填充，而map的key/value使用key和pair<const Key,T>进行填充。因此，set和map中底层虽然都是红黑树，但这两种数据结构中的红黑树实例化类型并不相同。

那么使用同一颗红黑树的模板，如何实例化出适配set和/map的对象？

2、利用模板区分set/map

template <class T>//T类型代表value
struct RBTreeNode
{
	RBTreeNode(const T& data)
		:_parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
		, _data(data)
		, _col(RED)
	{}
	RBTreeNode<T>* _parent;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	T _data;
	Color _col;
};

map和set的区别在于value的不同，红黑树模板参数T，代表value用以区分set和map。

3、利用仿函数控制比较大小

我们会发现红黑树的插入等接口会对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。这样就解决了比较大小的规则问题。

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

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

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

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

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

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

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

三、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);
}

四、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();
}

五、迭代器类的拷贝构造

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>
#include <map>
#include <set>
#include <string>
using namespace std;
enum Color
{
	RED,
	BLACK,
};
template <class T>//T类型代表value
struct RBTreeNode
{
	RBTreeNode(const T& data)
		:_parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
		, _data(data)
		, _col(RED)
	{}
	RBTreeNode<T>* _parent;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	T _data;
	Color _col;
};
//红黑树的迭代器
//        key/value T&        T*
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)
	{}
	__RBTreeIterator(const iterator& it)
		:_node(it._node)
	{}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()//返回类型的地址
	{
		return &_node->_data;
	}
	//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;
	}
	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;
	}
	bool operator!=(const Self& s)const
	{
		return _node != s._node;
	}
	bool operator==(const Self& s)const
	{
		return _node == s._node;
	}
};
//pair的比较是如果first小还要比second，我们只要比first，所以加了仿函数KeyOfT，用以取出first进行比较
//set->RBTree<K, K, SetKeyOfT>
//map->RBTree<const K, pair<K,V>, MapKeyOfT>
template <class K, class T,class KeyOfT>
class RBTree
{
public:
	typedef __RBTreeIterator<T,T&,T*> iterator;
	typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
	iterator begin()//找红黑树最左节点
	{
		Node* left = _root;
		while (left!=nullptr&&left->_left!=nullptr)
		{
			left = left->_left;
		}
		return iterator(left);
	}
	iterator end()
	{
		return iterator(nullptr);
	}
	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);
	}
	typedef RBTreeNode<T> Node;
	pair<iterator,bool> Insert(const T& data)//对于map来说data是pair
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;//根节点给黑色
			return make_pair(iterator(_root), true);//返回插入的节点
		}
		KeyOfT kot;//搞一个仿函数对象
		//_root不为空
		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);//插入失败，说明找到了，返回被查找节点的迭代器
		}
		//开始插入
		cur = new Node(data);
		Node* newNode = cur;//记录cur的地址，make_pair返回插入节点的地址
		cur->_col = RED;//新插入节点给红色，可能违反规则。如果给黑色会导致其他路径的黑色节点数量不相同，必定违反规则。  
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
			cur->_parent = parent;//维护cur的父指针
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		//调整
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;//找到祖父
			if (grandfather->_left == parent)//如果父亲是祖父的左孩子
			{
				Node* uncle = grandfather->_right;//找到叔叔
				//情况一：叔叔存在且为红
				if (uncle != nullptr && uncle->_col == RED)
				{
					//变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else//情况二或情况三
				{
					if (cur == parent->_left)//情况二，直线
					{
						RotateRight(grandfather);//右单旋
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//情况三，折线
					{
						RotateLeft(parent);//左单旋
						RotateRight(grandfather);//右单旋
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else//如果父亲是祖父的右孩子
			{
				Node* uncle = grandfather->_left;
				if (uncle != nullptr && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)//情况二，直线
					{
						//g
						//  p
						//    c
						RotateLeft(grandfather);//左单旋
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//情况三，折线
					{
						//g
						//  p
						//c   
						RotateRight(parent);//右单旋
						RotateLeft(grandfather);//左单旋
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return make_pair(iterator(newNode), true);//返回插入的节点
	}
	void Inorder()
	{
		_Inorder(_root);
	}
	bool IsBalance()
	{
		return _IsBalance();
	}
private:
	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;

		_Inorder(root->_left);
		cout << kot(root->_data) << ":" << root->_data.second << endl;
		_Inorder(root->_right);
	}
	bool Check(Node* root, int blackNum, const int ref)//检查有没有连续红节点
	{
		if (root == nullptr)
		{
			if (blackNum != ref)
			{
				cout << "路径上黑节点数量不一致" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == BLACK)
		{
			++blackNum;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "违反规则，父子均为红" << endl;
			return false;
		}
		return Check(root->_left, blackNum, ref) && Check(root->_right, blackNum, ref);
	}
	bool _IsBalance()
	{
		if (_root == nullptr)
			return true;
		if (_root->_col != BLACK)
		{
			return false;
		}
		//数一下一条路径黑色节点数量
		int ref = 0;//统计一条路上黑色节点的数量
		Node* left = _root;
		while (left != nullptr)
		{
			if (left->_col == BLACK)
			{
				++ref;
			}
			left = left->_left;
		}
		return Check(_root, 0, ref);
	}
	void RotateLeft(Node* parent)//左单旋
	{
		Node* grandfather = parent->_parent;
		Node* cur = parent->_right;
		if (parent == _root)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (grandfather->_left == parent)//需要判定parent原来属于grandfather的哪一边
				grandfather->_left = cur;
			else
				grandfather->_right = cur;
			cur->_parent = grandfather;
		}
		parent->_right = cur->_left;
		if (cur->_left != nullptr)
			cur->_left->_parent = parent;
		cur->_left = parent;
		parent->_parent = cur;
	}
	void RotateRight(Node* parent)//右单旋
	{
		Node* grandfather = parent->_parent;
		Node* cur = parent->_left;
		if (parent == _root)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (grandfather->_left == parent)
			{
				grandfather->_left = cur;
				cur->_parent = grandfather;
			}
			else
			{
				grandfather->_right = cur;
				cur->_parent = grandfather;
			}
		}
		parent->_parent = cur;
		parent->_left = cur->_right;
		if (cur->_right != nullptr)
			cur->_right->_parent = parent;
		cur->_right = parent;
	}
private:
	Node* _root = nullptr;
};

迭代器的begin(),end()接口放在红黑树这个类中，而operator++--放在迭代器这个类中，自己写一下循环遍历红黑树的代码就知道为什么这样设计了。

2、Set.h

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

	};
	void test2()
	{
		//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
		int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
		//int a[] = { 9,8,7,6,5,4,3,2,1};
		set<int> s;
		for (auto e : a)
		{
			s.insert(e);
		}
		set<int>::iterator it = s.begin();
		while (it != s.end())
		{
			cout << *it << " ";
			++it;
		}
	}
}

3、map.h

#pragma once
#include "RBTree.h"
namespace jly
{
	template <class K,class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)//传入value
			{
				return kv.first;
			}
		};
	public:
		//typename是C++中用于指定一个类的类型的关键字。
		//通常用于表示某个类型是一个类类型，而不是其他类型，如int等。
		//这里不加typedef编译器无法区分iterator是一个类型还是一个静态变量。因为他俩都可以这么写。。
		//所以从类模板取出内嵌类型就需要加typedef
		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;
		pair<iterator,bool> insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}
		
		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)//传入key值
		{
			pair<iterator,bool> ret= _t.Insert(key,V());
			return ret.first->second;//找到ret（make_pair<iterator,bool>）的first，解引用找到节点value
		}
	private:
		RBTree<const K, pair<const K,V>, MapKeyOfT> _t;
	};
	void test1()
	{
		int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
		//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
		//int a[] = { 9,8,7,6,5,4,3,2,1};
		map<int,int> m;
		for (auto e : a)
		{
			m.insert(make_pair(e,e));
		}
		map<int, int>::iterator it = m.begin();
		while (it != m.end())
		{
			cout << (* it).first << " ";
			++it;
		}
		cout << endl;
		for (auto& e : m)
		{
			cout << e.first<<" ";
		}
	}
}

C++set parent const 61 c++数据结构 java map

有关【C++】用手搓的红黑树手搓set和map的更多相关文章

ruby-on-rails - 如何使用 instance_variable_set 正确设置实例变量？ - 2
我正在查看instance_variable_set的文档并看到给出的示例代码是这样做的:obj.instance_variable_set(:@instnc_var,"valuefortheinstancevariable")然后允许您在类的任何实例方法中以@instnc_var的形式访问该变量。我想知道为什么在@instnc_var之前需要一个冒号:。冒号有什么作用？最佳答案我的第一直觉是告诉你不要使用instance_variable_set除非你真的知道你用它做什么。它本质上是一种元编程工具或绕过实例变量可见性的黑客攻击
ruby - Sinatra set cache_control to static files in public folder编译错误 - 2
我不知道为什么，但是当我设置这个设置时它无法编译设置:static_cache_control，[:public，:max_age=>300]这是我得到的syntaxerror,unexpectedtASSOC,expecting']'(SyntaxError)set:static_cache_control,[:public,:max_age=>300]^我只想将“过期”header设置为css、javaascript和图像文件。谢谢。最佳答案我猜您使用的是Ruby1.8.7。Sinatra文档中显示的语法似乎是在Ruby1.
【Java 面试合集】HashMap中为什么引入红黑树，而不是AVL树呢 - 2
HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候
ruby - Arrays Sets 和 SortedSets 在 Ruby 中是如何实现的 - 2
通常，数组被实现为内存块，集合被实现为HashMap，有序集合被实现为跳跃列表。在Ruby中也是如此吗？我正在尝试从性能和内存占用方面评估Ruby中不同容器的使用情况最佳答案数组是Ruby核心库的一部分。每个Ruby实现都有自己的数组实现。Ruby语言规范只规定了Ruby数组的行为，并没有规定任何特定的实现策略。它甚至没有指定任何会强制或至少建议特定实现策略的性能约束。然而，大多数Rubyist对数组的性能特征有一些期望，这会迫使不符合它们的实现变得默默无闻，因为实际上没有人会使用它:插入、前置或追加以及删除元素的最坏情况步骤复
ruby - 在 ruby 中使用 .try 函数和 .map 函数 - 2
我需要从json记录中获取一些值并像下面这样提取curr_json_doc['title']['genre'].map{|s|s['name']}.join(',')但对于某些记录，curr_json_doc['title']['genre']可以为空。所以我想对map和join()使用try函数。我试过如下curr_json_doc['title']['genre'].try(:map,{|s|s['name']}).try(:join,(','))但是没用。最佳答案你没有正确传递block。block被传递给参数括号外的方法
ruby-on-rails - 尝试设置 Amazon 的 S3 存储桶 : 403 Forbidden error & setting permissions - 2
我正在关注Hartl的railstutorial.org并已到达11.4.4:Imageuploadinproduction.我做了什么:注册亚马逊网络服务在AmazonIdentityandAccessManagement中，我创建了一个用户。用户创建成功。在AmazonS3中，我创建了一个新存储桶。设置新存储桶的权限:权限:本教程指示“授予上一步创建的用户读写权限”。但是，在存储桶的“权限”下，未提及新用户名。我只能在每个人、经过身份验证的用户、日志传送、我和亚马逊似乎根据我的名字+数字创建的用户名之间进行选择。我已经通过选择经过身份验证的用户并选中了上传/删除和查看权限的框(而不
ruby - 不能将 `each` 的所有或大多数情况替换为 `map` 吗？ - 2
Enumerable#each和Enumerable#map的区别在于返回的是接收者还是映射后的结果。回到接收者是微不足道的，你通常不需要在each之后继续一个方法链，比如each{...}.another_method(我可能没见过这样的案例。即使你想回到接收者那里，你也可以通过tap来实现)。所以我认为所有或者大部分使用Enumerable#each的情况都可以用Enumerable#map代替。我错了吗？如果我是对的，each的目的是什么？map是否比each慢？编辑:我知道当您对返回值不感兴趣时使用each是一种常见的做法。我对这种做法是否存在不感兴趣，但感兴趣的是，除了从
ruby - 厨师和 ruby : how to convert a array into a set - 2
我有一个如下所示的数组:nodes=['server1','server1','server2']在厨师食谱中，我需要在传递给模板erb之前将其转换为集合。我该怎么做？最佳答案此模式适用于Set、Matrix、JSON等；这是尝试的第一件事。require'set'nodes=['server1','server1','server2']pnodes.to_set## 关于ruby-厨师和ruby:howtoconvertaarrayintoaset，我们在StackOverflow
ruby - `map` 比 `each` 快吗？ - 2
map遍历数组是否比each更快？两者有速度差异吗？mapresult=arr.map{|a|a+2}每个result=[]arr.eachdo|a|result.push(a+2)end 最佳答案我认为是的。我试过这个测试require"benchmark"n=10000arr=Array.new(10000,1)Benchmark.bmdo|x|#Mapx.reportdon.timesdoresult=arr.map{|a|a+2}endend#Eachx.reportdon.timesdoresult=[]arr.each
ruby - 用于 Ruby 哈希的 map_values()？ - 2
我想念Ruby中的Hash方法来仅转换/映射散列值。h={1=>[9,2,3,4],2=>[6],3=>[5,7,1]}h.map_values{|v|v.size}#=>{1=>4,2=>1,3=>3}你如何在Ruby中归档它？更新:我正在寻找map_values()的实现。#moreexamplesh.map_values{|v|v.reduce(0,:+)}#=>{1=>18,2=>6,3=>13}h.map_values(&:min)#=>{1=>2,2=>6,3=>1} 最佳答案 Ruby2.4引入了方法Hash#tran