C++에서 목록의 일부를 반복합니다.

Question

저는 C++을 처음 사용하고 있으며, 언어에 익숙해 지도록 병합 정렬을 구현 중입니다. 현재

나는 정수의 목록을 가지고 있고 2 개 하위 목록을 작성하고 '왼쪽'라는 이름의 목록에 원래 목록의 첫 번째 절반을 저장하기 원하는리스트로 나머지 절반은 '권리'

전 이름 : 원래 목록 데이터가 16, 24, 56, 12, 89라고 가정합니다. 이 목록을 반복하여 16, 24를 새로운 하위 목록 '왼쪽' 에 추가하고 하위 목록 '오른쪽'에 56, 12, 89를 추가하십시오. 이렇게 남겨두면 [16, 24] 이되고 오른쪽은 [56 , 12, 89]

여기에 지금있는 코드가 있습니다. if 조건문에 어떤 조건을 써야합니까? 이 작동 할

list<int> left, right; 
    int midpt = l.size()/2; 
    for(listIt = l.begin(); listIt!= l.end(); listIt++){ 
     if() left.push_back(*listIt); 
     if() right.push_back(*listIt); 
    } 

Answer 1

('난'함수의 매개 변수에 전달 된 목록의 이름입니다).

list<int> left, right; 
int midpt = l.size()/2; 
int count = 0; 
for(listIt = l.begin(); listIt!= l.end(); listIt++){ 
    if (count++ < midpt) 
     left.push_back(*listIt); 
    else 
     right.push_back(*listIt); 
} 

Answer 2

for-loop 대신 std::list::insert을 사용하십시오. 시도 -

left.insert(l.begin(), l.begin() + midpt); 
right.insert(l.begin() + midpt, l.end()); 

Answer 3

이 쉽게 될 수 있습니다

는

#include <iterator> 
#include <list> 

auto middle = std::next(l.begin(), l.size()/2); 

std::list<int> left(l.begin(), middle), right(middle, l.end()); 

이 직접 각각의 범위에서, 두 개의 새로운 목록, left 및 right를 구축합니다. std::next 알고리즘은 주어진 반복자를 주어진 단계 수만큼 앞당긴 반복자를 반환합니다. std::list<int>::size()은 반복자를 반복 할 때 선형 작업을 수행하지만 C++ 11부터는 런타임 런타임이 일정합니다.

Answer 4

std::list은 이중 연결 목록을 정의 했으므로 다소 다른 접근 방법을 고려해 볼 가치가 있습니다. 목록의 중간을 찾고 그 왼쪽에있는 것을 하나의 목록에 추가하는 대신 다른 목록에 추가하는 것이 좋습니다. 목록의 첫 번째 요소 인 left 목록을 right 목록의 마지막 요소로 추가하는 것이 좋습니다. 반복자 (반복자가 만날 때까지) 반복.

다른 대부분의 방법은 가운데를 찾기 위해 목록을 선형 순회 (traversal)해야하며 두 개의 새로운 목록을 작성하기 위해 양측을 선형 순회 (traversal)합니다. 즉, 목록을 1.5 번 탐색합니다.

전면과 후면에서 동시에 트래버스하면 목록을 한 번만 탐색하여 전체 작업을 수행 할 수 있습니다. Big-O의 복잡성 측면에서 볼 때,이 두 가지 경우는 동일하지만 (O (N)), 더 실용적인 측면에서 볼 때 목록을 가로 지르는 속도는 1.5 배가되는 속도보다 빠릅니다. 목록 크기, 캐싱은 아마도 어느 정도는 영향을 미칠 것입니다).