0

我刚开始学习哈希表，在尝试使用 std::map 时我想出了这个问题：当使用单独的链接方法来解决冲突时，我可以使用std:: priority_queue而不是仅仅使用列表吗？

例如，有一大群人，我有他们的名字和年龄的信息，而我想要得到的是具有相同名字的人的排序列表，例如“大卫”基于他们的年龄。

所以要做到这一点，我首先使用他们的名字作为将这些人放入地图的键，然后应该根据年龄使用 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对象之间的映射。您需要将映射更改为 name 和 a 之间的映射，并std::priority_queue为优先级队列使用自定义比较器：

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 回答