C++ Splitting Liste in O (n) anstelle von O (1)

Question

Mir Umsetzung Liste in C++, und ich habe Problem mit der Komplexität von Split-Methode. . Statt konstanter Zeitkomplexität, meine Komplexität ist linear (O (n)) Hier ist mein Code:

 /* 
     * Destructively splits the list into the two that are returned. 
     * The first list consists of elements formerly in the [begin, place) range. 
     * The second list consists of elements formerly in the [place, end) range. 
     */ 
     std::pair<list, list> list::split(list::const_iterator place) { 
      list first_list{}, second_list{}; 
      if (head == nullptr) { 
       return{ first_list, second_list }; 
      } 
      if (head == place.current_ptr) { 
       swap(second_list); 
       return{ first_list, second_list }; 
      } 
      if (place.current_ptr == nullptr) { 
       swap(first_list); 
       return{ first_list, second_list }; 
      } 
      first_list.head = head; 
      first_list.num_elements = std::distance(cbegin(), place); 
      first_list.tail = place.current_ptr->prev; 

      second_list.head = place.current_ptr; 
      if (second_list.head == nullptr) { 
       second_list.tail = nullptr; 
     } 
     else 
     { 
      second_list.head->prev = nullptr; 
      second_list.tail = tail; 
     } 
     second_list.num_elements = num_elements - first_list.num_elements; 
     first_list.tail->next = nullptr; 

     tail = head = nullptr; 
     num_elements = 0; 

     return{ first_list, second_list }; 
    } 

Answer 1

fand ich das Problem. std::pair erstellte Kopie der zwei Listen, die ich zurückgab, das war, was die lineare Zeit nahm. Wenn ich std::move auf das Paar listet, läuft es zeitlich gleich wo ich splitte.