迈耶斯偏爱地图上的矢量 [英] Meyers's preference for vectors over maps

问题描述

您好，


我正在查看Meyers的有效STL，项目23

关于在矢量和地图之间进行选择（至少

那个选择对我而言）。在许多情况下，使用

排序向量对于查找来说更快。两个

的原因是（1）矢量元素较小，

因为地图元素需要至少3个指针，并且

（2）内存中矢量元素的连续性确保

更少的页面错误。


对我来说，我将是一个容积很大的物品

比指针大，所以理由（1）不适用。


理由（2）是我想要更好地理解的。

让我来描述一下我的应用程序。


在我的情况下，我将在容器中有N个项目，

将查找n（n< N）个项目，做一些处理，

然后用处理中的n个新项目替换容器中的n个最差项目

。在这里，更糟糕

由排序功能定义。问题

是n可以在1到N之间变化，这使得向量与地图的优势相比非常不清楚。对于小n，

地图更好，因为我基本上穿插了

1修改数据库，1次查找。

对于大n ，矢量更好，因为它比同时对一大堆物体进行排序更快，而不是以零碎的方式构建地图。


由于我无法从那条

推理中获得明确的答案，我更仔细地看了Meyers的

原因（ 2）。我将使用二进制搜索进行

查找，并且他声称元素的连续性特别适用于二进制搜索。更多

具体来说，我理解他的意思是

内存中元素的接近度应该匹配

遍历中元素的接近度>
容器元素。但是，我理解二元搜索的
是它不按顺序遍历元素b $ b元素。那么为什么

元素中元素的连续性具有任何

优势？


感谢您的澄清。如果有任何

的其他注意事项可以让它更容易决定一个合适的容器，我会很感激

那些。现在，我很想去找一个

的矢量因为我以前没用过地图。但是因为这个原因，我还认为这也是一个不错的理由，因为它也涉及地图。


Fred

-

Fred Ma

卡尔顿大学电子学系

1125上校按驱动器，渥太华，安大略省

加拿大，K1S 5B6

解决方案

弗雷德·马说：
在我的情况下，我将在容器中有N个项目，
将查找n（n< N）项目，进行一些处理，
然后替换容器中的n个最差项目
来自处理的n个新项目。这里，更糟糕的是由排序功能定义。问题是，n可以在1到N之间变化，使得矢量与地图的优势非常不清楚。对于小n，
地图更好，因为我基本上穿插了1次数据库修改1次查找。
对于大n，矢量更好，因为它更快
一次性排序一大堆对象而不是以零碎的方式构建地图。

这看起来像是一个很好的候选用户优先级队列。

从向量和地图中删除项目的速度很慢，因为你需要

a排序标准，所以正常的双端队列是不够的。


-

要获得我真正的电子邮件地址，请删除两个onkas

-

Dipl.-通知。亨德里克Belitz

电子的中央研究所

研究中心于利希

亨德里克Belitz写道：
Fred Ma写道：

在我的情况下，我将在容器中有N个项目，
将查找n（n< N）个项目，做一些处理，然后用处理过的n个新项目替换容器中最差的n个项目。这里，更糟糕的是由排序功能定义。问题是，n可以在1到N之间变化，使得矢量与地图的优势非常不清楚。对于小n，
地图更好，因为我基本上穿插了1次数据库修改1次查找。
对于大n，矢量更好，因为它更快
一次性排序一大堆对象而不是以零碎的方式构建地图。

这看起来像是使用优先级队列的一个很好的候选者。
从向量和地图中删除项目的速度很慢，因为你需要一个排序标准，一般的双端队列就不够了。

你好，Hendrik ，


我在Josuttis的The C ++

标准库中查找了优先级队列。它建立在标准的

迭代器支持容器之上，其向量为

默认值。难道我还没有面对比较

向量和地图之间的问题我的用法？我的

印象是特殊的容器适配器

简化了界面而不是改变数据存储和检索的基础机制。

不可否认，这可能是我的错误印象。


Fred

Fred Ma写道：

Hendrik，

我在Josuttis的The C ++
标准库中查找了优先级队列。它建立在标准的支持iterator的容器之上，将vector作为默认值。难道我还不会面对我使用的矢量和地图之间的问题的比较吗？我的印象是，特殊的容器适配器简化了界面，而不是改变数据存储和检索的基础机制。
不可否认，这可能是我的错误印象。

嗯，我甚至没有认识到优先级队列可用作

STL适配器。通常优先级队列由斐波那契堆实现

并且非常有效。也许你应该寻找一些实现，

这样做而不是使用stl容器/适配器。


-

要获取我真实的电子邮件地址，请删除两个onkas

-

Dipl.-Inform。 Hendrik Belitz

中央电子学院

研究中心Juelich

Hello,

I was looking at Meyers''s "Effective STL", item 23
about choosing between vectors and maps (at least
that the choice for me). In many cases, using
sorted vectors is faster for lookups. The two
reasons are (1) that vector elements are smaller,
since map elements need at least 3 pointers, and
(2) contiguity of vector elements in memory ensure
fewer page faults.

For me, I will a container of objects that are much
bigger than pointers, so reason (1) doesn''t apply.

Reason (2) is what I''m trying to understand better.
Let me describe my application.

In my case, I will have N items in the container,
will look up n (n<N) items, do some processing,
then replace the n worst items in the container
with the n new items from processing. Here, worse
is defined by the sorting function. The problem
is that n can vary from 1 to N, making the advantages
of vector vs. map very unclear. For small n,
map is better because I''m basically interspersing
1 modification of the database with 1 lookup.
For large n, vector is better because it''s faster
to sort a whole bunch of objects at once rather
than building a map in a piecemeal fashion.

Since I can''t get a clear answer from that line of
reasoning, I looked more carefully at Meyers''s
reason (2). I will be using binary search for
lookup, and he claims that contiguity of elements
is good for binary search in particular. More
specifically, I understood him as meaning that
closeness of elements in memory should match
closeness of elements in the traversal of
container elements. However, my understanding
of binary search is that it doesn''t traverse
elements in sequential order. So why the
contiguity of elements in a vector be of any
advantage?

Thanks for clarifying. And if there are any
other considerations that would make it easier
to decide upon a proper container, I''d appreciate
those too. Right now, I''m tempted to go for a
vector because I haven''t used a map before. But
for that reason, I''m also thinking it''s not a bad
reason to dabble in maps, too.

Fred
--
Fred Ma
Dept. of Electronics, Carleton University
1125 Colonel By Drive, Ottawa, Ontario
Canada, K1S 5B6

解决方案

Fred Ma wrote:

In my case, I will have N items in the container,
will look up n (n<N) items, do some processing,
then replace the n worst items in the container
with the n new items from processing. Here, worse
is defined by the sorting function. The problem
is that n can vary from 1 to N, making the advantages
of vector vs. map very unclear. For small n,
map is better because I''m basically interspersing
1 modification of the database with 1 lookup.
For large n, vector is better because it''s faster
to sort a whole bunch of objects at once rather
than building a map in a piecemeal fashion.

That looks like a good candidate for usage of a priority queue.
Removing items from both a vector and a map is slow, and since you need
a sorting criteria, a normal deque will not suffice.

--
To get my real email adress, remove the two onkas
--
Dipl.-Inform. Hendrik Belitz
Central Institute of Electronics
Research Center Juelich

Hendrik Belitz wrote:

Fred Ma wrote:

In my case, I will have N items in the container,
will look up n (n<N) items, do some processing,
then replace the n worst items in the container
with the n new items from processing. Here, worse
is defined by the sorting function. The problem
is that n can vary from 1 to N, making the advantages
of vector vs. map very unclear. For small n,
map is better because I''m basically interspersing
1 modification of the database with 1 lookup.
For large n, vector is better because it''s faster
to sort a whole bunch of objects at once rather
than building a map in a piecemeal fashion.

That looks like a good candidate for usage of a priority queue.
Removing items from both a vector and a map is slow, and since you need
a sorting criteria, a normal deque will not suffice.

Hi, Hendrik,

I looked up priority queues in Josuttis''s "The C++
Standard Library". It''s built on top of the standard
iterator-supporting containers, with the vector as a
default. Wouldn''t I still be faced with the comparison
of issues between vectors and maps for my usage? My
impression is that the special container adapters
simplify the interface rather than changing the
underlying mechanism of data storage and retrieval.
Admittedly, this could be a misimpression on my part.

Fred

Fred Ma wrote:

Hi, Hendrik,

I looked up priority queues in Josuttis''s "The C++
Standard Library". It''s built on top of the standard
iterator-supporting containers, with the vector as a
default. Wouldn''t I still be faced with the comparison
of issues between vectors and maps for my usage? My
impression is that the special container adapters
simplify the interface rather than changing the
underlying mechanism of data storage and retrieval.
Admittedly, this could be a misimpression on my part.

Uh well, I didn''t even recognized that priority queues are available as an
STL adapter. Normally priority queues are implemented by fibonacci heaps
and are very efficient. Maybe you should look for some implementation which
does it that way instead of using a stl container/adapter.

--
To get my real email adress, remove the two onkas
--
Dipl.-Inform. Hendrik Belitz
Central Institute of Electronics
Research Center Juelich

这篇关于迈耶斯偏爱地图上的矢量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！