質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.53%

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

解決済

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 1,241

reotantan

score 253

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

あと別の話になるのですが、
QueueType<ItemType>::QueueType(int maxSize){
// parameterized constructor
    this->maxSize = maxSize+1;
    front = maxSize-1;
    rear = maxSize-1;
    items = new ItemType[this->maxSize];
}
では引数maxsizeに1を足してから、front,rearや動的メモリ確保をしていますが、maxsizeに1を足すという動作が無駄に感じて、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];
    }
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • Stripe

    2015/12/20 19:00

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

    キャンセル

回答 3

checkベストアンサー

+2

こんにちは。

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/12/20 11:04

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

    キャンセル

  • 2015/12/20 11:27 編集

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

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

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

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

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

    キャンセル

  • 2015/12/21 00:14

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

    キャンセル

+1

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/12/20 11:18

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

    キャンセル

  • 2015/12/20 12:04

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

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

    キャンセル

  • 2015/12/20 17:48

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

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

    キャンセル

  • 2015/12/21 00:16

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

    キャンセル

0

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/12/21 00:17

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.53%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る