我想实现一个带关键字的自定义数据结构的类似队列的东西，用list还是map比较好？

如:
struct mylist{
  int key; //关键字，作为搜索的依据
  string a1;
  string a2;
  ...
};想实现这个数据结构的一个处理队列，实现如查询，入队，删除等
用list实现是不是效率太低？以删除关键字为6的结点为例，只能如下操作
list<mylist> q;
list<mylist>::iterator M1;
  for (M1=q.begin();  M1!=q.end(); ++M1) {
    if ((*M1).key==6)
    {
       q.erase(M1);
       break;
     }有人建议用map,如何实现？初学STL,谢谢！

解决方案 »

免费领取超大流量手机卡，每月29元包185G流量+100分钟通话, 中国电信官方发货

如果带关键字
用map比较合适，速度较快
C++ STL简介
作者：怒火之袍
一、STL简介
STL（Standard Template Library，标准模板库)是惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。现在虽说它主要出现在C++中，但在被引入C++之前该技术就已经存在了很长的一段时间。STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模版函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。在C++标准中，STL被组织为下面的13个头文件：<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>和<utility>。以下笔者就简单介绍一下STL各个部分的主要特点。二、算法
大家都能取得的一个共识是函数库对数据类型的选择对其可重用性起着至关重要的作用。举例来说，一个求方根的函数，在使用浮点数作为其参数类型的情况下的可重用性肯定比使用整型作为它的参数类性要高。而C++通过模板的机制允许推迟对某些类型的选择，直到真正想使用模板或者说对模板进行特化的时候，STL就利用了这一点提供了相当多的有用算法。它是在一个有效的框架中完成这些算法的——你可以将所有的类型划分为少数的几类，然后就可以在模版的参数中使用一种类型替换掉同一种类中的其他类型。STL提供了大约100个实现算法的模版函数，比如算法for_each将为指定序列中的每一个元素调用指定的函数，stable_sort以你所指定的规则对序列进行稳定性排序等等。这样一来，只要我们熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能并大大地提升效率。算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。<algorithm>是所有STL头文件中最大的一个（尽管它很好理解），它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。<functional>中则定义了一些模板类，用以声明函数对象。三、容器
在实际的开发过程中，数据结构本身的重要性不会逊于操作于数据结构的算法的重要性，当程序中存在着对时间要求很高的部分时，数据结构的选择就显得更加重要。经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所出入。STL容器就为我们提供了这样的方便，它允许我们重复利用已有的实现构造自己的特定类型下的数据结构，通过设置一些模版类，STL容器对最常用的数据结构提供了支持，这些模板的参数允许我们指定容器中元素的数据类型，可以将我们许多重复而乏味的工作简化。容器部分主要由头文件<vector>,<list>,<deque>,<set>,<map>,<stack>和<queue>组成。对于常用的一些容器和容器适配器（可以看作由其它容器实现的容器），可以通过下表总结一下它们和相应头文件的对应关系。----------------------------------------------------------------------------
|数据结构 |描述  |实现头文件|
----------------------------------------------------------------------------
|向量(vector)  |连续存储的元素  |vector    |
----------------------------------------------------------------------------
|列表(list)  |由节点组成的双向链表，每个结点包含着一个元素  |list      |
----------------------------------------------------------------------------
|双队列(deque)  |连续存储的指向不同元素的指针所组成的数组  |deque     |
----------------------------------------------------------------------------
|集合(set)  |由节点组成的红黑树，每个节点都包含着一个元素， |          |
| |节点之间以某种作用于元素对的谓词排列，没有两个 |          |
| |不同的元素能够拥有相同的次序  |set       |
----------------------------------------------------------------------------
|多重集合 | |          |
|(multiset)  |允许存在两个次序相等的元素的集合  |set       |  ----------------------------------------------------------------------------
|栈(stack)  |后进先出的值的排列  |stack     |
----------------------------------------------------------------------------
|队列(queue)  |先进先出的执的排列  |queue     |
----------------------------------------------------------------------------
|优先队列 |元素的次序是由作用于所存储的值对上的某种谓词 |          |
|(priority |决定的的一种队列 |queue     |
|_queue) | |          |
----------------------------------------------------------------------------
|映射(map)  |由{键，值}对组成的集合，以某种作用于键对上的 |          |
| |谓词排列  |map       |
----------------------------------------------------------------------------
|多重映射 | |          |
|(multimap)  |允许键对有相等的次序的映射  |map       |
----------------------------------------------------------------------------
四、迭代器
下面要说的迭代器从作用上来说是最基本的部分，可是理解起来比前两者都要费力一些（至少笔者是这样）。软件设计有一个基本原则，所有的问题都可以通过引进一个间接层来简化，这种简化在STL中就是用迭代器来完成的。概括来说，迭代器在STL中用来将算法和容器联系起来，起着一种黏和剂的作用。几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的迭代器，用以存取容器中的元素。迭代器部分主要由头文件<utility>,<iterator>和<memory>组成。<utility>是一个很小的头文件，它包括了贯穿使用在STL中的几个模板的声明，<iterator>中提供了迭代器使用的许多方法，而对于<memory>的描述则十分的困难，它以不同寻常的方式为容器中的元素分配存储空间，同时也为某些算法执行期间产生的临时对象提供机制,<memory>中的主要部分是模板类allocator，它负责产生所有容器中的默认分配器。五、对初学者学习STL的一点建议
对于之前不太了解STL的读者来说，上面的文字只是十分概括地描述了一下STL的框架，对您理解STL的机制乃至使用STL所起到的帮助微乎甚微，这不光是因为深入STL需要对C++的高级应用有比较全面的了解，更因为STL的三个部分算法、容器和迭代器三部分是互相牵制或者说是紧密结合的。从概念上讲最基础的部分是迭代器，可是直接学习迭代器会遇到许多抽象枯燥和繁琐的细节，然而不真正理解迭代器又是无法直接进入另两部分的学习的（至少对剖析源码来说是这样）。可以说，适应STL处理问题的方法是需要花费一定的时间的，但是以此为代价，STL取得了一种十分可贵的独立性，它通过迭代器能在尽可能少地知道某种数据结构的情况下完成对这一结构的运算，所以下决心钻研STL的朋友们千万不要被一时的困难击倒。其实STL运用的模式相对统一，只要适应了它，从一个STL工具到另一个工具，都不会有什么大的变化。对于STL的使用，也普遍存在着两种观点。第一种认为STL的最大作用在于充当经典的数据结构和算法教材，因为它的源代码涉及了许多具体实现方面的问题。第二种则认为STL的初衷乃是为了简化设计，避免重复劳动，提高编程效率，因此应该是“应用至上”的，对于源代码则不必深究。笔者则认为分析源代码和应用并不矛盾，通过分析源代码也能提高我们对其应用的理解，当然根据具体的目的也可以有不同的侧重。最后要说的是，STL是ANSI/ISO C++标准的一部分，所以对于一个可以有多种C++实现的过程，首先考虑的应该是STL提供的模板（高效且可移植性好），其次才是各个厂商各自相应的库（高效但可移植性不好）以及自己去编写代码（可移植性好但低效）。
Map的基本知识　　映射（Map），又称为字典（Dictionary），是由关键字（Key）及其对应的元素值（Value）所组成的元素单元（Element）的表单式集合。　　通常，对于Map而言，使用给定的Key，可以迅速地从单元集合中检索到相应的元素。因此，在需要对大量数据进行查找操作而查找的性能又占据重要地位的场合，Map无疑是一种较理想的容器。譬如，在MFC中，使用Map来实现HandleMaps（句柄映射），以及其他的一些内部数据结构。同时，MFC也提供了公共Map类。使用公共Map类，MFC程序员可以轻易地高效地根据自身的需求实现程序中自定义的映射。　　通常，当一个Map对象被删除时，或者，当其中的元素被移除时，关键字和元素值也将被完全删除。　　从数据结构的角度分析，有关Map的典型操作有：　　1、向Map中插入具有给定关键字的元素单元。　　2、在Map中查找具有给定关键字的元素单元。　　3、在Map中删除具有给定关键字的元素单元。　　4、枚举（遍历）Map中的所有元素单元。　　MFC中的各种Map实现，都提供了实现上述操作的成员函数。为了方便讨论，我们以CMap为代表，进行讲解。　　一旦你已经向Map中插入了一个关键字-元素值组合对(Key-Value pair)单元，就可以利用关键字访问Map，从而有效地检索、添加或者删除元素单元，也可以遍历Map中的所有单元。　　对MFC中的CMap等，除了关键字访问方法之外，还有另一种不同的类型--POSITION，也可以作为访问元素单元的辅助方式，可以使用一个POSITION来"记住"一个元素单元或者对Map进行枚举操作。你可能认为这种使用POSITION实现的遍历等同于使用关键字来进行的Map遍历，事实上并非如此，确切的说，两种检索的等价性是不确定的。　　MFC中的提供了基于模板的CMap类。利用CMap模板类，可以处理特定的数据类型，例如用户自定义的类或结构体等。同时，MFC也提供了基于指定数据类型的非模板类，其中包括：类名关键字类型  元素值类型
CMapWordToPtr WORDS Void pointers
CMapPtrToWord Void pointers WORDS
CMapPtrToPtr Void pointers Void pointers
CMapWordToOb WORDS Objects
CMapStringToOb Strings Objects
CMapStringToPtr Strings Void pointers
CMapStringToString Strings String
Map的工作原理　　使用Map的最大优势是它的快速查找的优秀性能，而取得最优性能的关键在于尽量使得在检索周期内所需进行的元素检查（比对）次数达到最少。顺序查找的性能是最差的，因为如果使用顺序查找算法在包含n个元素单元的Map中查找某个元素，可能（最坏情况下）需要进行n次独立的比较运算。　　二元查找（折中查找）的性能表现要稍好一些，可是，一个不容忽视的问题是--二元查找要求待查序列为有序排列，这无疑会降低Map自身的操作灵活性。在我们的理解中，所谓的最佳算法应当是不论元素单元数目的多少，也不论元素是以什么顺序进行排列，查找过程都无需任何额外的比对操作，而能够仅仅通过简单的计算方法，就可以直接指向最终的相应元素的快速、高效算法。这听起来有些玄乎，但事实上，这种算法的确是有可能实现的（而且，我相信，Map可以做得到）。　　在MFC的CMap及其相关的Map类中，只要对Map进行正确设置，Lookup函数通常能够一次到位的查找到任意元素，而很少需要进行两次或者三次以上的查找比对。　　那么，这种高效的查找是如何实现的呢？　　不失一般性，以MFC中的CMap模板类为例。在Map被创建之后（通常是恰恰在第一个元素被插入之前的瞬间），系统会为一个指向CAssoc结构体的指针数组的哈希表分配内存。MFC使用CAssoc结构体描述元素值和关键字的组合对。　　CAssoc结构体描述如下：struct CAssoc
　{
　　CAssoc* pNext;
　　UINT nHashValue;
　　CString key;
　　CString value;
　};
　　无论何时，只要有一个元素值-关键字单元被加入到Map中，就会随之创建一个新的CAssoc结构体，并根据单元中的关键字的实际值来计算出相应的哈希值。同时，拷贝一个指向CAssoc结构体的指针并将其插入到哈希表中索引值为i的位置中。其中，i的计算公式如下：　　i=nHashValue%nHushTableSize　　式中，nHashValue是由关键字Key的实际值计算出来的哈希值；nHashTableSize是哈希表中元素的数目（默认情况下，哈希表的大小为17）。　　如果在哈希表中的索引值为i的位置已经容纳了一个CAssoc指针，那么MFC将建立一个单独的CAssoc结构体的链表（List）,链表中的第一个CAssoc结构体的地址被存储到哈希表中，而将第二个CAssoc结构体的地址存储到前一个CAssoc结构体的pNext域，以此类推。下图展示了哈希表的一种可能实现情况，在该哈希表中，共有10个元素，其中5个元素地址分别唯一的存储，另外5个分别存储在长度为2和3的两个链表中。  　　调用一个Map的Lookup()函数时，MFC根据输入的关键字的实际值计算相应的哈希值，然后使用前面提到的公式将哈希值转换为索引值，并从哈希表中的相应位置检索CAssoc指针。　　理想情况下，该位置只包含一个CAssoc指针，而非CAssoc指针链表。如果事实情况真如同我们所期望的那样，单一地址对应单一CAssoc指针，那么，元素单元将能够被一次查找到位，并直接读出；如果从哈希表中检索到的是CAssoc链表的指针头地址，则MFC顺序比对链表元素CAssoc结构所包含的关键字，直至查找到正确结果。但是，正如我们先前所讨论的那样，只要正确设置Map，链表中的元素一般就不会超过三个，这就意味着，查找通常可以在三次元素比对操作之内完成。
嗯，楼上的已经说得很详细了。是用map比较好的。
struct mylist{
  stirng p1;
  string p2;
};map<const int,mylist> q;插入是用这样:
  mylist a;
  a.p1 = "3333";
  a.p2="cccc";
  q.insert(make_pair(222,a));查找并修改结点的p1,p2的值如何做呀
解决了查找和修改的问题：
  int p=222;
  map<const int,mylist>::iterator cur = q.find(p);
  if (cur!=q.end())
  {
    (*cur).second.p1="auleaf";
　｝谢谢！给分了