固定長キュー

概要

サイズ固定のキューを作りたい。
例えばキューのサイズが５として

before
|1|2|3|4|5|
6 を追加すると
|2|3|4|5|6|
になるようなもの。

作り方

std::deque クラスを使うと簡単に作れました。

FixedQueue.h

# include <deque>

/**
 * 固定長キュークラス
 */
template <typename T>
class FixedQueue
{
public:

    typedef typename std::deque<T>::iterator iterator;
    typedef typename std::deque<T>::const_iterator const_iterator;

    //! サイズ指定コンストラクタ
	FixedQueue(size_t size)
	{
		que.resize(size);
	}

    //! 後ろに要素を追加
    void push_back(const T&& t)
	{
	    que.pop_front();
	    que.push_back(t);
	}

	void push_back(const T& t)
	{
	    que.pop_front();
	    que.push_back(t);
	}
	
	//! 前に要素を追加
	void push_front(const T&& t)
	{
	    que.pop_back();
	    que.push_front(t);
	}

	void push_front(const T& t)
	{
	    que.pop_back();
	    que.push_front(t);
	}
	
	iterator begin() { return que.begin(); }
	const_iterator begin() const { return que.begin(); }
	
	iterator end() { return que.end(); }
	const_iterator end() const { return que.end(); }

private:

    std::deque < T > que;       //!< データが格納されているコンテナ
};

使い方

使い方は std::deque と同じ。
イテレータを持ってる（deque のを流用）ので拡張 for 文も使えます。

main.cpp

# include <iostream>
# include "FixedQueue.h"

using namespace std;

template <typename T>
void printQue(const FixedQueue<T>& que)
{
    cout << "print: ";
    for(const T& t : que)
    {
        cout << t << ", ";
    }
    cout << endl;
}

int main(void)
{    
    FixedQueue<int> que(5);
    
    for(int i = 1; i < 100; ++i)
    {
        que.push_back(i);
        printQue(que);
    }    
}

出力

print: 0, 0, 0, 0, 1, 
print: 0, 0, 0, 1, 2, 
print: 0, 0, 1, 2, 3, 
print: 0, 1, 2, 3, 4, 
print: 1, 2, 3, 4, 5, 
print: 2, 3, 4, 5, 6, 
print: 3, 4, 5, 6, 7, 
print: 4, 5, 6, 7, 8, 
print: 5, 6, 7, 8, 9, 
print: 6, 7, 8, 9, 10, 
print: 7, 8, 9, 10, 11, 
print: 8, 9, 10, 11, 12, 
print: 9, 10, 11, 12, 13, 
print: 10, 11, 12, 13, 14, 
print: 11, 12, 13, 14, 15, 
print: 12, 13, 14, 15, 16, 
print: 13, 14, 15, 16, 17, 
print: 14, 15, 16, 17, 18, 
print: 15, 16, 17, 18, 19, 
print: 16, 17, 18, 19, 20, 
print: 17, 18, 19, 20, 21, 
print: 18, 19, 20, 21, 22, 
print: 19, 20, 21, 22, 23, 
print: 20, 21, 22, 23, 24, 
print: 21, 22, 23, 24, 25, 
print: 22, 23, 24, 25, 26, 
print: 23, 24, 25, 26, 27, 
print: 24, 25, 26, 27, 28, 
print: 25, 26, 27, 28, 29, 
print: 26, 27, 28, 29, 30, 
print: 27, 28, 29, 30, 31, 
print: 28, 29, 30, 31, 32, 
print: 29, 30, 31, 32, 33, 
print: 30, 31, 32, 33, 34, 
print: 31, 32, 33, 34, 35, 
print: 32, 33, 34, 35, 36, 
print: 33, 34, 35, 36, 37, 
print: 34, 35, 36, 37, 38, 
print: 35, 36, 37, 38, 39, 
print: 36, 37, 38, 39, 40, 
print: 37, 38, 39, 40, 41, 
print: 38, 39, 40, 41, 42, 
print: 39, 40, 41, 42, 43, 
print: 40, 41, 42, 43, 44, 
print: 41, 42, 43, 44, 45, 
print: 42, 43, 44, 45, 46, 
print: 43, 44, 45, 46, 47, 
print: 44, 45, 46, 47, 48, 
print: 45, 46, 47, 48, 49, 
print: 46, 47, 48, 49, 50,