1

Q#1) 以下の構造体はコピーされたくないため、コンパイル エラーが発生します - なぜ、どのように対処すればよいですか?

#include <iostream>
#include <string>
#include <map>

using namespace std;

struct person
{
    person(string n)
        :name(n)
    {}

    string name;
};

int main()
{
    map<string, person> my_map;

    my_map["one"] = person("Tom");

    return 0;
}

Q#2) 構造体コンストラクタ "person(const string& n)" を省略し、構造体の値を 1 つずつ割り当てることで、上記の問題を回避できます。 

#include <iostream>
#include <string>
#include <map>

using namespace std;

struct person
{
    string name;
};

int main()
{
    map<string, person> my_map;

    person p;
    p.name = "Tom";
    my_map["one"] = p;

    return 0;
}

それで、私はこのようにして、多くの人をマップに保存した後、特定の人がマップ内に存在するかどうかを確認したいとしましょう。私が知っているように、それを行う正しい方法は次のとおりです。

if(my_map.find("one") == my_map.end()) { //it doesn't exist in my_map }  
else {//it exists}

しかし、私が理解しているように、これはマップ全体を 1 つずつ反復しますね。はいの場合、次のようにしても問題ありません。

using namespace std;

struct person
{
    string name;
    string identifier; // <--
};

int main()
{
    map<string, person> my_map;

    person p;
    p.name = "Tom";
    p.identifier = "something"; // <--
    my_map["one"] = p;

    if(my_map["unknown"].identifier == "something") // <--
        cout << "Found" << endl;
    else 
        cout << "Not found" << endl;

    return 0;
}

これを行うことで、反復を回避でき、メモリ内のガベージが識別子と一致する可能性は... 小さいと思います。特に、ハッシュを使用する場合はそうです。では、そのようにして (安全に) 大丈夫ですか?

4

2 に答える 2

8

1) 最初の例のコードは、次の式のためにコンパイルに失敗します:

my_map["one"]

my_map["one"]std::stringfromを構築し、"one"それをstd::map::operator[]に渡します。map::operator[]値が提供されたキーにマップされていることを確認し (キーがまだ値に関連付けられていない場合は、デフォルトで構築された値にキーを関連付けることによって)、その値への参照を返します。

デフォルトのコンストラクタがないため、これはコンパイルされpersonません (「デフォルトのコンストラクタ」とは、引数を取らないコンストラクタです)。

この問題を解決するには、いくつかの方法があります。

1 つの方法は、コンストラクターの削除です。コンストラクターを指定しない場合、デフォルトのコンストラクターが暗黙的に定義されるため、機能します。

もう 1 つの方法は、 のデフォルト コンストラクタを明示的に定義することですperson。

struct person
{
    person():name(){} //or person()=default; if your compiler supports this
    person(string n)
        :name(n)
    {}
    string name;
};

もう 1 つの方法は、次のように、まったく使用せず、operator[]代わりにmap::insertを使用することです。

auto pair(my_map.insert(std::make_pair(std::string("one"),person("Tom"))));
if (!pair.second) {
    *pair.first = person("Tom");
}

2）マップ内の要素を見つける正しい方法は（あなたが言ったように）使用することです：

if(my_map.find("one") == my_map.end()) {/*it doesn't exist in my_map*/}
else {/*it exists*/}

これは、マップ内のすべての要素を検査するわけではありません。実際には、O(log(map.size()))要素のみを検査する場合があります。

あなたの恐れはまったく根拠のないものです。これはマップ内の要素を見つけるための正しい方法ですが、続行する方法は、何が機能するかについての深刻な誤解を示唆してoperator[]います.

「マップに が存在しない場合にmy_map["unknown"].identifier == "something"true を返す確率は?」と尋ねます。"unknown"

これに対する答えは、これが true を返す可能性はまったくないということです。キーを持つ値がstd::string("unknown")マップに存在しない場合、デフォルトで構築されたoperator[]に関連付けられ、空の文字列になるためです。std::string("unknown")personidentifier

于 2012-04-25T06:23:09.387 に答える
2

まず、コンストラクターがあるため、デフォルトのコンストラクターを提供する必要があります。これは、C++ 標準ライブラリ コンテナーが値のセマンティクスを使用するためです。したがって、マップは値をコピーして割り当て、デフォルトで構築できる必要があります。コンストラクターを提供するため、コンパイラーはデフォルトのコンストラクターを合成しません。これは何もしないデフォルトのコンストラクタです:

person() {} // default constructs string, so no special aciton required.

特に の場合std::map、operator[]キーを持つ要素がマップにまだ存在しない場合、デフォルトで構築された値への参照を返します。

my_map["one"] = p; // creates *default* person, then *assigns* it the value of p.

次に、マップの検索に関する質問についてstd::map、検索は対数的な複雑さを持ち、通常は自己均衡二分木として実装されます。そのため、検索するときにマップ全体を横断するわけではありません。operator[]また、検索されたキーが存在しない場合に経由でアクセスすると新しい要素が導入されるため、使用するフォームfind()はそれを行う標準的な方法です。

あなたがハッシュについて言及したので、C++11 はstd::unordered_map、 andtr1およびboosthave を提供しますhash_map。これらはハッシュ関数を使用して検索を実行し、一定時間です。使用する価値があるかどうかは、マップのサイズなどの要因によって異なります。定数時間は、小さなマップの検索にかかる対数時間よりも長くなる可能性があります。

注: 構造体をキーとして使用する場合、または標準ライブラリの 1 つに挿入するsets場合は、さらに要件があります。

maps :クラスの小なり演算子またはカスタム コンパレータ ファンクターのいずれかを使用して、キーに対して厳密な弱い順序付けを提供する必要があります。personキーとして使用する場合は、次のようなものが必要です。

bool operator<(const person& rhs) const { return name < rhs.name; }

unordered_ または hash maps :またはファンクターを介して、ハッシュ関数とキーの等値比較の両方を提供する必要があります。operator==.

于 2012-04-25T05:29:46.623 に答える