没有断言的单元测试不是单元测试,没有任何意义.建议用testify库或者直接reflect.DeepEqual比较下期望值和实际值.

First of all, I will say It's great repository. @liyue201 Thanks for implementing it!
I want to ask a question that what's the meaning of the first line in ds/array.go Equal() ?

// Equal returns true if the iterator is equal to the passed iterator, otherwise returns false
func (iter *ArrayIterator) Equal(other iterator.ConstIterator) bool {
	otherIter, ok := other.(*ArrayIterator)  // what's the grammar in here?Thanks a lot!
	if !ok {
		return false
	}
	if otherIter.array == iter.array && otherIter.position == iter.position {
		return true
	}
	return false
}

`
func TestMulitMap(t *testing.T) {
m := NewMultiMap()

x := []int{20, 40, 50, 50, 35, 60, 70, 80, 120, 140, 50, 2, 5, 60, 50,50,50}
N := len(x)
for i := 1; i <= N; i++ {
	m.Insert(x[i-1], i)
}
m.Erase(50)

}
`

试一下上面这个Test

`
--- FAIL: TestMulitMap (0.00s)
panic: runtime error: invalid memory address or nil pointer dereference [recovered]
panic: runtime error: invalid memory address or nil pointer dereference
[signal 0xc0000005 code=0x0 addr=0x0 pc=0x52274f]

goroutine 19 [running]:
testing.tRunner.func1(0xc0000ea300)
C:/Go/src/testing/testing.go:792 +0x38e
panic(0x695580, 0x8e9fd0)
C:/Go/src/runtime/panic.go:513 +0x1c7
github.com/liyue201/gostl/ds/rbtree.(*RbTree).rbFixupLeft(0xc0000468e0, 0x0, 0xc000048d40, 0x0, 0xe, 0xc0000f9e98)
E:/third/gostl/ds/rbtree/rbtree.go:249 +0x2f
github.com/liyue201/gostl/ds/rbtree.(*RbTree).rbDeleteFixup(0xc0000468e0, 0x0, 0xc000048d40)
E:/third/gostl/ds/rbtree/rbtree.go:237 +0x95
github.com/liyue201/gostl/ds/rbtree.(*RbTree).Delete(0xc0000468e0, 0xc000048c40)
E:/third/gostl/ds/rbtree/rbtree.go:225 +0x106
github.com/liyue201/gostl/ds/map.(*MultiMap).Erase(0xc000046900, 0x67e300, 0x72ba68)
E:/third/gostl/ds/map/multimap.go:62 +0x146
github.com/liyue201/gostl/ds/map.TestMulitMap(0xc0000ea300)
E:/third/gostl/ds/map/multimap_test.go:18 +0x155
testing.tRunner(0xc0000ea300, 0x6fbc60)
C:/Go/src/testing/testing.go:827 +0xc6
created by testing.(*T).Run
C:/Go/src/testing/testing.go:878 +0x363
`

我不确定是红黑树的问题还是Erase时后继迭代问题，可能删除时有两个子节点的情况的处理为删除最先后继使得 mutilateMap Erase时不能简单用后继迭代

No release version exist currently.

First of all, I will say It's great repository. @liyue201 Thanks for implementing it. I was going through it and found findUpprBoundNode method is not present in treemap. Can you please provide the implementation.

It seems that it's lacking some testcases and benchmarks for skiplist, rdtree and etc.

Motivation

I wanted to delete a element one by one from MultiSet and MultiMap. However, Erase(K) delete all elements having key K.

Solution

Using EraseIter(iter), we can delete the element one by one.

Example

package main

import (
	"fmt"

	"github.com/liyue201/gostl/ds/set"
	"github.com/liyue201/gostl/utils/comparator"
)

func main() {
	ms := set.NewMultiSet(comparator.IntComparator)

	// Insert
	for i := 0; i < 3; i++ {
		ms.Insert(5000)
	}
	fmt.Println(ms) // [5000 5000 5000]

	// EraseIter (one element)
	it := ms.Find(5000)
	ms.EraseIter(it)
	fmt.Println(ms) // [5000 5000]

	// Erase (all elements)
	ms.Erase(5000)
	fmt.Println(ms) // []
}

Other little things

Map already have had EraseIter, so I did nothing to that.

I am ready to send a pull request related this issue. If you approve of this feature addition, I will send that to this repository.

we can move the replicas field to the ketama.add() function as a parameter.
so we can adjust the replicas of the machine based at the ability of these machines.
this is better

Does it support setting priority?I cannot find the method.

Go1.18 has used generics to improve generality

看到介绍里面，大部分算法标记的都是线程安全。但在具体使用过程中，协程使用场景远远大于线程使用场景，所以向大佬确认一下到底是线程安全还是协程安全？

Hi, there is a problem in the implementation of the delete function of Red Black Tree.
rbtree.go:219:

if y != z {
	z.key = y.key
	z.value = y.value
}

It reuse the node-to-delete z in the tree and delete the successor node y
This is not correct because all pointers stored by the user on the y node will be invalidated.
I found a solution in the C++ STL of clang 13 (I believe), they swap the nodes y and z such that only z is invalidated, as expected.
Here is the code that I found:
__tree:382:

if (__y != __z)
{
    // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr
    __y->__parent_ = __z->__parent_; // 1
    if (_VSTD::__tree_is_left_child(__z))
      __y->__parent_->__left_ = __y;
    else
      __y->__parent_unsafe()->__right_ = __y;
    __y->__left_ = __z->__left_;
    __y->__left_->__set_parent(__y);
    __y->__right_ = __z->__right_;
    if (__y->__right_ != nullptr)
      __y->__right_->__set_parent(__y);
    __y->__is_black_ = __z->__is_black_;
    if (__root == __z)
      __root = __y;
}

Which I try'd to adapt to our implementation, it give me something like:
rbtree.go:219:

if y != z {
    //z.key = y.key
    //z.value = y.value

    y.parent = z.parent

    if t.root == z {
      t.root = y
    } else if z.parent.left == z {
      y.parent.left = y
    } else {
      y.parent.right = y
    }

    y.left = z.left
    y.left.parent = y

    y.right = z.right
    if y.right != nil {
      y.right.parent = y
    }

    y.color = z.color
}

But unfortunately this solution seems to break the tree for some reason that I don't know, it fail the tests.
Could a brilliant brain figure it out? I'm stuck

传统的哈希表怎么没有实现呢，我认为这个不是更常用么

May I ask why there is an additional multiplication by 1.2 here?

// shrinkIfNeeded shrinks the deque if it has too many unused space.
func (d *Deque[T]) shrinkIfNeeded() {
	if int(float64(d.segUsed()*2)*1.2) < cap(d.segs) {
		newCapacity := cap(d.segs) / 2
		seg := make([]*Segment[T], newCapacity)
		for i := 0; i < d.segUsed(); i++ {
			seg[i] = d.segs[(d.begin+i)%cap(d.segs)]
		}
		u := d.segUsed()
		d.begin = 0
		d.end = u
		d.segs = seg
	}
}