Закажите контейнер участником с STL

Question

Предположим, у меня есть некоторые данные, хранящиеся в контейнере unique_ptr s:

struct MyData {
    int id;  // a unique id for this particular instance
    data some_data; // arbitrary additional data
};

// ...

std::vector<std::unique_ptr<MyData>> my_data_vec;

Порядок my_data_vec важен.Предположим, теперь у меня есть другой вектор идентификаторов MyDatas:

std::vector<int> my_data_ids;

Теперь я хочу переставить my_data_vec так, чтобы элементы были в последовательности, указанной my_data_ids.(Не забудьте, что для перемещения unique_ptr требуется семантика перемещения с помощью std::move().)

Какой наиболее алгоритмически эффективный способ добиться этого, и подойдет ли какой-либо из алгоритмов STL для достижения этой цели?Я не вижу, чтобы std::sort помог бы.

Редактировать: Я могу использовать O (n) памяти (не слишком беспокоюсь о памяти), но идентификаторы произвольные (в моем конкретном случае онина самом деле генерируются случайным образом).

Answer 1

1. Создайте карту, которая отображает идентификаторы на их индекс в my_data_ids.
2. Создайте объект функции, который сравнивает std::unique_ptr<MyData> на основе индекса их идентификатора в этой карте.
3. Используйте std::sort для сортировки my_data_vec с использованием этого функционального объекта.

Вот эскиз этого:

// Beware, brain-compiled code ahead!
typedef std::vector<int> my_data_ids_type;
typedef std::map<int,my_data_ids_type::size_type> my_data_ids_map_type;

class my_id_comparator : public std::binary_function< bool
                                                    , std::unique_ptr<MyData>
                                                    , std::unique_ptr<MyData> > {
public:
  my_id_comparator(const my_data_ids_map_type& my_data_ids_map)
    : my_data_ids_map_(my_data_ids_map) {}

  bool operator()( const std::unique_ptr<MyData>& lhs
                 , const std::unique_ptr<MyData>& rhs ) const
  {
     my_data_ids_map_type::const_iterator it_lhs = my_data_ids_map_.find(lhs.id);
     my_data_ids_map_type::const_iterator it_rhs = my_data_ids_map_.find(rhs.id);
     if( it_lhs == my_data_ids_map_.end() || it_rhs == my_data_ids_map_.end() )
       throw "dammit!"; // whatever
     return it_lhs->second < it_rhs->second;
  }
private
  my_data_ids_map_type& my_data_ids_map_;
};

//...

my_data_ids_map_type my_data_ids_map;
// ...
// populate my_data_ids_map with the IDs and their indexes from my_data_ids
// ...
std::sort( my_data_vec.begin(), my_data_vec.end(), my_id_comparator(my_data_ids_map) );

Если памяти мало, но время не имеет значения, вы можете покончить с картой и искать идентификаторы в векторе my_data_ids для каждого сравнения. Тем не менее, вы должны быть действительно отчаянно нуждающимися в памяти, чтобы сделать это, поскольку две линейно сложные операции на сравнение будут довольно дорогими.

Answer 2

Почему бы вам просто не использовать map<int, unique_ptr<MyData>> (или multimap)?

Answer 3

Почему бы вам не попробовать переместить данные в набор STL?вам нужно только реализовать функцию сравнения, и вы получите очень упорядоченный набор данных очень быстро.