C++ map 질문

Question

나는 완전한 위치 기반 알고리즘을 가지고 있습니다. 즉, 알고리즘 출력은 곡선 위치를 기반으로하며 각 결과는 이전 결과 값의 영향을받습니다.

각 시간을 다시 계산하지 않으려면 주어진 샘플 속도로 사전 계산하고이어서 룩업을 수행하고 사전 계산 된 결과를 반환하거나 (내가 직접 착륙 한 경우) 또는 인접한 두 인접 사이를 보간합니다. 결과.

이것은 F #이나 C#에서 제게는 사소한 것이지만 C++은 매우 녹슬 었으며 (심지어 그렇게 좋지도 않았습니다).

사용할 올바른 구조를 매핑하고 있습니까? 그리고 당신이 나에게 조회를 수행하는 방법의 예를 보여줄만큼 친절 할 수 있습니까? (나는 키가 int가 될 수 있음을 의미하는 milimetres로 미리 계산할 생각입니다. 값은 double이 될 것입니다).

업데이트 좋아, 아마도 내가 원하는 정렬 된 사전입니다.

Answer 1

성병 : :지도 합리적인 소리

//Initialisation 
fun MyFunction(int position, double previousresult) returns double {/*etc*/}; 
double lastresult = 0.0; 
for(int s = startposition to endposition by sampledist) 
{ 
    lastresult = MyFunction(s, lastresult); 
    MapOrWhatever.Add(s, lastresult); 
} 
//Using for lookup 
fun GetValueAtPosition(int position) returns double 
{ 
    CheckPositionIsInRangeElseException(position); 
    if(MapOrWhatever.ContainsKey(position)) 
     return MapOrWhatever[position]; 
    else 
    { 
     int i = 0; 
     //or possibly something clever with position % sampledist... 
     while(MapOrWhatever.Keys[i] < position) i+=sampledist; 
     return Interpolate(MapOrWhatever, i, i+sampledist, position); 
    } 
} 

내가 상수 sampledist을 유지 어쩌면 경우, 난 그냥 배열과 인덱스를 사용할 수 ... 생각한다 ... : 의사 (소매를 롤업) 당신의 가치가 연속적이지 않을 것이라는 점을 보장한다면 여기에서 메모를 해주십시오. 여기

#include <map> 

// ... 

std::map<int, double> memo; 
memo.insert(std::make_pair(5, 0.5)); 
double x = memo[5]; // x == 0.5 

Answer 2

내 의견을 참조하십시오,하지만 언급하지 않았다 다른 포스터 사용 []가 '아무튼 중요한 검색하는 것이보다 맵 문서

http://www.cplusplus.com/reference/stl/map/

및 중요하다 지도에 존재하지 않는다면,지도는 거기에 무엇인가 존재하도록 객체를 생성 할 것입니다.

편집 : 반복자를 반환이 정보 대신 http://msdn.microsoft.com/en-us/library/fe72hft9%28VS.80%29.aspx

를 사용 발견(), 여기 문서를 참조하십시오. 이 반복자를 map.end()에 대해 테스트하고, 같으면 일치하는 것이 없다.

Answer 3

지도를 고려하는 경우 항상 벡터도 고려하십시오. 응용 프로그램을 실행하는 동안 많이 변경되지 않거나 전혀 변경되지 않은 값의 경우 미리 정렬 된 std::vector< std::pair<Key,Value> > (O(N) 조회)은 더 이상 수행하지 않고 std::map<key,Value> (O(log N) 조회)보다 조회를 빠르게 수행합니다. 이론.

시도하고 측정해야합니다.

Answer 4

HASH_MAP은 다른 알고리즘보다 빠른 검색을위한 최고의 STL 알고리즘입니다. 그러나 채우기는 맵이나 벡터보다 약간 시간이 걸리고 또한 정렬되지 않습니다. 모든 가치 검색에 일정한 시간이 걸립니다.

std::hash_map<int, double,> memo; 
memo.insert(std::make_pair(5, 0.5)); 
memo.insert(std::make_pair(7,0.8)); 
. 
. 
. 
hash_map<int,double>::iterator cur = memo.find(5); 
hash_map<int,double>::iterator prev = cur; 
hash_map<int,double>::iterator next = cur;  
    ++next; 
    --prev; 

보간 전류 값 (* 다음) .second() (* 이전) .second() 값 ..

Answer 5

참조 : http://www.cplusplus.com/reference/stl/map/

당신은지도를 사용할 수는지도의

typedef std::map<int,const double> mapType; 

성능 등이있다 :

지도 :: 크기 복잡성 대수를 찾을 수 있습니다. X는 컨테이너 요소의 키 일치 함수가 매핑 된 값에 대한 참조를 반환하면

지도

에서 조작 []주의.

x가 컨테이너의 모든 요소의 키와 일치하지 않으면 함수는 해당 키와 함께 새 요소를 삽입하고 매핑 된 값에 대한 참조를 반환합니다. 매핑 된 값이 요소에 할당되지 않은 경우에도 요소 크기가 항상 1 씩 증가합니다 (요소는 기본 생성자를 사용하여 구성됩니다).

Answer 6

속도가 너무 중요하지 않은 한 std :: map은 괜찮습니다. 룩업의 속도가 중요하다면 위에서 언급 한 바와 같이 원하는 요소로 곧바로 갈 수있는 벡터를 시도 할 수 있습니다 (위치에서 인덱스를 계산할 수 있으므로 이진 검색을 사용하지 마십시오). 예 :

vector<double> stored; 

// store the values in the vector 
double lastresult = 0.0; 
for(int s = startposition, index = 0; s <= endposition; s+=sampledist, ++index) 
{ 
    lastresult = MyFunction(s, lastresult); 
    stored[index] = lastresult; 
} 

//then to lookup 
double GetValueAtPosition(int position) returns double 
{ 
int index = (position - startposition)/sampledist; 
lower = stored[index]; 
upper = stored[index+1]; 
return interpolate(lower, upper, position); 
}