配列で実装した円形リストー動的なメモリ確保

Question

このコードだと引数なしのインスタンス化されたときに、
501個分のメモリを確保するんですよね。リストで一つずつ動的にメモリを確保して要素を足していくほうが、動的なイメージは強いのですが、最初に５０１個メモリを確保するなら動的らしくないと感じてしまったのですが、
もちろんデータ構造なので場合によって使い分けるのは当然ですが、
配列で実装した円形リストって、かなり使われているものなのでしょうか？

あと別の話になるのですが、
QueueType<ItemType>::QueueType(int maxSize){
// parameterized constructor
this->maxSize = maxSize+1;
front = maxSize-1;
rear = maxSize-1;
items = new ItemType[this->maxSize];
}
では引数maxsizeに１を足してから、front,rearや動的メモリ確保をしていますが、maxsizeに１を足すという動作が無駄に感じて、lengthを引数にしたほうが分かりやすくないですか？
皆さまのご意見を伺いたいです。
よろしくお願いします

コード
#ifndef QUEUETYPE_H
#define QUEUETYPE_H

class FullQueue{};  // Exception class used by Enqueue when queue is full.
class EmptyQueue{}; // Exception class used by Dequeue when queue is empty.

template<class ItemType>
class QueueType{
	private:
		int maxSize;
		int front;
		int rear;
		ItemType *items;
	public:
		QueueType(int maxSize);
		QueueType();
		~QueueType();
		void MakeEmpty();
		bool IsEmpty() const;
		bool IsFull() const;
		void Enqueue(ItemType item);
		void Dequeue(ItemType& item);
};

#endif

template<class ItemType>
QueueType<ItemType>::QueueType(int maxSize){
// parameterized constructor
	this->maxSize = maxSize+1;
	front = maxSize-1;
	rear = maxSize-1;
	items = new ItemType[this->maxSize];
}

template<class ItemType>
QueueType<ItemType>::QueueType(){
// default constructor
	this->maxSize = 501;
	front = maxSize-1;
	rear = maxSize-1;
	items = new ItemType[this->maxSize];
}

template<class ItemType>
QueueType<ItemType>::~QueueType(){
// destructor
	delete [] items;
}

template<class ItemType>
void QueueType<ItemType>::MakeEmpty(){
	front = maxSize-1;
	rear = maxSize-1;
}

template<class ItemType>
bool QueueType<ItemType>::IsEmpty() const{
	return (rear == front);
}

template<class ItemType>
bool QueueType<ItemType>::IsFull() const{
	return ( (rear+1) % maxSize == front );
}

template<class ItemType>
void QueueType<ItemType>::Enqueue(ItemType newItem){
	if (IsFull())
		throw FullQueue();
	else
	{
		rear = (rear+1) % maxSize;
		items[rear] = newItem;
	}
}

template<class ItemType>
void QueueType<ItemType>::Dequeue(ItemType& item){
	if(IsEmpty())
		throw EmptyQueue();
	else{
		front = (front+1) % maxSize;
		item = items[front];
	}
}

Comments

[Stripe]

new QueueType(500);だと、maxSize = 501; front = 499; rear = 499;ですが、new QueueType();だと、maxSize = 501; front = 500; rear = 500;になりますが、これでいいんですか？

Answer 1

こんにちは。

文脈にもよりますが、QueueType<>のインスタンスの要素の記録領域を動的に確保(new)しているので、動的と考えた方がよいように思います。

配列で実装した円形リストって、かなり使われているものなのでしょうか？

私は循環キューを作る時は、配列的な連続メモリを使って作りますし、このような作り方されるケースも多いと思います。
キューは最後尾に追加／先頭から取り出しなので、基本的なキューで列の途中に要素を追加／削除が必要になるケースはないため、連続メモリでの実装が最も効率が良いからです。（メモリがフラグメントするリスクも最小限にできるので長期間動作するプログラムでも比較的安心して使えます。）

Comments

[reotantan]

chironian様は引数として長さを渡し、それをそのまま動的メモリ配置に適用しますか？
このコードを書いた人がlengthではなくmaxsizeという名前にしてそれを＋１した意図はどこにあると考えますか

[Chironian]

> chironian様は引数として長さを渡し、それをそのまま動的メモリ配置に適用しますか？

私が、今まで実装してきた循環キューはそのようにしたケースがほとんどです。
循環キューのサイズは最初に決めたらそのまま使うことが多いです。動的に大きさを変えるのは、キューが空の時だけの場合が多く、その時は破棄→生成すればよいですから。
恐らく、これは比較的一般的に通用すると思います。（もちろん、例外はあります。）

> このコードを書いた人がlengthではなくmaxsizeという名前にしてそれを＋１した意図はどこにあると考えますか

循環キューのフルとエンプティを表現する方法が２つあります。
①要素を記録する領域をちょうど500個用意し、500個でフルにする場合
②要素を記録する領域をちょうど501個用意し、500個でフルにする場合
です。
①の場合、front==rearの時フル、もしくは、エンプティです。
ですで、別途フル・フラグのようなフラグで管理する必要があります。
②の場合、front==rearの場合エンプティで、front == (rear+1)%maxsizeの時フルですので、フル・フラグのようなフラグが不要です。
どちらも一長一短あるので、どちらを用いるのかはケースバイケースですが、このコードの作者は②で実装されています。

【追記】
この場合、パラメータとして501を指定するのではなく500を指定するのは妥当と思います。+1個しているのは実装の問題ですので、それを使う人に見えないようにするのは正しいオブジェクト指向的方針です。

[reotantan]

確かに、説得される解説でした。ありがとうございました

Answer 2

必要な要素の数がはじめから明確になっている場合はこのように最初からその数分のメモリと確保しておいたほうが、動的に毎回メモリを確保するより、効率がいい場合もあります。
汎用的に作るならば、要素の数がわからないので、ひとつずつ(またはある程度の個数分)確保する方法が一般的かと思います。

Comments

[reotantan]

なるほど使い分けですね、コンストラクタについて質問ですが、
lengthを引数にして、それをitems = new ItemType[this->length];としたほうがコードとしては綺麗ではと思ったのですが、回答者様はどう思いますか

[Chironian]

> 汎用的に作るならば、要素の数がわからないので、ひとつずつ(またはある程度の個数分)確保する方法が一般的かと思います。

キューは名前の通り「待ち行列」として使われるケースが多いですが、無限に要素数を増やすと最悪、全てのメモリを食い尽くす可能性が出てきます。それを防ぐため上限を決め、上限に達したら、もしくは、上限に達しないようにEnqueue側を待たせるのが一般的です。
特に性能を重視する循環キューの場合は、上限に達する前に他の処理にメモリを奪われたくない場合が多く、最初に上限まで確保するのは良くある実装と思います。

[yoshi777]

> lengthを引数にして、それをitems = new ItemType[this->length];としたほうがコードとしては綺麗ではと思ったのですが、回答者様はどう思いますか

たしかに引数を length にすれば、-1 する必要はありませんが、使う側にしてみれば maxSize を指定する方が自然であり、使いやすい(迷ったり、間違いをしない)と思います。

[reotantan]

そういう事ですか、解説ありがとうございました

Answer 3

メモリの確保が動的なのか静的なのかではなく、固定長なのか可変長なのか、ということでしょう。
これは、キューのサイズに上限値を設定するかどうかの問題だと思います。

Comments

[reotantan]

そういう事ですね、理解が進みました。
ありがとうございました