再谈谈列表元素的删除

淩亂°似流年 2022-08-21 10:57 229阅读 0赞

[之前][Link 1]（以及[更早之前][Link 2]）都提到了列表元素的删除，也提到过几种方法，有兴趣的朋友可以去看看，其中一种个人比较倾向的写法大概是这个样子(C++)：

auto iter = vec.begin();
    while (iter != vec.end()) {
    	if (isEven(*iter)) {
    		iter = vec.erase(iter);
    	}
    	else {
    		++iter;
    	}
    }

近几日恰巧看到了C\#系统库中List<T>的RemoveAll实现，觉的实现的更好，所以想到可以就这个问题再随便写写，算做笔记吧~

基本思路大概是这样的：由于列表元素都是顺序存放的，导致的一个常见问题就是插入或者删除元素的代价较高，列表在插入元素或者删除元素之后需要移动相关列表数据以保证数据存放的顺序性，遇到容量(Capacity)不足时，列表还需要重新申请内存，甚至于移动整个列表元素~

所以一般情况下，如果你的业务场景需要频繁的插入或者删除元素，那么建议你使用链表等数据结构来代替列表，拿C++来说就是使用[list][]来代替[vector][]，不过鉴于list的访问效率不高，C++中还有一个结合了list和vector的[deque][]，有兴趣的朋友可以看看~

有点扯远了，我们继续来说RemoveAll的实现：对于列表结构，顺序存放这个特点是固有的，我们无法规避，但是对于删除操作，如果我们能先将需要删除的元素移动至列表尾部，然后再执行删除操作，那么就可以规避掉多余的列表元素移动！

想法是挺好的，但是新的问题又来了：如何移动元素至列表尾部呢？对于不要求元素间顺序的列表来说，这一点是挺容易实现的，一个Swap操作即可，但是在多数情况下，我们还是希望保持列表元素间的相对顺序的，这时如果要实现移动元素至尾部的操作，那么就需要将元素后的所有列表数据统一前置，这在本质上跟直接删除元素，然后由列表自行完成数据迁移没有区别~（大多数情况下，由于列表的内部实现往往经过了很多优化，其“内部”移动数据的效率往往比“外部”来移动要高，但这是属于实现层面或者说工程层面的问题，在此我们就简单假定只要是移动数据，那么效率就是一致的，没有内部和外部之分）

对于删除单个元素来说，上述做法确实与传统的直接删除法没有区别，但是考虑一下同时删除多个元素的情景，如果仍然沿用之前的直接删除法，那么就可能会触发多次列表元素的移动，但是如果我们首先将需要删除的多个元素统一移动至列表尾部，然后再执行清理操作，那么就可以大幅度降低列表元素的移动次数！

OK，废话完毕，上代码~

public int RemoveAll(Predicate<T> match)
    {
    	// 首先检查参数合法性
    	if (match == null) {
    		ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
    	}
    	int num = 0;
    	// 尝试找到第一个需要删除的元素的位置（num）
    	while (num < this._size && !match(this._items[num])) {
    		num++;
    	}
    	// 已到达列表末尾，说明不存在符合条件的元素，直接返回
    	if (num >= this._size) {
    		return 0;
    	}
    	int i = num + 1;
    	while (i < this._size) {
    		// 寻找下一个不需要删除的元素的位置
    		while (i < this._size && match(this._items[i])) {
    			i++;
    		}
    		// 将不需要删除的元素直接移动至目前num的位置，并递增位置索引
    		if (i < this._size) {
    			this._items[num++] = this._items[i++];
    		}
    	}
    	// 清除列表末尾的数据（大小为列表大小减去当前num）
    	Array.Clear(this._items, num, this._size - num);
    	// 更新列表内部数据并返回
    	int result = this._size - num;
    	this._size = num;
    	this._version++;
    	return result;
    }

还是不懂？那就再看下这张示意图：

![20160427213843046][]

简单分析一下时间复杂度：

假设列表中每个元素被删除的概率为P（1/n <= P <=1）（其中n为列表大小），那么对于之前提到过的直接删除法，其平均情况下的时间复杂度为：

T(n) = P \* (n -1) + P \* (n - 2) + P \* (n - 3) + ... + P \* 1 = P \* (n^2 - n) / 2 = O(P\*n^2)

对于目前所分析的这种方法，其平均情况下的时间复杂度为：

T(n) = O(n)

并且在最坏情况下的复杂度依然如此~Cool！

（PS：如果取P为1/n，即只删除一个元素的情况，那么这两种方法的时间复杂度便都是O(n)，没有区别，这与我们之前的分析一致~）

[Link 1]: http://blog.csdn.net/tkokof1/article/details/51165082
[Link 2]: http://blog.csdn.net/tkokof1/article/details/23197215
[list]: http://www.cplusplus.com/reference/list/list/
[vector]: http://www.cplusplus.com/reference/vector/vector/
[deque]: http://www.cplusplus.com/reference/deque/deque/?kw=deque
[20160427213843046]: /images/20220724/93548fedcf134c7aa099fb9fd11eae32.png