当前位置: 开发笔记 > 编程语言 > 正文

---------------------------问个STL问题。已知一个下标，从LIST里直接删除它，其中找到的复杂度是多少？

作者：向着成功一直努力的人 | 来源：互联网 | 2023-10-12 08:39

看了很多都是BEGIN---END的循环，找到后删除，这个很慢，有没更快的？find??如果没有只好自己写个数组+链表，删除直接偏移到位置

看了很多都是BEGIN---END的循环，找到后删除，这个很慢，
有没更快的？find??

如果没有只好自己写个数组+链表，删除直接偏移到位置

12 个解决方案

#1

好吧 deque的实现就是你说的。

#2

情况不对，不是2分了。完了，估计这家伙以后发帖是0分了。

#3

deque支持随机访问，提供c.erase(pos)方法，删除指定下标元素

#4

那得看是什么样的容器，像deque,vector,string删除pos位置的元素，其查找的时间复杂度都是O(1)的，list就是O(n)了，map和set就是O(logN)了。

#5

引用 4 楼 michael_xie 的回复:

那得看是什么样的容器，像deque,vector,string删除pos位置的元素，其查找的时间复杂度都是O(1)的，list就是O(n)了，map和set就是O(logN)了。

++1
不是排序，只是查找的会用DEQUE，时间是常量，最快

#6

有删除需求建议用多map组合

#7

引用 1 楼 pengzhixi 的回复:

好吧 deque的实现就是你说的。

不会的大侠，偶会结贴的。。

我看了下deque，只有两个接口，push和pop，好像根据不了pos操作呢

引用 4 楼 michael_xie 的回复:

那得看是什么样的容器，像deque,vector,string删除pos位置的元素，其查找的时间复杂度都是O(1)的，list就是O(n)了，map和set就是O(logN)了。

vector我看到这样段代码：

	void _Orphan_range(pointer _First, pointer _Last) const

		{	// orphan iterators within specified (inclusive) range

		_Lockit _Lock(_LOCK_DEBUG);

		const_iterator **_Pnext = (const_iterator **)&this->_Myfirstiter;

		while (*_Pnext != 0)

			if ((*_Pnext)->_Myptr < _First || _Last < (*_Pnext)->_Myptr)

				_Pnext = (const_iterator **)&(*_Pnext)->_Mynextiter;

			else

				{	// orphan the iterator

				(*_Pnext)->_Mycont = 0;

				*_Pnext = (const_iterator *)(*_Pnext)->_Mynextiter;

				}

		}

删除有遍历吧？

其实我想要的就是，插入O(1),根据pos删除，也是O(1).现成容器有解？

#8

deque,vector,string在pos插入和删除时所用的查找时间复杂度都是O(1),但是有可能导致大量的数据移动，总体效率不高。

#9

你看的是queue不是deque，deque都支持[]下标操作

#10

vector.erase(begin()+pos),删除好慢啊好慢，不做点手脚的话，release下的速度起码慢了十倍

#11

引用 9 楼 pengzhixi 的回复:

你看的是queue不是deque，deque都支持[]下标操作

打工去了，回来再看。不过删除的代码里似乎看到了copy的字样哦

#12

去看看有些什么接口吧
http://www.cplusplus.com/reference/stl/deque/

推荐阅读

java
Java集合框架特性详解与开发实践笔记

Java集合框架特性详解与开发实践笔记 ... [详细]

蜡笔小新 2024-11-02 12:55:56
java
CentOS 7环境下Jenkins的安装与前后端应用部署详解

CentOS 7环境下Jenkins的安装与前后端应用部署详解 ... [详细]

蜡笔小新 2024-11-04 16:46:02
io
POJ 2777：线段树的懒惰更新策略分析与实现

题目链接：POJ 2777。问题描述：给定一个区域，需要进行多次涂色操作，并在每次操作后查询某个区间内的不同颜色数量。解决方案：由于题目中颜色种类不超过30种，可以利用线段树的懒惰更新策略来高效处理这些操作。通过懒惰标记，避免了不必要的节点更新，从而显著提高了算法的效率。此外，该方法还能有效应对大规模数据输入，确保在合理的时间内完成所有操作。 ... [详细]

蜡笔小新 2024-11-03 15:22:44
java
Java中处理NullPointerException：getStackTrace()方法详解与实例代码

Java中处理NullPointerException：getStackTrace()方法详解与实例代码 ... [详细]

蜡笔小新 2024-11-03 13:55:30
io
每日精选Codeforces训练题：1119E（贪心算法）、821C（栈模拟）和645D（拓扑排序）

题目涉及三种不同类型的算法问题：1119E（贪心算法）、821C（栈模拟）和645D（拓扑排序）。其中，1119E的问题背景是有n种不同长度的棍子，长度分别为2^0, 2^1, …, 2^(n-1)，每种棍子的数量为a[i]。任务是计算可以组成的三角形数量。根据三角形的性质，任意两边之和必须大于第三边。该问题可以通过贪心算法高效解决，通过合理选择棍子组合来最大化三角形的数量。 ... [详细]

蜡笔小新 2024-11-03 11:42:58
java
Java 模式原型在游戏服务器架构中的应用与优化

Java 模式原型在游戏服务器架构中的应用与优化 ... [详细]

蜡笔小新 2024-11-03 10:50:00
post
题目：图像处理（HDU1828，计算周长并集，利用线段树与离散化技术进行扫描）

题目：图像处理（HDU1828，计算周长并集，利用线段树与离散化技术进行扫描） ... [详细]

蜡笔小新 2024-11-02 17:13:02
数组
第2周：高精度计算（支持任意进制，仅需调整基数）+ 前缀和 + 差分技术

本周课程涵盖了高精度计算、前缀和及差分技术。在高精度计算部分，我们将探讨如何处理任意进制的数值运算，包括但不限于正数的加法、减法和乘法。通过调整基数，可以灵活应对不同进制的需求。前缀和与差分技术则主要用于高效解决数组和区间查询问题，提升算法性能。 ... [详细]

蜡笔小新 2024-11-01 17:46:37
io
Prim算法优化实现：基于优先队列的最小生成树构建方法

Prim算法在处理稠密图时表现出色，尤其适用于边数远多于顶点数的情形。传统实现的时间复杂度为 \(O(n^2)\)，但通过引入优先队列进行优化，可以在点数为 \(m\)、边数为 \(n\) 的情况下显著降低时间复杂度，提高算法效率。这种优化方法不仅能够加速最小生成树的构建过程，还能在大规模数据集上保持良好的性能表现。 ... [详细]

蜡笔小新 2024-11-01 16:06:14
io
开发笔记：STL 容器 deque 的元素访问与迭代器详解

开发笔记：STL 容器 deque 的元素访问与迭代器详解 ... [详细]

蜡笔小新 2024-11-01 13:44:43
io
ICM Technex 2017与Codeforces第400轮（合并组）C题：莫莉的化学物质分析

在解决区间相关问题时，我发现自己经常缺乏有效的思维方式，即使是简单的题目也常常需要很长时间才能找到解题思路，而一旦得到提示便能迅速理解。题目要求对一个包含n个元素的数组进行操作，并给出一个参数k，具体任务是…… ... [详细]

蜡笔小新 2024-11-05 15:59:59
c语言
如何在Lua中调用C语言编译的动态链接库

本文介绍了如何在Lua中调用C语言编译的动态链接库。通过详细步骤和示例代码，帮助开发者理解和掌握这一技术。参考了《Lua编程入门》一书中的相关内容，并结合实际操作经验，提供了更加清晰和实用的指导。此外，还探讨了在不同操作系统下编译和链接Lua的方法，为跨平台开发提供了有价值的参考。 ... [详细]

蜡笔小新 2024-11-05 11:58:03
io
2016-2017 ACM-ICPC东北欧区域赛（NEERC 16）Gym101190E：离线查询与排序优化策略

题目链接：http://codeforces.com/gym/101190/attachments题意：在一个共享三轮车站点，某些用户需要租用车辆。该问题涉及如何通过离线查询和排序优化策略来高效地管理和分配车辆资源。具体来说，需要设计一种算法，在满足所有用户需求的同时，最小化总等待时间和资源浪费。通过合理的数据结构和算法优化，可以显著提高系统的整体性能和用户体验。 ... [详细]

蜡笔小新 2024-11-05 11:36:52
jsp
Hibernate实战笔记14：深入解析反向工程技术

在处理遗留数据库的映射时，反向工程是一个重要的初始步骤。由于实体模式已经在数据库系统中存在，Hibernate 提供了自动化工具来简化这一过程，帮助开发人员快速生成持久化类和映射文件。通过反向工程，可以显著提高开发效率并减少手动配置的错误。此外，该工具还支持对现有数据库结构进行分析，自动生成符合 Hibernate 规范的配置文件，从而加速项目的启动和开发周期。 ... [详细]

蜡笔小新 2024-11-04 18:29:37
java
计算 n 叉树中各节点子树的叶节点数量分析

计算 n 叉树中各节点子树的叶节点数量分析 ... [详细]

蜡笔小新 2024-11-01 12:22:01

向着成功一直努力的人

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章