주문 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의 ID의 또 다른 벡터를 가지고 :

지금 요소가 my_data_ids에 의해 지정된 순서에 있는지 my_data_vec는 재 배열 할

std::vector<int> my_data_ids; 

. (unique_ptr은 std::move()으로 이동 의미가 필요함을 잊지 마십시오.)

알고리즘을 효율적으로 구현하는 방법은 무엇이며, STL 알고리즘은이를 달성하는 데 도움이됩니까? 나는 std::sort 어떤 도움이 될 것을 볼 수 없습니다.

편집 : O (n) 메모리 공간을 사용할 수 있지만 (메모리가 너무 걱정되지는 않음) ID는 임의적입니다 (실제로는 임의로 생성됩니다).

Answer 1

1. 색인에 ID를 my_data_ids에 매핑하는지도를 만듭니다.
2. 해당 맵의 ID 색인을 기준으로 std::unique_ptr<MyData>을 비교하는 함수 개체를 만듭니다.
3. 해당 기능 개체를 사용하여 my_data_vec을 정렬하려면 std::sort을 사용하십시오. 메모리가 부족하지만, 시간이 문제가되지 않는 경우

   // 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 벡터의 ID를 검색 할 수 있습니다 :

다음은이의 스케치입니다. 그러나 비교 당 두 개의 선형으로 복잡한 연산이 상당히 비싸기 때문에 이 실제로는이되어야합니다.

Answer 2

왜 데이터를 STL 세트로 이동하지 않으시겠습니까? 비교 기능 만 구현하면 완벽하게 정렬 된 데이터 세트가 매우 빨리 완성됩니다.

Answer 3

왜 map<int, unique_ptr<MyData>> (또는 multimap)을 사용하지 않으시겠습니까?