前言

有一段时间未使用c#/c++，因此写个合集用来回忆常用容器，也方便以后复习记忆

C#常见容器

Array 【数组】

简单的数组集合
特点：内存中连续存储，索引快，赋值修改也快。
缺点：需要事先声明数组长度，插值复杂。

String[] array = new String[5];
array[0] = '1';

ArrayList 【数组列表】

特点：

• 无需像Array需要初始长度，可以动态增加。
• 底层是Array，但继承了List接口
• 可以存储不同类型数据，所有元素视为object，也因此会出现类型不匹配，即不是类型安全。在拆箱操作时，性能消耗大。

ArrayList Alist = new Arraylist();
Alist.add('there')
Alist.add(2333)

List< T > 泛型

可以自定义list中元素的结构

public class TeamMate
{
    public string name;
    public int age;
    public int groupNum;

    public override string ToString()
    {
        return "name=" + name + ",age=" + age + ",groupNum=" + groupNum;
    }
}
static void Main(string[] args)
{
    List<TeamMate> list = new List<TeamMate>();
    list.Add(new TeamMate { name = "Tom", age = 20, groupNum = 12 });
    list.Add(new TeamMate { name = "Jerry", age = 22, groupNum = 13 });
    foreach(Person p in list)
    {
        Console.WriteLine(p.ToString());
    }
}

LinkedList< T > 【双向链表】

LinkedList< T >集合类没有非泛型类的版本，相当于C++中的list，内部实现是双链表

优点：如果要插入一个元素到链表的中间位置，会非常的快，
原因：如果插入，只需要修改上一个元素的Next与下一个元素的Previous的引用则可。而像ArrayList数组列表中，如果插入，需要移动其后的所有元素。
缺点：链表只能是一个接着一个的访问，这样就要用较长的时间来查找定位位于链表中间的元素。

因此从时间复杂度上，要在第K个位置插入一个元素，无论是ArrayList还是LinkedList的时间复杂度都为O(n)+O(1)=O(n)
其中数组列表查找时间为O(1),但由于要将后续元素向后移动，则插入时间为O(n)；
而链表查找时间为O(n)，但插入时间为O（1）。

将 List.Add方法和LinkedList的Add方法相比较，真正的性能差别不在于Add操作，而在LinkedList在给GC（垃圾回收机制）的压力上。一个List本质上是将其数据保存在一个堆栈的数组上，而LinkedList是将其所有节点保存在一系列堆栈上。这就使得GC需要更多地管理堆栈上LinkedList的节点对象。

LinkedListNode被LinkedList类包含，用LinkedListNode类，可以获得元素的上一个与下一个元素的引用。

LinkedList<int> list = new LinkedList<int>();
list.AddFirst(2);
list.AddFirst(1);
list.AddLast(4);
list.AddLast(5);

此时链表结构为：1 2 4 5

LinkedListNode<int> NewList = list.Find(4); //4节点的位置
list.AddBefore(NewList, 3); //在4前增加3

此时链表结构为：1 2 3 4 5

HashTable【哈希表】

哈希表是通过key-value形式来存取数据的，相同存储形式的还有字典Dictionary，由于存储对象都是object，因而可以满足任意形式的键值对，但也因此有装箱和拆箱的性能消耗。

特点：当前HashTable中的被占用空间达到一个百分比的时候就将该空间自动扩容，在.net中这个百分比是72%,也叫.net中HashTable的填充因子为0.72。

构造哈希表

Hashtable table = new Hashtable();
table.Add("Name", "Tom");
table.Add("Age", 20);

遍历哈希表

Hashtable table = new Hashtable();
table.Add("Name", "Tom");
table.Add("Age", 20);
foreach(DictionaryEntry entry in table)
{
    Console.Write(entry.Key + ":");
    Console.WriteLine(entry.Value);
}

Dictionary< T >【字典】（HashTable的泛型）

相当于C++中的map。只不过map的内部实现是红黑树，Dictionary的内部实现是哈希表，是类型安全的容器。在单线程的时候使用Dictionary更好，多线程的时候使用HashTable更好。

class Person
{
    public string name;
    public int age;

    public override string ToString()
    {
        return "name=" + name + ",age=" + age;
    }
}
class Program
{
    static void Main(string[] args)
    {
        Dictionary<string, Person> dictionary = new Dictionary<string, Person>();
        Person person1 = new Person() { name = "Tom", age = 20 };
        Person person2 = new Person() { name = "Jerry", age = 21};
        dictionary.Add("学生1", person1);
        dictionary.Add("学生2", person2);
        foreach(KeyValuePair<string, Person> pair in dictionary)
        {
            Console.Write(pair.Key + "：");
            Console.WriteLine(pair.Value.ToString());
        }
    }
}

//只取Key值
foreach (string key in dictionary.Keys)
{
    Console.WriteLine(key);
}

//只取value

foreach (Person person in dictionary.Values)
{
    Console.WriteLine(person);
}

HashSet< T >

特点：

• 一组不包含重复元素的集合
• 用O(n)的space来换取O(n)的时间，也就是查找元素的时间是O(1)

HashSet<string> set = new HashSet<string>();
set.Add("Tom");
set.Add("Jerry");
set.Add("Tom");
foreach(var n in set)
{
    Console.WriteLine(n);
}

上述集合元素中Tom有2个，是重复值，那么输出HashSet结果就只显示一个，这就是不显示重复值的功能。

Queue【队列】

特点：先进先出的对象集合
当需要对各项进行先进先出的访问时，则使用队列。当在列表中添加一项，称为入队，当从列表中移除一项时，称为出队。

Queue q = new Queue();
//入队操作
q.Enqueue("A");
q.Enqueue("B");
q.Enqueue("C");

//出队操作
q.Dequeue()

Queue< T >【泛型队列】

class Person
{
    public string name;
    public int age;
    public override string ToString()
    {
        return "name=" + name + ",age=" + age;
    }
}

class Program
{
    static void Main(string[] args)
    {
        Person person1 = new Person() { name = "Tom", age = 20};
        Person person2 = new Person() { name = "Jerry", age = 20 };
        Queue<Person> q = new Queue<Person>();
        q.Enqueue(person1);
        q.Enqueue(person2);

        Console.WriteLine(q.Dequeue());
    }
}

Stack【栈】

特点：后进先出的对象集合。
当需要对各项进行后进先出的访问时，则使用栈。当在列表中添加一项，称为推入元素，当从列表中移除一项时，称为弹出元素。

Stack st = new Stack();

//入栈
st.Push("A");
st.Push("B");
//出栈
st.Pop()

C++常见容器

转载

C++ STL的实现：
1.vector 底层数据结构为数组，支持快速随机访问

2.list 底层数据结构为双向链表，支持快速增删

3.deque 底层数据结构为一个中央控制器和多个缓冲区，支持首尾（中间不能）快速增删，也支持随机访问
注：deque是一个双端队列(double-ended queue)，也是在堆中保存内容的.它的保存形式如下:
[堆1] --> [堆2] -->[堆3] --> ...
每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品
4.stack 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时

5.queue 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
（stack和queue其实是适配器,而不叫容器，因为是对容器的再封装）

6.priority_queue 的底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现

7.set 底层数据结构为红黑树，有序，不重复

8.multiset 底层数据结构为红黑树，有序，可重复

9.map 底层数据结构为红黑树，有序，不重复

10.multimap 底层数据结构为红黑树，有序，可重复

11.hash_set 底层数据结构为hash表，无序，不重复

12.hash_multiset 底层数据结构为hash表，无序，可重复

13.hash_map 底层数据结构为hash表，无序，不重复

14.hash_multimap 底层数据结构为hash表，无序，可重复

stl容器区别: vector list deque set map-底层实现

在STL中基本容器有: vector、list、deque、set、map

set 和map都是无序的保存元素,只能通过它提供的接口对里面的元素进行访问

set:集合, 用来判断某一个元素是不是在一个组里面,使用的比较少
map:映射,相当于字典,把一个值映射成另一个值,如果想创建字典的话使用它好了
底层采用的是树型结构,多数使用平衡二叉树实现,查找某一值是常数时间,遍历起来效果也不错, 只是每次插入值的时候,会重新构成底层的平衡二叉树,效率有一定影响.

vector、list、deque是有序容器

1.vector

vector就是动态数组.它也是在堆中分配内存,元素连续存放,有保留内存,如果减少大小后，内存也不会释放.如果新值>当前大小时才会再分配内存.

它拥有一段连续的内存空间，并且起始地址不变，因此它能非常好的支持随即存取，即[]操作符，但由于它的内存空间是连续的，所以在中间进行插入和删除会造成内存块的拷贝，另外，当该数组后的内存空间不够时，需要重新申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。

对最后元素操作最快(在后面添加删除最快), 此时一般不需要移动内存,只有保留内存不够时才需要

对中间和开始处进行添加删除元素操作需要移动内存,如果你的元素是结构或是类,那么移动的同时还会进行构造和析构操作，所以性能不高 （最好将结构或类的指针放入vector中，而不是结构或类本身，这样可以避免移动时的构造与析构)。
访问方面,对任何元素的访问都是O(1),也就是是常数的,所以vector常用来保存需要经常进行随机访问的内容,并且不需要经常对中间元素进行添加删除操作.

相比较可以看到vector的属性与string差不多,同样可以使用capacity看当前保留的内存,使用swap来减少它使用的内存.

capacity()返回vector所能容纳的元素数量(在不重新分配内存的情况下）

总结
需要经常随机访问请用vector

2.list

list就是双向链表,元素也是在堆中存放,每个元素都是放在一块内存中,它的内存空间可以是不连续的，通过指针来进行数据的访问，这个特点使得它的随机存取变的非常没有效率，因此它没有提供[]操作符的重载。但由于链表的特点，它可以以很好的效率支持任意地方的删除和插入。

list没有空间预留习惯,所以每分配一个元素都会从内存中分配,每删除一个元素都会释放它占用的内存.

list在哪里添加删除元素性能都很高,不需要移动内存,当然也不需要对每个元素都进行构造与析构了,所以常用来做随机操作容器.
但是访问list里面的元素时就开始和最后访问最快
访问其它元素都是O(n) ,所以如果需要经常随机访问的话,还是使用其它的好

总结
如果你喜欢经常添加删除大对象的话,那么请使用list
要保存的对象不大,构造与析构操作不复杂,那么可以使用vector代替
list<指针>完全是性能最低的做法,这种情况下还是使用vector<指针>好,因为指针没有构造与析构,也不占用很大内存

3.deque

deque是一个双端队列(double-ended queue)，也是在堆中保存内容的.它的保存形式如下:
[堆1]
...
[堆2]
...
[堆3]
每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品.

它支持[]操作符，也就是支持随即存取，可以让你在前面快速地添加删除元素,或是在后面快速地添加删除元素,然后还可以有比较高的随机访问速度,和vector的效率相差无几，它支持在两端的操作：push_back,push_front,pop_back,pop_front等，并且在两端操作上与list的效率也差不多。
在标准库中vector和deque提供几乎相同的接口,在结构上它们的区别主要在于这两种容器在组织内存上不一样,deque是按页或块来分配存储器的,每页包含固定数目的元素.相反vector分配一段连续的内存,vector只是在序列的尾段插入元素时才有效率,而deque的分页组织方式即使在容器的前端也可以提供常数时间的insert和erase操作,而且在体积增长方面也比vector更具有效率

总结：
vector是可以快速地在最后添加删除元素,并可以快速地访问任意元素
list是可以快速地在所有地方添加删除元素,但是只能快速地访问最开始与最后的元素
deque在开始和最后添加元素都一样快,并提供了随机访问方法,像vector一样使用[]访问任意元素,但是随机访问速度比不上vector快,因为它要内部处理堆跳转
deque也有保留空间.另外,由于deque不要求连续空间,所以可以保存的元素比vector更大,这点也要注意一下.还有就是在前面和后面添加元素时都不需要移动其它块的元素,所以性能也很高。

因此在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则：
1、如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
2、如果你需要大量的插入和删除，而不关心随即存取，则应使用list
3、如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。

c++部分的原文出处