目录
一，容器适配器
deque双端队列
二，stack栈
stack接口
stack模拟实现
三，queue队列
queue接口
queue模拟实现
四，priority_queue优先级队列
priority_queue接口
priority_queue模拟实现
注：Date*，无法转化为const Date* &；
一，容器适配器
优缺点
注：
int main()
{
deque<int> dq;
dq.push_back(1);
dq.push_back(2);
dq.push_front(3);
dq.push_front(4);
cout << dq[0] << endl;
cout << dq.front() << endl;
cout << dq.back()<< endl;
dq.pop_back();
dq.pop_front();
deque<int>::iterator it = dq.begin();
while (it != dq.end())
{
cout << *it << " ";
++it;
}
return 0;
}二，stack栈
int main()
{
stack<int> st;
st.push(1);
st.push(2);
st.top();
st.pop();
st.size();
st.empty();
return 0;
}template <class T, class container = deque<T>>
class stack
{
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_back();
}
const T& top()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
container _con;
};
int main()
{
stack<int, list<int>> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
return 0;
}三，queue队列
int main()
{
queue<int> q;
q.push(1);
q.push(2);
q.front();
q.back();
q.pop();
q.size();
q.empty();
return 0;
}template <class T, class container = deque<T>>
class queue
{
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_front();
}
const T& front()
{
return _con.front();
}
const T& back()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
container _con;
};
int main()
{
queue<int, list<int>> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
while (!st.empty())
{
cout << st.front() << " ";
st.pop();
}
return 0;
}四，priority_queue优先级队列
int main()
{
vector<int> v = { 1,2,3,4 };
priority_queue<int> pq(v.begin(), v.end());
pq.push(3);
pq.push(5);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
return 0;
}template<class T, class container = vector<T>, class compare = less<T>>
class priority_queue
{
public:
priority_queue()
{}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
while (first != last)
{
push(*first);
++first;
}
}
void push(const T& val)
{
_con.push_back(val);
AdjustUp(_con.size() - 1);
}
void pop()
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
const T& top()const
{
return _con.front();
}
size_t size()const
{
return _con.size();
}
bool empty()const
{
return _con.empty();
}
void AdjustDown(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && compare()(_con[child], _con[child + 1]))
child++;
if (compare()(_con[parent], _con[child]))
{
std::swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void AdjustUp(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (compare()(_con[parent], _con[child]))
{
std::swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
private:
container _con;
};
template<class T>
class less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};注，嵌套依赖名字需添加关键字typename
template<class container>
void print(const container& con)
{
//无法确定container::iterator是类型，还是静态成员变量
//需在前添加typename
typename container::const_iterator it = con.begin();
while (it != con.end())
{
cout << *it << " ";
++it;
}
}附，自定义compare仿函数，控制比较结果；
class Date
{
friend ostream& operator<<(ostream& _cout, const Date& d);
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
bool operator<(const Date& date) const
{
return (_year < date._year) ||
(_year == date._year && _month < date._month) ||
(_year == date._year && _month == date._month && _day < date._day);
}
bool operator>(const Date& date) const
{
return (_year > date._year) ||
(_year == date._year && _month > date._month) ||
(_year == date._year && _month == date._month && _day > date._day);
}
private:
int _year;
int _month;
int _day;
};
ostream& operator<<(ostream& _cout, const Date& date)
{
_cout << date._year << "-" << date._month << "-" << date._day << endl;
return _cout;
}
//自定义compare仿函数，控制比较结果
class pDateLess
{
public:
bool operator()(const Date* pdate1, const Date* pdate2)
{
return *pdate1 < *pdate2;
}
};
int main()
{
priority_queue<Date*, vector<Date*>, pDateLess> pq;
pq.push(new Date(2000, 1, 1));
pq.push(new Date(2001, 1, 1));
pq.push(new Date(2002, 1, 1));
while (!pq.empty())
{
cout << *pq.top();
pq.pop();
}
return 0;
}//const Date*&，是对类型const Date*的引用
//但实际传递的类型为Date*，无法转化为const Date* &
bool operator()(const Date*& pdate1, const Date*& pdate2)
{
return *pdate1 < *pdate2;
}
//说明
int a = 1;
int* pa = &a;
const int*& pb = pa; //报错int*无法转换为const int*&
//const引用非const对象
//首先int*会隐形转化为const int*, 需借助临时变量，临时变量具有常性