вектор повторного заказа <станд :: unique_ptr <X>> задан вектор <const X*>

Question

У меня есть vector<std::unique_ptr<X>> и vector<const X*>, которые содержат один и тот же набор указателей, но в другом порядке. Я хочу, чтобы вектор уникальных указателей упорядочивался точно так же, как вектор указателей const.

Один способ, которым я мог бы это сделать, как это:

vector<std::unique_ptr<X>> uniq_ptrs; 
vector<const X*> const_ptrs; 
vector<std::unique_ptr<X>> tmp(uniq_ptrs.size()); 

hash_map<const X*, int> indices; 
for (int i = 0; i < const_ptrs->size(); ++i) { 
    indices[const_ptrs[i]] = i; 
} 
for (std::unique_ptr<X>& uniq_ptr : uniq_ptrs) { 
    tmp[indices[uniq_ptr.get()]].swap(uniq_ptr); 
} 
uniq_ptrs.swap(tmp) 

версия на месте, еще с hash_map:

vector<const X*> const_ptrs; 

hash_map<const X*, int> indices; 
for (int i = 0; i < const_ptrs.size(); ++i) { 
    indices[const_ptrs[i]] = i; 
} 
for (int i = 0; i < const_ptrs.size(); ++i) { 
    std::swap(uniq_ptrs[i], uniq_ptrs[indices[const_ptrs[i]]]); 
} 

Но я надеюсь, что есть более хороший способ, который не включают временный вектор хэш-карту и два прохода над данными.

Answer 1

Поскольку const_ptrs содержит же указатели как uniq_ptrs, нет необходимости использовать последний вообще, и не нужно также для временного. Однако вы должны быть осторожны, чтобы не удалять объекты.

// release the unique_ptrs of their ownership 
for(auto&x : uniq_ptrs) 
    x.release(); 
// fill the array with the pointers in another order 
uniq_ptrs.clear(); 
for(auto x : const_ptrs) 
    uniq_ptrs.emplace_back(const_cast<X*>(x)); // const_cast okay here 

Answer 2

Если производительность не было проблемой:

auto idx_of = [&](X const* p) { 
    return std::distance(begin(const_ptrs), std::find(begin(const_ptrs), end(const_ptrs), p)); 
}; 
std::sort(begin(uniq_ptrs), end(uniq_ptrs), [&](std::unique_ptr<X> const& a, std::unique_ptr<X> const& b) { 
      return idx_of(a.get()) < idx_of(b.get()); 
     }); 

Если производительность является проблемой, использовать промежуточную карту:

hash_map<const X*, int> indices; 
for (auto i = 0u; i < const_ptrs.size(); ++i) { 
    indices[const_ptrs[i]] = i; 
} 

std::sort(begin(uniq_ptrs), end(uniq_ptrs), [&](std::unique_ptr<X> const& a, std::unique_ptr<X> const& b) { 
      return indices[ a.get() ] < indices[ b.get() ]; 
     }); 

--- Если вы абсолютно уверены в наборах указатели, вы могли бы обмануть и создать совершенно новые unique_ptrs «на лету» .-- Хм не будет работать из-за const, как вы сказали.

Обновление Просто отпустите const, если производительность здесь. Если вы знаете, что объекты не фактически Const, вы можете использовать зло const_cast<>

Смотреть все три подхода: Live on Coliru

#include <unordered_map> 
#include <algorithm> 
#include <memory> 
#include <vector> 
#include <cassert> 

template <typename K, typename V> 
using hash_map = std::unordered_map<K,V>; 

struct X{}; 

int main() 
{ 
    std::vector<std::unique_ptr<X>> uniq_ptrs; 
    std::vector<const X*> const_ptrs; 

    // naive approach, no performance worries 
    auto idx_of = [&](X const* p) { 
     return std::distance(begin(const_ptrs), std::find(begin(const_ptrs), end(const_ptrs), p)); 
    }; 
    std::sort(begin(uniq_ptrs), end(uniq_ptrs), [&](std::unique_ptr<X> const& a, std::unique_ptr<X> const& b) { 
       return idx_of(a.get()) < idx_of(b.get()); 
      }); 

    // less naive approach, no performance worries 
    hash_map<const X*, int> indices; 
    for (auto i = 0u; i < const_ptrs.size(); ++i) { 
     indices[const_ptrs[i]] = i; 
    } 

    std::sort(begin(uniq_ptrs), end(uniq_ptrs), [&](std::unique_ptr<X> const& a, std::unique_ptr<X> const& b) { 
       return indices[ a.get() ] < indices[ b.get() ]; 
      }); 

    // cheating! only not UB if you know the objects aren't "physically" const 
    assert(const_ptrs.size() == uniq_ptrs.size()); 
    for (auto i = 0u; i < const_ptrs.size(); ++i) { 
     uniq_ptrs[i].release(); 
     uniq_ptrs[i].reset(const_cast<X*>(const_ptrs[i])); 
    } 
}