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

---------------------------问个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/

推荐阅读

buffer
RTThread线程间通信

线程中通信在裸机编程中，经常会使用全局变量进行功能间的通信，如某些功能可能由于一些操作而改变全局变量的值，另一个功能对此全局变量进行读取& ... [详细]

蜡笔小新 2024-11-18 14:56:11
buffer
UE4 中的距离场技术详解

本文将深入探讨 Unreal Engine 4 (UE4) 中的距离场技术，包括其原理、实现细节以及在渲染中的应用。距离场技术在现代游戏引擎中用于提高光照和阴影的效果，尤其是在处理复杂几何形状时。文章将结合具体代码示例，帮助读者更好地理解和应用这一技术。 ... [详细]

蜡笔小新 2024-11-19 18:21:03
buffer
深入理解RxJava操作符

根据官方定义，RxJava是一种用于异步编程和可观察数据流的API。其核心特性在于流式处理能力和丰富的操作符支持。 ... [详细]

蜡笔小新 2024-11-19 17:37:35
buffer
RTSP协议详解

本文介绍了实时流协议（RTSP）的基本概念、组成部分及其与RTCP的交互过程，详细解析了客户端请求格式、服务器响应格式、常用方法分类及协议流程，并提供了SDP格式的深入解析。 ... [详细]

蜡笔小新 2024-11-19 12:19:47
less
pypy 真的能让 Python 比 C 还快么？

作者：肖恩顿来源：游戏不存在最近“pypy为什么能让python比c还快”刷屏了，原文讲的内容偏理论，干货比较少。我们可以再深入一点点，了解pypy的真相。正式开始之前，多唠叨两句 ... [详细]

蜡笔小新 2024-11-18 08:45:23
php
深入理解：AJAX学习指南

本文详细探讨了AJAX的基本概念、工作原理及其在现代Web开发中的应用，旨在为初学者提供全面的学习资料。 ... [详细]

蜡笔小新 2024-11-20 17:58:54
go
将图像平移到画布中心python_python – Tkinter画布缩放移动/平移

高级缩放示例.就像谷歌地图一样.它仅缩放图块,但不缩放整个图像.因此,缩放的瓷砖占据了恒定的记忆,并且不会为大型缩放图像调整大小的图像.对于简化的缩放示例lookhere.在Win ... [详细]

蜡笔小新 2024-11-20 15:47:04
express
JavaScript AST抽象语法树常见节点及结构

文章目录前言Program（程序）Identifier（标识符）Literal（字面量）Vari ... [详细]

蜡笔小新 2024-11-19 17:59:26
buffer
实现系统调用

实现系统调用一、实验环境本次操作还是基于上次编译Linux0.11内核的实验环境进行操作。环境如下：二、实验目标通过对上述实验原理的认识，相信 ... [详细]

蜡笔小新 2024-11-19 17:13:33
buffer
开发技巧: Effective Java第三版——优先选用Collection而非Stream作为方法返回类型

在Effective Java第三版中，建议在方法返回类型中优先考虑使用Collection而非Stream，以提高代码的灵活性和兼容性。 ... [详细]

蜡笔小新 2024-11-19 15:31:16
eval
解决UIScrollView上Webview点击图片后无法立即滑动的问题

本文探讨了在UIScrollView上嵌入Webview时遇到的一个常见问题：点击图片放大并返回后，Webview无法立即滑动。我们将分析问题原因，并提供有效的解决方案。 ... [详细]

蜡笔小新 2024-11-18 21:13:13
go
Java集合框架深入解析：HashSet详解

本文详细介绍了HashSet类，它是Set接口的一个实现，底层使用哈希表（实际上是HashMap实例）。HashSet不保证元素的迭代顺序，并且是非线程安全的。 ... [详细]

蜡笔小新 2024-11-18 16:58:22
php
使用参数化查询防止SQL注入

本文介绍如何通过参数化查询来防止SQL注入攻击，确保数据库的安全性。示例代码展示了在C#中使用参数化查询添加学生信息的方法。 ... [详细]

蜡笔小新 2024-11-18 15:53:22
go
MIT 6.824 实验笔记：MapReduce 开发指南

本文详细记录了 MIT 6.824 课程中 MapReduce 实验的开发过程，包括环境搭建、实验步骤和具体实现方法。 ... [详细]

蜡笔小新 2024-11-18 12:05:23
buffer
2019-2021年阿里Java面试真题汇总

本文总结了近年来在实际项目中使用消息中间件的经验和常见问题，旨在为Java初学者和中级开发者提供实用的参考。文章详细介绍了消息中间件在分布式系统中的作用，以及如何通过消息中间件实现高可用性和可扩展性。 ... [详细]

蜡笔小新 2024-11-18 10:03:28

向着成功一直努力的人

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

Tags | 热门标签

RankList | 热门文章