点击查看Evernote原文。
#@author: gr
#@date: 2014-08-23
#@email: forgerui@gmail.com
STL中的关联容器。
###stl学习
|--迭代器
|--类属算法
|--容器
|--vector
|--deque
|--list
|--set
|--map
|--函数对象
|--适配器
|--分配器
一、Contents
1. why关联容器
序列容器以线性排列方式保存数据项,并且各数据项保持了它们在插入时的相对位置,关联容器则摒弃了这种顺序,把注意力集中在如何通过保存在数据中的索引项来尽可能快地检索到数据项。
2. 实现形式
一种方法可以把索引项按照某种全序关系排列起来,用二叉树查找,时间复杂度为O(log N)
。
一种方法是使用散列函数,时间复杂度为常数。
3. 四种关联容器
set
和multiset
,其数据项就是索引项本身,其区别是multiset
允许出现重复索引项。map
和multimap
,数据项是由索引项和其他的数据类型组成的一对数据,同样,区别就是multimap
允许出现重复索引项。
4. set && multiset
template <typename Key, typename Compare = less<Key>, class Allocator = allocator<Key> >
5. insert
//set最简单的insert函数只有一个参数
set set1;
for(list<int>::iterator it = list1.begin(); it != list1.end(); it++){
set1.insert(*it);
}
set
和multiset
定义的insert
有些不同,下面是set的定义:
pair<interator, boo> insert(const value_type& x);
multiset
的insert
定义:
iterator insert(const value_type& x);
set
中不允许有重复元素,所以不一定插入成功,所以需要返回一个bool,表明是否插入成功。
它们还提供一个关于位置的insert
成员函数,这个位置不是插入的位置,插入的位置由比较函数确定,而是从该位置搜索插入位置。
iterator insert(iterator position, const value_type& x);
使用inserter
插入迭代器:
copy(list1.begin(), list1.end(), inserter(multiset1, multiset1.end() ));
6. erase
//删除所有索引值为e的元素
multiset1.erase('e');
//删除第一个e元素
multiset1.erase(multiset.find('e'));
//删除一个区间,迭代器[i, j)
multiset.erase(i, j);
7. 访问器
lower_bound
表示索引的第一个位置,upper_bound
表示最后一个位置。
//multiset1: aaabccccddeeefhhhxy
multiset<char>::iterator i = multiset1.lower_bound('c');
multiset<char>::iterator j = multiset1.upper_bound('h')
//erase之后,multiset1值为: aaabxy
multiset1.erase(i, j);
如果lower_bound
和upper_bound
作用于同一个索引值,则可以使用equal_range
,返回一对迭代器,上面的代码可以写为下面的形式:
pair<multiset<char>::iterator, multiset<char>::iterator> > p = multiset1.equal_range('s');
multiset1.erase(p->first, p->second);
另外,count
函数可以获取索引值的个数:
int num = multiset1.count('s');
8. map && multimap
map
和multimap
类的模板定义:
template <typename Key, typename T, typename Compare = less<Key>,
class Allocator = allocator<pair<const Key, T> > >
9. 插入
map
的insert
函数需要求一个pair
做参数。
map.insert(pair<const Key, T>);
也可以使用运算符[]
,比如
map[k] = t;
如果不存在索引值为k的元素,则插入元素(k, t),如果已经存在某个元素(k, t0),则以t代替t0。
还可以用如下的替换操作:
//i为map<Key, T>::iterator
i->second = t;
//索引值是const, 不能修改,下面的语句是错误的
i->first = k1;
10. 删除
和集合一样,可以通过索引或位置删除映射和多映射中的元素。
11. 访问器
有下面的访问器:
begin,end,size,empty,find,lower_bound,upper_bound,equal_range,count,operatar[]...
二、Miscellany
@author gr
@mail forgerui@gmail.com