c++ - C++の存在マップ

Question

std :: mapのようなものが必要ですが、アイテムが存在するかどうかだけを確認したいので、実際にはキーと値は必要ありません。何を使うべきですか？

score 23 · Accepted Answer

23

std::setが必要なようです。

于 2008-09-24T01:56:53.220 に答える

score 7 · Accepted Answer

と同じタイプの動作が必要な場合はstd::map、が必要ですstd::set。

挿入/削除操作とクエリ操作を混在させている場合std::setは、おそらく最良の選択です。std::vectorただし、最初にセットにデータを入力してからクエリを実行できる場合は、を使用してソートし、バイナリ検索を使用してベクトル内の存在を確認することを検討する価値があります。

score 4 · Accepted Answer

本当に存在だけが必要で、注文さえ必要ない場合は、が必要ですunordered_set。お気に入りのC++0xベンダーまたはboost.orgから入手できます。

score 2 · Accepted Answer

データが数値の場合は、スペースに最適化された std::vector を使用できます。

D:\Temp>type vectorbool.cpp
#include <iostream>
#include <vector>

using namespace std;

int main() {
        vector<bool> vb(10);
        vb[5] = true;

        for (vector<bool>::const_iterator ci = vb.begin(); ci != vb.end(); ++ci) {
                cout << *ci << endl;
        }
}

D:\Temp>cl /nologo /W4 /EHsc vectorbool.cpp
vectorbool.cpp

D:\Temp>vectorbool.exe
0
0
0
0
0
1
0
0
0
0

score 2 · Accepted Answer

おそらく、stl::set必要なものを探す必要があります。Astl::bitsetは別のオプションです。

どちらが優れているかを定義する情報をどのように使用する必要があるかによって異なります。Asetはソートされたデータ構造であり、挿入、検索、および削除には O(LOG N) の時間がかかります。ただし、「存在」としてマークしたすべての値を反復処理する必要がある場合は、これが適していますset。

何かがセットのメンバーであるという事実をマークして検索するだけでよい場合は、のbitset方が適している可能性があります。挿入、検索、削除は O(1) しかかかりませんが、int値を収集することしかできません。に設定されているメンバーを見つけるためにセット全体を調べる必要があるため、マークされたすべての値を反復処理すると O(N) かかりますtrue。これをstl::mapと組み合わせて使用して、持っている値から必要な数値にマップできbitsetます。

セット内の値を使用して実行する必要がある操作を確認すると、適切なデータ構造を選択できるはずです

score 1 · Accepted Answer

キーが値である場合は、セットではなく「ブルームフィルター」を検討することもできます。

score 1 · Accepted Answer

目的に合わせて std::map を使い続けることができます。

特定のアイテム (キータイプ) がマップに存在するかどうかを確認するには、次のコードを使用できます。

if (mapObj.count(item) != 0)
{
   // item exists
}

前に答えたように、 std::set も仕事をします。興味深いことに、セットとマップの両方が内部的にツリーとして表されます。

c++ - C++の存在マップ

7 に答える 7

Related

Reference