首页 > 代码库 > 20141029

20141029

1.vector:
            vector的数据安排以及操作方式与array非常相似,两者的唯一区别在于空间的运用的灵活性。array是静态空间,一旦配置了就不能改变,要换个大点的空间就需要程序员首先配置一块新空间,然后将元素从旧空间搬到新空间,再把原来的空间释放给系统。vector是动态空间,随着元素的加入,它的内部机制会自行扩充空间以容纳新元素。vector实现的关键技术在于其对大小的控制以及重新配置是数据移动的效率。
            vector采用的数据结构非常简单:线性连续空间,普通指针可以作为vector的迭代器,以两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围,并以迭代器end_of_srotage指向整块连续空间(含备用空间)的尾端;对vector的任何操作一旦引起空间重新配置,指向原有的vector的所有迭代器就都失效。
            vector 一般常用的方法有beigin(),end()返回第一个和最后一个下一个的迭代器;front()和back()返回第一个和最后一个元素;push_back()和pop_back()在尾端添加和删除元素;erase()和clear()删除元素;size()返回容器中元素个数,capacity返回配置的空间容量,大于等于size().;insert()在任意位置插入元素,;vector支持随机访问。
  2.list
        list的内存不是连续线性空间,好处是每次插入或删除一个元素就会配置或释放一个元素空间。对任何位置元素的插入或者删除,永远是常数时间。list不能像vector一样以普通指针作为迭代器,因为其节点不保证在存储空间中连续存在。list的插入操作和接洽操作都不会造成原有的list迭代器失效,这在vector中是不成立的。list不支持随机访问。
        list元素的操作有push_front, push_back, pop_front, pop_back, erase, clear, remove, unique(移除数值相同的连续元素), splice(接合操作,将某连续范围内的元素从一个list移动到另一个(或同一个)list的某个结点), merge融合(将list x合并到*this身上,这里的两个list的内容都必须经过递增排序), reverse(逆转), sort. list不能使用STL的sort,因为STL算法sort()只接受随机访问迭代器,所以list有自己的sort。
3.deque
        vector是单向开口的连续线性空间,deque则是一种双向开口的分段连续线性空间。所谓双向开口就是可以在头尾两端分别分别作元素的插入和删除操作。vector和deque的差异主要在于以下两个方面: 一deque允许常数时间内对其头端进行元素的插入和删除操作;二是没有所谓的容量观念,因为它是动态地以分段连续空间组合而成,随时可以增加一段新的空间并链接起来,不会像vector那样发生“重新配置空间,复制数据,释放旧空间”,因此deque没有提供所谓的空间保留功能。deque的迭代器不能是普通指针,因为它是分段连续空间。
4.stack
        stack是一种后进先出的数据结构,stack允许新增元素、移除元素、取得最顶端元素。但除了最顶端外,没有任何其他方法可以存取stack元素,换言之,stack不允许有遍历行为。stack不提供随机访问,也不提供迭代器,即不能够遍历。可以用list或者的却实现stack;
5.queue
        queue是一种先进先出的数据结构,允许从最低端加入元素,从顶端获取元素。queue不允许有遍历行为,没有迭代器。
6.priority_queue
        priority_queue是一个拥有权值观念的queue,其内的元素并非按照被推入的次序排列,而是自动按照元素权值(通常权值以实值表示)排列,权值高者排在前面,就这是一个已经排序过的queue。
4.联合容器map、multimap、set、multiset:
            set的特性是所有元素都会根据元素的键值自动被排序。set元素的键值就是实值,实值就是键值,set不允许两个元素有相同的键值。不可以通过键值改变set的迭代器改变set的元素值,因为set的元素值就是其键值,关系到set元素的排列规则。如果任意改变set的元素值,会严重破坏set组织。换句话说set的迭代器是一种常量迭代器。set的底层实现机制是RB-tree。
            map的特性是所有元素都会根据元素的键值自动被排序。map的所有元素都是pair,通知拥有实值(value)和键值(key)。pair的第一元素被视为键值,第二元素被视为实值,map不允许两个元素拥有相同的键值。不可以通过迭代器修改map元素的键值,但是可以通过迭代器修改map元素的实值。map的底层实现机制是RB-tree。
           使用下标访问map与使用下标访问数组或者vector的行为截然不同:用下标访问不存在的元素将导致在map容器中添加一个新的元素,它的键值即为该下标值。
            map<string,int>::value_type其实就是pair<const string, int>类型的同义词。key_type是键类型,mapped_type是值类型。map对象中一个给定键值只对应一个元素。如果试图插入的元素所对应的键已在容器中,则
insert不做任何操作。带有一个键-值pair形参的insert版本将返回一个值:一个包含迭代器(指向map中具有相应键的元素)和一个bool(该键是否已经在容器中,在返回false)值得pair对象,
            multiset的特性以及用法和set完全相同,唯一的差别在于它允许键值重复。
            multimap的特性以及用法和map完全相同,唯一的差别在于它允许键值重复。
            hash_set的底层实现机制是hashtable,但是请注意RB-tree有自动排序功能而hashtable没有,反映出来的结果就是set元素有自动排序功能而hash_set没有。
            hash_map的底层实现机制是hashtable,但是请注意RB-tree有自动排序功能而hashtable没有,反映出来的结果就是set元素有自动排序功能而hash_map没有。

20141029