c++ map是有序还是无序的_实现有序map之go「建议收藏」

c++ map是有序还是无序的_实现有序map之go「建议收藏」GoMap介绍Go中Map是一种无序的键值对的集合。Map最重要的一点是通过key来快速检索数据,key类似于索引,指向数据的值。Map是一种集合,所以我们可以像迭代数组和切片那样迭代它。不过,Map是无序的,我们无法决定它的返回顺序,这是因为Map是使用链式hash表来实现的。c++中的实现在C++STL中map采用红黑树实现,可以实现有序的Map.Go中实现实现原理这个实现方法的…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

Go Map介绍

Go 中 Map是一种无序的键值对的集合。Map最重要的一点是通过key来快速检索数据,key类似于索引,指向数据的值。Map是一种集合,所以我们可以像迭代数组和切片那样迭代它。不过,Map是无序的,我们无法决定它的返回顺序,这是因为Map是使用链式hash表来实现的。

c++中的实现

在C++ STL 中map 采用红黑树实现,可以实现有序的Map.

Go 中实现

实现原理

这个实现方法的主要的方法是用空间换取时间。通过list 和 map 两种数据结构,保存相同的一份数据。list 用来做顺序遍历,map 用来做查找,删除操作

实现代码

package main

import (

“container/list”

“fmt”

)

type Keyer interface {

GetKey() string

}

type MapList struct {

dataMap map[string]*list.Element

dataList *list.List

}

func NewMapList() *MapList {

return &MapList{

dataMap: make(map[string]*list.Element),

dataList: list.New(),

}

}

func (mapList *MapList) Exists(data Keyer) bool {

_, exists := mapList.dataMap[string(data.GetKey())]

return exists

}

func (mapList *MapList) Push(data Keyer) bool {

if mapList.Exists(data) {

return false

}

elem := mapList.dataList.PushBack(data)

mapList.dataMap[data.GetKey()] = elem

return true

}

func (mapList *MapList) Remove(data Keyer) {

if !mapList.Exists(data) {

return

}

mapList.dataList.Remove(mapList.dataMap[data.GetKey()])

delete(mapList.dataMap, data.GetKey())

}

func (mapList *MapList) Size() int {

return mapList.dataList.Len()

}

func (mapList *MapList) Walk(cb func(data Keyer)) {

for elem := mapList.dataList.Front(); elem != nil; elem = elem.Next() {

cb(elem.Value.(Keyer))

}

}

type Elements struct {

value string

}

func (e Elements) GetKey() string {

return e.value

}

func main() {

fmt.Println(“Starting test…”)

ml := NewMapList()

var a, b, c Keyer

a = &Elements{“Alice”}

b = &Elements{“Bob”}

c = &Elements{“Conrad”}

ml.Push(a)

ml.Push(b)

ml.Push(c)

cb := func(data Keyer) {

fmt.Println(ml.dataMap[data.GetKey()].Value.(*Elements).value)

}

fmt.Println(“Print elements in the order of pushing:”)

ml.Walk(cb)

fmt.Printf(“Size of MapList: %d \n”, ml.Size())

ml.Remove(b)

fmt.Println(“After removing b:”)

ml.Walk(cb)

fmt.Printf(“Size of MapList: %d \n”, ml.Size())

}

优点

红黑树的插入、删除、查找的复杂度都是 O(logn), 而这个实现插入查找删除的复杂度都是 O(1), 可以说是一种非常好的数据结构。

缺点

使用了两个数据结构,空间占用稍微大了一点。但是和树的实现比,这个占用也不算非常大

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/190163.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • window10蓝屏终止代码system service_win10蓝屏driverpowerstatefailure

    window10蓝屏终止代码system service_win10蓝屏driverpowerstatefailureWindows10蓝屏代码:SYSTEM_SERVICE_EXCEPTION排查及解决方案问题描述win10正常使用过程中,出现蓝屏,蓝屏代码为SYSTEM_SERVICE_EXCEPTION,出现时间或时机没有明显规律,但最近两次出现均是在电脑待机睡眠后重新唤醒时。电脑配置环境如下其中:内存为阿斯加特32GB300051°灰套条解决方案因最近出现时机为睡眠唤醒中,考虑与主板芯片组驱动及睡眠机制有关,故重新安装系统[可选]:如条件允许,重新安装系统是最好的解决方案,可以基本排除掉系

  • Python变量

    Python中变量类型:局部变量全局变量类变量对象变量外部变量

    2021年12月18日
  • 微信公众号开发-超级简单[通俗易懂]

    微信公众号开发-超级简单[通俗易懂]1自动回复功能【图片模糊的双击图片,就清晰了】公众号注册网上一大把,搜下就可以了这个功能就是别人给公众号发什么消息,就返回指定内容关键词回复:输入关键词,返回指定内容收到消息回复:当你不是输入关键词时,自动发送当前消息,如果输入的是关键词,就返回关键词所指定的内容被关注回复:当公众号被关注时,自动给用户发的消息1案例,添加关键…

  • java专业是什么专业,写的太详细了「建议收藏」

    java专业是什么专业,写的太详细了「建议收藏」前言SQL语句执行慢的原因是面试中经常会被问到的,对于服务端开发来说也是必须要关注的问题。在生产环境中,SQL执行慢是很严重的事件。那么如何定位慢SQL、慢的原因及如何防患于未然。接下来带着这些问题让我们开启本期之旅!第1章:Dubbo的简史、后续的规划和整体架构大图————Dubbo高性能RPC通信框架1.1应用架构演进过程1.2Dubbo简介1.3Dubbo总体大图第2章:Dubbo的环境配置和基于Dubbo开发第一款应用程序————开发第一款Dubbo应用程序

  • AutoFac文档5(转载)

    AutoFac文档5(转载)

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号