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={10203040};  //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)
특정 위치 이후 삭제	에)
순회	에)

앞으로 목록과 목록

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