C&C++   发布时间:2022-04-03  发布网站:大佬教程  code.js-code.com
大佬教程收集整理的这篇文章主要介绍了c – stl deque :: insert()的复杂性大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
我从C标准2003(第23.2.1.3章)中了解了deque :: insert()的复杂性,如下所示:

在最坏的情况下,将单个元素插入到双端队列中需要时间在从插入点到双端队列开始的距离的最小值以及从插入点到双端队列结束的距离的线性.

我总是将stl deque的实现理解为内存块的集合.因此,插入仅影响与插入位置相同的存储块中的元素.我的问题是,标准是什么意思是“从插入点到双端队列开始的距离的最小值和从插入点到双端队列结束的距离的线性”?

我的理解是因为C标准没有强制实施deque的某种实现.对于最坏的情况,复杂性通常是一般的.但是,在编译器的实际实现中,它与内存块中的元素数量成线性关系,这可能因不同的元素大小而异.

一个猜测可能是,因为insert()将使所有迭代器无效,deque需要更新所有迭代器.因此它是线性的.

解决方法

std :: deque通常(总是?)实现为内存块的集合,但它通常不会插入一个全新的块,只是为了在集合的中间插入一个新元素.因此,它将查找插入点是否更接近开头或结尾,并对现有元素进行随机播放,以便为现有块中的新元素腾出空间.它只会在集合的开头或结尾添加一大块内存.

大佬总结

以上是大佬教程为你收集整理的c – stl deque :: insert()的复杂性全部内容,希望文章能够帮你解决c – stl deque :: insert()的复杂性所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。