C++ 인덱스 - 인덱스 맵

Question

ID (정수) 목록이 있습니다. 내 응용 프로그램을 쉽게 처리 할 수 ​​있도록 그들은 (이런 종류의 내 응용 프로그램에서 정말 중요하다)

9382 
297832 
92 
83723 
173934 

예를

를 들어, 정말 효율적인 방법으로 정렬됩니다.

이제 다른 벡터에서 특정 값의 ID에 액세스해야하는 문제에 직면하고 있습니다.

예를 들어 ID 9382의 특정 값은 someVectorB [30]에 있습니다. 나는 그러나

const int UNITS_MAX_SIZE = 400000; 

class clsUnitsUnitIDToArrayIndex : public CBaseStructure 
{ 
private: 
    int m_content[UNITS_MAX_SIZE]; 
    long m_size; 
protected: 
    void ProcessTxtLine(string line); 
public: 
    clsUnitsUnitIDToArrayIndex(); 
    int *Content(); 
    long Size(); 
}; 

을 사용하고있다

지금은 400.000에 UNITS_MAX_SIZE 살리신 것을, 나는 페이지 스택 오류를 얻을, 그리고 내가 뭔가 잘못하고있는 중이 야 하더군요. 나는 전체 접근법이 정말로 좋지 않다고 생각한다.

"위치"가 다른 경우 다른 벡터에서 ID를 찾으려면 어떻게해야합니까?

ps : 파일에서 쉽게 읽을 수 있고 파일로 쉽게 serialize 할 수있는 간단한 것을 찾고 있습니다. 그래서 전에이 무차별 대입 방식을 사용 해왔다.

Answer 1

당신은 INT 년대 INT 년대와 인덱스 번호 비 연속적인 대응 관계를 원하는 경우 std::map을 고려해야합니다. 이 경우 다음과 같이 정의합니다.

std::map<int, int> m_idLocations; 

지도는 두 유형 간의 매핑을 나타냅니다. 첫 번째 유형은 "키"이며 두 번째 유형 인 "값"을 조회하는 데 사용됩니다. 각 ID 조회를 위해 당신은 그것을 삽입 할 수 있습니다

m_idLocations[id] = position; 
// or 
m_idLocations.insert(std::pair<int,int>(id, position)); 

그리고 다음과 같은 구문을 사용하여 조회 할 수 있습니다 : 일반적으로

m_idLocations[id]; 

worse-이 red-black trees를 사용하여 구현하는 STL에서 std::map을 O (log n)의 캐스트 검색 속도. 이것은 거대한 배열에서 얻을 수있는 O (1)보다 약간 느립니다. 그러나 공간을 상당히 효율적으로 사용하기 때문에 실제로 엄청난 양의 숫자를 저장하지 않으면 연습의 차이를 눈치 채기 어렵습니다. 엄청난 양의 조회를 수행합니다.

편집 : 의견의 일부에 대응

나는 그것이 (1) O (로그 n)에 O에서 이동하는 응용 프로그램의 속도에 큰 차이를 만들 수 있다는 것을 지적하는 것이 중요하다고 생각합니다 고정 된 메모리 블록에서 트리 기반 구조로 옮겨가는 것에 대한 실질적인 속도 문제는 말할 것도 없습니다. 그러나 나는 당신이 말하고자하는 것을 int-to-int 매핑으로 표현하고 조숙 한 최적화의 함정을 피하는 것이 중요하다고 생각한다.

개념을 표현한 후에는 프로파일러을 사용하여 속도 문제가있는 곳과 위치를 확인하십시오. 맵이 문제를 일으킨다는 것을 알게되면 맵핑을보다 빠른 것으로 생각하는 것으로 대체해야합니다. 최적화가에 도움이되었는지 테스트했는지 확인하고 대표하는 내용과 변경해야하는 이유에 대한 커다란 설명을 포함하는 것을 잊지 마십시오.

Answer 2

아마 당신은 int m_content [UNITS_MAX_SIZE]로 인해 stackoverflow 오류가 발생합니다. 배열은 스택에 할당되며 400000은 스택에 꽤 큰 숫자입니다. 복사 작업을 피하기 위해 당신은 동적으로 할당되고, 대신에 표준 : : 벡터를 사용할 수 있으며 벡터 부재의 참조를 반환 할 수 있습니다

std::vector<int> m_content(UNITS_MAX_SIZE); 

const std::vector<int> &clsUnitsUnitIDToArrayIndex::Content() const 
{ 
    return m_content; 
} 

Answer 3

아무 것도 작동하지 않으면 배열을 생성자에서 동적으로 할당 할 수 있습니다. 그러면 힙에서 큰 배열이 이동하고 페이지 스택 오류가 발생하지 않습니다.