容器
2018-06-27 10:03:58来源:未知 阅读 ()
一、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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ 模板类vector 2020-05-31
- C++ 模板类vector 2020-05-30
- 数据结构—链表 2020-05-29
- 图 2020-05-02
- STL之map 2020-04-27
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash