도프 벡터
Dope vector컴퓨터 프로그래밍에서, dope 벡터는 데이터 객체,[1] 특히 그것의 메모리 레이아웃에 대한 정보를 저장하는 데 사용되는 데이터 구조다.
목적
도프 벡터는 어레이를 설명하는 데 가장 일반적으로 사용되며, 특정 데이터 유형의 여러 인스턴스를 연속적인 메모리 블록으로 저장한다.예를 들어, 각각 32바이트를 차지하는 100개의 요소를 포함하는 배열은 100 × 32바이트가 필요하다.그 자체로 그러한 메모리 블록은 배열(또는 다른 물체)이 전체적으로 얼마나 큰지, 그 안에 있는 각 원소가 얼마나 큰지, 또는 얼마나 많은 원소가 들어 있는지 추적할 곳이 없다.마약 벡터는 그러한 정보를 저장하는 곳이다.도프 벡터는 배열이나 가변 요소를 포함할 수 있는 구조도 설명할 수 있다.
만일 그러한 배열이 메모리 위치 M에 첫 번째 바이트와 함께 연속적으로 저장된다면, 그것의 마지막 바이트는 위치 M + 3199에 있다.이 배열의 주요 장점은 항목 N을 찾는 것이 쉽다는 것이다: 위치 M + (N × 32)에서 시작된다.물론 값 32를 알아야 한다(이 값을 일반적으로 어레이의 "스트라이드" 또는 어레이 요소의 "폭"이라고 한다).인덱스를 사용하여 배열 데이터 구조를 탐색하는 것을 데드카운팅이라고 한다.
그러나 이 배열은 (도프 벡터를 추가하지 않고) 항목 N의 위치를 갖는 것만으로는 지수 N 자체 또는 보폭을 발견하기에 충분하지 않다는 것을 의미하며, 또는 N - 1 또는 N + 1에 요소가 있는지 여부를 의미한다.예를 들어, 함수나 방법은 배열의 모든 항목에 반복하여 각각의 항목을 다른 함수나 방법에 전달할 수 있다. 이 함수나 방법은 배열이 어디에 있든 얼마나 크든 전혀 알지 못한다.
도프 벡터가 없으면 전체 배열의 주소를 안다고 해서 그것이 얼마나 큰지 알 수 없다.이는 N 요소만 포함하는 배열의 N + 1 요소에 쓰는 것이 일부 다른 데이터를 파괴할 가능성이 높기 때문에 중요하다.많은 프로그래밍 언어가 문자열을 배열의 한 종류로 취급하기 때문에 악명 높은 버퍼 오버플로 문제로 직결된다.
도프 벡터는 어레이(또는 다른 개체)와 함께 소량의 메타데이터를 저장함으로써 이러한 문제를 줄인다.도프 벡터를 사용하면 컴파일러는 배열이나 다른 객체의 끝을 넘어 실수로 쓰지 않도록 하는 코드를 쉽게(그리고 선택적으로) 삽입할 수 있다.또는 프로그래머는 안전이나 다른 목적을 위해 원할 때 도프 벡터에 접근할 수 있다.
설명
도프 벡터에 포함된 정확한 메타데이터 집합은 언어 및/또는 운영 체제에 따라 다르지만 어레이에 대한 도프 벡터는 다음을 포함할 수 있다.
- 배열 요소가 시작되는 메모리의 위치에 대한 포인터(일반적으로 이것은 배열의 zerot 요소(모든 첨자 0 포함)의 위치와 동일하다). (첨자가 0에서 시작되지 않는 경우 이는 첫 번째 실제 요소가 아닐 수 있다.)
- 각 배열 요소의 유형(integer, Boolean, 특정 클래스 등)
- 대열의 서열
- 배열의 범위(지수의 범위)(많은 언어에서 어레이의 시작 인덱스는 0 또는 1로 고정되지만 어레이가 (재할당)될 때 끝 인덱스가 설정됨)
- 주어진 시간에 사용 범위가 변경될 수 있는 배열의 경우, 최대 범위와 현재 범위를 모두 저장할 수 있다.
- 배열의 계단 또는 배열의 각 요소가 차지하는 메모리 양
그러면 프로그램은 도프 벡터를 참조하여 배열(또는 다른 도프 벡터 사용 객체)을 참조할 수 있다.이것은 고차원 언어에서는 일반적으로 자동적이다.배열의 요소에 도달하는 데는 약간의 비용이 더 든다(일반적으로 하나의 명령어, 도프 벡터로부터 포인터를 실제 데이터로 가져오는 명령어).반면에 다른 많은 공통 작업을 수행하는 것이 더 쉽고/또는 더 빠르다.
- 도프 벡터가 없으면 배열의 원소 수를 결정할 수 없다.따라서 어레이의 끝에 "예약된" 값(예: NULL)으로 추가 요소를 추가하는 것이 일반적이다.그런 다음 이 "엔드마커"에 도달할 때까지 요소를 세면서 배열을 통해 전방으로 스캔하여 길이를 결정할 수 있다.물론, 이것은 dope 벡터에서 직접 길이를 확인하는 것보다 훨씬 더 느리게 만든다.
- 배열의 범위를 알지 못하면, 더 이상 필요하지 않을 때 그 메모리를 자유롭게(할당하지 않음)할 수 없다.그러므로, 마약 벡터가 없다면, 어떤 것은 그 길이를 다른 곳에 저장해야 한다.예를 들어 특정 OS에 3200바이트 어레이에 대한 공간을 할당하도록 요청하면 특정 위치 M에 3204바이트를 할당하게 될 수 있다. 그런 다음 처음 4바이트에 크기를 저장하고 할당된 공간이 M+4에서 시작됨을 요청 프로그램에 알린다(따라서 호출자가 추가 4바이트를 어레이의 일부로 취급하지 않음).이 추가 데이터는 도프 벡터로 간주되지 않고, 동일한 목표의 일부를 달성한다.
- 도프 벡터가 없으면 배열 요소의 보폭(또는 너비)에 대한 추가 정보도 보관해야 한다.C에서, 이 정보는 컴파일러에 의해 처리되며, 컴파일러는 "20바이트 폭 요소의 배열로 가는 포인터"와 "1000바이트 폭 요소의 배열로 가는 포인터" 사이의 데이터 형식 구분을 추적해야 한다.이것은 두 종류의 배열에서 어떤 요소에 대한 포인터가 다음 또는 이전 요소에 도달하기 위해 증가하거나 감소할 수 있다는 것을 의미하지만, 또한 배열 폭은 더 이른 단계에서 고정되어야 한다는 것을 의미한다.
도프 벡터(dope vector)를 사용하더라도 배열의 특정 멤버에 대한 포인터를 갖는 것은 배열의 위치나 배열 또는 도프 벡터 자체의 위치를 찾을 수 없다.만약 그것이 원한다면, 그러한 정보는 배열 내의 각 요소에 추가될 수 있다.그러한 요소별 정보는 유용할 수 있지만, 도프 벡터의 일부는 아니다.
도프 벡터는 여러 데이터 유형(배열 및/또는 문자열만이 아님)에 걸쳐 공유되는 일반적인 시설일 수 있다.[2]
참고 항목
참조
- ^ Pratt, T.; Zelkowitz, M. (1996). Programming Languages: Design and Implementation (3rd ed.). Upper Saddle River, NJ: Prentice-Hall. p. 114. ISBN 978-0-13-678012-0.
- ^ Claybrook, Billy G. (October 13–15, 1976). The design of a template structure for a generalized data structure definition facility. ICSE '76: 2nd international conference on Software engineering. San Francisco, California, USA: IEEE Computer Society Press. pp. 408–413.
