我目前有一个std::map<std::string,int>存储整数值到唯一字符串标识符,我确实查找字符串.它主要是我想要的,除了它不跟踪插入顺序.因此,当我迭代地图以打印出值时,它们将根据字符串进行排序; 但是我希望它们按照(第一次)插入的顺序排序.
我想过使用一个vector<pair<string,int>>替代,但我需要查找字符串并将整数值增加大约10,000,000次,所以我不知道是否std::vector会明显变慢.
有没有办法使用std::map或是否有std更适合我需要的容器？
[我在GCC 3.4上,我的价值可能不超过50对std::map].
谢谢.
是否有一个标准的swift类是一个Dictionary,但是像Java的LinkedHashMap那样将键保存在插入顺序中？如果没有,将如何实施？
ListJava中是否存在基于提供的维护顺序的现有实现Comparator？
可以通过以下方式使用的东西:
Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);
使得someT被插入,使得在列表中的顺序是根据保持cmp
(关于@andersoj的建议我正在完成我的问题,还有一个请求)
此外,我希望能够按排序顺序遍历列表而不删除元素,即:
T min = Const.SMALLEST_T;
for (T e: l) {
assertTrue(cmp.compare(min, e) >= 0);
min = e;
}
应该通过.
欢迎所有的建议(除了告诉我Collections.sort在无序的完整列表中使用),但是,我更喜欢某些内容java.*或最终,org.apache.*因为此时很难引入新的库.
注意:(UPDATE4)我意识到这种列表的实现性能不足.有两种一般方法:
没有1. CPU缓存未命中问题No 2.在数组中移位元素有问题.
UPDATE2:
TreeSet不起作用,因为它使用提供的比较器(MyComparator)来检查是否相等,并基于它假设元素相等并排除它们.我需要那个比较器只用于排序,而不是"唯一性"过滤(因为元素按其自然顺序不相等)
UPDATE3:
PriorityQueue不能正常工作List(因为我需要),因为没有办法按照"排序"的顺序遍历它,要按排序顺序获取元素,你必须从集合中删除它们.
更新:
让我们说我们正在处理密钥1-15.要获得常规BST的最差情况,您可以按升序或降序插入键,如下所示:
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
那么BST将基本上成为一个链表.
对于BST的最佳情况,您可以按以下顺序插入键,它们的排列方式使插入的下一个键是要插入的总范围的一半,因此第一个是15/2 = 8,然后是8/2 = 4等......
8,4,12,2,6,10,14,1,3,5,7,9,11,13,15
那么BST将是一个平衡良好的树,最佳高度为3.
对于红黑树的最佳情况也可以用BST的最佳情况构建.但是我们如何构建一棵红黑树的最坏情况呢？是否与BST的最坏情况相同？是否有特定的模式会产生最坏的情况？
我面临一个应用程序,我必须设计一个随机访问(或至少优于O(n))具有廉价(O(1))插入和删除的容器,并根据顺序存储数据(排名)插入时指定.
例如,如果我有以下数组:
[2, 9, 10, 3, 4, 6]
我可以调用索引2上的remove来删除10,我也可以通过插入13来调用索引1上的insert.
在我完成这两项操作之后:
[2, 13, 9, 3, 4, 6]
数字存储在一个序列中,插入/删除操作需要一个索引参数来指定应插入数字的位置或应删除的数字.
我的问题是,除了链接列表和向量之外,什么样的数据结构可以维护这样的东西？我倾向于优先考虑下一个可用索引的Heap.但我一直在看一些关于融合树有用的东西(但在理论意义上更多).
什么样的数据结构可以在保持内存消耗的同时为我提供最佳的运行时间？我一直在玩一个保留哈希表的插入顺序,但到目前为止它还没有成功.
我直接使用std :: vector折腾的原因是因为我必须根据这些基本操作构造一些预先形成向量的东西.容器的大小有可能增长到数十万个元素,因此承诺在std :: vector中进行转换是不可能的.带有链接列表的相同问题行(即使是双重链接),将其遍历给定索引将采用最坏情况O(n/2),其舍入为O(n).
我想到了一个包含Head,Tail和Middle指针的双倍链表,但我觉得它不会好多了.
这是我的插入排序,与"算法简介"一书中的方式完全相同:
def insertion_sort():
A = [5,2,4,6,1,3]
for j in range(1, len(A)):
print 'j:'+str(j)
key = A[j]
print 'key:'+str(key)
i=j-1
print 'i:'+str(i)
while i > 0 and A[i] > key:
A[i+1] = A[i]
i=i-1
print 'new i: '+str(i)
print 'swapping value: '+str(A[i]) + ' with value: '+str(A[i+1])
print ' '
A[i+1] = key
print A
这打印:
[5, 1, 2, 3, 4, 6]
如果让它们失灵,我做错了什么？
我使用C#已经有10多年了，但今天我发现Dictionary<string, int>保留了插入顺序？据我所知，Dictionary内部是使用哈希表实现的，所以内部排列应该没有特定的顺序，但是下面的测试代码似乎显示遍历时的顺序和插入的顺序是一模一样的？
const int N = 1000000;
List<string> ss = new List<string>();
Dictionary<string, int> dict = new Dictionary<string, int>();
for (int i = 0; i < N; ++i)
{
var s = string.Empty;
for (int j = 0; j < 15; ++j)
s += (char)('a' + UnityEngine.Random.Range(0, 26));
//ss.add(s);
ss.Add(new string(s));
//dict[s] = UnityEngine.Random.Range(0, 1024);
dict.Add(s, UnityEngine.Random.Range(0, 1024));
}
int same = 0;
var keys = dict.Keys.ToArray();
for (int i = 0; i < N; ++i) …