问题描述
-施工
我构造了一个元组vector<tuple<int,int,int>> x的向量.为了简单起见，让我们假设它是以这种方式构造的.vector<tuple<int,int,int>> x;
for (int ii=0; ii < 10; ii++){
for (int jj=0; jj < 10; jj++){
currpeak[0] = ii + rand() % 10;
currpeak[1] = jj + rand() % 10;
currpeak[2] = rand() % 100;
x.emplace_back(currpeak[0], currpeak[1], currpeak[2]);
}
}
现在，我想根据第3个元素获得n个最大的元组，并将它们附加到另一个变量vector<tuple<int,int,int>> y中.让我们假设n=10.
-排序
目前，我正在按照这种方式进行操作:对它们进行反向排序，然后选择前n个元素.
// Sort them by 3rd element
bool sortbythird_desc(const tuple<int,int,int>& a,
const tuple<int,int,int>& b){
return (get<2>(a) > get<2>(b));
}
sort(x.begin(), x.end(), sortbythird_desc);
// Extract the top 10 elements from x and put into y
vector<tuple<int,int,int>> y;
for(int jdx =0; jdx<10; jdx++){
int curr_peak0=get<0>(x[jdx]);
int curr_peak1=get<1>(x[jdx]);
int curr_peak2=get<2>(x[jdx]);
y.emplace_back(curr_peak0, curr_peak1, curr_peak2);
}
但是由于排序，这是O(nlogn)操作.
-失败的堆尝试
如果我可以将x转换为堆，或者甚至从一开始就将其构造为堆:O(n)操作. pop_heap:O(log n)次.总共只需要执行O(n + log n) = O(n)操作.但是以下失败
// Convert x to a heap
bool Comp(const tuple<int,int,int>& a){
return get<2>(a);
}
make_heap(x.begin(), x.end(), Comp);
错误
Severity Code Description Project File Line Suppression State
Error C2197 'bool (__cdecl *)(const std::tuple<int,int,int> &)': too many arguments for call Shash C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Tools\MSVC\14.24.28314\include\xutility 1481
我如何修改我的代码以将x转换为堆，或者甚至首先构造1?
最简单的方法是使用()运算符传递结构.例如
struct Comp {
bool operator()(const tuple<int,int,int>& a,
const tuple<int,int,int>& b){
return (get<2>(a) > get<2>(b));
}
};
并将其传递给make_heap
- Construction
i constructed a vector of tuples vector<tuple<int,int,int>> x. For sake of simplicity, lets assume it is constructed it this way.
vector<tuple<int,int,int>> x;
for (int ii=0; ii < 10; ii++){
for (int jj=0; jj < 10; jj++){
currpeak[0] = ii + rand() % 10;
currpeak[1] = jj + rand() % 10;
currpeak[2] = rand() % 100;
x.emplace_back(currpeak[0], currpeak[1], currpeak[2]);
}
}
Now i want to get the n largest tuples, according to the 3rd element, and append them to another variable vector<tuple<int,int,int>> y. Lets assume n=10.
- Sorting
Currently i am doing it this way : reverse sorting them, then choosing the first n elements.
// Sort them by 3rd element
bool sortbythird_desc(const tuple<int,int,int>& a,
const tuple<int,int,int>& b){
return (get<2>(a) > get<2>(b));
}
sort(x.begin(), x.end(), sortbythird_desc);
// Extract the top 10 elements from x and put into y
vector<tuple<int,int,int>> y;
for(int jdx =0; jdx<10; jdx++){
int curr_peak0=get<0>(x[jdx]);
int curr_peak1=get<1>(x[jdx]);
int curr_peak2=get<2>(x[jdx]);
y.emplace_back(curr_peak0, curr_peak1, curr_peak2);
}
However this is O(nlogn) operations due to the sorting.
- Failed heap attempt
If i can convert x to a heap, or even construct it as a heap from the beginning : O(n) operations. pop_heap : O(log n) times. In total it would take only O(n + log n) = O(n) operations. However the following fails
// Convert x to a heap
bool Comp(const tuple<int,int,int>& a){
return get<2>(a);
}
make_heap(x.begin(), x.end(), Comp);
Error
Severity Code Description Project File Line Suppression State
Error C2197 'bool (__cdecl *)(const std::tuple<int,int,int> &)': too many arguments for call Shash C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Tools\MSVC\14.24.28314\include\xutility 1481
How do i modify my code to convert x to a heap, or even to construct 1 in the first place ?
The easiest way is to pass a struct with the () operator. For example
struct Comp {
bool operator()(const tuple<int,int,int>& a,
const tuple<int,int,int>& b){
return (get<2>(a) > get<2>(b));
}
};
And pass this to make_heap
这篇关于将元组的向量转换/构造为堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！