C++ 有没有结合了数组和链表优点的容器?

发布网友发布时间：2022-04-29 04:22

共4个回答

热心网友时间：2023-10-11 05:52

C++语言中可以用数组处理一组数据类型相同的数据，但不允许动态定义数组的大小，即在使用数组之前必须确定数组的大小。而在实际应用中，用户使用数组之前有时无法准确确定数组的大小，只能将数组定义成足够大小，这样数组中有些空间可能不被使用，从而造成内存空间的浪费。
链表是一种常见的数据组织形式，它采用动态分配内存的形式实现。需要时可以用new分配内存空间，不需要时用delete将已分配的空间释放，不会造成内存空间的浪费。
A 从逻辑结构来看
A-1. 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。
A-2. 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）
B 从内存存储来看
B-1. (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小
B-2. 链表从堆中分配空间, 自由度大但是申请管理比较麻烦.

热心网友时间：2023-10-11 05:52

没有。C++的所有容器没有一样能达到这个效果:
A. Sequence Container
- basic_string
- vector
- list
- forward_list( since 11)
- deque
- array
B. associative container
- map/multimap
- set/multiset
- unordered_map/unordered_multimap( since 11)
- set同上。
其他都不叫容器，包括你可能以为是容器的stack queue any等等。
你要的容器很显然就只能是map。但是正如你所说，它的下标无法做到邻接，因为维护一次邻接需要的复杂度达到nlogn级别。
但是这样的要求真的无法实现吗？不。有一种叫做order statistic tree(名次树)的数据结构能够达到这个要求，它维护键的排名，从而可以以logn级别时间查询到第k大键所在位置，这样，如果你的键是浮点数，那么你就可以达到利用浮点数的数量多这一优点几乎完美(甚至可以认为是完美)地实现你的目的。
gcc拓展pbds(policy-based data structure)中有名次树的红黑树实现，可以使用。
最后作为题外话提醒你一下渐进记号的使用。O(f(n))本身就代表上界，没有T(n)<=O(f(n))这种说法。当然对于渐进记号的讨论超出了这个问题。详见算法导论。追问是不是把operator[x]转化成求平衡树中第x大的数（key），这个key对应的值就是要求的值。
如何求平衡树第k大数啊
名次树网上的资料太少了，只能查到它能求第k大的数
好吧现在明白了
谢谢

热心网友时间：2023-10-11 05:52

你确定平衡树不好用？

#include <map>
using namespace std;

int main() {
map<int, int> s;
s[5] = 1;
s[6] = 2;
s[7] = 3;
s.erase(6); //删除元素
return 0;
}

热心网友时间：2023-10-11 05:53

没有这样的现成东西

热心网友时间：2023-10-11 05:52

热心网友时间：2023-10-11 05:53

你确定平衡树不好用？

#include <map>
using namespace std;

int main() {
map<int, int> s;
s[5] = 1;
s[6] = 2;
s[7] = 3;
s.erase(6); //删除元素
return 0;
}

热心网友时间：2023-10-11 05:53

没有这样的现成东西