C ++. The most efficient way to iterate over specific content into a vector

Question

I have two vectors, vec and p, such that p is a vector of pointers to different locations in vec.

So something like:

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

etc .. p the size will always be less than or equal to vec and will not contain duplicate links to the same place in vec.

What I would like to have is some data structure through which I can iterate to get the dereferenced p values ​​in the order of the index they point to in a. Thus, for the above example, the result will have to go through the order vec [1], vec [12], vec [20].

I know that I can get a position in vec, since p indicates that it does something like p[i] - &vec[0], and probably can implement this using std :: sort and a custom comparison function, but I feel there is more efficient way to do this than O (nlogn) sort functions. I could be wrong about that too.

Thanks for any help!

Answer 1

After discarding a few mental ideas, I thought of a simple one:

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
    }
}

This is obviously a two-pass algorithm, therefore O (n). Easy.

StilesCrisis reminds me that this is an implementation of counting sorting .