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

---------------------------问个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容器中的compareto方法排序原理解析

本文从源码解析Java容器中的compareto方法的排序原理，讲解了在使用数组存储数据时的限制以及存储效率的问题。同时提到了Redis的五大数据结构和list、set等知识点，回忆了作者大学时代的Java学习经历。文章以作者做的思维导图作为目录，展示了整个讲解过程。 ... [详细]

蜡笔小新 2023-12-14 13:53:31
数组
集合的遍历方式及其局限性

本文介绍了Java中集合的遍历方式，重点介绍了for-each语句的用法和优势。同时指出了for-each语句无法引用数组或集合的索引的局限性。通过示例代码展示了for-each语句的使用方法，并提供了改写为for语句版本的方法。 ... [详细]

蜡笔小新 2023-12-12 15:34:14
数组
模板引擎StringTemplate的使用方法和特点

本文介绍了模板引擎StringTemplate的使用方法和特点，包括强制Model和View的分离、Lazy-Evaluation、Recursive enable等。同时，还介绍了StringTemplate语法中的属性和普通字符的使用方法，并提供了向模板填充属性的示例代码。 ... [详细]

蜡笔小新 2023-12-11 21:45:03
char
电话号码的字母组合解题思路和代码示例

本文介绍了力扣题目《电话号码的字母组合》的解题思路和代码示例。通过使用哈希表和递归求解的方法，可以将给定的电话号码转换为对应的字母组合。详细的解题思路和代码示例可以帮助读者更好地理解和实现该题目。 ... [详细]

蜡笔小新 2023-12-14 18:50:22
数组
Redis数据结构之string应用场景解析

本文介绍了Redis的基础数据结构string的应用场景，并以面试的形式进行问答讲解，帮助读者更好地理解和应用Redis。同时，描述了一位面试者的心理状态和面试官的行为。 ... [详细]

蜡笔小新 2023-12-14 14:02:42
数组
如何在有序字符序列中插入新字符并保持有序

本文介绍了如何在给定的有序字符序列中插入新字符，并保持序列的有序性。通过示例代码演示了插入过程，以及插入后的字符序列。 ... [详细]

蜡笔小新 2023-12-14 11:16:33
数组
Android JSON基础，音视频开发进阶指南目录

Array里面的对象数据是有序的，json字符串最外层是方括号的，方括号：[]解析jsonArray代码try{json字符串最外层是 ... [详细]

蜡笔小新 2023-12-13 15:05:45
数组
Java中vector的使用详解

本文详细介绍了Java中vector的使用方法和相关知识，包括vector类的功能、构造方法和使用注意事项。通过使用vector类，可以方便地实现动态数组的功能，并且可以随意插入不同类型的对象，进行查找、插入和删除操作。这篇文章对于需要频繁进行查找、插入和删除操作的情况下，使用vector类是一个很好的选择。 ... [详细]

蜡笔小新 2023-12-13 14:14:39
数组
[大整数乘法] java代码实现

本文介绍了使用java代码实现大整数乘法的过程，同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率，并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]

蜡笔小新 2023-12-13 11:21:32
数组
Redis底层数据结构之压缩列表的介绍及实现原理

本文介绍了Redis底层数据结构之压缩列表的概念、实现原理以及使用场景。压缩列表是Redis为了节约内存而开发的一种顺序数据结构，由特殊编码的连续内存块组成。文章详细解释了压缩列表的构成和各个属性的含义，以及如何通过指针来计算表尾节点的地址。压缩列表适用于列表键和哈希键中只包含少量小整数值和短字符串的情况。通过使用压缩列表，可以有效减少内存占用，提升Redis的性能。 ... [详细]

蜡笔小新 2023-12-12 16:06:05
php
Day2列表、字典、集合操作详解

本文详细介绍了列表、字典、集合的操作方法，包括定义列表、访问列表元素、字符串操作、字典操作、集合操作、文件操作、字符编码与转码等内容。内容详实，适合初学者参考。 ... [详细]

蜡笔小新 2023-12-12 14:14:34
char
EPPlus绘制刻度线的方法及示例代码

本文介绍了使用EPPlus绘制刻度线的方法，并提供了示例代码。通过ExcelPackage类和List对象，可以实现在Excel中绘制刻度线的功能。具体的方法和示例代码在文章中进行了详细的介绍和演示。 ... [详细]

蜡笔小新 2023-12-10 19:32:38
数组
C++语言入门：数组的基本知识和应用领域

本文介绍了C++语言的基本知识和应用领域，包括C++语言与Python语言的区别、C++语言的结构化特点、关键字和控制语句的使用、运算符的种类和表达式的灵活性、各种数据类型的运算以及指针概念的引入。同时，还探讨了C++语言在代码效率方面的优势和与汇编语言的比较。对于想要学习C++语言的初学者来说，本文提供了一个简洁而全面的入门指南。 ... [详细]

蜡笔小新 2023-12-10 18:20:14
数组
猜字母游戏

猜字母游戏猜字母游戏——设计数据结构猜字母游戏——设计程序结构猜字母游戏——实现字母生成方法猜字母游戏——实现字母检测方法猜字母游戏——实现主方法1猜字母游戏——设计数据结构1.1 ... [详细]

蜡笔小新 2023-12-13 12:04:03
web
MooTools和JQuery并排 - MooTools and JQuery Side by Side

IjustinheritedsomewebpageswhichusesMooTools.IneverusedMooTools.NowIneedtoaddsomef ... [详细]

蜡笔小新 2023-12-12 13:43:58

向着成功一直努力的人

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

Tags | 热门标签

RankList | 热门文章