시퀀스 컨테이너(C++)

이 문서는 Wikipedia의 품질 기준을 충족하기 위해 청소가 필요할 수 있습니다.구체적인 문제는 '토크 참조'입니다. 가능하면 이 문서를 개선해 주십시오. (2011년 12월) (이 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다)

컴퓨팅에서 시퀀스 컨테이너는 데이터 요소의 저장을 구현하는 C++ 프로그래밍 언어의 표준 라이브러리에 있는 컨테이너 클래스 템플릿 그룹을 말합니다.템플릿이므로 정수나 사용자 정의 클래스 등 임의의 요소를 저장하는 데 사용할 수 있습니다.모든 순차 컨테이너의 한 가지 공통 특성은 요소에 순차적으로 액세스할 수 있다는 것입니다.다른 모든 표준 라이브러리 구성 요소와 마찬가지로 이름 공간 규격에 있습니다.

다음 컨테이너는 C++ 표준의 현재 개정판에 정의되어 있습니다.array,vector,list,forward_list,deque각 컨테이너는 데이터 스토리지에 대해 서로 다른 알고리즘을 구현합니다. 즉,^[1] 각 컨테이너는 서로 다른 동작에 대해 서로 다른 속도를 보장합니다.

• array는 컴파일 타임의 크기 변경할 수 없는 어레이를 실장하고 있습니다.
• vector는 요소를 추가할 때 크기를 자동으로 조정하는 기능과 빠른 랜덤 액세스 기능을 갖춘 어레이를 구현합니다.
• deque는 비교적 빠른 랜덤액세스를 가진 더블 엔드 큐를 실장합니다.
• list는 이중 링크 목록을 구현합니다.
• forward_list는 단일 링크 목록을 구현합니다.

각 컨테이너가 제대로 작동하려면 요소를 복사할 수 있어야 하므로 요소의 유형은 다음을 충족해야 합니다.CopyConstructible그리고.Assignable필요조건에 따라주세요.^[2]지정된 컨테이너에 대해 모든 요소는 동일한 유형에 속해야 합니다.예를 들어 데이터를 동일한 컨테이너 인스턴스 내에 char 및 int 형식으로 저장할 수 없습니다.

역사

이 섹션은 확장해야 합니다.추가함으로써 도움이 될 수 있습니다. (2011년 12월)

원래만vector,list그리고.deque정의되어 있습니다.1998년 C++ 언어가 표준화되기 전까지는 SGI가 발행한 STL(Standard Template Library)의 일부였습니다.

그array컨테이너는 처음에 여러 권의 책에 다양한 이름으로 등장했습니다.나중에 Boost 라이브러리에 통합되었고 표준 C++ 라이브러리에 포함되도록 제안되었습니다.다음을 포함하는 동기arrayC-스타일 어레이의 두 가지 문제를 해결한다는 것입니다.STL과 같은 인터페이스가 없는 것과 다른 오브젝트와 같이 복사할 수 없는 것입니다.처음에 C++ TR1에 등장하고 나중에 C++11에 통합되었습니다.

그forward_listC++11에 공간 효율이 뛰어난 대체 수단으로 컨테이너가 추가되었습니다.list리버스 반복이 필요 없는 경우.

특성.

array,vector그리고.deque모두 요소에 대한 고속 랜덤액세스를 서포트하고 있습니다. list는 양방향 반복을 지원하지만,forward_list는 단방향 반복만 지원합니다.

array는 요소의 삽입 또는 분리를 지원하지 않습니다. vector는, 엔드에서의 신속한 요소 삽입 또는 분리를 서포트하고 있습니다.벡터의 끝부분이 아닌 요소의 삽입 또는 제거는 삽입위치와 벡터 끝부분 사이의 요소를 복사해야 한다.따라서 영향을 받는 요소에 대한 반복기는 무효화됩니다.실제로 삽입하면 모든 반복기가 비활성화될 수 있습니다.또한 에 할당된 스토리지가vector요소가 너무 작아서 삽입할 수 없습니다.새 어레이가 할당되고 모든 요소가 새 어레이로 복사 또는 이동되며 오래된 어레이가 해방됩니다. deque,list그리고.forward_list모두 컨테이너 내 어디에서나 요소를 신속하게 삽입 또는 제거할 수 있습니다. list그리고.forward_list는, 이러한 조작에 있어서의 반복자의 유효성을 보관 유지합니다만,deque모두 무효가 됩니다.

벡터

의 요소vector인접하게 ^[3]저장됩니다.모든 동적 어레이 구현과 마찬가지로 벡터는 메모리 사용량이 적고 참조 및 데이터 캐시 사용률의 인접성이 우수합니다.데크나 목록과 같은 다른 STL 컨테이너와 달리 벡터는 사용자가 컨테이너의 초기 용량을 나타낼 수 있도록 합니다.

벡터는 랜덤 액세스를 허용합니다.즉, 벡터의 요소는 배열의 요소와 동일한 방식으로 참조할 수 있습니다(배열 인덱스에 의해).반면 링크 목록 및 집합은 랜덤 액세스 또는 포인터 산술을 지원하지 않습니다.

벡터 데이터 구조는 특정 데이터 스토리지에 필요한 메모리를 빠르고 쉽게 할당할 수 있으며, 상각된 일정 시간 내에 할당할 수 있습니다.이 기능은 특히 목록을 설정하기 전에는 길이를 알 수 없지만 삭제(아마 마지막 이외)가 드문 목록에 데이터를 저장할 때 유용합니다.벡터에서 요소를 지우거나 벡터를 완전히 지우더라도 해당 요소와 관련된 메모리가 반드시 해방되는 것은 아닙니다.

용량 및 재할당

일반적인 벡터 실장은 내부적으로 동적으로 ^[1]할당된 어레이에 대한 포인터와 벡터의 용량과 크기를 유지하는 데이터 멤버로 구성됩니다.벡터의 크기는 실제 요소의 수를 나타내며 용량은 내부 배열의 크기를 나타냅니다.

새 요소가 삽입되면 벡터의 새 크기가 용량보다 커지면 재할당이 발생합니다.^[1][4]이 경우 일반적으로 벡터는 새로운 스토리지 영역을 할당하고 이전에 보유하고 있던 요소를 새로운 스토리지 영역으로 이동하여 오래된 영역을 해방합니다.

이 프로세스 중에 요소의 주소가 변경되기 때문에 벡터 내의 요소에 대한 참조 또는 반복기는 ^[5]비활성화됩니다.유효하지 않은 참조를 사용하면 정의되지 않은 동작이 발생합니다.

reserve() 연산은 불필요한 재할당을 방지하기 위해 사용할 수 있습니다.예약(n) 호출 후, 벡터의 용량은 적어도 ^[6]n이 될 것을 보증한다.

벡터는 요소의 특정 순서를 유지하므로 새 요소를 벡터의 시작 또는 중간에 삽입할 때 후속 요소가 할당 연산자 또는 복사 생성자 측면에서 뒤로 이동합니다.이것에 의해, 삽입점 후의 요소에 대한 참조나 반복은 ^[7]무효가 된다.

C++ 벡터는 설계상 메모리의 임플레이스 재할당을 지원하지 않습니다.즉, 벡터의 재할당 시, 보유하고 있던 메모리는 항상 요소의 복사 컨스트럭터를 사용하여 메모리의 새로운 블록에 복사되어 해방됩니다.이는 벡터에 플레인오래된 데이터가 저장되어 있어 메모리블록을 초과하는 인접 공간을 할당에 사용할 수 있는 경우에는 비효율적입니다.

불 전문화

Standard Library(표준 라이브러리)는 다음과 같은 전문화를 정의합니다.vector의 템플릿bool이 전문화에 대한 설명은 구현에서 요소를 포장해야 한다는 것을 나타냅니다.bool1비트 ^[8]메모리만 사용합니다.이것은 많은 사람들이 ^[9][10]잘못이라고 생각한다. vector<bool>는 C++ 표준 라이브러리 컨테이너 요건을 충족하지 않습니다.예를 들어,container<T>::reference유형의 진정한 l값이어야 합니다.T이 경우는 해당되지 않습니다.vector<bool>::reference로 변환할 수 있는 프록시 클래스입니다.bool마찬가지로,^[11]vector<bool>::iterator을 산출하지 않다bool&참조된 경우.C++ 표준 위원회와 라이브러리 작업 그룹 사이에는 다음과 같은 일반적인 합의가 있다.vector<bool>이 기능은 다른 이름으로 ^[12]재도입됩니다만, 표준 라이브러리에서 제외됩니다.

목록.

그list데이터 구조는 이중 링크 리스트를 구현합니다.데이터는 비연속적으로 메모리에 저장되므로 리스트 데이터 구조는 리스트에 새로운 요소가 삽입될 때 벡터에 의해 필요할 수 있는 메모리의 재할당을 회피할 수 있다.

리스트 데이터 구조는 필요에 따라 메모리를 할당 및 할당 해제하기 때문에 현재 사용하지 않는 메모리는 할당하지 않습니다.리스트에서 요소를 삭제하면 메모리가 해방됩니다.

목록은 새 요소를 목록에 삽입할 때 효율적입니다${\displaystyle .}$ 이것은 O${\displaystyle }$( ${\displaystyle 1}$)$$\ $displaystyle$O (1$)$} $작업$입니다.벡터처럼 이동할 필요가 없습니다.

리스트에는 벡터$O$ ( 1)\$displaystyle$O (1)$조작$)와$$같은 랜덤 액세스 기능이 없습니다.목록 내 노드에 액세스하려면 O${\displaystyle }$(${\displaystyle n}$ $)\displaystyle$ O$(n)$ $조작$이 필요합니다.이 조작에서는 액세스해야 할 노드를 찾기 위해 목록 트래버설이 필요합니다.

데이터 타입(ints 등)이 작을 경우 메모리 오버헤드는 벡터보다 훨씬 더 중요합니다.각 노드가 차지하다sizeof(type) + 2 * sizeof(type*)포인터는 보통 1워드(32비트 운영체제에서는 보통 4바이트)입니다.즉, 4바이트 정수의 리스트는 정수 벡터의 약 3배의 메모리를 차지합니다.

전송 리스트

그forward_list데이터 구조는 단일 링크 리스트를 구현합니다.

데쿠

deque는 더블 엔드 큐를 구현하는 컨테이너 클래스 템플릿입니다.계산 복잡도는 다음과 같습니다.vector대부분의 조작에 대해서, 소자 시퀀스의 양단에서 상각된 고정 시간 삽입 및 삭제를 제공하는 것을 제외하고, 현저한 예외입니다.와는 달리vector,deque는 비인접적인 메모리블록을 사용하며 컨테이너 용량 및 메모리 재할당 순간을 제어하는 수단을 제공하지 않습니다.맘에 들다vector,deque는 랜덤 액세스의 리테이터를 서포트하고 있습니다.요소를 삽입 및 삭제하면 디큐에 대한 모든 리테이터가 무효가 됩니다.

어레이

array는 크기 조정 불가능한 어레이를 구현합니다.크기는 컴파일 시 템플릿파라미터에 의해 결정됩니다.기본적으로 C 스타일 배열 래퍼이므로 컨테이너는 할당자를 지원하지 않습니다.

기능의 개요

컨테이너는 컨테이너 이름 뒤에 명명된 헤더에 정의됩니다.vector헤더에 정의되어 있습니다.<vector> 모든 컨테이너는 컨테이너 개념의 요구 조건을 충족합니다. 즉, 컨테이너 개념의 요구 조건을 충족합니다.begin(),end(),size(),max_size(),empty(),그리고.swap()방법들.

멤버 함수

목록 클래스의 일부로 사용할 수 있는 다른 연산도 있으며 C++ STL(알고리즘(C++))의 일부인 알고리즘도 있습니다.list그리고.forward_list클래스:

운용

• list::merge그리고.forward_list::merge- 정렬된 두 목록을 병합합니다.
• list::splice그리고.forward_list::splice_after- 다른 목록에서 요소를 이동합니다.
• list::remove그리고.forward_list::remove- 지정된 값과 동일한 요소를 제거합니다.
• list::remove_if그리고.forward_list::remove_if- 특정 기준을 충족하는 요소 제거
• list::reverse그리고.forward_list::reverse- 요소의 순서를 반대로 합니다.
• list::unique그리고.forward_list::unique- 연속된 중복 요소 제거
• list::sort그리고.forward_list::sort- 요소를 정렬합니다.

비구성원 함수

사용 예

다음 예시는 벡터 및 C++ 표준 라이브러리 알고리즘에 관한 다양한 기술을 보여 줍니다.특히, erase-remove idiod를 사용한 shuffling, 정렬, 최대 요소 검색 및 벡터로부터의 지우기를 보여 줍니다.

#실패하다 <iostream> #실패하다 <blocks> #실패하다 <어레이> #실패하다 <blocks>// 정렬, max_filename, random_filename, remove_if, lower_bound #실패하다 <기능>// 더 크다 #실패하다 <반복기>// 시작, 종료, cbegin, cend, 거리  // 여기서 사용하는 것은 편리합니다.실제 프로그램에서는 신중하게 사용해 주세요.  사용. 네임스페이스 표준;  인트 주된() {   배열 arr{ 1, 2, 3, 4 };    // 배열에서 벡터 초기화   벡터< >인트> 숫자(cbegin(arr), 센드(arr));    // 벡터에 더 많은 숫자를 삽입합니다.   숫자.푸시백(5);   숫자.푸시백(6);   숫자.푸시백(7);   숫자.푸시백(8);   // 벡터는 현재 {1, 2, 3, 4, 5, 6, 7, 8}을(를) 보유하고 있습니다.    // 요소를 무작위로 섞습니다.   섞다(시작한다.(숫자), 끝.(숫자));      // 가장 큰 요소 O(n)를 찾습니다.   자동 가장 큰 = max_displaces(최대_displaces)(cbegin(숫자), 센드(숫자));      외치다 << > '가장 많은 건' << > *가장 큰 << > "\n";   외치다 << > "인덱스에 있습니다." << > 거리(가장 큰, cbegin(숫자)) << > "\n";      // 요소 정렬   종류(시작한다.(숫자), 끝.(숫자));    // 벡터 내에서 숫자 5의 위치를 찾습니다.   자동 다섯개 = 하한(cbegin(숫자), 센드(숫자), 5);        외치다 << > 숫자 5는 인덱스에 있습니다. << > 거리(다섯개, cbegin(숫자)) << > ‘\n’;      // 4보다 큰 요소를 모두 지웁니다.   숫자.지우다(     삭제_if(시작한다.(숫자),               끝.(숫자),               [](자동 n) 콘스펙트 { 돌아가다 n > 4; });      // 나머지 숫자를 모두 인쇄합니다.   위해서 (컨스턴트 자동& 요소 : 숫자)     외치다 << > 요소 << > " "; } 

출력은 다음과 같습니다.

가장 큰 숫자는 8입니다.지수 6에 위치합니다(실시에 따라 다름).숫자 5는 색인 4 1 2 3 4에 있습니다.

레퍼런스

• 윌리엄 포드, 윌리엄 탑데이터 구조(C++ 및 STL, Second Edition 포함)프렌티스 홀, 2002년 ISBN0-13-085850-1.4장: 벡터 클래스, 195–203페이지.
• Josuttis, Nicolai M. (1999). The C++ Standard Library. Addison-Wesley. ISBN 0-201-37926-0.

메모들