STLマップをキーとしてstructとともに使用することは不可能ですか?
-
19-09-2019 - |
質問
次のコードがあります。
struct Node
{
int a;
int b;
};
Node node;
node.a = 2;
node.b = 3;
map<int, int> aa;
aa[1]=1; // OK.
map<Node, int> bb;
bb[node]=1; // Compile error.
私のstructのインスタンスをマップしようとしたとき Node
に int
, 、コンパイルエラーがありました。なんで?
解決
マップ内のキーとして使用できるようにするには、それを使用して比較することができなければなりません operator<()
. 。このようなオペレーターをノードクラスに追加する必要があります。
struct Node
{
int a;
int b;
bool operator<( const Node & n ) const {
return this->a < n.a; // for example
}
};
もちろん、実際のオペレーターが行うことは、実際にあなたの構造体の比較の意味に依存します。
他のヒント
std ::マップにノードオブジェクトを比較する方法を伝える必要があります。デフォルトでは、オペレーターよりも少ないものを使用してそうしようとします。しかし、ノードのオペレーター以下を提供しませんでした。最も簡単な解決策は、供給することです。
無料関数の例:
bool operator<(Node const& n1, Node const& n2)
{
return n1.a<n2.a || (n1.a==n2.a && n1.b<n2.b);
}
ノードオブジェクトx、yのペアについては、 !(x<y)
と !(y<x)
マップは、xとyを等しいと見なします(同じキー)。
ノードタイプの比較を有効にするには、以下のオペレーターを定義する必要があります。
struct Node
{
int a;
int b;
};
bool operator<(Node const& n1, Node const& n2)
{
// TODO: Specify condition as you need
return ... ;
}
ここであなたは何をチェックするかもしれません 少ないと同等です ユーザー定義のタイプの平均。
代替ソリューションは、に基づいてファンサーを定義することです std :: binary_function. 。設計の観点から、比較は効果的に分離されているため、このオプションには利点があります。 Node
クラス。これにより、異なる比較条件(ファンクター)で特殊なマップを定義できます。
#include <map>
struct Node
{
int a;
int b;
};
struct NodeLessThan
: public std::binary_function<Node, Node, bool>
{
bool operator() (Node const& n1, Node const& n2) const
{
// TODO: your condition
return n1.a < n2.a;
}
};
int main()
{
Node node;
node.a = 2;
node.b = 3;
typedef std::map<Node, int, NodeLessThan> node_map_t;
node_map_t bb;
bb[node] = 1;
}
したがって、単なる比較よりも多くの比較を定義できます NodeLessThan
, 、たとえば、異なる条件を使用しているか、それだけを比較する条件を使用します Node::a
両方のコンポーネントを比較する別の、 Node::a
と Node::b
. 。次に、さまざまなタイプのマップを定義します。
typedef std::map<Node, int, NodeLessThan> node_map_t;
typedef std::map<Node, int, NodeLessThanByA> node_map_a_t;
このようなデカップリングは邪魔にならない(ノードクラスにまったく触れない)、より拡張可能なソリューションを実現するために有益です。
キーでデータをソートする必要がある場合は、新しいUNORDERED_MAPを使用できます。
#include <unordered_map>
...
std::tr1::unordered_map<Node, int> aa; // Doesn't require operator<(Node, Node)
これが機能するには、最近のコンパイラが必要です。
アップデートニールが指摘しているように、あなたはodorded_mapをwindしたい場合は専門のハッシュ関数が必要です Node
キー。
struct NodeHash : std::unary_function<Node, size_t>
{
size_t operator()(Node const & node) const
{
return static_cast<size_t>(node.a + 1) * static_cast<size_t>(node.b + 1);
}
};
そして、マップは次のようになります。
std::tr1::unordered_map<Node, int, NodeHash> aa;
また、Sellibitzeが言うように、ハッシュ衝突の場合にキーを比較するには、オペレーター==が必要です。
bool operator==(const Node & lhs, const Node & rhs)
{
return lhs.a == rhs.a && rhs.b == rhs.b;
}
したがって、STD :: MAPは結局ははるかに使いやすいと思います。
コンパイラエラーを投稿していただけませんか? あなた, どうしたの.
それ以来あなたのエラーが発生すると思います Node
その要素を識別するためにマップで必要とされる比較演算子を実装しません。
として STD ::マップ そのキーによってソートされているので、2つを比較する方法を定義する必要があります Node
オブジェクト。以来 C ++ 11 aを使用することもできます ラムダの表現 比較演算子を定義する代わりに。その結果、次のようにコードを短くすることができます。
int main() {
Node node{ 2, 3 };
auto comp = [](const Node& n1, const Node& n2) {
return n1.a < n2.a || (n1.a == n2.a && n1.b < n2.b);
};
std::map<Node, int, decltype(comp)> bb(comp);
bb[node] = 1;
for (auto const &kv : bb)
std::cout << kv.first.a << ", " << kv.first.b << ": " << kv.second << std::endl;
return 0;
}
出力:
2, 3: 1
あなたのニーズに応じて、ラムダの表現の本体を交換してください。