C++ Разбиение списка в O (n) вместо O (1)

Question

Я реализую список в C++, и у меня есть проблема со сложностью метода split. . Вместо постоянной временной сложности, моя сложность линейна (О (п)) Вот мой код:

 /* 
     * 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

Я нашел проблему. std::pair создал копию двух списков, которые я возвращал, так что это заняло линейное время. Когда I std::move перечисляет пару, он работает во времени, равном где я раскалываю.