|
|
|
|
STL 之 Container Concepts |
|
|
|
作者：未知 来源：月光软件站 加入时间：2005-2-28 月光软件站 |
Container:
描述：存放各种元素，每个Container必须要有相应的Iterator,元素的存放顺序不定。
也许每次Iterator遍历Container的时候，每次的访问顺序都可能不一样，而且Container
不能保证在同一时刻有超过一个Iterator有效。Container自己拥有包含的元素（如果是指
针Container,那么就仅仅是对指针游泳所有权，而不是指针指向的对象）。Container可以
根据是否可以动态的改变容器大小分为Fixed Sized Container 和 Variable Sized Con
tainer.
定义：Container的Size是指包含的元素的个数，非负。
Container的Area是指该Container所占据的字节数。等于所有的元素占有的空间
+Container附加的空间消耗。
表达式语义：
1、x,y表示Container中元素对象。
表达式包括赋值 x=y,判等x==y,x!=y,比较大小x<y,x<=y,x>y,x>=y.
2、a,b表示Container对象。表达式包括构造函数，析够函数，拷贝构造函数，赋值运
算符、begin(),end(),size(),max_size(),empty(),swap()。
b=a ,把容器a拷贝给b,因此a，b的大小也就一致。
a.begin()，返回一个指向容器的第一个元素的Iterator
a.end() , 返回一个指向容器的最后一个元素的Iterator
a.size() ，返回容器a的元素个数
a.max_size()，返回容器a可能达到的最大的元素个数，在Fixed Sized Contain
er里面size()==max_size()
a.empty() ，判断容器a是否为空
Forward Container:
描述：Forward Container首先是Container,和Container区别的是他的元素存放顺序是
一定的，他的Iterator必定是Forward Iterator,因为他自己是一个Forward Container,I
terator遍历的时候每次的顺序都必定一样。
表达式语义：a,b表示Container对象。首先他包含Container的表达式，另外还有：a<
b,a==b。
a<b: 相当于lexicographical_compare(a,b)
a==b:a,b的大小相同，并且各个位置对应的元素相等
Reversible Container:
描述：Reversible Container首先是一个ForwardContainer,但是它的Iterator是双向
的（Bidirectional Iterators.），因此也就支持反方向循环子。他所要求的Iterator也
有所加强，必定是Bidirectional Iterators,而不仅仅要求是Forward Iterators。
表达式语义：a,b表示Container对象。除了ForwardContainer的操作之外，还有rbeg
in(),rend().
rbegin: 返回一个反方向的循环子，他指向该Container的最后一个元素。
rend: 返回一个反方向的循环子，他指向该Container的第一个元素。
Random Access Container
描述：首先Random Access Container是一个Reversible Container,它提供访问任何一
个元素的方法。他所要求的Iterator也有所加强，必定是Random Access Iterator. ,而不
仅仅要求是Bidirectional Iterators。
表达式语义：a,b表示Container对象。除了Reversible Container的操作之外，还有a
[n]：其中0<N<a.size(),返回该容器的第N个元素
Sequence：
描述：Sequence首先是个可以动态改变大小的Forward Container,另外还支持插入和删除
元素的操作。
表达式语义：X Sequence类型的容器
a, b 容器X的对象
T 容器X包含的元素的数据类型
t 数据类型T的对象
p, q 容器a，b的Iterator对象
n 容器a,b的元素个数
除了Forward Container的操作外，还支持X(n,t)，X a(n,t)，X(n)，X a(n,t)，X(i,j)，
X a(i,j)， a.front()，a.insert(p,t) a.insert(p,n, t), a.insert(p,i,j), a.erase
(p), a.erase(p,q), a.clear(), a.resize(n,t), a.resize(n)
X(n,t) :创建一个Sequence,size()==n,而每个元素都是t的拷贝
X a(n,t):创建一个Sequence对象a , a.size()==n,而每个元素都是t的拷贝
X(n) :创建一个Sequence,size()==n,而每个元素都是T( ),缺省构造函数
X a(n,t):创建一个Sequence对象a , a.size()==n,而每个元素都是T( )
X(i,j) :创建一个Sequence对象 , a.size()==size(i-j),而元素是i,j之间的元素的拷
贝,i,j是一个T类型的元素的范围
X a(i,j) : 创建一个Sequence对象 a, a.size()==size(i-j),而元素是i,j之间的元素的
拷贝
a.insert(p,t):在p处插入一个元素t,a.size()加1,而元素相互间的位置不变
a.insert(p,n,t):在p处插入n个元素t,a.size()加n，而元素相互间的位置不变
a.insert(p,i,j):在p处插入元素,a.size()加(j-i)，而元素相互间的位置不变
a.erase(p):删除p指向的元素,返回一个Iterator,指向p指向的元素的后一个元素
a.erase(p,q): 删除p,q之间的元素, 返回一个Iterator,指向q指向的元素的后一个元素
a.clear() : 相当于a.erase(a.begin,a.end)
a.resize(n,t):使Sequence a的size()=n,如果原来的size()>n,则相当于删除多余的元素
，如果原来的size()<n，则填充(n-size())个t元素
a.resize(n)：相当于a.resize(n,T())
Front Insertion Sequence
描述：首先他肯定是一个Sequence,另外他还支持在Sequence的第一个元素之前插入，
或者取得第一个元素、或者删除第一个元素
表达式：除了Sequence的表达式之外，他还包括：front()、push_front（）、pop_f
ront()。
a.front():取得a的第一个元素，相当于*(a.begin())
a.push_front(t):在a的第一个元素插入之前t，相当于a.insert(a.begin(),t)
a.pop_front():删除第一个元素，相当于a.erase(a.begin())
Back Insertion Sequence
描述：首先他肯定是一个Sequence,另外他还支持在Sequence的最后一个元素之后插入
，或者取得第一个元素、或者删除最后一个元素
表达式：除了Sequence的表达式之外，他还包括：back()、push_back（）、pop_bac
k()。
a.back():取得a的最后一个元素，相当于*(a.end())
a.push_back(t):在a的最后一个元素插入之前t，相当于a.insert(a.end(),t)
a.pop_back():删除最后一个元素，相当于a.erase(a.end())
Associative Container
描述：他首先是一个Variable Sized Container, 支持根据key从而进行元素的插入和
删除操作（和Sequence不同的是，他无法指定插入和删除的位置）。在Associative Cont
ainer中，每一个元素都有一个相对应的key ：在Simple Associative 中，key就是元素自
己本身，而在其他的Associative Container中，key是元素本身值的特殊的一部分。由于
元素是按照他们的key进行存储摆放的，因此也就要求每个key是永久不变的。在Simple A
ssociative 中，就是元素自己本身不可变；在Pair Associative Containers中，元素本
身是可变的，但是作为元素一部分的key就是不可变的。元素对应的key的不可变意味着As
sociative Container的元素是不可赋值（Assignable.）的。而不可赋值也就导致了一个
重要的后果：associative containers没有可变的循环子(mutable Iterator),因为mutab
le iterator要求可以赋值。就是说：如果i是一个mutable iterator，t是i指向的容器的
一个元素，那么*i=t是合法有效的。在Simple associative containers中，元素是永不可
变的，而其他的associative containers呢,则可以通过iterator改变元素的值。比如说P
air Associative Containers，循环子I是map<int,double>类型，则可以通过(*i).second=3改变元素的值。Unique Associative Containers中，所有的元素的
key值都是唯一的,而Unique Associative Containers中，允许多个元素拥有同样的key值
。
表达式语义：
a.erase(k)：删除所有key值为k的元素。返回只是被删除的元素的个数，size减少key值为
k的元素的个数a.count(k)
a.erase(p)：删除循环子p所指的元素，size减少1
a.erase(p, q)：删除循环子p,q之间的元素，size 减少p,q间元素的个数]
a.clear()：清空容器，相当于a.erase( a.begin(),a.end() )
a.find(k):查找key值为k的元素，如果有结果，则返回指向该元素的循环子，否则返回a.
end()
a.count(k):返回key值为k的元素的个数
a.equal_range(k)：返回一对循环子，第一个循环子指向key值为k的第一个元素，第二个
元素指向key值为k的最后一个元素
Simple Associative Container
描述：他的key就是元素自己本身，每个元素本身因为就是key,所以元素都是不可变的
Pair Associative Container
描述：他的元素的为 pair<const key_type, data_type>，注意：这里的pair的第一个
参数是const,因为key是不可变的，所以元素也就不能是 pair< key_type, data_type>.
Sorted Associative Container
描述：他的key值是可以排序的，如果两个key是无法比出大小的，那么就认为是相等的
。如果key值大小写无关，那么"abcde" and "aBcDe"这两个key是认为相等的
表达式：
a.lower_bound(k)：返回key值不小于k的最后一个元素，如果有多个和k同样的key,那么返
回第一个元素，如果不存在满足要求的元素， 那么返回end()
a.upper_bound(k):返回key值大于k的第一个元素，如果有多个和k 同样的key,那么返回和
k相同的key的元素中的最后一个的后一个元素，如果不存在满足要求的元素，返回end()
a.equal_range(k)：返回一对循环子，第一个是a.lower_bound(k),第二个是a.upper_bou
nd(k)
Hashed Associative Container
描述：Hashed Associative Container是一个利用Hash Table的Container。他的元素的排
列方式不是一定有意义的，甚至于，他的元素是无序的。Hashed Associative Container
中的操作的复杂度是和容器的大小成线性比例的。
哈希函数定义：一元参数函数，输入为key值，返回该key对应的在hash中的位置偏移量。
每个元素将key值代入到hash函数中进行运算，从而决定该元素的存放位置。哈希函数的返
回值仅仅只能由函数带入的参数决定。而hash表可能存放的元素的个数除以hash表的长度
得到的商就是负载因子（load factor）。哈希函数对于Hashed Associative Container来
说很重要，如果哈希函数找得不好，会有冲突（这里的冲突是指两个不同的元素被映射到
同一个位置）。最差的就是所有的元素都被映射到同一个位置，整个函数的复杂度就会增
加，变成和容器的size成线性比例关系。
表达式语义：
X A type that is a model of Hashed Associative Container
a Object of type X
t Object of type X::value_type
k Object of type X::key_type
p, q Object of type X::iterator
n Object of type X::size_type
h Object of type X::hasher
c Object of type X::key_equal
X() ，X a：缺省构造函数，容器的size为0，容器拥有的长度是一个未定值，该容器使用
hasher()为他的哈希函数，而key_equal()作为它的元素的key值比较函数。
X(n) X a(n) ：容器的size=0,但是容器拥有的长度是n, 使用hasher()为他的哈希函数，
而key_equal()作为它的元素的key值比较函数。
X(n, h) X a(n, h): 容器的size=0,但是容器拥有的长度是n, 使用h()为他的哈希函数，
而key_equal()作为它的元素的key值比较函数。
X(n, h, k) X a(n, h, k): 容器的size=0,但是容器拥有的长度是n, 使用h()为他的哈希
函数，而k()作为它的元素的key值比较函数。
a.hash_funct():返回该容器的哈希函数
a.erase(k)：删除容器里面key值为k的元素，整个容器的size减少a.count(k),返回删除的
元素个数
a.find(k)：查找key值为k的元素，如果有结果，则返回指向该元素的循环子，否则返回a
.end()
a.equal_range(k)：返回一个范围，从第一个key为k的元素到最后一个key为k的元素，如
果没有找到，那么返回一个空的范围
a.bucket_count()：返回容器的长度
a.resize(n)：增加容器的长度，最少为n,如果原来的长度大于n,那么不动 。注意：改变
容器的大小并不会使得该容器的循环子失效，但是可能会影响各个循环子之间的先后的顺
序。本来在前面的循环子在容器的长度改变之后可能到了后面。
Unique Associative Container
描述：所有的元素的各自的key值各不相同，所以a.count(k)的返回值或者为0或者为1
，a.insert(t)在这里也具有一定的特殊性：如果t已经在Unique Associative Container
存在了，那么就不插入，如果不存在，则插入。返回值为pair<>,第一个元素是一个指向t
的循环子，第二个是一个是否进行插入的布尔值。
Multiple Associative Container
描述：取消了Unique Associative Container限制的容器
Unique Sorted Associative Container
描述：需要满足Sorted Associative Container和 Unique Associative Container的
容器
Multiple Sorted Associative Container
描述：需要满足Sorted Associative Container和Multiple Associative Container的
容器
Unique Hashed Associative Container
描述：需要满足Hashed Associative Container, Unique Associative Container的容
器
Multiple Hashed Associative Container
描述：需要满足Hashed Associative Container, Multiple Associative Container的
容器
|
|
相关文章：相关软件： |
|
本类阅读TOP10