注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

老狗的博客

尽管每一步都很微小,但我确认我在进步

 
 
 

日志

 
 
关于我
sky

认真生活,努力工作 热爱技术,关注DB,存储,分布式,中间层,java,c++,php

网易考拉推荐

stl 学习  

2013-06-15 18:54:10|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一. stl container

Standard Containers

A container is a holder object that stores a collection of other objects (its elements). They are implemented as class templates, which allows a great flexibility in the types supported as elements.

container 是一个存储了 一组其他对象集合的 holder object, 他们通过class templates实现,支持各种各样的元素

The container manages the storage space for its elements and provides member functions to access them, either directly or through iterators (reference objects with similar properties to pointers).

1. container管理元素的存储空间
2. container支持使用成员函数对于对象进行存取,包括直接,或者通过迭代器进行存储

Containers replicate structures very commonly used in programming: dynamic arrays (vector), queues (queue), stacks (stack), heaps (priority_queue), linked lists (list), trees (set), associative arrays (map)...

container 使用编程中常见的结构,如动态数据(vector), 队列(queue), 站(stack), 堆(priority_queue), 线性连表(list), 树(set), 关联数组(map)

Many containers have several member functions in common, and share functionalities. The decision of which type of container to use for a specific need does not generally depend only on the functionality offered by the container, but also on the efficiency of some of its members (complexity). This is especially true for sequence containers, which offer different trade-offs in complexity between inserting/removing elements and accessing them.

许多容器有同样的成员函数,提供同样的功能,决定使用那种容器,不仅仅要看容器提供的功能,也要考虑效率,尤其对于sequence container

stackqueue and priority_queue are implemented as container adaptors. Container adaptors are not full container classes, but classes that provide a specific interface relying on an object of one of the container classes (such asdeque or list) to handle the elements. The underlying container is encapsulated in such a way that its elements are accessed by the members of the container adaptor independently of the underlying container class used.

stack, queue 和priority_queue 被作为container adaptors实现,container adaptors不是一个full container classes,  而是一个依赖于container class的对象,实现了某些具体接口的类,

二. std::vector

template < class T, class Alloc = allocator<T> > class vector; // generic template

Vectors are sequence containers representing arrays that can change in size.

vectors 是序列化容器,表示size可以变化的array

Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays. But unlike arrays, their size can change dynamically, with their storage being handled automatically by the container.

像数组一样,vecror使用连续的存储空间存储他们的元素, 这意味着如数组一样,可以在regular pointer 上使用偏移访问 元素,而且像数组一样高效,和数组不一样的是,他们的大小可以动态改变, 他们的空间自动的通过容器进行伸缩

Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time, and thus, vectors do not reallocate each time an element is added to the container.

从内部来说,vectors动态的分配array以存储他的元素,当心的元素被插入的时候,这个数组会重新分配空间,然后将所有的元素移动到新的空间中去,这个动作代价相当高,所以,vectors并不是每次添加元素都重新分配空间
Instead, vector containers may allocate some extra storage to accommodate for possible growth, and thus the container may have an actual capacity greater than the storage strictly needed to contain its elements (i.e., itssize). Libraries can implement different strategies for growth to balance between memory usage and reallocations, but in any case, reallocations should only happen at logarithmically growing intervals of size so that the insertion of individual elements at the end of the vector can be provided with amortized constant time complexity (seepush_back).

vectors容器会为将来可能的增长多分配一些空间,所以容器实际的分配的存储空间大小要大于它实际需要的,libraries可以实现不同的策略在内存使用率和重新分配空间之间平衡
Therefore, compared to arrays, vectors consume more memory in exchange for the ability to manage storage and grow dynamically in an efficient way.
所以相对于数组而言,vectors消耗很多的内存以方便数组大小的增长
Compared to the other dynamic sequence containers (dequeslists and forward_lists), vectors are very efficient accessing its elements (just like arrays) and relatively efficient adding or removing elements from its end. For operations that involve inserting or removing elements at positions other than the end, they perform worse than the others, and have less consistent iterators and references than lists and forward_lists.
相对于其他的dynamic sequence 容器而言,如deque,list和forward_list, vectors 在访问元素方面非常有效, 在尾部添加或者删除元素也非常有效,但是如果在其他位置进行插入或者删除,则比较低效, 不如lists和forward_lists,而且会使得iterators和引用失效


三. sequence container

Sequence containers

Headers<array><vector><deque><forward_list><list>
Membersarrayvectordequeforward_listlist
constructorimplicitvectordequeforward_listlist
destructorimplicit~vector~deque~forward_list~list
operator=implicitoperator=operator=operator=operator=
iteratorsbeginbeginbeginbeginbegin
before_begin
begin
endendendendendend
rbeginrbeginrbeginrbeginrbegin
rendrendrendrendrend
const iteratorsbegincbegincbegincbegincbegin
cbefore_begin
cbegin
cendcendcendcendcendcend
crbegincrbegincrbegincrbegincrbegin
crendcrendcrendcrendcrend
capacitysizesizesizesizesize
max_sizemax_sizemax_sizemax_sizemax_sizemax_size
emptyemptyemptyemptyemptyempty
resizeresizeresizeresizeresize
shrink_to_fitshrink_to_fitshrink_to_fit
capacitycapacity
reservereserve
element accessfrontfrontfrontfrontfrontfront
backbackbackbackback
operator[]operator[]operator[]operator[]
atatatat
modifiersassignassignassignassignassign
emplaceemplaceemplaceemplace_afteremplace
insertinsertinsertinsert_afterinsert
eraseeraseeraseerase_aftererase
emplace_backemplace_backemplace_backemplace_back
push_backpush_backpush_backpush_back
pop_backpop_backpop_backpop_back
emplace_frontemplace_frontemplace_frontemplace_front
push_frontpush_frontpush_frontpush_front
pop_frontpop_frontpop_frontpop_front
clearclearclearclearclear
swapswapswapswapswapswap
list operationssplicesplice_aftersplice
removeremoveremove
remove_ifremove_ifremove_if
uniqueuniqueunique
mergemergemerge
sortsortsort
reversereversereverse
observersget_allocatorget_allocatorget_allocatorget_allocatorget_allocator
datadatadata

四. 迭代器
An iterator is any object that, pointing to some element in a range of elements (such as an array or a container), has the ability to iterate through the elements of that range using a set of operators (with at least the increment (++) and dereference (*) operators)

迭代器可以是这样一种对象,指向一组集合中的某个元素,例如array或者container, 拥有使用一组 操作符遍历集合中元素的能力

the most obvious form of iterator is a pointer: A pointer can point to elements in an array, and can iterate through them using the increment operator (++). But other kinds of iterators are possible. For example, each container type (such as a list) has a specific iterator type designed to iterate through its elements.

迭代器最明显的形式就是指针,一个这阵可以指向数组中的元素,可以使用++操作符遍历集合中的元素,其他类型的迭代器也有类似这种功能,例如每个container都有具体的iteraotr, 设计用来遍历元素

notice that while a pointer is a form of iterator, not all iterators have the same functionality of pointers; Depending on the properties supported by iterators, they are classified into five different categories:

注意,指针是一种形式的iteraor, 单并不是所有的iterators都具有这种功能,依赖于iterators的属性,他们一般被设计为5种不同的种类
1. input interator
iterator b;
*b = "abc"; //不支持修改操作

b++; //支持
b--; //不支持
2. output iterator
iterator b;

*b = "abc" //支持修改操作

b++; //支持
b--; //不支持

3. forward iterator

4. bidirectional iterator
iterator b;
b++; //支持
b--; //支持
*b = "abc" //支持

5. random access
iterator b;
b++; //支持
b--; //支持
*b = "abc" //支持
b = b +n;//支持
b = b -n;//支持


  评论这张
 
阅读(168)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018