英文:
Search by value in a multimap in O(log(n)) complexity
问题
Here's the translated code portion:
如何以O(log(n))的时间复杂度高效搜索multimap中的值？
我有一个multimap，其中键表示位置，值表示城市名称。
我想要根据给定的城市名称在multimap中高效地搜索特定的城市名称。
这是数据结构：
std::multimap < Location, std::string, LessX > _mmapCitiesX;
这是我实现的搜索函数（有效运行）：
City CitiesManager::findCity(const std::string& cityName) const
{
auto it = std::find_if(_mmapCitiesX.begin(), _mmapCitiesX.end(),
[&](const City& city) {
return city.second == cityName;
});
if (it == _mmapCitiesX.end()) {
throw std::runtime_error(cityName +
"在城市列表中未找到。请重试");
}
return *it;
}
（City是std::pair<Location, std::string>，而Location是具有x、y坐标的结构体）
为了减少复杂性，我尝试使用std::equal_range，但它没有起作用...
这是我的尝试：
City CitiesManager::findCity(const std::string& cityName) const
{
auto range = std::equal_range(_mmapCitiesX.begin(), _mmapCitiesX.end(),
cityName, [](const City& city, const std::string& name) {
return city.second < name;
});
if (range.first == range.second) {
throw std::runtime_error(cityName +
"在城市列表中未找到。请重试");
}
return *(range.first);
}
我收到错误：
> C2664 'bool CitiesManager::findCity::<lambda_1>::operator ()(const
> City &,const
> std::basic_string<char,std::char_traits<char>,std::allocator<char>> &)
> const': 无法将参数1从'const _Ty'转换为'const City &'
编辑：
这是LessX，我需要它，因为我想按x坐标对位置进行排序，因此我选择使用Location作为键。
struct LessX
{
bool operator()(const Location& left, const Location& right) const
{
return left._x < right._x;
}
};
我会感激任何帮助
This is the translated code portion without the translation request.
英文:
How can I efficiently search for a value in a multimap with a time complexity of O(log(n))?
I have a multimap where the keys represent locations and the values represent city names.
I want to efficiently search for a specific city name in the multimap based on the given city name.
This is the data structure:
std::multimap < Location, std::string, LessX > _mmapCitiesX;
Here is the search function that I have implemented (this is working):
City CitiesManager::findCity(const std::string& cityName) const
{
auto it = std::find_if(_mmapCitiesX.begin(), _mmapCitiesX.end(),
[&](const City& city) {
return city.second == cityName;
});
if (it == _mmapCitiesX.end()) {
throw std::runtime_error(cityName +
" isn't found in the city list. Please try again");
}
return *it;
}
(City is std::pair<Location, std::string>,
and Location is a struct with x,y cords)
To reduce complexity , I attempted to use the std::equal_range, but it didn't work...
here is my attemp:
City CitiesManager::findCity(const std::string& cityName) const
{
auto range = std::equal_range(_mmapCitiesX.begin(), _mmapCitiesX.end(),
cityName, [](const City& city, const std::string& name) {
return city.second < name;
});
if (range.first == range.second) {
throw std::runtime_error(cityName +
" isn't found in the city list. Please try again");
}
return *(range.first);
}
I get error:
> C2664 'bool CitiesManager::findCity::<lambda_1>::operator ()(const
> City &,const
> std::basic_string<char,std::char_traits<char>,std::allocator<char>> &)
> const': cannot convert argument 1 from 'const _Ty' to 'const City &'
edit:
This is LessX, I need it because I want to sort the locations by x-chords, and therefore I choose to use Location as key.
struct LessX
{
bool operator()(const Location& left, const Location& right) const
{
return left._x < right._x;
}
};
I would appreciate any help
答案1
得分: 3
你无法这样做。即使你修复了调用点，你也忽略了std::equal_range的前提条件，所以你的程序是不合法的。
如果你想通过位置和名称进行查找，你需要一个能够提供这种查找功能的数据结构。boost::bimap或boost::multi_index是可以提供这种功能的容器。
英文:
You can't. Even if you fix your call site, you are ignoring the preconditions of std::equal_range, so your program is ill-formed.
If you want to lookup by both location and name, you need a data structure that provides such a lookup. boost::bimap or boost::multi_index are containers that can provide that.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论