stl源码剖析 详细学习笔记 set map
//
// set map.cpp
// 笔记
//
// Created by fam on 15/3/23.
//
//
//---------------------------15/03/23----------------------------
//set
{
/*
set概述:
1:所有的元素都会被自动排序,
2:所有的元素只有"键"没有“值”
或者说他们的“值”就是“键”
3:不允许出现两个相同的键值
4:不能通过迭代器改变set的值,因为set的值就是键,
如果可以改变,我们要先删除键,平衡二叉树,再加改变后的键,再平衡
这么做严重破坏了set的组织,iterator也会变得无效,到底是指向之前的位置
还是指向改变后的位置等等。所以stl中不允许改变set的值。
5:set用RB_tree作为底层机制(废话,不然干嘛花大篇幅介绍RB_tree)
*/
//class
template<class Key,
class Compare = less<Key>,
class Alloc = alloc>
class set
{
public:
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare;
typedef Compare value_compare;
private:
//identity<value_type>
可以根据key值得到value值
typedef rb_tree<key_type, value_type,
identity<value_type>, key_compare, Alloc> rep_type;
rep_type t;
public:
//由于上面说的set不能改变值,所以指针和迭代器引用这些
全都用RB_tree中的const类型的来指定
typedef typename rep_type::const_pointer pointer;
typedef typename rep_type::const_pointer const_pointer;
typedef typename rep_type::const_reference reference;
typedef typename rep_type::const_reference const_reference;
typedef typename rep_type::const_iterator iterator;
typedef typename rep_type::const_iterator const_iterator;
typedef typename rep_type::const_reverse_iterator reverse_iterator;
typedef typename rep_type::const_reverse_iterator const_reverse_iterator;
typedef typename rep_type::size_type size_type;
typedef typename rep_type::difference_type difference_type;
set() : t(Compare()){}
explicit set(const Compare& comp) : t(comp){}
//inset_unique
是不允许相同值出现的插入
template<class InputIterator>
set(InputIterator first, InputIterator last)
: t(Compare()){ t.insert_unique(first, last);}
template<class InputIterator>
set(InputIterator first, InputIterator last,const Compare& comp)
: t(comp){t.insert_unique(first, last);}
set(const set<Key, Compare, Alloc>& x): t(x.t){}
set<Key, Compare, Alloc>&
operator=(const set<Key, Compare, Alloc>& x)
{
t = x.t;
return *this;
}
key_compare key_comp()
const { return t.key_comp();}
//set中的值就是键
所以调用key_comp()
value_compare value_comp()
const {return t.key_comp();}
iterator begin()
const {return t.begin();}
iterator end()
const {return t.end();}
reverse_iterator rbegin()
const {return t.rbegin();}
reverse_iterator rend()
const {return t.end();}
bool empty()
const { return t.empty();}
size_type size()
const { return t.size();}
size_type max_size()
const { return t.max_size();}
void swap(set<Key, Compare, Alloc>& x) { t.swap(x.t);}
//insert erase
typedef pair<iterator,
bool> pair_interator_bool;
pair<iterator,
bool> inset(const value_type& x)
{
pair<typename rep_type::iterator,
bool> p =t.insert_unique(x);
return pair<iterator,
bool>(p.first, p.second);
}
iterator insert(iterator position,
const value_type& x)
{
typedef typename rep_type::iterator rep_iterator;
return t.insert_unique((rep_iterator&)position, x);
}
template<class InputIterator>
void insert(InputIterator first, InputIterator last)
{
t.insert_unique(first, last);
}
void erase(iterator position)
{
typedef typename rep_type::iterator rep_iterator;
t.erase((rep_iterator&)position);
}
size_type erase(const key_type& x)
{
return t.erase(x);
}
void erase(iterator first, iterator last)
{
typedef typename rep_type::iterator rep_iterator;
t.erase((rep_iterator&)first, (rep_iterator&)last);
}
void clear() { t.clear();}
//
iterator find(const key_type& x)
const { return t.find(x); }
size_type count(const key_type& x)
const { return t.count(x); }
iterator lower_bound(const key_type& x)
const
{
return t.lower_bound(x);
}
iterator upper_bound(const key_type& x)
const
{
return t.upper_bound(x);
}
pair<iterator,iterator> equal_range(const key_type& x)
const
{
return t.equal_range(x);
}
friend bool
operator== __STL_NULL_TMPL_ARGS (const set&,
const set&);
friend bool
operator< __STL_NULL_TMPL_ARGS (const set&,
const set&);
};
template<class Key,
class Compare, class Alloc>
inline bool
operator==(const set<Key, Compare, Alloc>& x,
const set<Key, Compare, Alloc>& y)
{
return x.t == y.t;
}
template<class Key,
class Compare, class Alloc>
inline bool
operator<(const set<Key, Compare, Alloc>& x,
const set<Key, Compare, Alloc>& y)
{
return x.t < y.t;
}
//
总结
//没什么好总结的,这里只是不断调用底层的东西,没有技术可言
}
//map
{
/*
map概述:
和set不同的就是,多了一个值的概念,每一个键都可以存储一个实值
排序是根据key(键)来排序的。一般都是根据key来取其中的值。
和set一样的原理,我们不能改变键。和set不同的是,可以改变data(实值)
实值只是节点所存储的东西,当然可以改,改了不会影响排序
*/
//struct pair
template<class T1,
class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair() : first(T1()), second(T2()){}
pair(const T1& a,const T2& b) : first(a), second(b){}
};
template<class Key,
class T, class Compare = less<Key>,
class Alloc = alloc>
class map
{
public:
typedef Key key_type;
typedef T data_type;
typedef T mapped_type;
typedef pair<const Key, T> value_type;
typedef Compare key_compare;
typedef Compare value_compare;
class value_compare
:
public binary_function<value_type, value_type,
bool>
{
friend class map<Key, T, Compare, Alloc>;
protected:
Compare comp;
value_compare(Compare c) : comp(c) {}
public:
bool operator()(const value_type& x,
const value_type& y)
const
{
return comp(x.first, y.first);
}
};
private:
typedef rb_tree<key_type, value_type,
select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t;
public:
typedef typename rep_type::pointer pointer;
typedef typename rep_type::const_pointer const_pointer;
typedef typename rep_type::reference reference;
typedef typename rep_type::const_reference const_reference;
typedef typename rep_type::iterator iterator;
typedef typename rep_type::const_iterator const_iterator;
typedef typename rep_type::reverse_iterator reverse_iterator;
typedef typename rep_type::const_reverse_iterator const_reverse_iterator;
typedef typename rep_type::size_type size_type;
typedef typename rep_type::difference_type difference_type;
map() : t(Compare()){}
explicit map(const Compare& comp) : t(comp){}
//inset_unique
是不允许相同值出现的插入
template<class InputIterator>
map(InputIterator first, InputIterator last)
: t(Compare()){ t.insert_unique(first, last);}
template<class InputIterator>
map(InputIterator first, InputIterator last,const Compare& comp)
: t(comp){t.insert_unique(first, last);}
map(const set<Key, Compare, Alloc>& x): t(x.t){}
map<Key, Compare, Alloc>&
operator=(const map<Key, Compare, Alloc>& x)
{
t = x.t;
return *this;
}
key_compare key_comp()
const { return t.key_comp();}
value_compare value_comp()
const { return t.value_compare(t.key_comp());}
iterator begin()
const { return t.begin();}
iterator end()
const { return t.end();}
reverse_iterator rbegin()
const { return t.rbegin();}
reverse_iterator rend()
const { return t.end();}
bool empty()
const { return t.empty();}
size_type size()
const { return t.size();}
size_type max_size()
const { return t.max_size();}
void swap(set<Key, Compare, Alloc>& x) { t.swap(x.t);}
//map可以根据
键 来取
值, 如果不存在就插入一个新的
键值对
T&
operator[] (const key_type& k)
{
return (*((insert(value_type(k,T()))).first)).second;
}
//insert erase
pair<iterator,
bool> inset(const value_type& x)
{
pair<typename rep_type::iterator,
bool> p =t.insert_unique(x);
return pair<iterator,
bool>(p.first, p.second);
}
iterator insert(iterator position,
const value_type& x)
{
typedef typename rep_type::iterator rep_iterator;
return t.insert_unique((rep_iterator&)position, x);
}
template<class InputIterator>
void insert(InputIterator first, InputIterator last)
{
t.insert_unique(first, last);
}
void erase(iterator position)
{
typedef typename rep_type::iterator rep_iterator;
t.erase((rep_iterator&)position);
}
size_type erase(const key_type& x)
{
return t.erase(x);
}
void erase(iterator first, iterator last)
{
typedef typename rep_type::iterator rep_iterator;
t.erase((rep_iterator&)first, (rep_iterator&)last);
}
void clear() { t.clear();}
//
iterator find(const key_type& x)
const { return t.find(x); }
size_type count(const key_type& x)
const { return t.count(x); }
iterator lower_bound(const key_type& x)
const
{
return t.lower_bound(x);
}
iterator upper_bound(const key_type& x)
const
{
return t.upper_bound(x);
}
pair<iterator,iterator> equal_range(const key_type& x)
const
{
return t.equal_range(x);
}
friend bool
operator== __STL_NULL_TMPL_ARGS (const set&,
const set&);
friend bool
operator< __STL_NULL_TMPL_ARGS (const set&,
const set&);
};
template<class Key,
class Compare, class Alloc>
inline bool
operator==(const set<Key, Compare, Alloc>& x,
const set<Key, Compare, Alloc>& y)
{
return x.t == y.t;
}
template<class Key,
class Compare, class Alloc>
inline bool
operator<(const set<Key, Compare, Alloc>& x,
const set<Key, Compare, Alloc>& y)
{
return x.t < y.t;
}
/*
总结:
map和set不同的是有了data这个概念,并且可以更改这个data值了
set插入时插的就是key, map插入时插的是value(键值对)
插入时,函数会调用keyofvalue仿函数取得value的key
之后排序会根据key_compare(也就是模版参数中的Compare)来比较key的大小
最后都是用key来比较的,不同的是set存的值也是key,map存的值是data。
*/
}
//multiset 和multimap
/*
这两个容器和之前的基本相同,不同的就是把inset_unique改成inset_equel
具体的底层实现在RB_tree
中已经实现了,只要调用就行了
*/
最新文章
- jmx完整示例
- jQuery.uploadify-----文件上传带进度条,支持多文件上传的插件
- 如何从官网下载springframework和document
- Nginx + PHP 缓存详解
- 使用weka进行Cross-validation实验
- visual studio 资源视图 空白 解决方案
- 【 枚举 Enum 】循环 名称与值
- JS闭包经典例题
- android使用xfire webservice框架远程对sqlserver操作(包括增删改查)的实例!!已在真机上试验通过
- java基本输入型数据Scanner
- index.do为后缀的是什么开发语言? 有什么技术特点?
- javascript设计模式之解释器模式详解
- 工作中git 操作汇总
- 为什么不要在viewDidLoad方法中设置开始监听键盘通知
- SQL 农经权数据库问题提取_身份证号码相同(字段值出现多次);身份证号码相同但姓名不同(A字段相同,B字段不相同);发包方无承包方信息(A表有,B表无)等
- 2017-2018-2 20155228 《网络对抗技术》 实验三:MAL_免杀原理与实践
- java实现将指定文件夹里所有文件路径输出到指定文件作为参数化文件给lr脚本使用
- 第一章02: 常用的DOS命令
- netbeans增加yii的代码提示
- 洛谷P2303 [SDOi2012] Longge的问题 数论