在此文章之前呢 我分享一下我学习C++中的STL源码的心得 最开始学习的是vector和string 这一部分实现起来比较简单 具体可以去看看我前面写的博客 然后就是stack和queue这部分序列式就是所谓的站和队列 这部分我没有以博客的形式呈现出来 具体大家可以去参考一下stack和queue的STL源码 然后就是学的list容器 这部分也比较简单 大家感兴趣可以去看看我写的博客 也是写到了的 然后就是deque双端队列这部分大家可以去参考侯捷老师的STL源码剖析shizhi 我下面也会给大家把图片和源代码给大家呈现出来 最后就是我们今天要讲解的map和set以及unordered_map和unordered_set以及我们的重点HashTable 那么我们就开始我们的今天的哈希的学习 注意今天这部分内容算是C++里面最难的内容 哈希表大概涉及了C++中的模板和泛型编程以及含函数和迭代器——所谓的smart poniter智能指针以及我们的继承多态和封装的知识
1.stack序列式容器
stack官方文档
- stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作
- stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出
- stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
empty：判空操作
back：获取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部删除元素操作 - 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque
2.queue序列式容器
queue序列式容器官方文档
- 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素
- 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列
- 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列 - 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque
3.priority_queue序列式容器
priority_queue是一个优先级队列 大概解释如下
- 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的
- 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)
- 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部
- 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素 - 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector
- 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作
priority_queue的底层模拟实现如下
#pragma once
#include <iostream>
using namespace std;
#include <vector>
// priority_queue--->堆
namespace bite
{
template<class T>
struct less
{
bool operator()(const T& left, const T& right)
{
return left < right;
}
};
template<class T>
struct greater
{
bool operator()(const T& left, const T& right)
{
return left > right;
}
};
template<class T, class Container = std::vector<T>, class Compare = less<T>>
class priority_queue
{
public:
// 创造空的优先级队列
priority_queue() : c() {}
template<class Iterator>
priority_queue(Iterator first, Iterator last)
: c(first, last)
{
// 将c中的元素调整成堆的结构
int count = c.size();
int root = ((count - 2) >> 1);
for (; root >= 0; root--)
AdjustDown(root);
}
void push(const T& data)
{
c.push_back(data);
AdjustUP(c.size() - 1);
}
void pop()
{
if (empty())
return;
swap(c.front(), c.back());
c.pop_back();
AdjustDown(0);
}
size_t size()const
{
return c.size();
}
bool empty()const
{
return c.empty();
}
// 堆顶元素不允许修改，因为：堆顶元素修改可以会破坏堆的特性
const T& top()const
{
return c.front();
}
private:
// 向上调整
void AdjustUP(int child)
{
int parent = ((child - 1) >> 1);
while (child)
{
if (Compare()(c[parent], c[child]))
{
swap(c[child], c[parent]);
child = parent;
parent = ((child - 1) >> 1);
}
else
{
return;
}
}
}
// 向下调整
void AdjustDown(int parent)
{
size_t child = parent * 2 + 1;
while (child < c.size())
{
// 找以parent为根的较大的孩子
if (child + 1 < c.size() && Compare()(c[child], c[child + 1]))
child += 1;
// 检测双亲是否满足情况
if (Compare()(c[parent], c[child]))
{
swap(c[child], c[parent]);
parent = child;
child = parent * 2 + 1;
}
else
return;
}
}
private:
Container c;
};
}
void TestQueuePriority()
{
bite::priority_queue<int> q1;
q1.push(5);
q1.push(1);
q1.push(4);
q1.push(2);
q1.push(3);
q1.push(6);
cout << q1.top() << endl;
q1.pop();
q1.pop();
cout << q1.top() << endl;
vector<int> v{ 5,1,4,2,3,6 };
bite::priority_queue<int, vector<int>, bite::greater<int>> q2(v.begin(), v.end());
cout << q2.top() << endl;
q2.pop();
q2.pop();
cout << q2.top() << endl;
}
4.deque序列式容器
deque被意为双端队列 这部分应该大家很好理解
我们对比我们的vector可以发现vector是单向开口的连续空间 deque是一种双向开口的连续性空间 所谓双向开口 就是我们可以在头尾两端分别做元素的插入和删除等操作 如上图所示
我们的deque还有个所谓的中控器可以理解成一个中控数组
这个图大家应该比较好理解 大概意思就是通过中控数组去指向你想要的那部分缓冲区或者是空间 cur指向当前节点 first指向开始 last指向结束 在vector中我们是分为finish和end_of_storage两部分 finish是指向和first对应的结尾部分 end_of_storage是指向的你的空间大小
但是下面这个图片你可能会有点疑惑 那我们来看看吧
这里的cur和first还有我们的last和我们上述的是一个意思 map指向的还是一个中控数组 node是我们的节点的意思 node指向的是哪一个deque的buffer 我们就在哪个buffer里面进行我们的查找和删除等操作 但是这里注明的start个finish是一个迭代器 大概意思就是我们现在这里有一串数 我们首先要将迭代器进行typename实例化 让编译器知道他是一个迭代器 或者说是一个类型 这样我们就可以使用我们C++11中的基于范围的for循环了 来遍历了 通俗来讲 迭代器我们暂且可以理解成一个指针 后续我会单独对于迭代器这部分大的章节给大家写一篇博客详细讲解一下 这个图片相信大家一定是看明白了
下面我将stack和queue以及deque的底层代码给大家呈现出来 大家作为了解就可以了 和先前的vector序列是容器是大同小异的 deque有点难理解 但是还是建议大家看一看源码 知道这个容器的来龙去脉
#ifndef __SGI_STL_INTERNAL_STACK_H
#define __SGI_STL_INTERNAL_STACK_H
#include <sequence_concepts.h>
__STL_BEGIN_NAMESPACE
// Forward declarations of operators == and <, needed for friend declaration.
template <class _Tp,
class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(deque<_Tp>) >
class stack;
template <class _Tp, class _Seq>
bool operator==(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y);
template <class _Tp, class _Seq>
bool operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y);
template <class _Tp, class _Sequence>
class stack {
// requirements:
__STL_CLASS_REQUIRES(_Tp, _Assignable);
__STL_CLASS_REQUIRES(_Sequence, _BackInsertionSequence);
typedef typename _Sequence::value_type _Sequence_value_type;
__STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Sequence_value_type);
#ifdef __STL_MEMBER_TEMPLATES
template <class _Tp1, class _Seq1>
friend bool operator== (const stack<_Tp1, _Seq1>&,
const stack<_Tp1, _Seq1>&);
template <class _Tp1, class _Seq1>
friend bool operator< (const stack<_Tp1, _Seq1>&,
const stack<_Tp1, _Seq1>&);
#else /* __STL_MEMBER_TEMPLATES */
friend bool __STD_QUALIFIER
operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
friend bool __STD_QUALIFIER
operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
#endif /* __STL_MEMBER_TEMPLATES */
public:
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
protected:
_Sequence c;
public:
stack() : c() {}
explicit stack(const _Sequence& __s) : c(__s) {}
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference top() { return c.back(); }
const_reference top() const { return c.back(); }
void push(const value_type& __x) { c.push_back(__x); }
void pop() { c.pop_back(); }
};
template <class _Tp, class _Seq>
bool operator==(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
{
return __x.c == __y.c;
}
template <class _Tp, class _Seq>
bool operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
{
return __x.c < __y.c;
}
#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
template <class _Tp, class _Seq>
bool operator!=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
{
return !(__x == __y);
}
template <class _Tp, class _Seq>
bool operator>(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
{
return __y < __x;
}
template <class _Tp, class _Seq>
bool operator<=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
{
return !(__y < __x);
}
template <class _Tp, class _Seq>
bool operator>=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
{
return !(__x < __y);
}
#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
__STL_END_NAMESPACE
#endif /* __SGI_STL_INTERNAL_STACK_H */
// Local Variables:
// mode:C++
// End:
__STL_BEGIN_NAMESPACE
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1174
#pragma set woff 1375
#endif
// Note: this function is simply a kludge to work around several compilers'
// bugs in handling constant expressions.
inline size_t __deque_buf_size(size_t __size) {
return __size < 512 ? size_t(512 / __size) : size_t(1);
}
template <class _Tp, class _Ref, class _Ptr>
struct _Deque_iterator {
typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Ptr pointer;
typedef _Ref reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Tp** _Map_pointer;
typedef _Deque_iterator _Self;
_Tp* _M_cur;
_Tp* _M_first;
_Tp* _M_last;
_Map_pointer _M_node;
_Deque_iterator(_Tp* __x, _Map_pointer __y)
: _M_cur(__x), _M_first(*__y),
_M_last(*__y + _S_buffer_size()), _M_node(__y) {}
_Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
_Deque_iterator(const iterator& __x)
: _M_cur(__x._M_cur), _M_first(__x._M_first),
_M_last(__x._M_last), _M_node(__x._M_node) {}
reference operator*() const { return *_M_cur; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return _M_cur; }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
difference_type operator-(const _Self& __x) const {
return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
(_M_cur - _M_first) + (__x._M_last - __x._M_cur);
}
_Self& operator++() {
++_M_cur;
if (_M_cur == _M_last) {
_M_set_node(_M_node + 1);
_M_cur = _M_first;
}
return *this;
}
_Self operator++(int) {
_Self __tmp = *this;
++*this;
return __tmp;
}
_Self& operator--() {
if (_M_cur == _M_first) {
_M_set_node(_M_node - 1);
_M_cur = _M_last;
}
--_M_cur;
return *this;
}
_Self operator--(int) {
_Self __tmp = *this;
--*this;
return __tmp;
}
_Self& operator+=(difference_type __n)
{
difference_type __offset = __n + (_M_cur - _M_first);
if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
_M_cur += __n;
else {
difference_type __node_offset =
__offset > 0 ? __offset / difference_type(_S_buffer_size())
: -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
_M_set_node(_M_node + __node_offset);
_M_cur = _M_first +
(__offset - __node_offset * difference_type(_S_buffer_size()));
}
return *this;
}
_Self operator+(difference_type __n) const
{
_Self __tmp = *this;
return __tmp += __n;
}
_Self& operator-=(difference_type __n) { return *this += -__n; }
_Self operator-(difference_type __n) const {
_Self __tmp = *this;
return __tmp -= __n;
}
reference operator[](difference_type __n) const { return *(*this + __n); }
bool operator==(const _Self& __x) const { return _M_cur == __x._M_cur; }
bool operator!=(const _Self& __x) const { return !(*this == __x); }
bool operator<(const _Self& __x) const {
return (_M_node == __x._M_node) ?
(_M_cur < __x._M_cur) : (_M_node < __x._M_node);
}
bool operator>(const _Self& __x) const { return __x < *this; }
bool operator<=(const _Self& __x) const { return !(__x < *this); }
bool operator>=(const _Self& __x) const { return !(*this < __x); }
void _M_set_node(_Map_pointer __new_node) {
_M_node = __new_node;
_M_first = *__new_node;
_M_last = _M_first + difference_type(_S_buffer_size());
}
};
template <class _Tp, class _Ref, class _Ptr>
inline _Deque_iterator<_Tp, _Ref, _Ptr>
operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
{
return __x + __n;
}
#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
template <class _Tp, class _Ref, class _Ptr>
inline random_access_iterator_tag
iterator_category(const _Deque_iterator<_Tp,_Ref,_Ptr>&)
{
return random_access_iterator_tag();
}
template <class _Tp, class _Ref, class _Ptr>
inline _Tp* value_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) { return 0; }
template <class _Tp, class _Ref, class _Ptr>
inline ptrdiff_t* distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) {
return 0;
}
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
// Deque base class. It has two purposes. First, its constructor
// and destructor allocate (but don't initialize) storage. This makes
// exception safety easier. Second, the base class encapsulates all of
// the differences between SGI-style allocators and standard-conforming
// allocators.
#ifdef __STL_USE_STD_ALLOCATORS
// Base class for ordinary allocators.
template <class _Tp, class _Alloc, bool __is_static>
class _Deque_alloc_base {
public:
typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
allocator_type get_allocator() const { return _M_node_allocator; }
_Deque_alloc_base(const allocator_type& __a)
: _M_node_allocator(__a), _M_map_allocator(__a),
_M_map(0), _M_map_size(0)
{}
protected:
typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type
_Map_allocator_type;
allocator_type _M_node_allocator;
_Map_allocator_type _M_map_allocator;
_Tp* _M_allocate_node() {
return _M_node_allocator.allocate(__deque_buf_size(sizeof(_Tp)));
}
void _M_deallocate_node(_Tp* __p) {
_M_node_allocator.deallocate(__p, __deque_buf_size(sizeof(_Tp)));
}
_Tp** _M_allocate_map(size_t __n)
{ return _M_map_allocator.allocate(__n); }
void _M_deallocate_map(_Tp** __p, size_t __n)
{ _M_map_allocator.deallocate(__p, __n); }
_Tp** _M_map;
size_t _M_map_size;
};
// Specialization for instanceless allocators.
template <class _Tp, class _Alloc>
class _Deque_alloc_base<_Tp, _Alloc, true>
{
public:
typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
_Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {}
protected:
typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type;
typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type;
_Tp* _M_allocate_node() {
return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
}
void _M_deallocate_node(_Tp* __p) {
_Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
}
_Tp** _M_allocate_map(size_t __n)
{ return _Map_alloc_type::allocate(__n); }
void _M_deallocate_map(_Tp** __p, size_t __n)
{ _Map_alloc_type::deallocate(__p, __n); }
_Tp** _M_map;
size_t _M_map_size;
};
template <class _Tp, class _Alloc>
class _Deque_base
: public _Deque_alloc_base<_Tp,_Alloc,
_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
{
public:
typedef _Deque_alloc_base<_Tp,_Alloc,
_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
_Base;
typedef typename _Base::allocator_type allocator_type;
typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator;
typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
_Deque_base(const allocator_type& __a, size_t __num_elements)
: _Base(__a), _M_start(), _M_finish()
{ _M_initialize_map(__num_elements); }
_Deque_base(const allocator_type& __a)
: _Base(__a), _M_start(), _M_finish() {}
~_Deque_base();
protected:
void _M_initialize_map(size_t);
void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
enum { _S_initial_map_size = 8 };
protected:
iterator _M_start;
iterator _M_finish;
};
#else /* __STL_USE_STD_ALLOCATORS */
template <class _Tp, class _Alloc>
class _Deque_base {
public:
typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator;
typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
typedef _Alloc allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
_Deque_base(const allocator_type&, size_t __num_elements)
: _M_map(0), _M_map_size(0), _M_start(), _M_finish() {
_M_initialize_map(__num_elements);
}
_Deque_base(const allocator_type&)
: _M_map(0), _M_map_size(0), _M_start(), _M_finish() {}
~_Deque_base();
protected:
void _M_initialize_map(size_t);
void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
enum { _S_initial_map_size = 8 };
protected:
_Tp** _M_map;
size_t _M_map_size;
iterator _M_start;
iterator _M_finish;
typedef simple_alloc<_Tp, _Alloc> _Node_alloc_type;
typedef simple_alloc<_Tp*, _Alloc> _Map_alloc_type;
_Tp* _M_allocate_node()
{ return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); }
void _M_deallocate_node(_Tp* __p)
{ _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); }
_Tp** _M_allocate_map(size_t __n)
{ return _Map_alloc_type::allocate(__n); }
void _M_deallocate_map(_Tp** __p, size_t __n)
{ _Map_alloc_type::deallocate(__p, __n); }
};
#endif /* __STL_USE_STD_ALLOCATORS */
// Non-inline member functions from _Deque_base.
template <class _Tp, class _Alloc>
_Deque_base<_Tp,_Alloc>::~_Deque_base() {
if (_M_map) {
_M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
_M_deallocate_map(_M_map, _M_map_size);
}
}
template <class _Tp, class _Alloc>
void
_Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
{
size_t __num_nodes =
__num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
_M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
_M_map = _M_allocate_map(_M_map_size);
_Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
_Tp** __nfinish = __nstart + __num_nodes;
__STL_TRY {
_M_create_nodes(__nstart, __nfinish);
}
__STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size),
_M_map = 0, _M_map_size = 0));
_M_start._M_set_node(__nstart);
_M_finish._M_set_node(__nfinish - 1);
_M_start._M_cur = _M_start._M_first;
_M_finish._M_cur = _M_finish._M_first +
__num_elements % __deque_buf_size(sizeof(_Tp));
}
template <class _Tp, class _Alloc>
void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
{
_Tp** __cur;
__STL_TRY {
for (__cur = __nstart; __cur < __nfinish; ++__cur)
*__cur = _M_allocate_node();
}
__STL_UNWIND(_M_destroy_nodes(__nstart, __cur));
}
template <class _Tp, class _Alloc>
void
_Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
{
for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
_M_deallocate_node(*__n);
}
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class deque : protected _Deque_base<_Tp, _Alloc> {
// requirements:
__STL_CLASS_REQUIRES(_Tp, _Assignable);
typedef _Deque_base<_Tp, _Alloc> _Base;
public: // Basic types
typedef _Tp value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef typename _Base::allocator_type allocator_type;
allocator_type get_allocator() const { return _Base::get_allocator(); }
public: // Iterators
typedef typename _Base::iterator iterator;
typedef typename _Base::const_iterator const_iterator;
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
typedef reverse_iterator<const_iterator, value_type, const_reference,
difference_type>
const_reverse_iterator;
typedef reverse_iterator<iterator, value_type, reference, difference_type>
reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
protected: // Internal typedefs
typedef pointer* _Map_pointer;
static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
protected:
#ifdef __STL_USE_NAMESPACES
using _Base::_M_initialize_map;
using _Base::_M_create_nodes;
using _Base::_M_destroy_nodes;
using _Base::_M_allocate_node;
using _Base::_M_deallocate_node;
using _Base::_M_allocate_map;
using _Base::_M_deallocate_map;
using _Base::_M_map;
using _Base::_M_map_size;
using _Base::_M_start;
using _Base::_M_finish;
#endif /* __STL_USE_NAMESPACES */
public: // Basic accessors
iterator begin() { return _M_start; }
iterator end() { return _M_finish; }
const_iterator begin() const { return _M_start; }
const_iterator end() const { return _M_finish; }
reverse_iterator rbegin() { return reverse_iterator(_M_finish); }
reverse_iterator rend() { return reverse_iterator(_M_start); }
const_reverse_iterator rbegin() const
{ return const_reverse_iterator(_M_finish); }
const_reverse_iterator rend() const
{ return const_reverse_iterator(_M_start); }
reference operator[](size_type __n)
{ return _M_start[difference_type(__n)]; }
const_reference operator[](size_type __n) const
{ return _M_start[difference_type(__n)]; }
#ifdef __STL_THROW_RANGE_ERRORS
void _M_range_check(size_type __n) const {
if (__n >= this->size())
__stl_throw_range_error("deque");
}
reference at(size_type __n)
{ _M_range_check(__n); return (*this)[__n]; }
const_reference at(size_type __n) const
{ _M_range_check(__n); return (*this)[__n]; }
#endif /* __STL_THROW_RANGE_ERRORS */
reference front() { return *_M_start; }
reference back() {
iterator __tmp = _M_finish;
--__tmp;
return *__tmp;
}
const_reference front() const { return *_M_start; }
const_reference back() const {
const_iterator __tmp = _M_finish;
--__tmp;
return *__tmp;
}
size_type size() const { return _M_finish - _M_start; }
size_type max_size() const { return size_type(-1); }
bool empty() const { return _M_finish == _M_start; }
public: // Constructor, destructor.
explicit deque(const allocator_type& __a = allocator_type())
: _Base(__a, 0) {}
deque(const deque& __x) : _Base(__x.get_allocator(), __x.size())
{ uninitialized_copy(__x.begin(), __x.end(), _M_start); }
deque(size_type __n, const value_type& __value,
const allocator_type& __a = allocator_type()) : _Base(__a, __n)
{ _M_fill_initialize(__value); }
explicit deque(size_type __n) : _Base(allocator_type(), __n)
{ _M_fill_initialize(value_type()); }
#ifdef __STL_MEMBER_TEMPLATES
// Check whether it's an integral type. If so, it's not an iterator.
template <class _InputIterator>
deque(_InputIterator __first, _InputIterator __last,
const allocator_type& __a = allocator_type()) : _Base(__a) {
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_initialize_dispatch(__first, __last, _Integral());
}
template <class _Integer>
void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
_M_initialize_map(__n);
_M_fill_initialize(__x);
}
template <class _InputIter>
void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
__false_type) {
_M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
}
#else /* __STL_MEMBER_TEMPLATES */
deque(const value_type* __first, const value_type* __last,
const allocator_type& __a = allocator_type())
: _Base(__a, __last - __first)
{ uninitialized_copy(__first, __last, _M_start); }
deque(const_iterator __first, const_iterator __last,
const allocator_type& __a = allocator_type())
: _Base(__a, __last - __first)
{ uninitialized_copy(__first, __last, _M_start); }
#endif /* __STL_MEMBER_TEMPLATES */
~deque() { destroy(_M_start, _M_finish); }
deque& operator= (const deque& __x) {
const size_type __len = size();
if (&__x != this) {
if (__len >= __x.size())
erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
else {
const_iterator __mid = __x.begin() + difference_type(__len);
copy(__x.begin(), __mid, _M_start);
insert(_M_finish, __mid, __x.end());
}
}
return *this;
}
void swap(deque& __x) {
__STD::swap(_M_start, __x._M_start);
__STD::swap(_M_finish, __x._M_finish);
__STD::swap(_M_map, __x._M_map);
__STD::swap(_M_map_size, __x._M_map_size);
}
public:
// assign(), a generalized assignment member function. Two
// versions: one that takes a count, and one that takes a range.
// The range version is a member template, so we dispatch on whether
// or not the type is an integer.
void _M_fill_assign(size_type __n, const _Tp& __val) {
if (__n > size()) {
fill(begin(), end(), __val);
insert(end(), __n - size(), __val);
}
else {
erase(begin() + __n, end());
fill(begin(), end(), __val);
}
}
void assign(size_type __n, const _Tp& __val) {
_M_fill_assign(__n, __val);
}
#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
void assign(_InputIterator __first, _InputIterator __last) {
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_assign_dispatch(__first, __last, _Integral());
}
private: // helper functions for assign()
template <class _Integer>
void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
{ _M_fill_assign((size_type) __n, (_Tp) __val); }
template <class _InputIterator>
void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
__false_type) {
_M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first));
}
template <class _InputIterator>
void _M_assign_aux(_InputIterator __first, _InputIterator __last,
input_iterator_tag);
template <class _ForwardIterator>
void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag) {
size_type __len = 0;
distance(__first, __last, __len);
if (__len > size()) {
_ForwardIterator __mid = __first;
advance(__mid, size());
copy(__first, __mid, begin());
insert(end(), __mid, __last);
}
else
erase(copy(__first, __last, begin()), end());
}
#endif /* __STL_MEMBER_TEMPLATES */
public: // push_* and pop_*
void push_back(const value_type& __t) {
if (_M_finish._M_cur != _M_finish._M_last - 1) {
construct(_M_finish._M_cur, __t);
++_M_finish._M_cur;
}
else
_M_push_back_aux(__t);
}
void push_back() {
if (_M_finish._M_cur != _M_finish._M_last - 1) {
construct(_M_finish._M_cur);
++_M_finish._M_cur;
}
else
_M_push_back_aux();
}
void push_front(const value_type& __t) {
if (_M_start._M_cur != _M_start._M_first) {
construct(_M_start._M_cur - 1, __t);
--_M_start._M_cur;
}
else
_M_push_front_aux(__t);
}
void push_front() {
if (_M_start._M_cur != _M_start._M_first) {
construct(_M_start._M_cur - 1);
--_M_start._M_cur;
}
else
_M_push_front_aux();
}
void pop_back() {
if (_M_finish._M_cur != _M_finish._M_first) {
--_M_finish._M_cur;
destroy(_M_finish._M_cur);
}
else
_M_pop_back_aux();
}
void pop_front() {
if (_M_start._M_cur != _M_start._M_last - 1) {
destroy(_M_start._M_cur);
++_M_start._M_cur;
}
else
_M_pop_front_aux();
}
public: // Insert
iterator insert(iterator position, const value_type& __x) {
if (position._M_cur == _M_start._M_cur) {
push_front(__x);
return _M_start;
}
else if (position._M_cur == _M_finish._M_cur) {
push_back(__x);
iterator __tmp = _M_finish;
--__tmp;
return __tmp;
}
else {
return _M_insert_aux(position, __x);
}
}
iterator insert(iterator __position)
{ return insert(__position, value_type()); }
void insert(iterator __pos, size_type __n, const value_type& __x)
{ _M_fill_insert(__pos, __n, __x); }
void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
#ifdef __STL_MEMBER_TEMPLATES
// Check whether it's an integral type. If so, it's not an iterator.
template <class _InputIterator>
void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_insert_dispatch(__pos, __first, __last, _Integral());
}
template <class _Integer>
void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
__true_type) {
_M_fill_insert(__pos, (size_type) __n, (value_type) __x);
}
template <class _InputIterator>
void _M_insert_dispatch(iterator __pos,
_InputIterator __first, _InputIterator __last,
__false_type) {
insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
}
#else /* __STL_MEMBER_TEMPLATES */
void insert(iterator __pos,
const value_type* __first, const value_type* __last);
void insert(iterator __pos,
const_iterator __first, const_iterator __last);
#endif /* __STL_MEMBER_TEMPLATES */
void resize(size_type __new_size, const value_type& __x) {
const size_type __len = size();
if (__new_size < __len)
erase(_M_start + __new_size, _M_finish);
else
insert(_M_finish, __new_size - __len, __x);
}
void resize(size_type new_size) { resize(new_size, value_type()); }
public: // Erase
iterator erase(iterator __pos) {
iterator __next = __pos;
++__next;
difference_type __index = __pos - _M_start;
if (size_type(__index) < (this->size() >> 1)) {
copy_backward(_M_start, __pos, __next);
pop_front();
}
else {
copy(__next, _M_finish, __pos);
pop_back();
}
return _M_start + __index;
}
iterator erase(iterator __first, iterator __last);
void clear();
protected: // Internal construction/destruction
void _M_fill_initialize(const value_type& __value);
#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
void _M_range_initialize(_InputIterator __first, _InputIterator __last,
input_iterator_tag);
template <class _ForwardIterator>
void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag);
#endif /* __STL_MEMBER_TEMPLATES */
protected: // Internal push_* and pop_*
void _M_push_back_aux(const value_type&);
void _M_push_back_aux();
void _M_push_front_aux(const value_type&);
void _M_push_front_aux();
void _M_pop_back_aux();
void _M_pop_front_aux();
protected: // Internal insert functions
#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
void insert(iterator __pos, _InputIterator __first, _InputIterator __last,
input_iterator_tag);
template <class _ForwardIterator>
void insert(iterator __pos,
_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag);
#endif /* __STL_MEMBER_TEMPLATES */
iterator _M_insert_aux(iterator __pos, const value_type& __x);
iterator _M_insert_aux(iterator __pos);
void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
#ifdef __STL_MEMBER_TEMPLATES
template <class _ForwardIterator>
void _M_insert_aux(iterator __pos,
_ForwardIterator __first, _ForwardIterator __last,
size_type __n);
#else /* __STL_MEMBER_TEMPLATES */
void _M_insert_aux(iterator __pos,
const value_type* __first, const value_type* __last,
size_type __n);
void _M_insert_aux(iterator __pos,
const_iterator __first, const_iterator __last,
size_type __n);
#endif /* __STL_MEMBER_TEMPLATES */
iterator _M_reserve_elements_at_front(size_type __n) {
size_type __vacancies = _M_start._M_cur - _M_start._M_first;
if (__n > __vacancies)
_M_new_elements_at_front(__n - __vacancies);
return _M_start - difference_type(__n);
}
iterator _M_reserve_elements_at_back(size_type __n) {
size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
if (__n > __vacancies)
_M_new_elements_at_back(__n - __vacancies);
return _M_finish + difference_type(__n);
}
void _M_new_elements_at_front(size_type __new_elements);
void _M_new_elements_at_back(size_type __new_elements);
protected: // Allocation of _M_map and nodes
// Makes sure the _M_map has space for new nodes. Does not actually
// add the nodes. Can invalidate _M_map pointers. (And consequently,
// deque iterators.)
void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
_M_reallocate_map(__nodes_to_add, false);
}
void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
_M_reallocate_map(__nodes_to_add, true);
}
void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
};
// Non-inline member functions
#ifdef __STL_MEMBER_TEMPLATES
template <class _Tp, class _Alloc>
template <class _InputIter>
void deque<_Tp, _Alloc>
::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag)
{
iterator __cur = begin();
for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
*__cur = *__first;
if (__first == __last)
erase(__cur, end());
else
insert(end(), __first, __last);
}
#endif /* __STL_MEMBER_TEMPLATES */
template <class _Tp, class _Alloc>
void deque<_Tp, _Alloc>::_M_fill_insert(iterator __pos,
size_type __n, const value_type& __x)
{
if (__pos._M_cur == _M_start._M_cur) {
iterator __new_start = _M_reserve_elements_at_front(__n);
__STL_TRY {
uninitialized_fill(__new_start, _M_start, __x);
_M_start = __new_start;
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else if (__pos._M_cur == _M_finish._M_cur) {
iterator __new_finish = _M_reserve_elements_at_back(__n);
__STL_TRY {
uninitialized_fill(_M_finish, __new_finish, __x);
_M_finish = __new_finish;
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
else
_M_insert_aux(__pos, __n, __x);
}
#ifndef __STL_MEMBER_TEMPLATES
template <class _Tp, class _Alloc>
void deque<_Tp, _Alloc>::insert(iterator __pos,
const value_type* __first,
const value_type* __last) {
size_type __n = __last - __first;
if (__pos._M_cur == _M_start._M_cur) {
iterator __new_start = _M_reserve_elements_at_front(__n);
__STL_TRY {
uninitialized_copy(__first, __last, __new_start);
_M_start = __new_start;
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else if (__pos._M_cur == _M_finish._M_cur) {
iterator __new_finish = _M_reserve_elements_at_back(__n);
__STL_TRY {
uninitialized_copy(__first, __last, _M_finish);
_M_finish = __new_finish;
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
else
_M_insert_aux(__pos, __first, __last, __n);
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::insert(iterator __pos,
const_iterator __first, const_iterator __last)
{
size_type __n = __last - __first;
if (__pos._M_cur == _M_start._M_cur) {
iterator __new_start = _M_reserve_elements_at_front(__n);
__STL_TRY {
uninitialized_copy(__first, __last, __new_start);
_M_start = __new_start;
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else if (__pos._M_cur == _M_finish._M_cur) {
iterator __new_finish = _M_reserve_elements_at_back(__n);
__STL_TRY {
uninitialized_copy(__first, __last, _M_finish);
_M_finish = __new_finish;
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
else
_M_insert_aux(__pos, __first, __last, __n);
}
#endif /* __STL_MEMBER_TEMPLATES */
template <class _Tp, class _Alloc>
typename deque<_Tp,_Alloc>::iterator
deque<_Tp,_Alloc>::erase(iterator __first, iterator __last)
{
if (__first == _M_start && __last == _M_finish) {
clear();
return _M_finish;
}
else {
difference_type __n = __last - __first;
difference_type __elems_before = __first - _M_start;
if (__elems_before < difference_type((this->size() - __n) / 2)) {
copy_backward(_M_start, __first, __last);
iterator __new_start = _M_start + __n;
destroy(_M_start, __new_start);
_M_destroy_nodes(__new_start._M_node, _M_start._M_node);
_M_start = __new_start;
}
else {
copy(__last, _M_finish, __first);
iterator __new_finish = _M_finish - __n;
destroy(__new_finish, _M_finish);
_M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
_M_finish = __new_finish;
}
return _M_start + __elems_before;
}
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::clear()
{
for (_Map_pointer __node = _M_start._M_node + 1;
__node < _M_finish._M_node;
++__node) {
destroy(*__node, *__node + _S_buffer_size());
_M_deallocate_node(*__node);
}
if (_M_start._M_node != _M_finish._M_node) {
destroy(_M_start._M_cur, _M_start._M_last);
destroy(_M_finish._M_first, _M_finish._M_cur);
_M_deallocate_node(_M_finish._M_first);
}
else
destroy(_M_start._M_cur, _M_finish._M_cur);
_M_finish = _M_start;
}
// Precondition: _M_start and _M_finish have already been initialized,
// but none of the deque's elements have yet been constructed.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value) {
_Map_pointer __cur;
__STL_TRY {
for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value);
}
__STL_UNWIND(destroy(_M_start, iterator(*__cur, __cur)));
}
#ifdef __STL_MEMBER_TEMPLATES
template <class _Tp, class _Alloc> template <class _InputIterator>
void deque<_Tp,_Alloc>::_M_range_initialize(_InputIterator __first,
_InputIterator __last,
input_iterator_tag)
{
_M_initialize_map(0);
__STL_TRY {
for ( ; __first != __last; ++__first)
push_back(*__first);
}
__STL_UNWIND(clear());
}
template <class _Tp, class _Alloc> template <class _ForwardIterator>
void deque<_Tp,_Alloc>::_M_range_initialize(_ForwardIterator __first,
_ForwardIterator __last,
forward_iterator_tag)
{
size_type __n = 0;
distance(__first, __last, __n);
_M_initialize_map(__n);
_Map_pointer __cur_node;
__STL_TRY {
for (__cur_node = _M_start._M_node;
__cur_node < _M_finish._M_node;
++__cur_node) {
_ForwardIterator __mid = __first;
advance(__mid, _S_buffer_size());
uninitialized_copy(__first, __mid, *__cur_node);
__first = __mid;
}
uninitialized_copy(__first, __last, _M_finish._M_first);
}
__STL_UNWIND(destroy(_M_start, iterator(*__cur_node, __cur_node)));
}
#endif /* __STL_MEMBER_TEMPLATES */
// Called only if _M_finish._M_cur == _M_finish._M_last - 1.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t)
{
value_type __t_copy = __t;
_M_reserve_map_at_back();
*(_M_finish._M_node + 1) = _M_allocate_node();
__STL_TRY {
construct(_M_finish._M_cur, __t_copy);
_M_finish._M_set_node(_M_finish._M_node + 1);
_M_finish._M_cur = _M_finish._M_first;
}
__STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
}
// Called only if _M_finish._M_cur == _M_finish._M_last - 1.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_back_aux()
{
_M_reserve_map_at_back();
*(_M_finish._M_node + 1) = _M_allocate_node();
__STL_TRY {
construct(_M_finish._M_cur);
_M_finish._M_set_node(_M_finish._M_node + 1);
_M_finish._M_cur = _M_finish._M_first;
}
__STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
}
// Called only if _M_start._M_cur == _M_start._M_first.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t)
{
value_type __t_copy = __t;
_M_reserve_map_at_front();
*(_M_start._M_node - 1) = _M_allocate_node();
__STL_TRY {
_M_start._M_set_node(_M_start._M_node - 1);
_M_start._M_cur = _M_start._M_last - 1;
construct(_M_start._M_cur, __t_copy);
}
__STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
}
// Called only if _M_start._M_cur == _M_start._M_first.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_front_aux()
{
_M_reserve_map_at_front();
*(_M_start._M_node - 1) = _M_allocate_node();
__STL_TRY {
_M_start._M_set_node(_M_start._M_node - 1);
_M_start._M_cur = _M_start._M_last - 1;
construct(_M_start._M_cur);
}
__STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
}
// Called only if _M_finish._M_cur == _M_finish._M_first.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_pop_back_aux()
{
_M_deallocate_node(_M_finish._M_first);
_M_finish._M_set_node(_M_finish._M_node - 1);
_M_finish._M_cur = _M_finish._M_last - 1;
destroy(_M_finish._M_cur);
}
// Called only if _M_start._M_cur == _M_start._M_last - 1. Note that
// if the deque has at least one element (a precondition for this member
// function), and if _M_start._M_cur == _M_start._M_last, then the deque
// must have at least two nodes.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_pop_front_aux()
{
destroy(_M_start._M_cur);
_M_deallocate_node(_M_start._M_first);
_M_start._M_set_node(_M_start._M_node + 1);
_M_start._M_cur = _M_start._M_first;
}
#ifdef __STL_MEMBER_TEMPLATES
template <class _Tp, class _Alloc> template <class _InputIterator>
void deque<_Tp,_Alloc>::insert(iterator __pos,
_InputIterator __first, _InputIterator __last,
input_iterator_tag)
{
copy(__first, __last, inserter(*this, __pos));
}
template <class _Tp, class _Alloc> template <class _ForwardIterator>
void
deque<_Tp,_Alloc>::insert(iterator __pos,
_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag) {
size_type __n = 0;
distance(__first, __last, __n);
if (__pos._M_cur == _M_start._M_cur) {
iterator __new_start = _M_reserve_elements_at_front(__n);
__STL_TRY {
uninitialized_copy(__first, __last, __new_start);
_M_start = __new_start;
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else if (__pos._M_cur == _M_finish._M_cur) {
iterator __new_finish = _M_reserve_elements_at_back(__n);
__STL_TRY {
uninitialized_copy(__first, __last, _M_finish);
_M_finish = __new_finish;
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
else
_M_insert_aux(__pos, __first, __last, __n);
}
#endif /* __STL_MEMBER_TEMPLATES */
template <class _Tp, class _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x)
{
difference_type __index = __pos - _M_start;
value_type __x_copy = __x;
if (size_type(__index) < this->size() / 2) {
push_front(front());
iterator __front1 = _M_start;
++__front1;
iterator __front2 = __front1;
++__front2;
__pos = _M_start + __index;
iterator __pos1 = __pos;
++__pos1;
copy(__front2, __pos1, __front1);
}
else {
push_back(back());
iterator __back1 = _M_finish;
--__back1;
iterator __back2 = __back1;
--__back2;
__pos = _M_start + __index;
copy_backward(__pos, __back2, __back1);
}
*__pos = __x_copy;
return __pos;
}
template <class _Tp, class _Alloc>
typename deque<_Tp,_Alloc>::iterator
deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos)
{
difference_type __index = __pos - _M_start;
if (__index < size() / 2) {
push_front(front());
iterator __front1 = _M_start;
++__front1;
iterator __front2 = __front1;
++__front2;
__pos = _M_start + __index;
iterator __pos1 = __pos;
++__pos1;
copy(__front2, __pos1, __front1);
}
else {
push_back(back());
iterator __back1 = _M_finish;
--__back1;
iterator __back2 = __back1;
--__back2;
__pos = _M_start + __index;
copy_backward(__pos, __back2, __back1);
}
*__pos = value_type();
return __pos;
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
size_type __n,
const value_type& __x)
{
const difference_type __elems_before = __pos - _M_start;
size_type __length = this->size();
value_type __x_copy = __x;
if (__elems_before < difference_type(__length / 2)) {
iterator __new_start = _M_reserve_elements_at_front(__n);
iterator __old_start = _M_start;
__pos = _M_start + __elems_before;
__STL_TRY {
if (__elems_before >= difference_type(__n)) {
iterator __start_n = _M_start + difference_type(__n);
uninitialized_copy(_M_start, __start_n, __new_start);
_M_start = __new_start;
copy(__start_n, __pos, __old_start);
fill(__pos - difference_type(__n), __pos, __x_copy);
}
else {
__uninitialized_copy_fill(_M_start, __pos, __new_start,
_M_start, __x_copy);
_M_start = __new_start;
fill(__old_start, __pos, __x_copy);
}
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else {
iterator __new_finish = _M_reserve_elements_at_back(__n);
iterator __old_finish = _M_finish;
const difference_type __elems_after =
difference_type(__length) - __elems_before;
__pos = _M_finish - __elems_after;
__STL_TRY {
if (__elems_after > difference_type(__n)) {
iterator __finish_n = _M_finish - difference_type(__n);
uninitialized_copy(__finish_n, _M_finish, _M_finish);
_M_finish = __new_finish;
copy_backward(__pos, __finish_n, __old_finish);
fill(__pos, __pos + difference_type(__n), __x_copy);
}
else {
__uninitialized_fill_copy(_M_finish, __pos + difference_type(__n),
__x_copy, __pos, _M_finish);
_M_finish = __new_finish;
fill(__pos, __old_finish, __x_copy);
}
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
}
#ifdef __STL_MEMBER_TEMPLATES
template <class _Tp, class _Alloc> template <class _ForwardIterator>
void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
_ForwardIterator __first,
_ForwardIterator __last,
size_type __n)
{
const difference_type __elemsbefore = __pos - _M_start;
size_type __length = size();
if (__elemsbefore < __length / 2) {
iterator __new_start = _M_reserve_elements_at_front(__n);
iterator __old_start = _M_start;
__pos = _M_start + __elemsbefore;
__STL_TRY {
if (__elemsbefore >= difference_type(__n)) {
iterator __start_n = _M_start + difference_type(__n);
uninitialized_copy(_M_start, __start_n, __new_start);
_M_start = __new_start;
copy(__start_n, __pos, __old_start);
copy(__first, __last, __pos - difference_type(__n));
}
else {
_ForwardIterator __mid = __first;
advance(__mid, difference_type(__n) - __elemsbefore);
__uninitialized_copy_copy(_M_start, __pos, __first, __mid,
__new_start);
_M_start = __new_start;
copy(__mid, __last, __old_start);
}
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else {
iterator __new_finish = _M_reserve_elements_at_back(__n);
iterator __old_finish = _M_finish;
const difference_type __elemsafter =
difference_type(__length) - __elemsbefore;
__pos = _M_finish - __elemsafter;
__STL_TRY {
if (__elemsafter > difference_type(__n)) {
iterator __finish_n = _M_finish - difference_type(__n);
uninitialized_copy(__finish_n, _M_finish, _M_finish);
_M_finish = __new_finish;
copy_backward(__pos, __finish_n, __old_finish);
copy(__first, __last, __pos);
}
else {
_ForwardIterator __mid = __first;
advance(__mid, __elemsafter);
__uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
_M_finish = __new_finish;
copy(__first, __mid, __pos);
}
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
}
#else /* __STL_MEMBER_TEMPLATES */
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
const value_type* __first,
const value_type* __last,
size_type __n)
{
const difference_type __elemsbefore = __pos - _M_start;
size_type __length = size();
if (__elemsbefore < __length / 2) {
iterator __new_start = _M_reserve_elements_at_front(__n);
iterator __old_start = _M_start;
__pos = _M_start + __elemsbefore;
__STL_TRY {
if (__elemsbefore >= difference_type(__n)) {
iterator __start_n = _M_start + difference_type(__n);
uninitialized_copy(_M_start, __start_n, __new_start);
_M_start = __new_start;
copy(__start_n, __pos, __old_start);
copy(__first, __last, __pos - difference_type(__n));
}
else {
const value_type* __mid =
__first + (difference_type(__n) - __elemsbefore);
__uninitialized_copy_copy(_M_start, __pos, __first, __mid,
__new_start);
_M_start = __new_start;
copy(__mid, __last, __old_start);
}
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else {
iterator __new_finish = _M_reserve_elements_at_back(__n);
iterator __old_finish = _M_finish;
const difference_type __elemsafter =
difference_type(__length) - __elemsbefore;
__pos = _M_finish - __elemsafter;
__STL_TRY {
if (__elemsafter > difference_type(__n)) {
iterator __finish_n = _M_finish - difference_type(__n);
uninitialized_copy(__finish_n, _M_finish, _M_finish);
_M_finish = __new_finish;
copy_backward(__pos, __finish_n, __old_finish);
copy(__first, __last, __pos);
}
else {
const value_type* __mid = __first + __elemsafter;
__uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
_M_finish = __new_finish;
copy(__first, __mid, __pos);
}
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
const_iterator __first,
const_iterator __last,
size_type __n)
{
const difference_type __elemsbefore = __pos - _M_start;
size_type __length = size();
if (__elemsbefore < __length / 2) {
iterator __new_start = _M_reserve_elements_at_front(__n);
iterator __old_start = _M_start;
__pos = _M_start + __elemsbefore;
__STL_TRY {
if (__elemsbefore >= __n) {
iterator __start_n = _M_start + __n;
uninitialized_copy(_M_start, __start_n, __new_start);
_M_start = __new_start;
copy(__start_n, __pos, __old_start);
copy(__first, __last, __pos - difference_type(__n));
}
else {
const_iterator __mid = __first + (__n - __elemsbefore);
__uninitialized_copy_copy(_M_start, __pos, __first, __mid,
__new_start);
_M_start = __new_start;
copy(__mid, __last, __old_start);
}
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else {
iterator __new_finish = _M_reserve_elements_at_back(__n);
iterator __old_finish = _M_finish;
const difference_type __elemsafter = __length - __elemsbefore;
__pos = _M_finish - __elemsafter;
__STL_TRY {
if (__elemsafter > __n) {
iterator __finish_n = _M_finish - difference_type(__n);
uninitialized_copy(__finish_n, _M_finish, _M_finish);
_M_finish = __new_finish;
copy_backward(__pos, __finish_n, __old_finish);
copy(__first, __last, __pos);
}
else {
const_iterator __mid = __first + __elemsafter;
__uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
_M_finish = __new_finish;
copy(__first, __mid, __pos);
}
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
}
#endif /* __STL_MEMBER_TEMPLATES */
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems)
{
size_type __new_nodes
= (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
_M_reserve_map_at_front(__new_nodes);
size_type __i;
__STL_TRY {
for (__i = 1; __i <= __new_nodes; ++__i)
*(_M_start._M_node - __i) = _M_allocate_node();
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
for (size_type __j = 1; __j < __i; ++__j)
_M_deallocate_node(*(_M_start._M_node - __j));
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems)
{
size_type __new_nodes
= (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
_M_reserve_map_at_back(__new_nodes);
size_type __i;
__STL_TRY {
for (__i = 1; __i <= __new_nodes; ++__i)
*(_M_finish._M_node + __i) = _M_allocate_node();
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
for (size_type __j = 1; __j < __i; ++__j)
_M_deallocate_node(*(_M_finish._M_node + __j));
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
bool __add_at_front)
{
size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
_Map_pointer __new_nstart;
if (_M_map_size > 2 * __new_num_nodes) {
__new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2
+ (__add_at_front ? __nodes_to_add : 0);
if (__new_nstart < _M_start._M_node)
copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
else
copy_backward(_M_start._M_node, _M_finish._M_node + 1,
__new_nstart + __old_num_nodes);
}
else {
size_type __new_map_size =
_M_map_size + max(_M_map_size, __nodes_to_add) + 2;
_Map_pointer __new_map = _M_allocate_map(__new_map_size);
__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
+ (__add_at_front ? __nodes_to_add : 0);
copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
_M_deallocate_map(_M_map, _M_map_size);
_M_map = __new_map;
_M_map_size = __new_map_size;
}
_M_start._M_set_node(__new_nstart);
_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
}
// Nonmember functions.
template <class _Tp, class _Alloc>
inline bool operator==(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return __x.size() == __y.size() &&
equal(__x.begin(), __x.end(), __y.begin());
}
template <class _Tp, class _Alloc>
inline bool operator<(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return lexicographical_compare(__x.begin(), __x.end(),
__y.begin(), __y.end());
}
#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
template <class _Tp, class _Alloc>
inline bool operator!=(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return !(__x == __y);
}
template <class _Tp, class _Alloc>
inline bool operator>(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return __y < __x;
}
template <class _Tp, class _Alloc>
inline bool operator<=(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return !(__y < __x);
}
template <class _Tp, class _Alloc>
inline bool operator>=(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return !(__x < __y);
}
template <class _Tp, class _Alloc>
inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) {
__x.swap(__y);
}
#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1174
#pragma reset woff 1375
#endif
__STL_END_NAMESPACE
#endif /* __SGI_STL_INTERNAL_DEQUE_H */
// Local Variables:
// mode:C++
// End:
#ifndef __SGI_STL_INTERNAL_QUEUE_H
#define __SGI_STL_INTERNAL_QUEUE_H
#include <sequence_concepts.h>
__STL_BEGIN_NAMESPACE
// Forward declarations of operators < an
template <class _Tp,
class _Sequence __STL_DEPENDENT
class queue;
template <class _Tp, class _Seq>
inline bool operator==(const queue<_Tp, _
template <class _Tp, class _Seq>
inline bool operator<(const queue<_Tp, _S
template <class _Tp, class _Sequence>
class queue {
// requirements:
__STL_CLASS_REQUIRES(_Tp, _Assignable);
__STL_CLASS_REQUIRES(_Sequence, _FrontI
__STL_CLASS_REQUIRES(_Sequence, _BackIn
typedef typename _Sequence::value_type
__STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Se
#ifdef __STL_MEMBER_TEMPLATES
template <class _Tp1, class _Seq1>
friend bool operator== (const queue<_Tp
const queue<_Tp
template <class _Tp1, class _Seq1>
friend bool operator< (const queue<_Tp1
const queue<_Tp1
#else /* __STL_MEMBER_TEMPLATES */
friend bool __STD_QUALIFIER
operator== __STL_NULL_TMPL_ARGS (const
friend bool __STD_QUALIFIER
operator< __STL_NULL_TMPL_ARGS (const
#endif /* __STL_MEMBER_TEMPLATES */
public:
typedef typename _Sequence::value_type
typedef typename _Sequence::size_type
typedef _Sequence
typedef typename _Sequence::reference
typedef typename _Sequence::const_refer
protected:
_Sequence c;
public:
queue() : c() {}
explicit queue(const _Sequence& __c) :
bool empty() const { return c.empty();
size_type size() const { return c.size(
reference front() { return c.front(); }
const_reference front() const { return
reference back() { return c.back(); }
const_reference back() const { return c
void push(const value_type& __x) { c.pu
void pop() { c.pop_front(); }
};
template <class _Tp, class _Sequence>
bool
operator==(const queue<_Tp, _Sequence>& _
{
return __x.c == __y.c;
}
template <class _Tp, class _Sequence>
bool
operator<(const queue<_Tp, _Sequence>& __
{
return __x.c < __y.c;
}
#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
template <class _Tp, class _Sequence>
bool
operator!=(const queue<_Tp, _Sequence>& _
{
return !(__x == __y);
}
template <class _Tp, class _Sequence>
bool
operator>(const queue<_Tp, _Sequence>& __
{
return __y < __x;
}
template <class _Tp, class _Sequence>
bool
operator<=(const queue<_Tp, _Sequence>& _
{
return !(__y < __x);
}
template <class _Tp, class _Sequence>
bool
operator>=(const queue<_Tp, _Sequence>& _
{
return !(__x < __y);
}
#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORD
template <class _Tp,
class _Sequence __STL_DEPENDENT
class _Compare
__STL_DEPENDENT_DEFAULT_TMPL(le
class priority_queue {
// requirements:
__STL_CLASS_REQUIRES(_Tp, _Assignable);
__STL_CLASS_REQUIRES(_Sequence, _Sequen
__STL_CLASS_REQUIRES(_Sequence, _Random
typedef typename _Sequence::value_type
__STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Se
__STL_CLASS_BINARY_FUNCTION_CHECK(_Comp
public:
typedef typename _Sequence::value_type
typedef typename _Sequence::size_type
typedef _Sequence
typedef typename _Sequence::reference
typedef typename _Sequence::const_refer
protected:
_Sequence c;
_Compare comp;
public:
priority_queue() : c() {}
explicit priority_queue(const _Compare&
priority_queue(const _Compare& __x, con
: c(__s), comp(__x)
{ make_heap(c.begin(), c.end(), comp)
#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
priority_queue(_InputIterator __first,
: c(__first, __last) { make_heap(c.be
template <class _InputIterator>
priority_queue(_InputIterator __first,
_InputIterator __last, c
: c(__first, __last), comp(__x)
{ make_heap(c.begin(), c.end(), comp)
template <class _InputIterator>
priority_queue(_InputIterator __first,
const _Compare& __x, con
: c(__s), comp(__x)
{
c.insert(c.end(), __first, __last);
make_heap(c.begin(), c.end(), comp);
}
#else /* __STL_MEMBER_TEMPLATES */
priority_queue(const value_type* __firs
: c(__first, __last) { make_heap(c.be
priority_queue(const value_type* __firs
const _Compare& __x)
: c(__first, __last), comp(__x)
{ make_heap(c.begin(), c.end(), comp)
priority_queue(const value_type* __firs
const _Compare& __x, con
: c(__c), comp(__x)
{
c.insert(c.end(), __first, __last);
make_heap(c.begin(), c.end(), comp);
}
#endif /* __STL_MEMBER_TEMPLATES */
bool empty() const { return c.empty();
size_type size() const { return c.size(
const_reference top() const { return c.
void push(const value_type& __x) {
__STL_TRY {
c.push_back(__x);
push_heap(c.begin(), c.end(), comp)
}
__STL_UNWIND(c.clear());
}
void pop() {
__STL_TRY {
pop_heap(c.begin(), c.end(), comp);
c.pop_back();
}
__STL_UNWIND(c.clear());
}
};
// no equality is provided
__STL_END_NAMESPACE
#endif /* __SGI_STL_INTERNAL_QUEUE_H */
// Local Variables:
// mode:C++
// End:
5.unordered系列的关联式容器
unordered_map的官方文档
- unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value
- 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同
- 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中
- unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低
- unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value
- 它的迭代器至少是前向迭代器
unordered_set的官方文档
6.HashTable的底层结构
unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构
6.1哈希概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log_2 N)，搜索的效率取决于搜索过程中元素的比较次数
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一 一映射的关系，那么在查找时通过该函数可以很快找到该元素
当向该结构中：
插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置
取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
例如：数据集合{1，7，6，4，5，9}；哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？
6.2 哈希冲突
对于两个数据元素的关键字k_i和 k_j(i != j)，有k_i != k_j，但有：Hash(k_i) ==
Hash(k_j)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”
发生哈希冲突该如何处理呢？
6.3哈希函数
引起哈希冲突的一个原因可能是：哈希函数设计不够合理
哈希函数设计原则：
哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单
6.4常见哈希函数
如下
6.4.1.直接定址法–(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
6.4.2.除留余数法–(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
6.4.3.平方取中法–(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
6.4.4.折叠法–(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
6.4.5.随机数法–(了解)
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数
通常应用于关键字长度不等时采用此法
6.4.6.数学分析法–(了解)
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分均匀的若干位作为散列地址例如：
假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突
6.5哈希冲突解决
解决哈希冲突两种常见的方法是：闭散列和开散列
6.5.1闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？
线性探测
比如2.1中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止
插入
通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，
使用线性探测找到下一个空位置，插入新元素
删除
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素
// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};
思考：哈希表什么情况下进行扩容？如何扩容？
void CheckCapacity()
{
if(_size * 10 / _ht.capacity() >= 7)
{
HashTable<K, V, HF> newHt(GetNextPrime(ht.capacity));
for(size_t i = 0; i < _ht.capacity(); ++i)
{
if(_ht[i]._state == EXIST)
newHt.Insert(_ht[i]._val);
}
Swap(newHt);
}
线性探测优点：实现非常简单，
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。如何缓解呢？
2. 二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法
为：H_i = (H_0 + i^2 )% m, 或者：H_i = (H_0 – i^2 )% m。其中：i = 1,2,3…， H_0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小
开散列
3. 开散列概念
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地
址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链
接起来，各链表的头结点存储在哈希表中
开散列增容
桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容
开散列的思考
4. 只能存储key为整形的元素，其他类型怎么解决？
/// @brief BKDR Hash Function
/// @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得 名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法（累乘因子为31）。
template<class T>
size_t BKDRHash(const T *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = hash * 131 + ch; // 也可以乘以31、131、1313、13131、131313..
// 有人说将乘法分解为位运算及加减法可以提高效率，如将上式表达为：hash = hash << 7 + hash << 1 + hash + ch;
// 但其实在Intel平台上，CPU内部对二者的处理效率都是差不多的，
// 我分别进行了100亿次的上述两种运算，发现二者时间差距基本为0（如果是Debug版，分解成位运算后的耗时还要高1/3）；
// 在ARM这类RISC系统上没有测试过，由于ARM内部使用Booth's Algorithm来模拟32位整数乘法运算，它的效率与乘数有关：
// 当乘数8-31位都为1或0时，需要1个时钟周期
// 当乘数16-31位都为1或0时，需要2个时钟周期
// 当乘数24-31位都为1或0时，需要3个时钟周期
// 否则，需要4个时钟周期
// 因此，虽然我没有实际测试，但是我依然认为二者效率上差别不大
}
return hash;
}
/// @brief SDBM Hash Function
/// @detail 本算法是由于在开源项目SDBM（一种简单的数据库引擎）中被应用而得名，它与BKDRHash思想一致，只是种子不同而已。
template<class T>
size_t SDBMHash(const T *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = 65599 * hash + ch;
//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
/// @brief RS Hash Function
/// @detail 因Robert Sedgwicks在其《Algorithms in C》一书中展示而得名。
template<class T>
size_t RSHash(const T *str)
{
register size_t hash = 0;
size_t magic = 63689;
while (size_t ch = (size_t)*str++)
{
hash = hash * magic + ch;
magic *= 378551;
}
return hash;
}
解决方式参照我发的这份文档
各种字符串哈希函数
7.HashTable的模拟实现
我先把我自己模拟实现的HashTable的代码给大家呈现出来
#pragma once
#include<string>
using namespace std;
std::allocator
//vector<int, std::alloc> iv;
//_malloc_alloc_template;//malloc和free的封装
//(size_t)_MAX_BYTES;
template<typename K>
class HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
//特化
template<>
class HashFunc<std::string>
{
size_t operator()(const std::string & key)
{
size_t hash = 0;
for (const auto& e : key)
{
hash += e;
hash *= 131;
}
return hash;
}
};
namespace Hash_Bucket
{
template<typename T>
class HashNode
{
HashNode<T>* _next;
T _data;
HashNode(const T& data)
:_next(nullptr)
, _data(data)
{}
};
template<typename K, typename T, typename KeyOfT, typename Hash>
class HashTable;
template<typename K, typename T, typename KeyOfT, typename Hash>
class __HashTableIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef __HashTableIterator<K, T, KeyOfT, Hash> Self;
Node* _node;
HT* _ht;
__HashTableIterator(const Node* node, const Ht* ht)
:_node(node)
, _ht(ht)
{}
T& operator*()
{
Hash hs;
KeyOfT kot;
return hs(kot(_node->_data));
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
KeyOfT KOT;
Hash hs;
size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();
hashi++;
while (hashi < _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
hashi++;
}
if (hashi == _ht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
template<typename K, typename T, typename KeyOfT, typename Hash>
class HashTable
{
template<typename K, typename T, typename KeyOfT, typename Hash>
friend struct __HashTableIterator;
typedef HashNode<T> Node;
public:
typedef __HashTableIterator<K, T, KeyOfT, Hash> iterator;
iterator begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return iterator(_tables[i], this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
HashTable()
{
_tables.resize(10, nullptr);
_n = 0;
}
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* current = _tables[i];
while (current)
{
Node* next = current->_next;
delete cur;
current = next;
}
_tables[i] = nullptr;
}
}
bool Insert(const T& data)
{
KeyOfT kot;
if (Find(kot(data)))
{
return false;
}
Hash hs;
if (_n == _tables.size())
{
vector<Node*> NewTables(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* current = _tables[i];
while (current)
{
Node* next = current->_next;
size_t hashi = hs(kot(current->_data)) % NewTables.size();
current->_next = NewTables[hashi];
NewTables[hashi] = current;
current = next;
}
_tables[i] = nullptr;
}
_tables.swap(NewTables);
}
size_t hashi = hs(kot(data)) % _tables.size();
Node* NewNode = new Node(data);
NewNode->_next = _tables[hashi];
_tables[hashi] = NewNode;
++_n;
return true;
}
Node* Find(const T& key)
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(kot(key)) % _tables.size();
Node* current = _tables[hashi];
while (current)
{
if (kot(current->_data) == key)
{
return current;
}
current = current->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(kot(key)) % _tables.size();
Node* prev = nullptr;
Node* current = _tables[hashi];
while (current)
{
if (kot(current->_data) == key)
{
if (prev)
{
prev->_next = current->_next;
}
else
{
_tables[hashi] = current->_next;
}
delete current;
--_n;
return true;
}
prev = current;
current = current->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n;
};
}
#pragma once
#include"HashTable.hpp"
namespace Bit
{
template<typename K, typename V, typename Hash = HashFunc<K>>
class Unordered_Map
{
class MapKeyOfT
{
const K& operator()(const pair<K, V>& key)
{
return key.first;
}
};
public:
typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
bool insert(const pair<K, V>& key)
{
return _ht.Insert(key);
}
private:
Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}
大家可以先尝试着理解一下
代码解释我给大家放在下面的代码框了
// K:关键码类型
// V: 不同容器V的类型不同，如果是unordered_map，V代表一个键值对，如果是
unordered_set,V 为 K
// KeyOfValue: 因为V的类型不同，通过value取key的方式就不同，详细见
unordered_map/set的实现
// HF: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能
取模
template<class K, class V, class KeyOfValue, class HF = DefHashF<T> >
class HashBucket;
// 为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身，
template<class K, class V, class KeyOfValue, class HF>
class HashBucket;
// 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作
template <class K, class V, class KeyOfValue, class HF>
这部分内容算是C++里面最难的内容 哈希表大概涉及了C++中的模板和泛型编程以及含函数和迭代器——所谓的smart poniter智能指针以及我们的继承多态和封装的知识
8.基于Hash和位图的海量数据处理面试题
由于本文章篇幅较长 我们将基于Hash和位图的海量数据处理面试题放于下一节讲解
版权声明：本文为博主作者：_Return_My_Offer_原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/fjj2397194209/article/details/137203588
