C++ 迭代 vector 中特定内容的最有效方法

我有两个 vector ，vec 和 p，这样 p 是指向 vec 中不同位置的指针的 vector 。

所以像:

p[0] = &vec[12]
p[1] = &vec[20]
p[3] = &vec[1]

等等。
p 的大小将始终小于或等于 vec，并且不会包含对 vec 中相同位置的重复引用。

我想要的是一些数据结构，我可以遍历它以按照它们在 a 中指向的索引的顺序获取 p 的取消引用值。所以对于上面的例子，结果需要按照 vec[1]、vec[12]、vec[20] 的顺序迭代。

我知道可以在 vec 中获得位置 p 指向做类似 p[i] - &vec[0] 的事情，并且可能可以使用 std::sort 和自定义比较函数来实现这一点，但我觉得有一种比 ojit_code 更有效的方法来做到这一点排序函数的 O(nlogn)。我也可能完全错了。

谢谢你的帮助!

最佳答案

舍弃了几个脑子里的想法，想到了一个简单的:

std::vector<char> is_pointed_to(vec.size(), 0);//initialize the "bools" to "false"
//set is_pointed_to values
for(T* pointer : p) {
    size_t orig_index = pointer - &vec[0];
    is_pointed_to[orig_index] = 1; //set this index to "true"
}
//now do the iteration
for(int i=0; i<vec.size(); ++i) {
    if(is_pointed_to[i]) {
        //DO TASK HERE
    }
}

这显然是一个两遍算法，所以 O(n)。简单的。

StilesCrisis 提醒我这是 counting sort 的实现。

关于C++ 迭代 vector 中特定内容的最有效方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29173767/

Vec

C++ 迭代 vector 中特定内容的最有效方法