C++ STL의 전달 목록

Forward_list 컨테이너는 다음의 구현을 제공합니다. 단일 연결 리스트 데이터 구조. 각 요소가 시퀀스의 다음 요소를 가리키는 비연속 메모리에 데이터를 저장합니다. 이렇게 하면 요소의 위치가 알려지면 삽입과 삭제가 더 빨라집니다.

통사론

전달 목록은 다음과 같이 정의됩니다. 표준::forward_list 클래스 템플릿 내부 < 앞으로_목록 > 헤더 파일.

앞으로_목록 fl;

어디

티: 정방향 목록에 있는 요소의 데이터 유형입니다.
에프: 전달 목록에 할당된 이름입니다.

선언 및 초기화

아래 예제와 같이 여러 가지 방법으로 Forward_list를 선언하고 초기화할 수 있습니다.

C++

    #include          using     namespace     std  ;   void     printFL  (  forward_list   <  int  >&     fl  )     {      for     (  auto     i     :     fl  )      cout      < <     i      < <     ' '  ;      cout      < <     'n'  ;   }   int     main  ()     {          // Creating an empty forward_list      forward_list   <  int  >     fl1  ;      // Creating a forward_list with      // default value      forward_list   <  int  >     fl2  (  3       4  );          // Creating a forward_list from an      // initializer list      forward_list   <  int  >     fl3     =     {  1       5       3       4  };          printFL  (  fl2  );      printFL  (  fl3  );      return     0  ;   }

산출

4 4 4 1 5 3 4

예: 위 프로그램에서는 세 가지 방법으로 간단하게 초기화된 정방향 목록을 만듭니다.

성명 앞으로_목록 FL1 빈 정수 정방향 목록을 생성합니다.
성명 앞으로_목록 fl2(34) 크기가 3이고 각 요소가 4인 정방향 목록을 만듭니다.
성명 앞으로_목록 fl3 = {1 5 3 4} 정방향 목록을 생성하고 초기화 목록의 요소로 초기화합니다.

기본 작업

정방향 목록에서 수행할 수 있는 기본 작업은 다음과 같습니다.

1. 요소에 접근하기

정방향 목록의 요소는 배열이나 벡터와 같은 인덱스를 사용하여 액세스할 수 없습니다. 목록에 접근하려면 처음부터 원하는 위치까지 순차적으로 이동해야 합니다. 이 작업은 증분을 통해 수행할 수 있습니다. 시작하다() 반복자이지만 사용하는 것이 더 좋습니다 다음() 또는 전진() 기능.

그러나 목록의 첫 번째 요소는 다음을 통해 쉽게 액세스할 수 있습니다. 앞쪽() 방법.

예:

C++

    #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Access the first element      cout      < <     fl  .  front  ()      < <     endl  ;          // Access third element      auto     it     =     next  (  fl  .  begin  ()     2  );      cout      < <     *  it  ;      return     0  ;   }

산출

1 3

예: 위 프로그램에서 첫 번째 요소는 다음을 사용하여 인쇄됩니다. 앞쪽() 방법. 세 번째 요소에 액세스하려면 다음() 반복자를 처음부터 두 위치 이동하는 데 사용됩니다. *그것 반복자를 역참조하는 데 사용됩니다.

2. 요소 삽입

다음을 사용하여 요소를 정방향 목록에 삽입할 수 있습니다. insert_after() 기능. 요소를 삽입하려면 반복자가 필요합니다. 그러나 전면에서의 빠른 삽입은 다음과 같은 방식으로 지원됩니다. push_front() 방법.

예:

C++

    #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  5       4  };      // Inserting Element at front      fl  .  push_front  (  1  );          // Insert 3 after the second element      auto     it     =     fl  .  begin  ();      advance  (  it       1  );      fl  .  insert_after  (  it       3  );          for     (  auto     x  :     fl  )     cout      < <     x      < <     ' '  ;      return     0  ;   }

산출

1 5 3 4

설명: 이 프로그램에서는 forward_list의 첫 번째 요소가 다음을 사용하여 앞에 삽입됩니다. push_front() 기능. 그런 다음 반복자가 생성되고 다음을 사용하여 한 위치 앞으로 이동됩니다. 전진() 기능. 그 후 요소 5 다음을 사용하여 두 번째 요소 뒤에 삽입됩니다. insert_after() 기능.

3. 요소 업데이트

기존 요소의 값은 해당 요소에 액세스하고 다음을 사용하여 간단히 변경할 수 있습니다. 할당 연산자 새 값을 할당합니다.

예:

C++

    #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Updating first element      fl  .  front  ()     =     111  ;      cout      < <     fl  .  front  ()      < <     endl  ;          // Updating third element      auto     it     =     next  (  fl  .  begin  ()     2  );      *  it     =     333  ;      cout      < <     *  it  ;      return     0  ;   }

산출

111 333

4. 요소 찾기

정방향 목록은 요소를 검색하는 멤버 함수를 제공하지 않지만 다음을 사용할 수 있습니다. 찾다() 주어진 값을 찾는 알고리즘.

예 :

C++

    #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Finding 3      auto     it     =     find  (  fl  .  begin  ()     fl  .  end  ()     3  );          if     (  it     !=     fl  .  end  ())     cout      < <     *  it  ;      else     cout      < <     'Element not Found'  ;      return     0  ;   }

산출

5. 횡단

정방향 목록은 다음을 사용하여 탐색할 수 있습니다. 시작하다() 그리고 끝() 루프가 있는 반복자는 앞으로만 이동할 수 있고 뒤로는 이동할 수 없습니다.

예:

C++

    #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };          // Traversing using range-based for loop      for  (  auto     i     :     fl  )      cout      < <     i      < <     ' '  ;      cout      < <     endl  ;          return     0  ;   }

산출

1 5 3 4

6. 요소 삭제

정방향 목록에서는 다음을 사용하여 주어진 위치의 요소를 삭제할 수 있습니다. 지우기_후() 방법. 이 메서드는 반복자를 대상 요소 앞의 한 위치로 가져옵니다. 다음을 사용하여 전면에서 빠른 삭제가 가능합니다. 팝프론트() 방법.

예:

C++

    #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Delete first element      fl  .  pop_front  ();          // Delete third element      auto     it     =     fl  .  begin  ();      advance  (  it       1  );      fl  .  erase_after  (  it  );          for     (  auto     x  :     fl  )     cout      < <     x      < <     ' '  ;      return     0  ;   }

산출

5 3

7. 전달 목록의 크기

Forward_list에는 내장된 size() 함수가 없습니다. 크기를 찾으려면 루프를 사용하거나 std:: 거리를 사용하여 요소를 수동으로 계산해야 합니다.

C++

    #include          #include         #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     flist  =  {  10    20    30    40  };      //Calculate size by counting elements using std:: distance      int     size  =  distance  (  flist  .  begin  ()  flist  .  end  ());      cout   < <  'Size of forward_list: '   < <  size   < <  endl  ;      return     0  ;   }

산출

Size of forward_list: 4

8. 빈()

Forward_list가 비어 있는지 확인하는 데 사용됩니다.
목록이 비어 있으면 true를 반환하고 그렇지 않으면 컨테이너에 데이터가 없는지 빠르게 확인할 수 있도록 false를 반환합니다.

C++

    #include          #include         using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     flist  ;      if     (  flist  .  empty  ())     {      cout      < <     'The forward_list is empty.'      < <     endl  ;      }      flist  .  push_front  (  10  );      if     (  !  flist  .  empty  ())     {      cout      < <     'The forward_list is not empty.'      < <     endl  ;      }      return     0  ;   }

산출

The forward_list is empty. The forward_list is not empty.

시간 복잡도

아래 표에는 정방향 목록에서 위 작업의 시간 복잡도가 나열되어 있습니다.

작업	시간 복잡도
첫 번째 요소에 액세스	오(1)
액세스 n ^일 요소	에)
앞쪽에 삽입	오(1)
특정 위치 뒤에 삽입	에)
첫 번째 요소 삭제	오(1)
특정 위치 이후 삭제	에)
순회	에)

앞으로 목록과 목록

특징	앞으로_목록	목록
연결리스트의 종류	단일 연결 리스트	이중 연결 리스트
순회	앞으로만 이동할 수 있음	앞뒤로 모두 이동할 수 있습니다.
메모리 사용량	더 적은 메모리를 사용합니다(노드당 하나의 포인터만 사용).	더 많은 메모리를 사용합니다(노드당 포인터 2개).
삽입/삭제	삽입 및 삭제는 빠르지만 특정 위치나 그 이후에만 가능	어느 위치에서나(위치 앞이나 뒤) 빠른 삽입 및 삭제
지원되는 기능	목록에 비해 제한됨(size() 없음 역방향 반복자 없음)	size() reverse() 양방향 반복자를 포함한 더욱 완전한 인터페이스입니다.