go语言的map以及红黑树的map

结论：

1. go语言自带的map是基于hash表实现的

2. c++语言中map是基于红黑树实现的

3. go语言很多第三方库中提供了基于红黑树map的实现

这里我们推荐的是由Social Explorer团队开源的gods框架，简称"上帝"，其实是GoDS(Go Data Structures)，是数据结构与算法相关的框架

使用如下图：

示例代码如下（有很详细的注释，基本上C++中map有的，这里都有对应的方法）：

package main

import (
	"fmt"

	rbt "github.com/emirpasic/gods/trees/redblacktree"
	utils "github.com/emirpasic/gods/utils"
)

// 玩家结构体的定义
type player struct {
	playerID uint64 // 玩家ID
	score    int64  // 分数
	nation   int32  // 国家ID
}

// 新建一个玩家
func newPlayer(playerID uint64, score int64, nation int32) *player {
	return &player{
		playerID: playerID,
		score:    score,
		nation:   nation,
	}
}

// 遍历打印已一个map
func printMap(t *rbt.Tree) {
	iter := t.Iterator()
	for iter.Next() {
		pPlayer := iter.Value().(*player)
		fmt.Printf("key:%v, value:%v\n", iter.Key().(uint64), pPlayer)
	}
}

func main() {
	// 四个玩家
	player1 := newPlayer(1, 1, 1)
	player2 := newPlayer(2, 2, 2)
	player3 := newPlayer(3, 3, 3)
	player4 := newPlayer(4, 4, 4)

	// 新建红黑树(自带比较函数,库中带了几乎所有的基础类型,如果还是不够,可以自定义)
	allPlayers := rbt.NewWith(utils.UInt64Comparator)

	// 插入
	allPlayers.Put(player1.playerID, player1)
	allPlayers.Put(player2.playerID, player2)
	allPlayers.Put(player3.playerID, player3)

	// 重复插入key(下面会发现会覆盖)
	allPlayers.Put(player3.playerID, player4)

	// 遍历
	fmt.Println("插入后遍历")
	printMap(allPlayers)

	// 获取存在的key
	pValue, exist := allPlayers.Get(uint64(1))
	if exist {
		pPlayer := pValue.(*player)
		fmt.Printf("\n获取存在的key:1 的玩家信息:%v \n", pPlayer)
	}
	// 获取不存在的key
	pValue, exist = allPlayers.Get(uint64(111))
	if !exist {
		fmt.Printf("获取不存在的key:111 的玩家信息:%v \n", pValue)
	}

	// 查找最后一个比5小的迭代器信息(包括5)
	pNode, exist := allPlayers.Floor(uint64(5))
	if exist {
		pPlayer := pNode.Value.(*player)
		fmt.Printf("查找最后一个比key:5小(包括5)的迭代器信息:%v \n", pPlayer)
	}

	// 查找首个比2大的迭代器信息(包括2)
	pNode, exist = allPlayers.Ceiling(uint64(2))
	if exist {
		pPlayer := pNode.Value.(*player)
		fmt.Printf("查找首个比key:2大的迭代器信息:%v \n", pPlayer)
	}

	// 删除
	allPlayers.Remove(uint64(123)) // 删除不存在的key
	allPlayers.Remove(uint64(2))   // 删除存在的key

	// 删除后再次遍历
	fmt.Println("\n删除后遍历")
	printMap(allPlayers)
}