C++ Programmer's Cookbook

{C++ 基础} {C++ 高级} {C#界面,C++核心算法} {设计模式} {C#基础}

stl-什么时候用那种container?

Overview of Container Abilities
  Vector Deque List Set Multiset Map Multimap
Typical internal data structure Dynamic array Array of arrays Doubly linked list Binary tree Binary tree Binary tree Binary tree
Elements Value Value Value Value Value Key/value pair Key/value pair
Duplicates allowed Yes Yes Yes No Yes Not for the key Yes
Random access available Yes Yes No No No With key No
Iterator category Random access Random access Bidirectional Bidirectional (element constant) Bidirectional (element constant) Bidirectional (key constant) Bidirectional (key constant)
Search/find elements Slow Slow Very slow Fast Fast Fast for key Fast for key
Inserting/removing of elements is fast At the end At the beginning and the end Anywhere
Inserting/removing invalidates iterators, references, pointers On reallocation Always Never Never Never Never Never
Frees memory for removed elements Never Sometimes Always Always Always Always Always
Allows memory reservation Yes No
Transaction safe (success or no effect) Push/pop at the end Push/pop at the beginning and the end All except sort() and assignments All except multiple-element insertions All except multiple-element insertions All except multiple-element insertions All except multiple-element insertions


As a supplement to the table, the following rules of thumb might help:

  • By default, you should use a vector. It has the simplest internal data structure and provides random access. Thus, data access is convenient and flexible, and data processing is often fast enough.

  • If you insert and/or remove elements often at the beginning and the end of a sequence, you should use a deque. You should also use a deque if it is important that the amount of internal memory used by the container shrinks when elements are removed. Also, because a vector usually uses one block of memory for its elements, a deque might be able to contain more elements because it uses several blocks.

  • If you insert, remove, and move elements often in the middle of a container, consider using a list. Lists provide special member functions to move elements from one container to another in constant time. Note, however, that because a list provides no random access, you might suffer significant performance penalties on access to elements inside the list if you only have the beginning of the list.

    Like all node-based containers, a list doesn't invalidate iterators that refer to elements, as long as those elements are part of the container. Vectors invalidate all of their iterators, pointers, and references whenever they exceed their capacity, and part of their iterators, pointers, and references on insertions and deletions. Deques invalidate iterators, pointers, and references when they change their size, respectively.

  • If you need a container that handles exceptions in a way that each operation either succeeds or has no effect, you should use either a list (without calling assignment operations and sort() and, if comparing the elements may throw, without calling merge (), remove(), remove_if(), and unique(); see page 172) or an associative container (without calling the multiple-element insert operations and, if copying/assigning the comparison criterion may throw, without calling swap()). See Section 5.11.2, for a general discussion of exception handling in the STL and Section 6.10.10, for a table of all container operations with special guarantees in face of exceptions.

  • If you often need to search for elements according to a certain criterion, use a set or a multiset that sorts elements according to this sorting criterion. Keep in mind that the logarithmic complexity involved in sorting 1,000 elements is in principle ten times better than that with linear complexity. In this case, the typical advantages of binary trees apply.

    A hash table commonly provides five to ten times faster lookup than a binary tree. So if a hash container is available, you might consider using it even though hash tables are not standardized. However, hash containers have no ordering, so if you need to rely on element order they're no good. Because they are not part of the C++ standard library, you should have the source code to stay portable.

  • To process key/value pairs, use a map or a multimap (or the hash version, if available).

  • If you need an associative array, use a map.

  • If you need a dictionary, use a multimap.

posted on 2005-12-14 09:02 梦在天涯 阅读(1359) 评论(1)  编辑 收藏 引用 所属分类: STL/Boost

评论

# re: stl-什么时候用那种container? 2005-12-14 11:34 力为

Effective STL Item One is also helpful.  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


公告

EMail:itech001#126.com

导航

统计

  • 随笔 - 461
  • 文章 - 4
  • 评论 - 746
  • 引用 - 0

常用链接

随笔分类

随笔档案

收藏夹

Blogs

c#(csharp)

C++(cpp)

Enlish

Forums(bbs)

My self

Often go

Useful Webs

Xml/Uml/html

搜索

  •  

积分与排名

  • 积分 - 1661895
  • 排名 - 5

最新评论

阅读排行榜