elliotchance / orderedmap Goto Github PK

View Code? Open in Web Editor NEW

770.0 13.0 62.0 36 KB

🔃 An ordered map in Go with amortized O(1) for Set, Get, Delete and Len.

License: MIT License

Go 100.00%

golang data-structures maps orderedmap

orderedmap's Introduction

🔃 github.com/elliotchance/orderedmap/v2

Basic Usage

An *OrderedMap is a high performance ordered map that maintains amortized O(1) for Set, Get, Delete and Len:

import "github.com/elliotchance/orderedmap/v2"

func main() {
	m := orderedmap.NewOrderedMap[string, any]()

	m.Set("foo", "bar")
	m.Set("qux", 1.23)
	m.Set("123", true)

	m.Delete("qux")
}

Note: v2 requires Go v1.18 for generics. If you need to support Go 1.17 or below, you can use v1.

Internally an *OrderedMap uses the composite type map combined with a trimmed down linked list to maintain the order.

Iterating

Be careful using Keys() as it will create a copy of all of the keys so it's only suitable for a small number of items:

for _, key := range m.Keys() {
	value, _:= m.Get(key)
	fmt.Println(key, value)
}

For larger maps you should use Front() or Back() to iterate per element:

// Iterate through all elements from oldest to newest:
for el := m.Front(); el != nil; el = el.Next() {
    fmt.Println(el.Key, el.Value)
}

// You can also use Back and Prev to iterate in reverse:
for el := m.Back(); el != nil; el = el.Prev() {
    fmt.Println(el.Key, el.Value)
}

The iterator is safe to use bidirectionally, and will return nil once it goes beyond the first or last item.

If the map is changing while the iteration is in-flight it may produce unexpected behavior.

orderedmap's People

Contributors

Stargazers

Watchers

Forkers

bonedaddy xcshuan algobot76 lang315 etleap orisano phantacix divjotarora abusizhishen jyotisj vidanio ttys3 junxie6 isgasho forkkit laijinhang dimakogan ebh flyyi accumulatenetwork khorevaa qiangzi-pro mantyr ouyangxizhu amoghyermalkar123 ccczone stonehao junftnt jbowa zbecnu gua-pian linuxea emirot markel1974 lutfuahmet strachi-sama ybocalandro mcules mrmarble cyber-meta achilsh magnaboscol forthespada steeledesmond adrissonsamersla d4c5d1e0 abanoubha newpurr mewbak juju227 ulyssessouza jpdro m277m277 code-monkeys oumkale francisoliverlee ilius tianyi666 zer0tonin triarius drshriveer mcsrainbow

orderedmap's Issues

unmarshal json to []orderedmap.OrderedMap make panic

feat: Concurrent safety for ordered maps

Using v2.

I saw in the source code that there is a lot of critical sections where race conditions can happen, this can be a feature that doesn't change the current API, more like a internal feature.

Have a great day.

Need GetElement method

Hi Elliot,

Thank you so much for implementing an awesome module. Your orderedmap module has helped me in two projects.

One of my project's requirement is to get previous and next values when a specific key is provided. Next() and Prev() are implemented for Element. However there is no GetElement method to get a specific Element when a key if provided.

How about adding a GetElement method in orderedmap package?

// GetElement returns the element for a key. If the key does not exist, the
// second return parameter will be false and the pointer will be nil.
func (m *OrderedMap) GetElement(key interface{}) (*Element, bool) {
value, ok := m.kv[key]
if ok {
element := value.Value.(*orderedMapElement)
return &Element{
element: value,
Key: element.key,
Value: element.value,
}, true
}

return nil, false

}

I am currently writing tests for the GetElement method. Thank you for writing detailed tests for the Get method. I'm following those to write tests for GetElement.

If you are fine with adding GetElement method then I'll create a pull request.

Thank you,
Jyoti

Benchmarks against CPP Python Java similar data structure

It would be illustrative to compare against other main languages, particularly CPP so that people see if this is a good fit for their project!

Delete operation is abnormal when iterating elements

The following code is used to test:

m := orderedmap.NewOrderedMap()
	m.Set(10, "ten")
	m.Set(9, "nine")
	m.Set(8, "eight")
	m.Set(7, "seven")
	m.Set(6, "six")
	m.Set(5, "five")
	m.Set(4, "four")
	m.Set(3, "three")
	m.Set(2, "two")
	m.Set(1, "one")

	for el := m.Front(); el != nil; el = el.Next() {
		if el.Key.(int)%2 == 0 {
			m.Delete(el.Key)
		}
	}

	for el := m.Front(); el != nil; el = el.Next() {
		fmt.Println(el.Key, el.Value)
	}

with the output:

9 nine
8 eight
7 seven
6 six
5 five
4 four
3 three
2 two
1 one

The reason for this is

func (l *list) Remove(e *Element) {
	if e.prev == nil {
		l.root.next = e.next
	} else {
		e.prev.next = e.next
	}
	if e.next == nil {
		l.root.prev = e.prev
	} else {
		e.next.prev = e.prev
	}
	e.next = nil // avoid memory leaks
	e.prev = nil // avoid memory leaks
}

e.next and e.prev are assigned to nil.
I don't think it's necessary. So Under what circumstances will this phenomenon(memory leaks) take place?

map is not sorted

var rs map[string][]byte

// 排序
m := orderedmap.NewOrderedMap()
for k, _ := range rs {
	fmt.Printf("  |-set-> %v\n", el.Key)
	m.Set(k, rs[k])
}

// You can also use Back and Prev to iterate in reverse:
for el := m.Back(); el != nil; el = el.Prev() {
	fmt.Printf("  |-get-> %v\n", el.Key)
}

----> 检索记录，前缀: auth_file_rec-001203-0100000084-
out--find more--> [auth_file_rec-001203-0100000084-%!s(int=23)]:
out--find more--> [auth_file_rec-001203-0100000084-%!s(int=24)]:
out--find more--> [auth_file_rec-001203-0100000084-%!s(int=25)]:
out--find more--> [auth_file_rec-001203-0100000084-%!s(int=26)]:
  |---> auth_file_rec-001203-0100000084-%!s(int=26)
  |---> auth_file_rec-001203-0100000084-%!s(int=25)
  |---> auth_file_rec-001203-0100000084-%!s(int=24)
  |---> auth_file_rec-001203-0100000084-%!s(int=23)
  
  
----> 检索记录，前缀: auth_file_rec-001203-0100000084-
out--find more--> [auth_file_rec-001203-0100000084-%!s(int=23)]:
out--find more--> [auth_file_rec-001203-0100000084-%!s(int=24)]:
out--find more--> [auth_file_rec-001203-0100000084-%!s(int=25)]:
out--find more--> [auth_file_rec-001203-0100000084-%!s(int=26)]:
  |---> auth_file_rec-001203-0100000084-%!s(int=24)
  |---> auth_file_rec-001203-0100000084-%!s(int=23)
  |---> auth_file_rec-001203-0100000084-%!s(int=26)
  |---> auth_file_rec-001203-0100000084-%!s(int=25)

Nested ordered maps

Was looking to implement something similar in orderedmap

schematicMap := make(map[int]map[int]string)

Where m := orderedmap.NewOrderedMap[int, any]() is the key, and mm := orderedmap.NewOrderedMap[int, any]() is re-created in a loop as the value.

However, attempting to set the map with a value of another map, only returns the Set's bool success.

m.Set(yPos, mm.Set(xPos, s.Text()))

0 true
1 true
2 true
3 true
4 true
5 true
6 true
7 true
8 true
9 true

`json.Marshal` — doesn't work

Hi,

I try convert OrderedMap to json, but receive empty object :/

package main

import (
	"fmt"
	"encoding/json"
	"github.com/elliotchance/orderedmap"
)

func main() {
	m := orderedmap.NewOrderedMap()

	m.Set("foo", "bar")
	m.Set("qux", 1.23)
	m.Set(123, true)

	b, err := json.Marshal(m)
	if err != nil {
		fmt.Println("error:", err)
	}
	
	fmt.Println("result:", string(b)) // "result: {}" ⚠️
}

https://play.golang.org/p/UFER3tR6uPA

type Dependencies struct {
	Deps orderedmap.NewOrderedMap[string, Dependency]() `json:"packages" toml:"dependencies,omitempty"`
}

type Dependency struct {
	Name     string `json:"name" toml:"name,omitempty"`
	FullName string `json:"-" toml:"full_name,omitempty"`
	Version  string `json:"-" toml:"version,omitempty"`
	Sum      string `json:"-" toml:"sum,omitempty"`
	LocalFullPath string `json:"manifest_path" toml:"-"`
	Source        `json:"-"`
}

But i am getting an error.

cc: @elliotchance

invalid operation: cannot index orderedmap.NewOrderedMap

I am trying to migrate to orderedmap. I am getting an error that says

invalid operation: cannot index orderedmap.NewOrderedMap (value of type func() *"github.com/elliotchance/orderedmap".OrderedMap)

newDeps := pkg.Dependencies{
    Deps: orderedmap.NewOrderedMap[string, pkg.Dependency](),
}

My Dependencies looks like:

type Dependencies struct {
	Deps *orderedmap.OrderedMap[string, Dependency] `json:"packages" toml:"dependencies,omitempty"`
}