표준 템플릿 라이브러리

Standard Template Library
C++ 표준 라이브러리와 혼동하지 마십시오.
그 외의 사용법에 대해서는, 「STL」을 참조해 주세요.
C++ 표준 라이브러리
컨테이너
C 표준 라이브러리

STL(Standard Template Library)은 C++ 표준 라이브러리의 많은 부분에 영향을 준 C++ 프로그래밍 언어용으로 Alexander Stepanov에 의해 설계된 소프트웨어 라이브러리입니다.알고리즘, 컨테이너, 함수 및 [1]반복기라고 하는 4개의 컴포넌트를 제공합니다.

STL은 컨테이너나 관련 배열 등의 C++용 공통 클래스 세트를 제공합니다.이 클래스는 내장형 및 일부 기본 조작(복사 및 할당 등)을 지원하는 사용자 정의 유형과 함께 사용할 수 있습니다.STL 알고리즘은 컨테이너에 의존하지 않기 때문에 라이브러리의 복잡성이 현저하게 감소합니다.

STL은 템플릿을 사용하여 결과를 얻습니다.이 접근방식은 기존 런타임 다형성보다 효율적인 컴파일 타임 다형성을 제공합니다.최신 C++ 컴파일러는 STL의 과도한 사용으로 인한 추상화의 불이익을 최소화하도록 조정되어 있습니다.

STL은 일반 프로그래밍, 효율성 손실 없는 추상성, Von Neumann 연산 [2]모델 및 가치 의미론의 4가지 아이디어를 염두에 두고 C++를 위한 일반 알고리즘과 데이터 구조의 첫 번째 라이브러리로 만들어졌습니다.

STL과 C++ 표준 라이브러리는 2개의 독립된 [3]엔티티입니다.

역사

주요 기사:표준 템플릿 라이브러리 이력

1993년 11월 알렉산더 스테파노프는 C++ 표준화를 위해 ANSI/ISO 위원회에 범용 프로그래밍에 기초한 라이브러리를 제공하였다.위원회의 반응은 압도적으로 호의적이었고 1994년 3월 회의에 맞춰 앤드류 코닉으로부터 정식 제안을 요청하게 되었다.위원회는 여러 차례 변경과 연장에 대한 요청을 받았고, 위원들은 세부 사항을 해결하기 위해 스테파노프와 멍 리를 만났다.Stepanov가 David Musser에게 위임한 작업을 완전히 구현함으로써 가장 중요한 확장(관련 컨테이너)의 요건이 일관됨을 보여야 했습니다.제안은 1994년 7월 ANSI/ISO 위원회 회의에서 최종 승인을 받았다.그 후, 스테파노프 및 Lee 문서 17은 ANSI/ISO C++ 초안 표준(1, 조항 17~27의 일부)에 통합되었다.

1994년 8월 Hewlett-Packard의 인터넷 무료 제공 결정으로 STL의 조기 확산 가능성은 상당히 개선되었다.표준화 프로세스 중에 Stepanov, Lee 및 Musser에 의해 개발된 이 구현은 오늘날 컴파일러 및 라이브러리 벤더가 제공하는 많은 구현의 기반이 되었습니다.

구성.

컨테이너

STL에는 시퀀스 컨테이너와 관련 컨테이너가 포함되어 있습니다.컨테이너는 데이터를 저장하는 개체입니다.표준 시퀀스 컨테이너에는 다음이 포함됩니다.vector,deque,그리고.list. 표준 연관 용기는 다음과 같습니다.set,multiset,map,multimap,hash_set,hash_map,hash_multiset그리고.hash_multimap컨테이너 어댑터도 있습니다. queue,priority_queue,그리고.stack특정 인터페이스를 가진 컨테이너로, 다른 컨테이너를 구현으로 사용합니다.

컨테이너. 묘사
간이 컨테이너
짝 페어 컨테이너는 데이터 요소 또는 객체의 2태플로 구성된 단순한 연관 컨테이너로, 'first'와 'second'라고 합니다.STL '쌍'을 할당, 복사 및 비교할 수 있습니다.맵 또는 hash_map에 할당된 객체의 배열(아래 설명)은 기본적으로 '쌍' 유형입니다.여기서 모든 '첫 번째' 요소는 고유한 키로 기능하며 각각 '두 번째' 값 객체와 관련지어집니다.
시퀀스(어레이/링크 리스트): 순서부 컬렉션
벡터 오브젝트를 삽입 또는 삭제할 때 자동으로 크기를 조정할 수 있는 C 어레이(랜덤 액세스 가능)와 같은 동적 어레이.벡터의 끝에 요소를 삽입하려면 상각된 상수 시간이 걸립니다.크기 조정이 이루어지지 않기 때문에 마지막 요소를 제거하는 데 걸리는 시간은 일정합니다.처음 또는 중간에 삽입 및 지우기는 시간이 선형적입니다.

bool 타입의 전문화가 존재하며, bool 값을 비트로 저장하여 공간을 최적화합니다.

목록. 이중 링크 리스트. 요소는 연속 메모리에 저장되지 않습니다.벡터와 반대되는 성능입니다.검색 및 액세스 속도가 느리지만(선형 시간), 위치가 발견되면 빠른 삽입 및 삭제(정수 시간)
슬리스트
 단일 링크 리스트. 요소는 연속 메모리에 저장되지 않습니다.벡터와 반대되는 성능입니다.검색 및 액세스 속도가 느리지만(선형 시간), 위치가 발견되면 빠른 삽입 및 삭제(정수 시간)삽입과 삭제가 약간 더 효율적이며 이중으로 연결된 목록보다 메모리 사용량이 적지만 앞으로만 반복할 수 있습니다.C++ 표준 라이브러리에서 다음과 같이 구현됩니다.forward_list.
디큐(양단 큐) 디큐를 변경한 후 반복기 유효성에 대한 보장이 부족하지만 상각된 상수 시간의 시작 또는 끝에 삽입/삽입이 있는 벡터.
컨테이너 어댑터
큐잉 다음 관점에서 FIFOqueue 인터페이스를 제공합니다.push/pop/front/back운용을 실시합니다.

작업을 지원하는 모든 시퀀스front(),back(),push_back(),그리고.pop_front()큐 인스턴스화에 사용할 수 있습니다(예:list그리고.deque).

priority 큐 priority 큐인터페이스를 제공합니다.push/pop/top조작(priority가 가장 높은 요소가 위에 있음)

동작을 지원하는 임의의 랜덤액세스 시퀀스front(),push_back(),그리고.pop_back()를 사용하여 priority_module을 인스턴스화할 수 있습니다(예:vector그리고.deque). 힙을 사용하여 구현됩니다.

요소는 비교를 추가로 지원해야 합니다(어떤 요소가 더 높은 우선순위를 가지며 먼저 팝해야 하는지 판단하기 위해).

스택 다음과 같은 측면에서 LIFOstack 인터페이스를 제공합니다.push/pop/topoperations(마지막으로 표시된 요소가 맨 위에 있음)

작업을 지원하는 모든 시퀀스back(),push_back(),그리고.pop_back()스택 인스턴스화에 사용할 수 있습니다(예:vector,list,그리고.deque).

연관 컨테이너: 정렬되지 않은 컬렉션
세트 수학적 집합. 집합에 요소를 삽입/삽입해도 집합 내를 가리키는 반복기는 무효화되지 않습니다.집합 연산 결합, 교차점, 차이, 대칭 차이 및 포함 검정을 제공합니다.데이터 유형은 비교 연산자를 구현해야 합니다.<또는 사용자 정의 비교기 함수를 지정해야 합니다. 이러한 비교 연산자 또는 비교기 함수는 엄격한 약한 순서를 보장해야 합니다. 그렇지 않으면 동작이 정의되지 않습니다.일반적으로 자가 밸런싱 바이너리 검색 트리를 사용하여 구현됩니다.
멀티셋 세트와 동일하지만 중복 요소(연속 멀티셋)를 허용합니다.
지도 연관 배열: 한 데이터 항목(키)에서 다른 데이터 항목(값)으로 매핑할 수 있습니다.키 유형은 비교 연산자를 구현해야 합니다.<또는 사용자 정의 비교기 함수를 지정해야 합니다. 이러한 비교 연산자 또는 비교기 함수는 엄격한 약한 순서를 보장해야 합니다. 그렇지 않으면 동작이 정의되지 않습니다.일반적으로 자가 밸런싱 바이너리 검색 트리를 사용하여 구현됩니다.
멀티맵 맵과 동일하지만 중복된 키를 허용합니다.
hash_set
해시_멀티셋
hash_map
hash_map		 각각 set, multiset, map 또는 multimap과 비슷하지만 해시 테이블을 사용하여 구현됩니다.키는 순서가 매겨지지 않지만 키 유형에 대해 해시 함수가 존재해야 합니다.이러한 유형은 C++ 표준에서 제외되었습니다. 유사한 컨테이너는 C++11에서 표준화되었지만 이름은 다릅니다.unordered_set그리고.unordered_map).
기타 유형의 컨테이너
비트셋 는 부울의 고정 크기 벡터와 유사한 일련의 비트를 저장합니다.비트 단위 연산을 구현하고 반복기가 없습니다.시퀀스가 아닙니다.랜덤 액세스를 제공합니다.
밸런스 어레이 수치 사용(특히 벡터와 행렬을 나타내기 위한)을 목적으로 하는 또 다른 어레이 데이터 유형. C++ 표준을 사용하면 이 목적을 위한 특정 최적화가 가능합니다.조수티스에 따르면Valarray는 "표준이 완성되기 훨씬 전에 [C++ 표준] 위원회를 떠난" 사람들에 의해 잘못 설계되었으며 표현식 템플릿 라이브러리가 [4]선호됩니다.이 맥락에서 표준의 Valarray 부분에 대한 제안된 개서는 거부되었고, 대신 표현식 [5]템플릿을 사용하여 이를 구현하는 허가가 되었습니다.

반복기

STL은 5가지 유형의 반복기를 구현합니다.이것들은 입력 iterators(오직 값 시퀀스를 읽는 데만 사용될 수 있), 출력 iterators, 전방 iterators(,에 작곡된, 그리고 앞으로 나아가게 읽을 수 있), 양방향 iterators과 .mw-parser-output .vanchor>(는 전방 iterators처럼 보이지만, 또한 뒤로 움직입니다),(오직 값 시퀀스를 쓰는 데 사용될 수 있):target~.Vanchor-text{background-color:#b1d2ff}random-access iterators게 움직일 수 있다.한 번의 조작으로 임의의 수의 스텝을 자유롭게 수행할 수 있습니다).

STL의 기본 개념은 계산의 시작과 끝을 지정하는 한 쌍의 반복기이며, 데이터 구조에서 작동하는 라이브러리의 알고리즘 템플릿 대부분은 [6]범위를 사용하는 인터페이스를 가지고 있습니다.

양방향 반복기를 랜덤 액세스 반복기처럼 작동시킬 수 있으므로 한 번에 한 단계씩 총 10회씩만 진행하면 10단계씩 진행할 수 있습니다.그러나 별도의 랜덤 액세스 반복기를 사용하면 효율의 이점을 얻을 수 있습니다.예를 들어, 벡터는 랜덤 액세스 반복기를 가지지만 쌍방향 반복기만을 나열합니다.

반복기는 STL의 범용성을 가능하게 하는 주요 기능입니다.예를 들어 시퀀스를 반전시키는 알고리즘은 쌍방향 반복기를 사용하여 구현할 수 있으며, 리스트, 벡터 및 디큐에서도 동일한 구현을 사용할 수 있습니다.사용자가 작성한 컨테이너는 5개의 표준 반복기 인터페이스 중 하나를 구현하는 반복기만 제공하면 되며 STL에서 제공되는 모든 알고리즘을 컨테이너에서 사용할 수 있습니다.

이 일반성은 때때로 대가를 치르기도 한다.예를 들어 맵이나 세트 등의 관련 컨테이너에서 검색을 실행하는 것은 컨테이너 자체에 의해 제공되는 멤버 함수를 호출하는 것보다 반복기를 사용하는 것이 훨씬 느릴 수 있습니다.이는 연관 컨테이너의 메서드가 반복기를 사용하는 알고리즘에 불투명한 내부 구조에 대한 지식을 활용할 수 있기 때문입니다.

알고리즘

검색 및 정렬 등의 액티비티를 실행하기 위한 다수의 알고리즘이 STL에 제공되며, 각 알고리즘은 일정 수준의 반복기를 요구하도록 구현됩니다(따라서 반복기에 의해 인터페이스를 제공하는 모든 컨테이너에서 작동합니다.다음과 같은 알고리즘 검색binary_search그리고.lower_bound이진 검색 및 유사한 정렬 알고리즘을 사용하려면 데이터 유형이 비교 연산자를 구현해야 합니다.<또는 사용자 정의 비교기 함수를 지정해야 합니다. 이러한 비교 연산자 또는 비교기 함수는 엄격한 약한 순서를 보장해야 합니다.이와는 별도로 요소 범위로부터 힙을 만들고, 요소 범위의 사전순으로 정렬된 순열을 생성하며, 정렬된 범위를 병합하고, 정렬된 범위의 결합, 교차, 차이를 실행하기 위한 알고리즘이 제공된다.

기능들

STL에는 함수 호출 연산자를 오버로드하는 클래스가 포함되어 있습니다(operator()). 이러한 클래스의 인스턴스를 펑터 또는 함수 개체라고 합니다.함수는 관련된 함수의 동작을 파라미터화(예를 들어 함수의 생성자에게 전달되는 인수를 통해)할 수 있도록 하며 함수와 관련된 펑터별 상태 정보를 유지하는 데 사용할 수 있습니다.펑터와 함수 포인터는 모두 함수 호출 구문을 사용하여 호출할 수 있으므로 대응하는 파라미터가 함수 호출 컨텍스트에만 표시되는 경우 템플릿에 대한 인수로 교환할 수 있습니다.

특히 일반적인 펑터의 유형은 술어입니다.예를 들어 다음과 같은 알고리즘이 있습니다.find_if수열의 원소에 작용하는 단항 술어를 취한다.sort, partial_sort, nth_element 및 정렬된 모든 컨테이너와 같은 알고리즘은 엄밀하게 약한 순서를 제공해야 하는 이진 술어를 사용합니다. 즉, 전이적, 비반사적 및 비대칭적 이진 관계에 대한 구성원 자격 테스트처럼 동작해야 합니다.아무것도 지정되지 않은 경우 이러한 알고리즘과 컨테이너는 기본적으로 적게 사용됩니다.이것에 의해, less-than-operator< 가 호출됩니다.

비판

C++ 컴파일러 구현 품질

C++ 컴파일러의 Quality of Implementation(QoI; 구현 품질)은 STL(및 일반적으로 템플릿화된 코드)의 사용성에 큰 영향을 미칩니다.

  • 템플릿과 관련된 오류 메시지는 매우 길고 해독하기 어려운 경향이 있습니다.이 문제는 매우 심각한 것으로 간주되어 STL 관련 오류 메시지를 보다 이해하기 쉽게 단순화하고 인쇄하는 다수의 툴이 작성되었습니다.
  • 템플릿을 부주의하게 사용하면 코드가 [7]커질 수 있습니다.이는 STL 구현 내에서 특별한 기술(예를 들어 내부 void* 컨테이너 및 기타 "다이어트 템플릿" 기술 사용)과 컴파일러 최적화 기술 개선으로 상쇄되었습니다.단, 이 증상은 다른 유형의 기능을 사용하기 위해 순진하게 수동으로 복사하는 것과 유사하며, 두 기능 모두 주의와 좋은 기술로 방지할 수 있습니다.
  • 템플릿 인스턴스화는 일반적으로 (가상 기능을 통해) 실행 시 의사결정을 줄이는 대신 컴파일 시간과 메모리 사용량을 늘릴 수 있습니다.컴파일러 테크놀로지가 충분히 개선될 때까지 이 문제는 신중하게 코딩하고 특정 관용구를 사용하지 않으며 단순히 템플릿이 적절하지 않거나 컴파일 시 퍼포먼스가 우선되는 경우만 부분적으로 해소할 수 있습니다.

기타 문제

  • 소스 코드 내에 상수가 있는 STL 컨테이너의 초기화는 C에서 상속된 데이터 구조(Initializer 목록을 사용하여 C++11로 주소 지정)만큼 쉽지 않습니다.
  • STL 컨테이너는 베이스 클래스로 사용하는 것을 의도하지 않았습니다(디스트럭터는 의도적으로 가상이 아닙니다).컨테이너에서 파생되는 것은 일반적인 [8][9]실수입니다.
  • STL에 의해 실장된 반복기의 개념은 처음에는 이해하기 어려울 수 있습니다.예를 들어 반복기에서 지적된 값이 삭제되면 반복기 자체는 더 이상 유효하지 않습니다.이것은 일반적인 에러의 원인입니다.STL의 대부분의 구현에서는 속도가 느린 디버깅모드가 제공되고 있습니다만, 사용하는 경우는 이러한 에러를 검출할 수 있습니다.Java 등 다른 언어에서도 유사한 문제가 발생합니다.범위는 반복기에 [10]대한 보다 안전하고 유연한 대안으로 제안되었다.
  • 특정 반복 패턴은 STL 반복기 [citation needed]모델에 매핑되지 않습니다.예를 들어 플랫폼에 의존하거나 사용할 수 없는 Coroutine을 사용하지 않으면 [11]콜백 열거 API를 STL 모델에 적합하게 할 수 없습니다.또한 C++20까지 C++ 표준외가 됩니다.
  • 컴파일러 컴플라이언스는 컨테이너의 메모리 관리에 사용되는 Allocator 개체가 상태에 따라 동작하는 것을 보증하지 않습니다.예를 들어 휴대용 라이브러리는 해당 유형의 다른 할당자 개체를 사용하여 서로 다른 풀에서 메모리를 꺼내는 할당자 유형을 정의할 수 없습니다.(Meyers, 페이지 50) (C++11로 주소 지정)
  • 알고리즘 세트가 완전하지 않습니다.예를 들어,copy_ifC++[13]11에서 추가되었지만 알고리즘은 [12]생략되었습니다.

실장

「 」를 참조해 주세요.

메모들

  1. ^ Holzner, Steven (2001). C++ : Black Book. Scottsdale, Ariz.: Coriolis Group. p. 648. ISBN 1-57610-777-9. The STL is made up of containers, iterators, function objects, and algorithms
  2. ^ Musser, David (2001). STL tutorial and reference guide: C++ programming with the standard template library. Addison Wesley. ISBN 0-201-37923-6.
  3. ^ Lightness Races in Orbit, Commnuity (5 March 2011). "What's the difference between "STL" and "C++ Standard Library"?". Stack Overflow. Retrieved 21 October 2021.
  4. ^ Josuttis, Nicolai M. (1999). The C++ Standard Library: A Tutorial and Handbook. Addison-Wesley Professional. p. 547.
  5. ^ Vandevoorde, David; Josuttis, Nicolai M. (2002). C++ Templates: The Complete Guide. Addison Wesley. ISBN 0-201-73484-2.
  6. ^ Stepanov, Alexander; Lee, Meng (31 October 1995). "The Standard Template Library" (PDF). Retrieved 16 December 2018. Most of the library’s algorithmic templates that operate on data structures have interfaces that use ranges. A range is a pair of iterators that designate the beginning and end of the computation. [...] in general, a range [i, j) refers to the elements in the data structure starting with the one pointed to by i and up to but not including the one pointed to by j. Range [i, j) is valid if and only if j is reachable from i.
  7. ^ Adrian Stone. "Minimizing Code Bloat: Template Overspecialization".
  8. ^ Meyers, Scott (2005). Effective C++ Third Edition – 55 Specific Ways to Improve Your Designs. Addison Wesley. ISBN 0-321-33487-6.
  9. ^ Sutter, Herb; Alexandrescu, Andrei (2004). C++ Coding Standards: 101 Rules, Guidelines, and Best Practices. Addison-Wesley. ISBN 0-321-11358-6.
  10. ^ Andrei Alexandrescu (6 May 2009). "Iterators Must Go" (PDF). BoostCon 2009. Retrieved 19 March 2011.
  11. ^ Matthew Wilson (February 2004). "Callback Enumeration APIs & the Input Iterator Concept". Dr. Dobb's Journal.
  12. ^ Bjarne Stroustrup (2000). The C++ Programming Language (3rd ed.). Addison-Wesley. ISBN 0-201-70073-5.: 페이지 530
  13. ^ 기타 STL 알고리즘 (리비전 2)
  14. ^ Apache C++ 표준 라이브러리.Stdcxx.apache.org 를 참조해 주세요.2013-07-29에 취득.

레퍼런스

외부 링크