2017-10-10 14 views

답변

0

이들은 근본적으로 다릅니다. g2[0]g1[0]을 모두 수행 할 수는 있지만 문제는 매우 다릅니다. 인덱스 0에 아무것도 없다고 가정하면 std::map은 기본값으로 새 value_type을 생성합니다 (이 경우 벡터). 참조는 반환되지만 반면에 std::vector에는 정의되지 않은 동작이 있지만 일반적으로 segfaults 또는 garbage를 반환합니다.

또한 메모리 레이아웃면에서 완전히 다릅니다. std::map은 빨간색 - 검은 색 트리로 뒷받침되지만 std::vector은 메모리에서 연속적입니다. 따라서지도에 삽입하면 메모리의 어딘가에 동적 할당이 이루어 지지만 현재 용량이 초과 될 경우 벡터의 크기가 조정됩니다. 그러나 벡터의 벡터는 메모리에서 인접하지 않습니다.

struct vector 
{ 
    T* data; 
    size_t capacity; 
    size_t size; 
}; 

벡터의 각 data에서 동적 메모리 할당을 소유 : 자체가 메모리의 연속 인 제 1 벡터가 데이터의 측면에서 대략 다음과 같이 벡터로 구성된다.

지도의 이점은 인구 밀도가 높아야 할 필요가 없다는 것입니다. 즉, 중간에 모든 항목을 포함하지 않고 색인 0과 12902에 항목을 추가 할 수 있으며, 정렬도 가능합니다. 정렬 된 속성이 필요하지 않고 C++ 11을 사용할 수있는 경우 std::unordered_map을 고려하십시오. 벡터는 항상 밀집되어 있습니다. 즉, 크기가 10000이고 요소가 0-9999입니다.

+0

RB 트리는 표준에 의해 지정되지 않습니다. 대부분의 경우에도 구현 종속적입니다. – Caduchon

+0

사실,하지만 rb-tree를 사용하지 않는 구현을 알고 있습니까? IIRC 표준은 일반적으로 특정 작업에 대해 특정 점근선 런타임 만 요구하지만 실제로 메모리 할당 전략은 대부분의 경우 점근선 런타임 차이보다 훨씬 큰 영향을 미칩니다. – midor

+0

아니요,하지만 이상한 컴파일러가 너무 많기 때문에 다른 알고리즘 (예 : Casio 또는 Texas Instrument와 같이 이미 16 비트의 바이트를 사용하고있는 알고리즘)을 구현하는 경우 놀라지 않을 것입니다. – Caduchon

1

유사성은 데이터를 액세스하는 방법은, 그것은 동일한 구문 될 수 있습니다

std::cout << g1[3][2] << std::endl; 
std::cout << g2[3][2] << std::endl; 

주요 차이점은 다음과 같다 : 벡터의지도가 모든 인덱스를 포함 할 필요가 없습니다. 그런 다음 예를 들어,지도 만 3 벡터는 키 '17', '1234'와 13579로 액세스 가질 수 있습니다 : 당신이 벡터의 벡터와 동일한 구문을 원하는 경우

g2[17].resize(10); 
g2[1234].resize(5); 
g2[13579].resize(100); 

을 수행해야 주 벡터에 적어도 13579 개의 벡터 (13576 개의 빈 벡터 포함)가 있어야합니다. 그러나 이것은 메모리에서 사용되지 않는 공간을 많이 사용합니다.

또한,지도에, 당신은 또한 (벡터의 벡터에서 가능하지 않은) 부정적인 키를 사용하여 벡터에 액세스 할 수 있습니다 :이 분명히 높은 차이 후

g2[-10].resize(10); 

, 데이터의 저장은 다르다 . 벡터는 인접한 메모리를 할당하고지도는 트리로 저장됩니다. 벡터에서의 액세스 복잡도는 O(1)이며,지도에서는 ​​O(log(n))입니다. C++의 컨테이너에 대한 튜토리얼을 배우고 모든 차이점을 이해하고이를 사용하는 일반적인 방법을 이해하도록 권유합니다.

0

예를 들어 차이점을 이해할 수 있습니다. vector<int>은 고유 한 ID를 저장하고 map은 해당 PIN 코드를 키로 저장합니다.

map< int , vector<int> > listOfPeopleAtRespectivePinCode; 
vector< vector<int> > bunchOfGroupsOfPeople; 

분명히, mapvector 효율적 무리의 데이터를 저장할 수 있지만, 키와 값 (값 여기서 list)을 연관시킬 수있다.