map< int , vector<int> > g1;
vector< vector<int> > g2;
이 둘 사이의 유사성과 비 유사성은 무엇인가
을 선언 한 가정 해 봅시다?map< int , vector<int> > g1;
vector< vector<int> > g2;
이 둘 사이의 유사성과 비 유사성은 무엇인가
을 선언 한 가정 해 봅시다?이들은 근본적으로 다릅니다. 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입니다.
RB 트리는 표준에 의해 지정되지 않습니다. 대부분의 경우에도 구현 종속적입니다. – Caduchon
사실,하지만 rb-tree를 사용하지 않는 구현을 알고 있습니까? IIRC 표준은 일반적으로 특정 작업에 대해 특정 점근선 런타임 만 요구하지만 실제로 메모리 할당 전략은 대부분의 경우 점근선 런타임 차이보다 훨씬 큰 영향을 미칩니다. – midor
아니요,하지만 이상한 컴파일러가 너무 많기 때문에 다른 알고리즘 (예 : Casio 또는 Texas Instrument와 같이 이미 16 비트의 바이트를 사용하고있는 알고리즘)을 구현하는 경우 놀라지 않을 것입니다. – Caduchon
유사성은 데이터를 액세스하는 방법은, 그것은 동일한 구문 될 수 있습니다
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++의 컨테이너에 대한 튜토리얼을 배우고 모든 차이점을 이해하고이를 사용하는 일반적인 방법을 이해하도록 권유합니다.
예를 들어 차이점을 이해할 수 있습니다. vector<int>
은 고유 한 ID를 저장하고 map
은 해당 PIN 코드를 키로 저장합니다.
map< int , vector<int> > listOfPeopleAtRespectivePinCode;
vector< vector<int> > bunchOfGroupsOfPeople;
분명히,
map
는
vector
효율적 무리의 데이터를 저장할 수 있지만, 키와 값 (값 여기서 list)을 연관시킬 수있다.
지도는 벡터가 아닌 연관 컨테이너입니다. –