0

ハッシュテーブルの学習を始めたばかりで、 std::map を試しているときに、この質問に出くわしました:衝突を解決するために別の連鎖法を使用する場合std:: priority_queue、単にリストする代わりに使用できますか?

たとえば、大きなグループの人々がいて、名前と年齢の情報を持っています。取得したいのは、年齢に基づいて「David」など、名前が同じ人々のリストです。

これを行うには、最初に名前をキーとして使用してこれらの人々をマップに配置します。次に、衝突を引き起こす同じ名前を持つ人々は、年齢に基づいて std::priority_queue で解決する必要があります。

これは、この問題を解決する正しい方法ですか? そして、 の背後にある謎を本当に知らないことに気づきましたstd::map。衝突を解決するために、個別の連鎖または線形プローブを使用していますか? 私はその答えを見つけることができませんでした。

私が説明した質問に対して私が持っている簡単なコードは、それを少し明確にするのに役立つかもしれません:

class people {

public:
people(string inName, int inAge):firstName(inName), age(inAge){};
private:

string firstName;
int age;


}

int main(int argc, char ** argv) {

string name;
int age;

name = "David";
age = 25;
people  aPerson(name, age);
//This is just an example, there are usually more than two attributes to deal with.


std::map <string, people> peopleList;

peopleList[name] = aPerson;

//now how do I implement the priority queue for collision first names? 
}

前もって感謝します！

編集: O(1) 検索が必要なので、マップの代わりに順不同マップを使用する必要があります。

4

1 に答える 1

1

現在、名前と単一のpeopleオブジェクトの間のマッピングがあります。std::priority_queue優先度キューのカスタム コンパレータを使用して、マッピングを name と の間のマップに変更する必要があります。

auto comparator = [](const people& p1, const people& p2) -> bool
    { return (p1.age < p2.age); }

std::map<std::string,
         std::priority_queue<people, std::vector<people>, comparator>> peopleList;

// ...

peopleList[name].push(aPerson);
于 2013-03-28T09:23:40.963 に答える