2D 벡터와 벡터지도의 차이점은 무엇입니까?

Question

의 내가

map< int , vector<int> > g1; 
vector< vector<int> > g2; 

이 둘 사이의 유사성과 비 유사성은 무엇인가

을 선언 한 가정 해 봅시다?

Answer 1

이들은 근본적으로 다릅니다. 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입니다.

Answer 2

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

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++의 컨테이너에 대한 튜토리얼을 배우고 모든 차이점을 이해하고이를 사용하는 일반적인 방법을 이해하도록 권유합니다.

Answer 3

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

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

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