컨테이너(추상 데이터 유형)
Container (abstract data type) |
컴퓨터 과학에서 컨테이너는 인스턴스가 다른 객체의 집합인 클래스 또는 데이터[1][2] 구조입니다.즉, 오브젝트는 특정 접근규칙에 따라 정리된 방법으로 저장됩니다.
컨테이너의 크기는 컨테이너에 포함된 개체(요소) 수에 따라 달라집니다.다양한 컨테이너 유형의 기본(상속되는) 구현은 크기, 복잡성 및 언어 유형이 다를 수 있지만 대부분의 경우 주어진 시나리오에 맞는 구현을 선택할 때 유연성을 제공합니다.
컨테이너 데이터 구조는 여러 유형의 프로그래밍 언어에서 일반적으로 사용됩니다.
기능 및 속성
컨테이너는 다음 세 가지 속성을 통해 특성화할 수 있습니다.
- access, 이것이 컨테이너의 객체에 액세스하는 방법입니다.어레이의 경우 어레이 인덱스를 사용하여 액세스합니다.스택의 경우, 액세스는 LIFO(라스트 인, 퍼스트 아웃) 순서에 따라서 행해지고 큐의 경우 FIFO(선입, 퍼스트 아웃) 순서에 따라서 행해집니다.
- 저장, 이것이 컨테이너의 물체를 저장하는 방법입니다.
- traversal, 이것이 컨테이너의 객체를 통과하는 방법입니다.
컨테이너 클래스는 다음 작업을 수행하기 위해 CRUD와 같은 메서드를 구현해야 합니다.
- 빈 컨테이너(용기)를 만듭니다.
- 컨테이너에 물체를 삽입합니다;
- 컨테이너에서 객체를 삭제합니다.
- 컨테이너의 모든 객체를 삭제합니다(맑음).
- 컨테이너에 있는 물체에 접근합니다;
- 컨테이너의 개체 수에 액세스합니다(카운트).
컨테이너는 때때로 반복기와 함께 구현됩니다.
종류들
용기는 단일 값 용기 또는 관련 용기로 분류할 수 있습니다.
단일 값 컨테이너는 각 개체를 독립적으로 저장합니다.오브젝트는 직접, 언어 루프 구조(예를 들어 루프)를 통해 또는 반복기를 사용하여 액세스할 수 있습니다.
연관 컨테이너는 키와 값의 쌍으로 구성된 연관 배열, 맵 또는 사전을 사용하여 각 키가 컨테이너에 한 번만 표시됩니다.컨테이너에 저장되어 있는 경우 키를 사용하여 값을 찾습니다.연관 컨테이너는 프로그래밍 언어에서 클래스 템플릿으로 사용됩니다.
컨테이너 추상 데이터 유형에는 다음이 포함됩니다.
- FIFO 큐
- LIFO 스택
- priority 큐
- 룩업 테이블(LUT)
- 주요 관련 데이터 구조
이러한 추상형 구현에 사용되는 일반적인 데이터 구조는 다음과 같습니다.
- 어레이 및 그 파생 모델
- 링크 리스트
- Binary Search Tree(BST; 바이너리 검색 트리), 특히 셀프밸런싱 BST
- 해시 테이블
그래픽 컨테이너
위젯 도구 키트는 창, 패널과 같은 다른 위젯을 그룹화하기 위한 특수 위젯인 컨테이너도 사용합니다.그래픽 속성 외에도 하위 위젯 목록을 유지하고 하위 위젯 간에 위젯을 추가, 제거 또는 검색할 수 있으므로 컨테이너 클래스와 동일한 유형의 동작이 있습니다.
정적으로 입력된 언어
컨테이너 추상화는 유형 [3]: 273 시스템에 관계없이 거의 모든 프로그래밍 언어로 작성할 수 있습니다.그러나 강한 타입의 객체 지향 프로그래밍 언어에서는 개발자가 재사용 가능한 균질 컨테이너를 작성하는 것이 다소 복잡할 수 있습니다.
요소 유형의 차이로 인해 모든 요소 [3]: 274–276 유형에 대한 컨테이너 컬렉션을 작성하고 유지하는 지루한 프로세스가 발생합니다.
많은 요소 유형(예: 정수 또는 부동수)은 점유하는 메모리 크기와 그 의미 때문에 본질적으로 서로 호환되지 않으므로 서로 다른 컨테이너가 필요합니다(물론 상호 호환성이 있거나 변환 가능한 경우가 [3]: 274–276 아니라면).현대의 프로그래밍 언어는 문제 [3]: 274–281 해결에 도움이 되는 다양한 접근 방식을 제공합니다.
- 범용 기본형
- 다른 모든 사용자가 보편적으로 할당할 수 있는 유형(예: 루트 개체 클래스)입니다.
- 다운캐스팅
- 클래스 대체
- 위의 세 가지 접근법은 약하게 입력된 언어에 사용됩니다.이는 일반적으로 유형별로 공유되는 상속 및 다형성을 의미합니다.
- 유니언 타입(C/C++ 언어)
- 데이터 크기가 다른 유형을 저장할 수 있습니다. 그러나 검색 시 어떤 유형이 유니언에 저장되는지 확인하기 어렵기 때문에 주의 깊게 따라야 합니다.
- 유형 변환
- 템플릿 또는 제네릭
- 재사용성과 타입의 안전성을 보증합니다.역대 상속으로 간주될 수 있습니다.단, 이 접근방식에서는 템플릿의 전문화 구현이 필요할 수 있습니다.이것은 일반적으로 시간이 많이 걸리는 프로세스로,[3]: 281 메서드의 유형이 다르기 때문입니다.
「 」를 참조해 주세요.
레퍼런스
- ^ Paul E. Black(ed.), 알고리즘 및 데이터 구조 사전의 데이터 구조 항목. 미국 국립표준기술연구소 2004년 12월 15일 2011년 10월 4일에 액세스.
- ^ Encyclopédia Britanica(2009) 온라인 엔트리의 엔트리 데이터 구조 2011년 10월 4일 액세스.
- ^ a b c d e Budd, Timothy (1997). An introduction to object-oriented programming (2nd ed.). Reading, Mass.: Addison-Wesley. ISBN 0-201-82419-1. OCLC 34788238.
