STL：地图与矢量 [英] STL: map vs vector
问题描述
这是此主题的后续行动：
http://groups.google.com/group/comp....2cab752779f1fa
我一直在咀嚼这个问题。当我遇到上面的
线程时，我想其他成员可能会更好地了解
如何处理这个问题。
我正在尝试决定使用哪一张地图或向量来使用
。我正在尝试提出一种设计，让我能够在排序的列表中快速执行插入和删除（没有重复）。然后
查找每25个左右的元素（然后依次迭代
接下来的25个值，所以顺序查找）。索引查找比插入和删除稍微更频繁地发生
，因此它使得查找效率更高。因为插入和删除也经常发生，所以快速/有效的查找也很有用。记忆
不像速度那么大。
我已经环顾四周了，所以如果这是一直有的话/>
之前讨论过，请告诉我。
现在我有2个解决方案。
一个是一个有序的向量，我用''lower_bound''来得到我应该的位置
插入值并将其插入那里，然后用它来找到值
删除。查找只是正常的查找（通过
my_vector.begin（）+ indexSubscript）。大多数插入和删除都来自列表中心
，所以每当插入或删除时，
我猜测所有元素都被复制或者下。值
是用户定义的对象，因此需要进行大量的复制调用。
另一种设计使用地图和矢量。地图包含实际的
排序值。向量是每个第25个键的索引，每次插入和删除时都会重置
（从
映射中最近的前一个键开始）。要访问第25个* x值，您将获得索引中的
对应键并在地图中找到它，然后依次迭代
。
实现这两个之后，对我来说性能差异真的很小，但是我不确定我是否错过了一个更好的做法。 />
这个。我猜这是人们经常遇到的事情。我是一个新的C ++ / STL用户，所以我可能会错过一个好的数据
结构使用或更好地解决这个问题。任何帮助都会被赞赏。
非常感谢。
-Z
Hi,
This is a follow-up of sort of this thread:
http://groups.google.com/group/comp....2cab752779f1fa
I''ve been chewing on this problem for a while. When I came across the
above thread, I figured that maybe other members have a better idea on
how to approach this.
I''m currently trying to decide between which one of maps or vectors to
use. I''m trying to come up with a design that will let me perform fast
insertions and deletions (w/o duplicates) in a sorted "list" and then
look up every 25th or so element (and then iterate sequentially for the
next 25 values , so sequential look up). The indexed lookup happens
slightly more frequently than insertions and deletions, so it makes
sense to make lookup efficient. Because the insertions and deletions
also happen often, fast/efficient lookups are helpful as well. Memory
isnt as much of an issue as speed is.
I''ve looked around a bit, so if this is something that has been
discussed before, please let me know.
Right now I have 2 "solutions".
One is a sorted vector, where I use ''lower_bound'' to get where I should
insert the value and insert it there, and use it to find the value to
remove. Lookups are just normal lookups (thru
my_vector.begin()+indexSubscript ). Most inserts and removals are from
the center of the list, so whenever there is an insertion or removal,
I''m guessing that all the elements are copied up or down. The values
are user defined objects so thats a lot of copying calls.
The other design uses a map and a vector. The map contains the actual
sorted values. The vector is an index to every 25th key which is reset
at every insertion and removal (from the closest previous key in the
map onwards). To access the 25th*x value, you would get the
corresponding key in the index and find it in the map, and then iterate
sequentially.
After implementing both of these, the performance difference is really
minimal for me, but I''m not sure if I''m missing a better way of doing
this. I''m guessing this is something that people have come across
often. I''m a new C++/STL user, so I might be missing a good data
structure to use or a better solution to this problem. Any help would
be appreciated.
Thanks much.
-Z
推荐答案
我建议一张地图通常是一个更好的主意，因为你打算经常进行插入和删除操作。我的理由是，
向量通常被实现为已分配的数组，而地图通常是作为红黑树实现的.b $ b。如果经常需要插入和删除
，那么红黑树的速度会更快，而不会显着降低搜索或跨越的速度。插入
和数组中的删除速度要慢得多。
JB
I''d suggest a map is generally a better idea as you intend often doing
insertion and deletion operations. My justification for this is that a
vector is generally implemented as an allocated array and a map is
generally implemented as a Red Black Tree. If insertion and deletions
are often required then the Red Black Tree will be faster without a
significant lose of speed for searching or spanning. Whereas insertion
and deletions in an array are significantly slower.
JB
我可能是错过了显而易见的，但由于你正在考虑
map和a * vector *之间，看起来std :: set可能比
map更好。但是同样的基本问题仍然存在。
索引是一个问题，你可以做的是你有索引
只有指针的向量 - 存储的对象集合。您可以尝试对索引服务进行惰性
评估：使用
对对象的地址进行排序，当第一个索引查询到达时，对象的地址作为谓词/>
你的更高级别的容器（包装）。
你遇到了一个很好的问题：排序，快速插入和删除 - 和 -
线性索引到容器中。索引绝对建议你想要类似于矢量的存储。如果您存储的对象存储起来很复杂，那么这是一个很大的问题。指针的复制成本更低，因此
将减少开销。这是我对
建议的合理化。
在理想解决方案不明显的情况下哪种方法最有效
取决于使用模式的程度。从我的帖子（我没有按照前一个帖子的链接）对我来说并不是很明显。
重要：懒惰的评价在这里是非常重要的，你*想*要
有一个标志，指示指针向量何时没有排序。当然，
仍然是b $ b，做随机的从向量中删除将花费一捆。这是非常丑陋的b $ b ..如果可能的话，我会尝试调整客户端代码，而不是要求b / b
需要索引到容器中（最有可能是非常实用的） />
但只是一个想法..） - 注意 - 删除不会使订单无效，
只插入。我推迟排序直到查询，然后
你可以使用琐碎的std :: sort
I might be missing the obvious, but since you are considering between
map and a *vector*, it looks like std::set might do the job better than
map. The same fundamental problem would still persist, though.
The indexing is a problem, what you could do is that you have indexing
vector with only pointers-to-objects-in-set stored. You could try lazy
evaluation for the indexing "service": sort the indexing vector using
the object''s address as predicate when first indexing query comes to
your higher level container (wrapper).
You got a nice problem there: sorting, fast insertion and removal -and-
linear indexing into the container. The indexing absolutely suggests
that you want vector-like storage. This is a big no if the objects you
are storing are expensive to copy. Pointers are cheaper to copy so that
will reduce the overhead. That''s the rationalization I have for the
suggestion.
What works best in situation where ideal solution is not obvious
depends to a degree on the usage pattern. It''s not obvious to me from
your post (I didn''t follow the link to previous thread).
Important: the lazy evaluation is highly important here, you *want* to
have a flag indicating when the pointer vector is not sorted. Ofcourse,
still, doing "random" removals from a vector will cost a bundle. It''s
really ugly.. if possible I''d try to adjust the client code to not
require indexing into the container (most probably highly inpractical
but just a thought..) -- note -- removal won''t invalidate the order,
only insertion. I''d postpone the sorting until a query is made, then
you can use trivial std::sort
你好，
我认为一套和地图之间没有真正的区别，所以
至少我能够映射到地图中的键对我来说可能更容易。
我对指向对象的指针感到有些困惑。如果我添加一个新的
对象或从set / map中删除一个对象..是指针
无效吗？
关于使用，我可以说的一点是阅读是周期性的。所以说，每隔30毫秒，你需要从列表中读取25个对象的块。你只需要
读取块中的东西，这样你就可以阅读前25个元素..然后
其他地方你可能会阅读75-100个元素。
由于查询是经常进行的，我不确定懒惰的评价是多么有用，或者我对此感到困惑。
谢谢！
Mehwish
persenaama写道：
Hi,
I figured there was no real difference between a set and a map, so at
least I''ll be able to map to keys in map, which might be easier for me.
I was a little confused about pointers to objects. If I add a new
object or remove an object from the set/map .. is the pointer
invalidated?
One thing I can say about usage is that reading is periodic. So say,
every 30 ms, you read chunks of 25 objects from the "list". You only
read things in chunks so you read the 1st 25 elements .. and then
somewhere else you might read 75-100th elements.
Since querying is performed so often, I''m not sure how helpful lazy
evaluation will be though, or maybe I''m confused about this.
Thanks!
Mehwish
persenaama wrote:
我可能会错过明显的，但是既然你正在考虑
map和a * vector *之间，看起来std :: set可能比
map更好。但是同样的基本问题仍然存在。
索引是一个问题，你可以做的是你有索引
向量只有指向对象的指针存储。您可以尝试对索引服务进行惰性评估：当第一个索引查询到达您的更高级别容器（包装器）时，使用对象的地址作为谓词对索引向量进行排序你有一个很好的问题：分类，快速插入和删除 - 以及 -
线性索引到容器中。索引绝对表明你想要类似矢量的存储。如果您要存储的对象复制起来很昂贵，这是一个很大的问题。指针的复制成本更低，这样可以减少开销。这就是我对
建议的合理化。
在理想解决方案不明显的情况下最有效的方法
取决于使用模式的程度。
你的帖子对我来说并不明显（我没有按照上一个帖子的链接）。
重要的是：懒惰的评价在这里非常重要，你想* *
有一个标志，指示指针向量何时未排序。当然，
仍然在做随机。从向量中删除将花费一捆。它真的很丑......如果可能的话，我会尝试调整客户端代码，以免需要索引到容器中（最有可能是非常实用的
但只是想一想...... ） - 注意 - 删除不会使订单无效，只能插入。我推迟排序直到查询，然后
你可以使用琐碎的std :: sort
I might be missing the obvious, but since you are considering between
map and a *vector*, it looks like std::set might do the job better than
map. The same fundamental problem would still persist, though.
The indexing is a problem, what you could do is that you have indexing
vector with only pointers-to-objects-in-set stored. You could try lazy
evaluation for the indexing "service": sort the indexing vector using
the object''s address as predicate when first indexing query comes to
your higher level container (wrapper).
You got a nice problem there: sorting, fast insertion and removal -and-
linear indexing into the container. The indexing absolutely suggests
that you want vector-like storage. This is a big no if the objects you
are storing are expensive to copy. Pointers are cheaper to copy so that
will reduce the overhead. That''s the rationalization I have for the
suggestion.
What works best in situation where ideal solution is not obvious
depends to a degree on the usage pattern. It''s not obvious to me from
your post (I didn''t follow the link to previous thread).
Important: the lazy evaluation is highly important here, you *want* to
have a flag indicating when the pointer vector is not sorted. Ofcourse,
still, doing "random" removals from a vector will cost a bundle. It''s
really ugly.. if possible I''d try to adjust the client code to not
require indexing into the container (most probably highly inpractical
but just a thought..) -- note -- removal won''t invalidate the order,
only insertion. I''d postpone the sorting until a query is made, then
you can use trivial std::sort
这篇关于STL：地图与矢量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
