컨테이너란 무엇입니까?

먼저 C에서 컨테이너는 다음과 같이 정의된다는 점을 이해해야 합니다. 데이터 저장소에는 다른 객체나 다른 객체에 대한 포인터를 보유할 수 있는 객체 유형이 있습니다. 컨테이너. 아주 간단히 말하면, 컨테이너는 다른 객체를 저장하는 객체입니다. 물론 이것은 단순한 이해입니다. 이 "객체"에는 "다른 객체"를 처리하는 일련의 메서드도 포함되어 있습니다. 이러한 메서드는 프로그램 설계에서 자주 사용됩니다. 따라서 컨테이너에는 "컨테이너 클래스는 특정 코드 재사용 문제에 대한 좋은 솔루션"이라는 이점도 반영됩니다. 컨테이너의 또 다른 특징은 스스로 확장할 수 있다는 점입니다. 문제를 해결할 때 우리는 얼마나 많은 객체를 저장해야 하는지 알지 못하는 경우가 많습니다. 이는 객체를 저장하기 위해 얼마나 많은 메모리 공간을 만들어야 하는지 알지 못한다는 의미입니다. 분명히 배열은 이와 관련하여 능력이 없습니다. 이것이 컨테이너의 장점입니다. 저장하려는 개체 수를 미리 알려줄 필요가 없습니다. 컨테이너 개체를 만들고 그것이 제공하는 메서드를 올바르게 호출하면 모든 처리 세부 사항이 완료됩니다. 컨테이너 그 자체. 메모리를 신청하거나 메모리를 해제할 수 있으며 최적의 알고리즘을 사용하여 명령을 실행할 수 있습니다. 컨테이너 클래스는 객체지향 언어의 탄생과 함께 제안되었으며, 객체지향 언어에서 특히 중요하며 초기 객체지향 언어의 기초로 간주되기도 합니다. 거의 모든 객체 지향 언어에는 컨테이너 세트도 함께 제공됩니다. C에서는 표준 템플릿 라이브러리(STL)입니다. 다른 언어와 달리 C는 컨테이너 처리에 템플릿 기반 접근 방식을 사용합니다. 표준 C 라이브러리의 컨테이너는 표준 알고리즘과 잘 작동할 수 있는 다양한 데이터 구조를 제공하여 소프트웨어 개발을 효과적으로 지원합니다! 일반 컨테이너 분류 STL은 정의된 일반 컨테이너를 순차 컨테이너, 연관 컨테이너 및 컨테이너 어댑터의 세 가지 범주로 나눕니다. 순차 컨테이너는 요소 간의 순차적 관계를 갖는 선형 목록이며, 선형 구조를 갖는 정렬된 클러스터입니다. 순차 컨테이너의 각 요소는 삭제나 삽입으로 인해 위치가 변경되지 않는 한 고정된 위치를 갖습니다. 이 위치는 요소 자체와는 관련이 없고, 작업이 수행되는 시간과 장소와 관련이 있습니다. 순차 컨테이너는 요소의 특성에 따라 정렬하지 않고 요소 작업의 논리적 순서를 직접 저장합니다. 예를 들어, 순차 컨테이너에 세 개의 요소를 한 번에 추가하는 경우 컨테이너에 있는 세 요소의 상대 위치는 추가 시 논리적 순서와 일치합니다. 연관 컨테이너는 순차 컨테이너와 다릅니다. 연관 컨테이너는 비선형 트리 구조, 보다 정확하게는 이진 트리 구조입니다. 요소 사이에는 엄격한 물리적 순서 관계가 없습니다. 즉, 컨테이너에 있는 요소가 컨테이너에 배치될 때 요소의 논리적 순서가 유지되지 않습니다. 그러나 연관 컨테이너는 요소의 특성에 따라 정렬하는 또 다른 기능을 제공하므로 반복자는 요소의 특성에 따라 "순차적으로" 요소를 얻을 수 있습니다. 연관 컨테이너의 또 다른 주목할만한 특징은 데이터를 키 값의 형태로 저장한다는 점인데, 이는 저장을 위해 키워드와 값을 연관시킬 수 있다는 것을 의미하는 반면, 순차 컨테이너는 한 가지 유형만 저장할 수 있다는 것을 의미한다(단지 키 값이라고 생각하면 된다). 키워드를 저장하므로 값만 보유한다고 간주할 수도 있습니다. 이는 아래의 특정 컨테이너 클래스에서 설명할 수 있습니다. 컨테이너 어댑터는 상대적으로 추상적인 개념입니다. C의 설명은 다음과 같습니다. 어댑터는 한 항목의 동작을 다른 항목의 동작과 유사하게 만드는 메커니즘입니다. 컨테이너 어댑터는 기존 컨테이너 유형이 다른 추상 유형에서 작동할 수 있도록 하는 메커니즘입니다. 실제로는 인터페이스 변환만 발생했습니다. 그러면 컨테이너의 컨테이너로 이해하면 됩니다. 실제로는 컨테이너이지만 특정 표준 컨테이너 유형에 의존하지 않는 컨테이너의 템플릿으로 이해하면 됩니다. 또는 이를 컨테이너의 인터페이스로 생각하고 어댑터가 이를 구현하는 데 사용하는 컨테이너 유형은 어댑터를 정의할 때 사용자가 결정할 수 있습니다.

다음 표에는 STL에서 정의한 세 가지 유형의 컨테이너에 포함된 특정 컨테이너 클래스가 나열되어 있습니다. 표준 컨테이너 클래스 기능: 순차 컨테이너 벡터: 뒤에서 빠른 삽입 및 삭제, 모든 요소에 대한 직접 액세스 deque: 앞에서 빠른 삽입 및 삭제 또는 뒤로, 직접 액세스 모든 요소 목록 이중 연결 목록, 어디서나 빠른 삽입 및 삭제, 연관된 컨테이너 세트의 빠른 검색, 중복 값 없음 다중 세트 빠른 검색, 중복 값 맵 일대다 매핑 허용, 키워드 기반 빠른 검색, 중복 값 없음 멀티맵 일대다 매핑, 키워드 기반 빠른 검색, 중복 값 허용 컨테이너 어댑터 스택 후입선출 큐 선입선출 Priority_queue 가장 높은 우선순위 요소는 항상 큐에서 가장 먼저 나오는 벡터, deque 및 순차 컨테이너 나열: 벡터 벡터: 선형 시퀀스 구조입니다. 배열과 동일하지만 크기가 미리 지정되지 않고 자동으로 확장됩니다. 배열처럼 작동할 수 있으며 그 특성상 벡터를 동적 배열로 취급할 수 있습니다. 벡터를 생성한 후 데이터 저장을 위해 메모리에 연속적인 메모리 공간을 자동으로 할당합니다. 초기 공간 크기는 미리 지정하거나 기본적으로 벡터로 지정할 수 있습니다. 저장된 데이터가 할당된 공간을 초과하면 벡터는 메모리 블록을 재할당하지만 이러한 할당에는 시간이 많이 걸립니다. 공간을 재할당할 때 벡터는 먼저 더 큰 메모리 블록을 적용합니다. 원본 데이터를 새 메모리 블록에 복사합니다. 둘째, 원본 메모리 블록의 객체를 삭제합니다(객체의 소멸자 호출). 마지막으로 원래 메모리 공간을 해제합니다. 벡터에 저장된 데이터의 양이 많은 경우 이러한 작업은 분명히 성능 저하로 이어질 것입니다. 이것이 벡터가 복사하기 쉬운 값 유형으로 설계된 이유입니다. 따라서 벡터의 성능은 모든 상황에서 좋지 않습니다. 벡터의 성능은 크기를 미리 알고 있을 때만 최적입니다. 벡터의 특징: (1) 배열처럼 연속적인 저장 공간을 지정하지만 공간을 동적으로 확장할 수 있습니다. 즉, 배열처럼 작동할 수도 있고 동적으로 작동할 수도 있습니다. 일반적으로 push_back() pop_back()에 반영됩니다. (2) 랜덤접근이 편리하며 배열처럼 접근한다. 즉, [ ]연산자와 vector.at()을 지원한다. (3) 연속적으로 저장되므로 공간이 절약되고, 데이터가 저장되는 영역이 줄어든다. 그러나 벡터는 대부분의 경우 완전히 저장되지 않으며 실제로 저장되지 않은 영역에서 낭비된다는 점은 분명해야 합니다. (4) 내부 삽입 및 삭제 작업은 매우 비효율적이므로 기본적으로 금지됩니다. Vector는 추가 및 삭제 작업이 백엔드에서만 수행될 수 있도록 설계되었습니다. 그 이유는 Vector의 내부 구현이 순차 목록의 원칙을 기반으로 하기 때문입니다. (5) 푸시 앤 팝은 벡터의 선두가 아닌 벡터의 끝에서만 수행할 수 있습니다. (6) 동적으로 추가된 데이터가 벡터의 기본 할당 크기를 초과하면 메모리를 다시 할당하고 복사하고 해제해야 합니다. 이 작업은 성능을 많이 소모합니다. 따라서 벡터의 최적 성능을 얻으려면 벡터를 생성할 때 공간 크기를 지정하는 것이 가장 좋습니다. 이중 연결 리스트는 선형 연결 리스트 구조이며, 해당 데이터는 여러 개의 노드로 구성됩니다. 각 노드에는 정보 블록(즉, 실제 저장된 데이터), 선행 포인터 및 후행 포인터가 포함됩니다. 지정된 메모리 크기를 할당할 필요가 없으며, 불연속적인 메모리 공간에 저장되고 순서가 지정된 요소가 포인터로 연결되므로 임의로 확장 가능합니다. 리스트 랜덤검색은 그 구조상 벡터처럼 요소의 주소를 직접 찾아내지 않고 처음부터 하나씩 검색해야 하기 때문에 성능이 매우 좋지 않습니다. , 검색 시간이 길어질수록.

검색 시간은 대상 요소의 위치에 비례합니다. 무작위 검색은 충분히 빠르지는 않지만 모든 노드에서 삽입 및 삭제 작업을 빠르게 수행할 수 있습니다. 목록의 각 노드는 연결 목록에 위치를 저장하기 때문에 요소를 삽입하거나 삭제하면 작업 지점 이후의 모든 요소의 저장 주소에 영향을 미치는 벡터와 달리 최대 3개의 요소에만 영향을 미칩니다. 리스트의 특징: (1) 연속적인 메모리 공간을 사용하지 않으므로 동적으로 마음대로 조작할 수 있다. (2) 리스트 내부 어느 위치에나 빠르게 삽입하거나 삭제할 수 있으며, 물론 push 및 pop도 수행할 수 있다. 양쪽 끝에서. (3) 내부 랜덤 액세스가 불가능합니다. 즉, [ ] 연산자와 vector.at()가 지원되지 않습니다. (4) 벡터보다 더 많은 메모리를 차지합니다. 양방향 대기열 deque는 시퀀스의 양쪽 끝에 요소를 추가하고 삭제하는 최적화된 기본 시퀀스 컨테이너입니다. 이는 더 빠른 임의 액세스를 허용하지만 모든 개체를 연속적인 메모리 블록에 저장하는 벡터와 달리 여러 개의 연속적인 저장 블록을 사용하고 이러한 블록과 해당 순서를 매핑 구조로 추적합니다. 데크의 양쪽 끝에서 요소를 추가하거나 제거하면 오버헤드가 거의 없습니다. 공간 재할당이 필요하지 않으므로 끝에 요소를 추가하는 것이 벡터보다 효율적입니다. 실제로 deque는 벡터와 리스트의 장점과 단점을 결합한 것입니다. deque의 특징은 다음과 같습니다. (1) 임의 액세스가 편리합니다. 즉, [ ] 연산자와 vector.at()을 지원하지만 성능은 벡터만큼 좋지 않습니다. (2) 삽입 및 삭제 작업을 내부적으로 수행할 수 있습니다. , 그러나 성능은 목록만큼 좋지 않습니다. (3) 푸시와 팝은 양쪽 끝에서 수행될 수 있습니다. 세 가지의 비교는 벡터, 목록 및 데크의 메모리 구조 특성을 설명합니다. 벡터는 연속적인 메모리 블록입니다. deque는 여러 연속 메모리 블록이고 list는 모두 데이터 요소가 별도로 저장되며 두 요소가 연속되지 않을 수 있습니다. 벡터는 쿼리 성능이 가장 뛰어나며, 효율적인 랜덤 저장에 적합한 메모리 세그먼트를 재할당하지 않는 한 마지막에 데이터를 추가하는 것도 좋습니다. 리스트는 연결된 리스트이며 모든 요소는 불연속적일 수 있지만 이전 요소와 다음 요소를 가리키는 두 개의 포인터가 있습니다. 따라서 요소 삽입 및 삭제에 대한 성능은 가장 좋지만 임의 액세스 요구 사항을 고려하지 않고 많은 수의 삽입 및 삭제 작업에 적합합니다. Deque는 배열과 연결 목록의 장점을 고려한 것입니다. 블록 연결 목록과 다중 배열의 결합입니다. 따라서 리스트보다 쿼리 성능이 좋고, 벡터보다 삽입 및 삭제 성능이 좋습니다. 무작위 액세스가 필요하고 양쪽 끝에서 데이터 삽입 및 삭제에 관심이 있는 경우 deque가 최선의 선택입니다. 연관 컨테이너 집합, 다중 집합, 맵 및 다중 맵은 비선형 트리 구조입니다. 특히 상대적으로 효율적인 특수 균형 검색 이진 트리인 레드-블랙 트리 구조를 사용합니다. (레드-블랙 트리가 무엇인지는 잘 모르겠습니다. 이진 트리 구조라는 것만 알 수 있습니다.) 연관 컨테이너의 이 네 가지 컨테이너 클래스는 모두 동일한 원리를 사용하므로 핵심 알고리즘은 다음과 같습니다. 동일하지만 적용에 있어 몇 가지 차이점이 있습니다. 먼저 차이점을 설명하겠습니다. 세트라고도 알려진 세트는 실제로 요소의 모음이지만, 그 안에 포함된 요소의 값은 고유하며 세트의 각 요소를 세트의 인스턴스라고 합니다. 내부적으로 연결리스트로 구성되어 있어서 삽입할 때는 벡터보다 빠르지만 검색하고 마지막에 추가할 때는 벡터보다 느립니다. Multiset은 다중 집합입니다. 단, 집합의 요소가 고유할 필요가 없다는 점을 제외하면 집합의 동일한 요소가 여러 번 나타날 수 있습니다. 맵은 "키-값" 관계에서 일대일 데이터 저장 기능을 제공합니다.

해당 "키"는 컨테이너에서 반복할 수 없으며 특정 순서로 배열됩니다(실제로 집합을 키-값 관계의 저장소로 간주할 수도 있지만 키만 있고 값은 없습니다. 특별한 형식입니다.) 지도) . 연결리스트에 저장되기 때문에 연결리스트의 장점과 단점도 상속받습니다. Multimap은 기본적으로 map과 유사합니다. 이는 컨테이너에서 "키"가 고유하지 않도록 허용합니다. 연관 컨테이너의 특징은 순차 컨테이너와 비교할 때 다음과 같은 주요 특징을 가지고 있습니다. 1. 내부 구현은 특히 레드-블랙 트리의 구조 원리를 기반으로 하는 비선형 이진 트리 구조를 사용합니다. map은 요소의 고유성을 보장하며, mulset 및 mulmap은 이 속성을 확장하여 요소가 고유하지 않도록 허용합니다. 3. 요소는 순서가 지정된 집합이며 삽입 시 기본적으로 오름차순으로 정렬됩니다. 위의 특성을 바탕으로 1. 벡터는 순차 저장소이므로 연관 컨테이너의 요소 삽입 및 삭제 작업은 벡터보다 빠르고, 연관 컨테이너는 모두 체인 구조이므로 목록보다 느립니다. 목록은 선형인 반면 연관 컨테이너는 이진 트리 구조입니다. 하나의 요소를 변경하면 목록보다 다른 요소가 더 많이 변경되며 각 삽입 및 삭제 시 요소를 다시 정렬해야 합니다. 요소 검색 작업은 벡터보다 느리지만 목록보다 훨씬 빠릅니다. 벡터는 순차적이고 연속적인 저장소이므로 비교할 수는 없지만 목록을 하나씩 검색하기 때문에 검색 시간은 컨테이너의 크기와 검색의 복잡성에 비례하기 때문에 체인 목록보다 훨씬 빠릅니다. 연관 컨테이너의 경우 기본적으로 동일하며, 예를 들어 레코드가 1,000개이면 최대 검색 시간은 1,000,000개이면 최대 검색 시간은 20회입니다. 3. 사용중인 벡터, 데크, 리스트와 다른 가장 큰 특징은 세트가 내부적으로 정렬된다는 점입니다. 쿼리의 경우 목록보다 훨씬 낫습니다. 4. 맵의 기능은 대체가 불가능하며 "키-값" 관계의 데이터를 저장하며 이 키-값 관계는 배열과 유사한 방식을 채택합니다. 배열은 숫자 아래 첨자를 사용하여 요소 위치를 인덱싱하고, 맵은 문자 키워드를 사용하여 요소 위치를 인덱싱합니다. 사용 측면에서 map은 배열과 유사한 작업도 제공합니다. 즉, set을 포함하여 다른 컨테이너가 수행할 수 없는 아래 첨자를 통해 데이터를 검색할 수 있습니다. (STL의 벡터와 맵만이 배열과 유사한 방식, 즉 ele[1]과 같이 요소를 작동할 수 있습니다.) 컨테이너 어댑터 STL에는 스택, 큐, 우선순위_큐라는 세 가지 어댑터가 포함되어 있습니다. 어댑터는 컨테이너의 인터페이스이므로 요소를 직접 저장할 수 없습니다. 요소를 저장하는 메커니즘은 이를 구현하기 위해 다른 순차 컨테이너를 호출하는 것입니다. 즉, 어댑터는 "컨테이너를 저장하고 이 컨테이너는 모든 것을 저장합니다." 강요." STL에서 제공되는 세 가지 어댑터는 특정 시퀀스 컨테이너로 구현될 수 있습니다. 기본적으로 stack과 queue는 deque 컨테이너를 기반으로 구현되고, Priority_queue는 Vector 컨테이너를 기반으로 구현됩니다. 물론 어댑터를 생성할 때 특정 구현 컨테이너를 지정할 수도 있습니다. 어댑터를 생성할 때 두 번째 매개변수에 특정 시퀀스 컨테이너를 지정하면 어댑터의 기본 구현이 재정의될 수 있습니다. 어댑터의 특성으로 인해 어떤 시퀀스 컨테이너에서도 어댑터를 구현할 수 없습니다.