您现在的位置是:首页 > 文章详情

笔记:C#和C++常见容器整合

日期:2020-02-21点击:607

前言

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

C#常见容器

e7911008f46893404a3a34d2cf21cf2

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++部分的原文出处

原文链接:https://yq.aliyun.com/articles/745763
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章