容器

2018-06-17 21:52:17来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

一、vector

数据结构是动态数组。支持随机存取,时间复杂度是O(1)。迭代器是随机存取迭代器。

在尾端添加或删除元素时,时间复杂度是O(1)。在其他位置添加或删除元素时,需要移动该位置后面的所有元素,每一次移动调用赋值运算符。

vector容量很重要有两个原因:

1.一旦内存重新分配,与vector元素相关的所有references、pointers、iterators都会失效。

2.内存重新分配很耗时间。

避免重新分配内存的最好方法是使用reserve()保留适当容量。

vector不能使用reserve()来缩减容量,这一点和string不同。

两个vector交换内容后,两者的容量也会互换,下面的例子虽然保留了元素,却缩减了容量:

1 template<class T>
2 void shrinkCapacity(std::vector<T> &v)
3 {
4   std::vector<T> tmp(v);
5   v.swap(tmp);
6 }

可以利用下面的语句直接缩减容量:

1 std::vector<T>(v).swap(v);

swap()之后原先所有的references、pointers、iterators都换了指涉对象,所以它们都失效。

插入元素和删除元素,都会使“作用点”之后的各元素的references、pointers、iterators失效。如果插入操作甚至引发内存重新分配,那么该容器身上的所有references、pointers、iterators都会失效。

 

二、deque

数据结构是动态数组。支持随机存取,接口和vector几乎一模一样。迭代器是随机存取迭代器。

deque通常实现为一组独立区块,第一区块朝某方向扩展,最后一个区块朝另一方向扩展。

与vector相比,deque功能上的不同处在于:

1.两端都能快速插入和删除元素,时间复杂度是O(1)。

2.存取元素时,deque的内部结构会多一个间接过程,所以元素的存取和迭代器的动作会稍微慢一些。

3.迭代器需要在不同区块间跳转,所以必须是特殊的智能指针。

4.在对内存区块有所限制的系统中(例如PC系统),deque可以内含更多元素,因为它使用不止一块内存。因此deque的max_size()可能更大。

5.除了头尾两端,在任何地方插入和删除元素,都将导致指向deque元素的任何pointers、references、iterators失效。

deque的内存重分配优于vector,因为其内部结构显示,deque不必在内存重分配时复制所有元素。

6.deque的内存区块不再被使用时会被释放。deque的内存大小是可缩减的。

 

三、list

list使用一个双向链表来管理元素。迭代器是双向迭代器。

list与vector和deque存在明显区别:

1.list不支持随机存取。

2.任何位置上插入和删除元素都非常快,时间复杂度是O(1),因为无需移动任何其它元素。实际上内部只是进行了一些指针操作。

3.插入和删除不会造成指向其它元素的各个pointers、references、iterators失效。

4.list对于异常有着这样的处理方式:要么操作成功,要么什么都不发生。

list所提供的成员函数与vector和deque的不同:

1.由于不支持随机存取,list即不提供下标运算符,也不提供at()。

2.list不提供容量、空间重新分配等操作函数,因为每个元素都有自己的内存,在被删除之前一直有效。

3.list提供了专门用于移动元素的成员函数。较之同名的STL通用算法,这些函数执行起来更快,因为它们无需拷贝或移动,只需调整若干指针即可。

 

四、set和multiset

set和multiset会根据特定的排序准则,自动将元素排序。两者不同处在于multiset允许元素重复而set不允许。迭代器是双向迭代器。

如果没有传入特别的排序准则,就采用标准库函数对象less<T>,以operator<对元素进行比较,以便完成排序。

set和multiset通常以平衡二叉树实现。自动排序的主要优点在于使二叉树在查找元素时具有良好性能。

自动排序造成set和multiset的一个重要限制:你不能直接改变元素值,因为这样会打乱原本正确的顺序。

因此,要改变元素值,必须先删除旧元素,再插入新元素。

有两种方式可以定义排序准则:

1.以模板参数定义。

2.以构造函数参数定义。

set和multiset提供了特殊的查找函数,这些函数是同名的STL算法的特殊版本。这些优化算法的时间复杂度是O(logn),STL算法的时间复杂度是O(n)。

要删除与某值相等的元素,只需调用erase(),它返回被删除元素的个数:

1 std::set<Elem> coll;
2 
3 coll.erase(value);

如果multiset含有重复元素,你不能使用erase()来删除这些重复元素中的第一个。你可以这么做:

1 std::multiset<Elem> coll;
2 
3 std::multiset<Elem>::iterator pos;
4 pos = coll.find(elem);
5 if (pos != coll.end())
6     coll.erase(pos);

这里应该采用成员函数find(),而非STL算法find(),因为前者速度更快。

作用于序列式容器和关联式容器的erase()函数,其返回值有以下不同:

1.序列式容器提供下面的erase()成员函数:

iterator erase(iterator pos);

iterator erase(iterator beg, iterator end);

2.关联式容器提供下面的erase()成员函数:

void erase(iterator pos);

void erase(iterator beg, iterator end);

存在这种差别,完全是为了性能。在关联式容器中查找某元素并返回后继元素可能颇为耗时,因为这种容器的底部是以二叉树完成。

无论是将排序准则作为第二个模板参数传入,或是采用标准库函数对象less<T>,通常你都会将排序准则定义为类型的一部分。

但有时必须在执行期处理排序准则,或者你可能需要对同一种数据类型采用不同的排序准则。

此时你就需要一个用来表现排序准则的特殊类型,使你能够在执行期间传递某个准则。以下程序说明了这种做法:

 1 #include <iostream>
 2 #include <set>
 3 #include "print.hpp"
 4 
 5 using namespace std;
 6 
 7 template<calss T>
 8 class RuntimeCmp
 9 {
10 public:
11     enum cmp_mode{normal, reverse};
12 
13 private:
14     cmp_mode mode;
15 
16 public:
17     RuntimeCmp(cmp_mode m = normal) :
18         mode(m)
19     {
20     }
21 
22     bool operator()(const T &t1, const T &t2) const
23     {
24         return mode == normal ? t1 < t2 : t2 < t1;
25     }
26 
27     bool operator==(const RuntimeCmp &rc)
28     {
29         return mode == rc.mode;
30     }
31 };
32 
33 typedef set<int, RuntimeCmp<int>> IntSet;
34 
35 void fill(IntSet &set);
36 
37 int main()
38 {
39     IntSet coll1;
40     fill(coll1);
41     PRINT_ELEMENTS(coll1, "coll1: ");
42 
43     RuntimeCmp<int> reverse_order(RuntimeCmp<int>::reverse);
44     IntSet coll2(reverse_order);
45     fill(coll2);
46     PRINT_ELEMENTS(coll2, "coll2: ");
47 
48     coll1 = coll2;
49     coll1.insert(3);
50     PRINT_ELEMENTS(coll, "coll: ");
51 
52     if (coll1.value_comp() == coll2.value_comp())
53         cout << "coll1 and coll2 have same sorting criterion" << endl;
54     else
55         cout << "coll1 and coll2 have different sorting criterion" << endl;
56 }
57 
58 void fill(IntSet &set)
59 {
60     set.insert(4);
61     set.insert(7);
62     set.insert(5);
63     set.insert(1);
64     set.insert(6);
65     set.insert(2);
66     set.insert(5);
67 }

程序输出如下:

coll1: 1 2 4 5 6 7

coll2: 7 6 5 4 2 1

coll1: 1 2 3 4 5 6 7

coll1 and coll2 have same sorting criterion

 

五、map和multimap

map和multimap将key/value pair当做元素,它们可根据key的排序准则自动将元素排序。multimap允许重复元素而map不允许。迭代器是双向迭代器。

元素的次序由它们的key决定,和value无关。如果使用者未传入特定排序准则,就使用标准库函数对象less<T>,以operator<来进行比较。

map和multimap通常以平衡二叉树实现。map可作为关联式数组来运用。

map和multimap根据元素的key自动对元素进行排序。自动排序这一性质使得map和multimap身上有了一条重要的限制:你不可以直接改变元素的key,因为这会破坏正确次序。

要修改元素的key,你必须先移除拥有该key的元素,然后插入拥有新的key/value的元素。

有两种方式可以定义排序准则:

1.以模板参数定义。

2.以构造函数参数定义。

map和multimap不支持元素直接存取,因此元素的存取通常是经由迭代器进行。不过有个例外:map提供下标运算符,可直接存取元素。

在map和multimap中,所有元素的key都被视为常数。因此元素的实质类型是pair<const key, T>。

这个限制是为了确保你不会因为变更元素的key而破坏已排好的元素次序。所以你不能针对map或multimap调用任何变动性算法。

你不能对它们调用remove(),因为remove()算法实际上是以一个参数值覆盖被移除的元素。如果要移除map和multimap的元素,你只能使用它们所提供的成员函数。

如果你一定得改变元素的key,只有一条路:以一个value相同的新元素替换掉旧元素。下面是个模板函数:

 1 namespace MyLib
 2 {
 3     template<class Cont>
 4     inline
 5     bool replace_key(Cont &c, 
 6                      const typename Cont::key_type &old_key,
 7                      const typename Cont::key_type &new_key)
 8     {
 9         typename Cont::iterator pos;
10         pos = c.find(old_key);
11 
12         if (pos != c.end())
13         {
14             c.insert(typename Cont::value_type(new_key, pos->second));
15             c.erase(pos);
16             return true;
17         }
18         else
19         {
20             return false;
21         }
22     }
23 }

map提供了一种非常方便的手法让你改变元素的key。只需这样做:

1 coll["new_key"] = coll["old_key"];
2 coll.erase("old_key");

有三个不同的方法可以在map中插入一个元素:

1.运用value_type

为了避免隐式类型转换,你可以利用value_type传递正确类型。value_type是容器本身提供的类型定义。例如:

1 std::map<std::string, float> coll;
2 
3 coll.insert(std::map<std::string, float>::value_type("otto", 22.3));

2.运用pair<>

1 std::map<std::string, float> coll;
2 
3 coll.insert(std::pair<std:;string, float>("otto", 22.3));
4 coll.insert(std::pair<const std::string, float>("otto", 22.3));

上述第一个insert()语句内的类型并不正确,所以会被转换成真正的元素类型。为了做到这一点,insert()成员函数被定义为成员模板。

3.运用make_pair()

1 std::map<std::string, float> coll;
2 
3 coll.insert(std::make_pair("otto", 22.3));

和做法2一样,也是利用成员模板insert()来执行必要的类型转换。

 

六、各种容器的运用时机

1.缺省情况下应该使用vector。vector的内部结构最简单,并允许随机存取,所以数据的存取十分方便灵活,数据的处理也够快。

2.如果经常要在序列头部和尾部插入和删除元素,应该采用deque。如果你希望元素被移除时,容器能够自动缩减内存,那么你也应该采用deque。

此外,由于vector通常采用一个内存区块来存放元素,而deque采用多个区块,所以后者可含有更多元素。

3.如果需要经常在容器的中段执行元素的插入、删除和移动,可考虑使用list。list提供特殊的成员函数,将元素从A容器转移到B容器,时间复杂度是O(1)。

但由于list不支持随机存取,所以如果只知道list的头部却要访问list的中间元素,性能会大打折扣。和所有以节点为基础的容器相似,只要元素还是容器的一部分,

list就不会令指向那些元素的迭代器失效。vector则不然,一旦超过其容量,它的所有iterators、pointers、references都会失效;执行插入或删除操作时,也会令

一部分iterators、pointers、references失效。至于deque,当它的大小改变,所有iterators、pointers、references都会失效。

4.如果你要的容器是这种性质:每次操作若不成功,便无效用。那么你应该选用list,或是采用关联式容器。

5.如果你经常需要根据某个准则来查找元素,那么应当使用以该排序准则对元素进行排序的set或multiset。

6.如果想处理key/value pair,请采用map或multimap。

7.如果需要关联式数组,应采用map。

8.如果需要字典结构,应采用multimap。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:9.28 作业 6

下一篇:P3183 [HAOI2016]食物链