stl 벡터가 랜덤 액세스를 제공하는 방법

Question

어제 저녁 내 작업에 std :: vector를 사용하고 있었고이 문제가 내 마음에 솟아났다.

코드를 살펴 보았지만 실패했습니다. 누군가 포인터를 줄 수 있습니까?

int *x, *y; 

하지만 심각하는 vector는 내부적으로 만 배열로 구현됩니다

감사합니다, 아룬

Answer 1

물론, 여기에 몇 가지 포인터입니다. 오버로드 된 인덱싱 연산자 ([])를 사용하여 배열처럼 액세스 할 수 있습니다.

Answer 2

Vector는 연속적인 메모리를 사용하므로 기본적으로 배열과 동일한 방법으로 랜덤 액세스를 제공합니다. 요소의 시작 주소와 크기를 알고 포인터 계산을 수행합니다.

Answer 3

벡터는 일반적으로 데이터가 연속적인 메모리 블록에 저장되므로 포인터 연산이 O (1)에 대한 (이미 존재하는) O에 액세스 할 수 있도록 항상 동적 배열 구현 [*] 요소.

효율적인 동적 배열의 트릭 (아직 알지 못한다고 가정)은 예약 된 상점의 크기를 항상 일정한 요소만큼 늘리는 것입니다 (Jerry Coffin 주석 참조). 그 결과, 무한 개수의 새로운 요소를 추가 할 때 요소를 단순화하기 위해 2로 취하면 첫 번째 요소가 n 번째 add에 복사되고 (2 * n) add와 (4 * n) 번째 add에 복사됩니다. 그리고 ...

이 시리즈는 수렴하므로 N 개의 새로운 요소를 추가하는 데 O (N) 시간이 걸릴 수 있습니다. 그러나 임의의 추가 작업에는 기존 요소의 재 할당 및 사본이 필요할 수 있으므로 대기 시간 보장이 없습니다.

[*] 필요한 성능을 얻을 수있는 다른 메커니즘을 알지 못합니다. 누군가?

Answer 4

이

의 적어도 요인은 사실, 많은 구현이 중요한 것은 당신이 기하 급수적 벡터의 성장을 얻을 수 있도록이 요소라는 것이다 1.5 의 요소를 사용합니다.