有序队列（sorted_queue）的C++实现

有序队列（sorted_queue）其实称作有序表（sorted_list）更好，基于各种考虑，我将 sorted_queue 的底层容器设为 deque，看起来好像折中了 vector 和 list。

sorted_queue 的插入保证有序，故有移动元素的开销，同样删除操作也会移动元素。但是，sorted_queue 支持随机访问，提供随机迭代器，对有序区间的算法都可用在上面。sorted_queue 的定义还可改进，比如可以增加带参的构造函数，swap 成员方法等。

sorted_queue 的定义及实现如下：

/******************************************************************** 
    created:    2013/08/16 
    created:    16:8:2013   23:56 
    file base:  sorted_queue 
    file ext:   h 
    author:     Justme0 (http://blog.csdn.net/Justme0) 
     
    purpose:    sorted_queue 的定义与实现 
*********************************************************************/  
  
#ifndef SORTED_QUEUE_H   
#define SORTED_QUEUE_H   
  
#include <deque>   
#include <algorithm>   
  
template <class T>  
class sorted_queue {  
public:  
    typedef typename std::deque<t>::value_type        value_type;  
    typedef typename std::deque<t>::size_type         size_type;  
    typedef typename std::deque<t>::reference         reference;  
    typedef typename std::deque<t>::const_reference   const_reference;  
    typedef typename std::deque<t>::iterator          iterator;  
    typedef typename std::deque<t>::const_iterator    const_iterator;  
  
protected:  
    std::deque<T> c;  // 底层容器   
  
public:  
    iterator begin() {  
        return c.begin();  
    }  
  
    const_iterator begin() const {  
        return c.begin();  
    }  
  
    iterator end() {  
        return c.end();  
    }  
  
    const_iterator end() const {  
        return c.end();  
    }  
  
    /* 
    ** 直接存取 
    */  
    reference operator[](size_type n) {  
        return c[n];  
    }  
  
    const_reference operator[](size_type n) const {  
        return c[n];  
    }  
  
    bool empty() const {  
        return c.empty();  
    }  
  
    size_type size() const {  
        return c.size();  
    }  
  
    reference front() {  
        return c.front();  
    }  
  
    const_reference front() const {  
        return c.front();  
    }  
  
    reference back() {  
        return c.back();  
    }  
  
    const_reference back() const {  
        return c.back();  
    }  
  
    /* 
    ** 插入元素 
    */  
    void push(const value_type & x) {  
        c.insert(lower_bound(c.begin(), c.end(), x), x);  
    }  
  
    void pop_front() {  
        c.pop_front();  
    }  
  
    void pop_back() {  
        c.pop_back();  
    }  
  
    iterator erase(const_iterator position) {  
        return c.erase(position);  
    }  
  
    iterator erase(const_iterator first, const_iterator last) {  
        return c.erase(first, last);  
    }  
  
    /* 
    ** 删除所有值为 x 的元素 
    */  
    void remove(const value_type & x) {  
        /* 
        ** 下面这条语句中应该是不得不用 auto，因为不知道返回的是 iterator 还是 const_iterator。 
        ** 用 equal_range 效率较高。 
        */  
        auto interval = equal_range(this->begin(), this->end(), x);  
        this->erase(interval.first, interval.second);  
    }  
  
    void clear() {  
        c.clear();  
    }  
};  
  
#endif

/******************************************************************** 
    created:    2013/08/16 
    created:    16:8:2013   23:42 
    file base:  test 
    file ext:   cpp 
    author:     Justme0 (http://blog.csdn.net/Justme0) 
     
    purpose:    sorted_queue 的测试程序 
*********************************************************************/  
  
#include <iostream>   
#include "sorted_queue.h"   
using namespace std;  
  
template <class T>  
void output(const sorted_queue<T> &sq) {  
    for (auto ite = sq.begin(); ite != sq.end(); ++ite) {  
        cout << *ite << " ";  
    }  
    cout << endl;  
}  
  
int main(int argc, char **argv) {  
    sorted_queue<int> sq;  
  
    sq.push(1);  
    sq.push(-1);  
    sq.push(0);  
    sq.push(0);  
  
    output(sq);  
    cout << "[3]=" << sq[3] << endl;  
    cout << "front=" << sq.front() << endl;  
    cout << "back=" << sq.back() << endl;  
    cout << (sq.empty() ? "empty" : "not empty") << endl;  
  
    cout << endl;  
    cout << "erase 0" << endl;  
    sq.remove(0);  
    output(sq);  
  
    cout << endl;  
    cout << "clear" << endl;  
    sq.clear();  
    cout << (sq.empty() ? "empty" : "not empty") << endl;  
  
    return 0;  
}

-1 0 0 1  
[3]=1  
front=-1  
back=1  
not empty  
  
erase 0  
-1 1  
  
clear  
empty  
请按任意键继续. . .  

-1 0 0 1
[3]=1
front=-1
back=1
not empty

erase 0
-1 1

clear
empty
请按任意键继续. . .

补充：软件开发 , C++ ,