有效搜索std::set中用于排序的元素以外的元素

Question

考虑以下集合实现。在这里，我已经根据fScore参数订购了这套。如果我想在"NodeData"中搜索特定"id"的元素，该怎么办。我知道我可以使用"find"在O(logn(的集合中搜索"fScore"的任何元素。有没有比线性搜索(下面实现(更有效的方法来搜索"id"(更短的时间(？

#include<iostream>
#include<algorithm>
#include<iterator>
#include<set>
#include<stdlib.h>
#include<vector>
struct NodeData{
int id;
int parent;
double fScore, gScore, hScore;
std::vector<double> nScores;
NodeData(const int& idIn = 0,
const int& parentIn = -1,
const double& fIn = 1,
const double& gIn = 1,
const double& hIn = 1):id(idIn), parent(parentIn), 
fScore(fIn), gScore(gIn), hScore(hIn)
{
}
bool operator<(const NodeData& rhs) const {
return fScore < rhs.fScore;
}
};
class test
{
public:
std::set<NodeData> NodeList;
};
int main()
{
test q;
for(int i=1;i<=5;i++)
{
NodeData n1 = {i,1,i,1,1};
q.NodeList.insert(n1);
}
std::set<NodeData>::iterator it;
//search for node with fScore 1 - cost O(logn)
it = q.NodeList.find(1);    
if(it != q.NodeList.end()){
std::cout<<"node with fScore 1 found. id = "<<it->id<<std::endl;
}
else{   
std::cout<<"node not found = "<<std::endl;
}
//searching for id=3 - Linear search - cost O(n) 
int searchId = 3;
std::set<NodeData>::iterator it1 = q.NodeList.begin();
while(it1 != q.NodeList.end())
{
if(it1->id == searchId)
{
std::cout <<"found node with id = "<<it1->id<<std::endl;    
}
it1++;
}   
}

Answer 1

您的set是否经常更改？如果没有，你可以考虑建立一个"；索引"-unordered_map<>，无论你需要什么字段到你集合的元素。

维持这样的"成本"是有成本的；索引"；，你应该看看它是否加重了更快的搜索。

Answer 2

如果不使用不同/额外的数据结构，就无法实现这一点。如果您正在使用C++，并且可以使用库，则可以在Boost多索引容器库中找到此功能。

Answer 3

除了Falk的答案之外，这里还有一个如何使用Boost完成这件事的例子。多索引：

在Coliru上直播

#include <iostream>
#include <algorithm>
#include <iterator>
#include <stdlib.h>
#include <vector>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
struct NodeData{
int id;
int parent;
double fScore, gScore, hScore;
std::vector<double> nScores;
NodeData(const int& idIn = 0,
const int& parentIn = -1,
const double& fIn = 1,
const double& gIn = 1,
const double& hIn = 1):id(idIn), parent(parentIn), 
fScore(fIn), gScore(gIn), hScore(hIn)
{
}

bool operator<(const NodeData& rhs) const {
return fScore < rhs.fScore;
}
};
class test
{
public:
typedef boost::multi_index_container<
NodeData,
boost::multi_index::indexed_by<
boost::multi_index::ordered_unique<
boost::multi_index::identity<NodeData>
>,
boost::multi_index::ordered_unique<
boost::multi_index::member<NodeData, int, &NodeData::id>
>
>
> NodeListType;
NodeListType NodeList;
};
int main()
{
test q;
for(int i=1;i<=5;i++)
{
NodeData n1 = {i,1,double(i),1,1};
q.NodeList.insert(n1);
}
test::NodeListType::iterator it;
//search for node with fScore 1 - cost O(logn)
it = q.NodeList.find(1);    
if(it != q.NodeList.end()){
std::cout<<"node with fScore 1 found. id = "<<it->id<<std::endl;
}
else{   
std::cout<<"node not found = "<<std::endl;
}
//searching for id=3 on second index - cost O(logn) 
int searchId = 3;
test::NodeListType::nth_index<1>::type::iterator it1 = q.NodeList.get<1>().find(searchId);
if(it1 != q.NodeList.get<1>().end()){
std::cout <<"found node with id = "<<it1->id<<std::endl;    
}   
}

如果NodeData::id使用散列索引而不是有序索引，则查找是恒定的(平均值(。