作者:心只为你跳国 | 来源:互联网 | 2023-02-06 23:44
map--------------------------------------------------------------------------------所有元素
本文为senlie原创,转载请保留此地址:http://blog.csdn.net/zhengsenlie
map
--------------------------------------------------------------------------------
所有元素都会根据元素的键值自动被排序。
map的所有元素都是 pair,同时拥有实值和键值。
不可以修改元素的键值,因为它关系到 map 元素的排列规则
可以修改元素的实值,因为它不影响 map 的排列规则
map iterator 既不是一种 constant iterators , 也不是一种 mutable iterator
标准 STL map 以 RB-tree 为底层机制。
multimap 和 map 基本一样,只不过在插入的时候调用的是底层 RB-tree 的 insert_equal(),允许元素重复
图 5-20
示例:
struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) <0;
}
};
int main()
{
map months;
months["january"] = 31; //这里调用了两个函数, 先调用 map 的operator[] 函数返回键值对应实值的引用, 再调用该实值类型的 operator= 函数进行赋值
months["february"] = 28;
months["march"] = 31;
months["april"] = 30;
months["may"] = 31;
months["june"] = 30;
months["july"] = 31;
months["august"] = 31;
months["september"] = 30;
months["october"] = 31;
months["november"] = 30;
months["december"] = 31;
cout <<"june -> " <::iterator cur = months.find("june");
map::iterator prev = cur;
map::iterator next = cur;
++next;
--prev;
cout <<"Previous (in alphabetical order) is " <<(*prev).first <
源码:
//stl_pair.h里 pair 的定义
template
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) {}
#ifdef __STL_MEMBER_TEMPLATES
template
pair(const pair& p) : first(p.first), second(p.second) {}
#endif
};
//stl_map.h 源码
#ifndef __SGI_STL_INTERNAL_MAP_H
#define __SGI_STL_INTERNAL_MAP_H
__STL_BEGIN_NAMESPACE
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1174
#endif
#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template , class Alloc = alloc>
#else
template
#endif
class map {
public:
// typedefs:
typedef Key key_type; //键值类型
typedef T data_type; //数值类型
typedef T mapped_type;
typedef pair value_type; //元素类型(键值/实值)
typedef Compare key_compare; //键值比较函数
// functor, 其作用是调用 "元素比较函数"
class value_compare
: public binary_function {
friend class map;
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); //以 x, y 的键值调用了键值比较函数
}
};
private:
typedef rb_tree, key_compare, Alloc> rep_type;
rep_type t; // 以红黑树表现 map
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;
//set 的 iterator 定义为 const ,因为它不允许改变 set 里的值
//map 的 iterator 不定义为 const,因为它虽不允许改变键值,但允许改变实值
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;
// allocation/deallocation
map() : t(Compare()) {}
explicit map(const Compare& comp) : t(comp) {}// 传递 Compare() 产生的函数对象给底层的红黑树作为初始化时设定的比较函数
//不允许键值重复,所以只能使用 RB-tree 的 insert_unique()
#ifdef __STL_MEMBER_TEMPLATES
template
map(InputIterator first, InputIterator last)
: t(Compare()) { t.insert_unique(first, last); }
template
map(InputIterator first, InputIterator last, const Compare& comp)
: t(comp) { t.insert_unique(first, last); }
#else
map(const value_type* first, const value_type* last)
: t(Compare()) { t.insert_unique(first, last); }
map(const value_type* first, const value_type* last, const Compare& comp)
: t(comp) { t.insert_unique(first, last); }
map(const_iterator first, const_iterator last)
: t(Compare()) { t.insert_unique(first, last); }
map(const_iterator first, const_iterator last, const Compare& comp)
: t(comp) { t.insert_unique(first, last); }
#endif /* __STL_MEMBER_TEMPLATES */
map(const map& x) : t(x.t) {}
map& operator=(const map& x)
{
t = x.t; // 调用了底层红黑树的 operator= 函数
return *this;
}
//以下所有的 map 操作行为,RB-tree 都已提供,所以 map 只要调用即可
// accessors:
key_compare key_comp() const { return t.key_comp(); }
value_compare value_comp() const { return value_compare(t.key_comp()); }
iterator begin() { return t.begin(); }
const_iterator begin() const { return t.begin(); }
iterator end() { return t.end(); }
const_iterator end() const { return t.end(); }
reverse_iterator rbegin() { return t.rbegin(); }
const_reverse_iterator rbegin() const { return t.rbegin(); }
reverse_iterator rend() { return t.rend(); }
const_reverse_iterator rend() const { return t.rend(); }
bool empty() const { return t.empty(); }
size_type size() const { return t.size(); }
size_type max_size() const { return t.max_size(); }
T& operator[](const key_type& k) {
return (*((insert(value_type(k, T()))).first)).second;
}
void swap(map& x) { t.swap(x.t); }
// insert/erase
pair insert(const value_type& x) { return t.insert_unique(x); }
iterator insert(iterator position, const value_type& x) {
return t.insert_unique(position, x);
}
#ifdef __STL_MEMBER_TEMPLATES
template
void insert(InputIterator first, InputIterator last) {
t.insert_unique(first, last);
}
#else
void insert(const value_type* first, const value_type* last) {
t.insert_unique(first, last);
}
void insert(const_iterator first, const_iterator last) {
t.insert_unique(first, last);
}
#endif /* __STL_MEMBER_TEMPLATES */
void erase(iterator position) { t.erase(position); }
size_type erase(const key_type& x) { return t.erase(x); }
void erase(iterator first, iterator last) { t.erase(first, last); }
void clear() { t.clear(); }
// map operations:
iterator find(const key_type& x) { return t.find(x); }
const_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) {return t.lower_bound(x); }
const_iterator lower_bound(const key_type& x) const {
return t.lower_bound(x);
}
iterator upper_bound(const key_type& x) {return t.upper_bound(x); }
const_iterator upper_bound(const key_type& x) const {
return t.upper_bound(x);
}
pair equal_range(const key_type& x) {
return t.equal_range(x);
}
pair equal_range(const key_type& x) const {
return t.equal_range(x);
}
friend bool operator== __STL_NULL_TMPL_ARGS (const map&, const map&);
friend bool operator<__STL_NULL_TMPL_ARGS (const map&, const map&);
};
template
inline bool operator==(const map& x,
const map& y) {
return x.t == y.t;
}
template
inline bool operator<(const map& x,
const map& y) {
return x.t
inline void swap(map& x,
map& y) {
x.swap(y);
}
#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1174
#endif
__STL_END_NAMESPACE
#endif /* __SGI_STL_INTERNAL_MAP_H */
// Local Variables:
// mode:C++
// End:
STL源码剖析 容器 stl_map.h,,
STL源码剖析 容器 stl_map.h