sorted-array

一个用了二分查找法构建的排序数组

Install

npm install sorted-array --save

场景

• 已经有一个映射容器，用于快速查找
• 需要一个按照指定规则排序的容器
• 以上这两个容器需要同步更新
• 排序容器的添加和删除性能有要求，拒绝遍历

原理

利用二分查找法精确定位数组中的指定元素，从而实现快速添加和删除

例子

const SortedArray = require("sorted-array")

const array = new SortedArray((first,second)=>
{
 if(first.updated != second.updated)
    {
        return first.updated - second.updated
    }

    if (first.id < second.id)
    {
        return 1
    }

    if (first.id > second.id)
    {
        return 1
    }
    return 0
})

const clients = {}      //

for(let i = 1;i < 10;++i>)
{
    let client = {
        id:i,
        updated:i,
    }

    clients[i] = client
    array.push(client)
}

console.log(array)      // 查看是否排序正确

let delete_id = 5

let delete_client = clients[delete_id]

array.pop(delete_client)

console.log(array)      //查看是否正确删除

cmp

cmp 的返回值必须是三值，用于精确定位元素，一定不要只返回true false

• 0：等于
• 1：大于
• -1：小于