Как быстро получить отсортированный подвектор из отсортированного вектора

У меня есть такая структура данных:

struct X {
  float value;
  int id;
};

вектор те (размер N (думаю, 100000), отсортированные по значению (остается постоянным во время выполнения программы):

std::vector values;

Теперь я хочу написать функцию

void subvector(std::vector const& values, 
               std::vector const& ids, 
               std::vector& out /*, 
               helper data here */);

, заполняет параметр out отсортированным подмножеством значений , заданных переданными идентификаторами (размер M N ] (примерно 0,8 раза N )), быстро (память не является проблемой, и это будет происходить неоднократно, поэтому создание таблиц поиска (вспомогательные данные ] из параметры функции) или что-то еще, что делается только один раз, вполне нормально). Создайте lookuptable lut , содержащий id -> смещение в значениях (подготовка, поэтому постоянное время выполнения)
create std :: vector tmp , размер N, заполненный недопустимыми идентификаторами (линейно в N )
для каждого идентификатора скопируйте значений [lut [id]] в tmp [lut [id]] (линейно в M )
цикл по tmp , копирование элементов в out (линейно по N )

это линейно по N (поскольку оно больше, чем M ), но временная переменная и повторное копирование меня беспокоят. Есть ли способ сделать это быстрее? Обратите внимание, что M будет близко к N , поэтому вещи, которые имеют O ( M log N ), являются неблагоприятными.

Редактировать : http://ideone.com/xR8Vp - это пример реализации упомянутого алгоритма, чтобы сделать желаемый результат понятным и доказать, что это выполнимо за линейное время - вопрос заключается в возможности избежать временной переменной или ускорение каким-либо другим способом, то, что не линейно, не быстрее :).