sorting - C++ Most efficient way iterate specific contents in vector -

i have 2 vectors, vec , p, such p vector of pointers different locations in vec.

so like:

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

etc. p's size less or equal vec, , contain no duplicate references same location in vec.

what i'd have data structure can iterate through dereferenced values of p in order of index pointing in a. above example, result need iterate through in order vec[1], vec[12], vec[20].

i know can position in vec p pointing doing p[i] - &vec[0], , implement using std::sort , custom comparing function, feel there more efficient way o(nlogn) of sort function. wrong that.

thanks help!

after discarding few mental ideas, thought of simple one:

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

this two-pass algorithm, o(n). easy.

stilescrisis reminds me implementation of counting sort.