沉寂了一年多之后，gocontainer这个library终于发布了v0.2.0。主要是支持了btree。
什么是gocontainer
虽然一年多前介绍过这个小项目，估计很多人已经忘记了它是干什么的了。所以这里再次做一个简单的介绍。
golang内置支持的(map, slice, array)以及标准库支持的(heap, list, ring)数据结构很少，所以我就自己实现了gocontainer。gocontainer主要实现了一些常用的数据结构，例如Stack, Queue, Set, List, PriorityQueue, LinkedMap以及BTree。
虽然gocontainer这个名字里包含"container"，但实际上它与现在流行的容器没有半毛钱关系。叫go-collection或者go-datastructure可能更准确，也不会引起误解。之所以取这个名字，以前解释过：
container这个概念最开始并不是表示现在流行的容器；
golang标准库中实现的几个数据结构就是放在了目录"container"里面；
短期内可能会有误解，但随着时间的推移，接触多了误解自然就消失了。
gocontainer在github上的地址如下，配有中英文的README。
https://github.com/ahrtr/gocontainer复制
也可以参考我一年多前写的一篇文章：
重构并改进BTree
在gocontainer的v0.2.0版本中，主要就是引入了BTree。原始的实现源码来自于google/btree (如下)， 这一点我在source code, README以及release note中都有提及，而且我也保留了原来的Copyright header。
https://github.com/google/btree复制
但是我对原来的实现做了一些比较大的重构和改进。重构是为了使其能融入gocontainer这个library，成为整体的一个有机组成部分。改进则是为了使其更加用户友好(user-friendly)。
这里重点讲一下其中最大的一个改进。我们都知道，BTree是一个有序集合，这就要求它里面存储的元素要支持排序。google/btree原始的代码中定义了一个接口：
// Item represents a single object in the tree.type Item interface {// Less tests whether the current item is less than the given argument.Less(than Item) bool}复制
这也要求使用google/btree的用户必须实现这个接口，哪怕存储到btree中的元素是golang build-in的数据类型，例如int, string等。google/btree中已经定义了一个自定义的类型Int，实现了这个接口，对于其它任何类型，用户必须自己实现这个接口。对于int，虽然可以直接使用google/btree中定义的Int，但也要做一次类型转换。总之，使用起来很不方便。
// Int implements the Item interface for integers.type Int int// Less returns true if int(a) < int(b).func (a Int) Less(b Item) bool {return a < b.(Int)}复制
对此，我在gocontainer中专门做了改进。对于golang的一些常见的build-in数据类型，用户无需自己定义任何接口，就可以直接存储到btree中。这时就默认按照元素的自然顺序排序。例如对于int，3肯定小于5；对于string， "abc"肯定小于“bcd"，等等。
对于一些复杂的组合类型(struct)，用户则需要实现如下接口：
// Comparator imposes a total ordering on some collection of objects, and it allows precise control over the sort order.type Comparator interface {// Compare compares its two arguments for order.// It returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.Compare(v1 interface{}, v2 interface{}) (int, error)}复制
显而易见，改进之后的实现使用起来更加方便，更加用户友好！
copy-on-write
这里要额外提一下btree中用到的copy-on-write (COW)逻辑。这个不是我增加的功能，而是google/btree的原本实现中就已经存在的。因为比较有意思，也值得学习，所以这里额外提一下。
稍微有点计算机背景知识的人对COW都不陌生，但我估计很多人只是停留在概念层面的理解上。如果让你自己动手实现COW，你会怎么做呢？
google/btree的实现就给出了一个现实版的例子。它提供了一个Clone()的接口方法，可以克隆一个btree。但是它并不是真的立即拷贝整个btree，而是采用的延迟(lazy)拷贝。后续如果只是读操作，则两个btree共享读同一个数据结构；一旦发生写操作，则会拷贝相应的节点(node)，注意这里也只是拷贝相应的节点，而不是整个btree。所以这里有几个关键点：
clone采用了延迟(lazy)拷贝；
一旦clone发生之后，原始的数据结构就变成只读了(read-only)；
clone之后，老的btree和新的btree可以共享读同一个数据结构；
clone之后，不管是写老btree还是写新btree，都会拷贝相应的节点（而不是整个btree），然后才修改。
具体实现代码也不复杂，具体请阅读源码：
https://github.com/ahrtr/gocontainer/blob/master/btree/btree.go复制
小结
欢迎提意见、留言、点赞、转发，更欢迎给ahrtr/gocontainer加星(star)! Thanks!
https://github.com/ahrtr/gocontainer复制
--END--
