0

次の機能を備えたC++の標準コンテナ/ライブラリを探しています。

  1. 数値のウィンドウを格納します（エンキューとデキューで十分です）。
  2. ウィンドウ内の一意の番号の数を返します。

これは、std::queueとstd::setの機能をマージするものである可能性があります。

編集済み：予想される操作の例。このシーケンス「123 3 4 4 5 5 6 6 7 7 8」およびウィンドウサイズ2の場合、次の手順が必要になります。

  1. ウィンドウ=[12]、一意のもの= 2
  2. ウィンドウ=[23]、一意のもの= 2
  3. ウィンドウ=[33]、一意のもの= 1
  4. ウィンドウ=[34]、一意のもの= 2
  5. 等々 ...
4

2 に答える 2

1

2つのコンテナが必要です。

  • adeque<number>番号をウィンドウに順番に保存します。
  • a map<number, size_t>（またはunordered_map利用可能な場合）各一意の番号のカウントを格納します。

次に、操作は次のとおりです。

void push(number n) {
    deque.push_back(n);
    ++map[n];
}

void pop() {
    auto found = map.find(deque.front());
    assert(found != map.end());
    assert(found->second > 0);
    if (--found->second == 0) {
        map.erase(found);
    }
    deque.pop_front();
}

size_t count_unique() {
    return map.size();
}
于 2012-08-30T09:50:57.807 に答える
0

マイクのおかげで、ここに完全なクラスがあります：

#include <stdio.h>
#include <assert.h>

using namespace std;
#include "map"
#include "deque"

class window{
    private:
        std::deque<int> numbers;
        std::map<int, size_t> unique;
    public:
        window(){};
        void push(int n) {
            numbers.push_back(n);
            ++unique[n];
        }

        void pop() {
            map<int, size_t>::iterator found = unique.find(numbers.front());
            assert(found != unique.end());
            assert(found->second > 0);
            if (--found->second == 0) {
                unique.erase(found);
            }
            numbers.pop_front();
        }

        size_t count_unique() {
            return unique.size();
        }
};

そしてこれはテストケースです：

int main(){
    // example list '1 2 3 3 4 4 5 5 6 6 7 7 8'
    int list[13] = {1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8};
    window w1;
    w1.push(list[0]);w1.push(list[1]);

    int i=0;
    printf("The list is: ");
    for(i=0; i<13; i++){
        printf("%d ",list[i]);
    }
    printf("\n");

    for(i=0; i<11; i++){
        printf("[%d] Unique ones: %d\n",i+1,w1.count_unique());
        w1.push(list[i+2]);w1.pop();
    }

    return 0;
}
于 2012-08-30T10:21:04.637 に答える