표준 : :지도에서 존재하지 않는 키 찾기

Question

지도에 존재하지 않는 키를 찾는 방법이 있습니까?

나는 std::map<int,myclass>을 사용하고 있으며 새 항목의 키를 자동으로 생성하려고합니다. 항목은 삽입 순서와 다른 순서로지도에서 삭제 될 수 있습니다.

myclass 항목은 동일하거나 동일하지 않을 수 있으므로 자신이 키 역할을 할 수 없습니다.

프로그램을 실행하는 동안 생성되고 삭제되는 항목의 수에는 제한이 없으므로 카운터를 키로 사용할 수 없습니다.

동일한 기능과 성능을 가진 대체 데이터 구조가 가능합니다.

내 항목에 대한 컨테이너를 구축을 위해 노력

편집 - I 삭제할 수 있도록/자신의 키에 따라 항목을 수정하고, 나는 항목을 반복 할 수 있습니다. 키 값 자체는 나에게 아무런 의미가 없지만 다른 개체는 내부 용도로 키를 저장합니다.

내가 증분 카운터를 사용할 수없는 이유는 프로그램의 수명 기간 동안 2^32 (또는 이론적으로 2^64) 개 항목이 될 수 있기 때문입니다. 그러나 항목 0은 이론적으로는 여전히 다른 항목은 삭제됩니다.

std :: map에 가장 낮은 값의 미사용 키를 묻는 것이 좋을 것이므로 사용되지 않은 키에 벡터 또는 다른 다른 저장 장치를 사용하는 대신 새 항목에 사용할 수 있습니다.

Answer 1

만약 내가 이해하면 보자. 원하는 작업은

입니다. 키를 찾으십시오. 요소가 없으면 요소를 삽입하십시오.

항목은 삭제 될 수 있습니다.

카운터 (대기 대기)와 벡터를 유지하십시오. 벡터는 삭제 된 항목의 ID를 유지합니다. 새 요소를 삽입하려고하면 벡터에서 키를 찾습니다. 벡터가 비어 있지 않으면 키를 제거하고 사용하십시오. 비어있는 경우 카운터 (카운터 ++)에서 하나를 가져옵니다. 그러나지도에서 항목을 제거하지 않으면 방금 카운터가 붙어 있습니다.

대체 : 요소의 메모리 주소를 키로 사용하는 것은 어떻습니까?

Answer 2

존재하지 않는 키를 찾을 수있는 방법이 있습니까?

여기에 무슨 뜻인지 확실하지 않습니다. 존재하지 않는 것을 어떻게 찾을 수 있습니까? 지도에 키가 포함되어 있지 않은지 여부를 알려주는 방법이 있습니까?

이것이 의미하는 바라면 find 함수를 사용하고 키가 존재하지 않으면 end()을 가리키는 반복자를 반환합니다.

if (my_map.find(555) == my_map.end()) { /* do something */ } 

계속 하시겠습니까?

나는 표준 : :지도를 사용하고

및 나는 자동으로 새로운 항목에 대한 키 를 생성합니다. 지도에서 항목을 삭제할 수 있습니다. 삽입 순서는 입니다. myclass 항목은 동일하거나 동일하지 않을 수 있기 때문에 키 항목으로 사용할 수 없습니다.

여기에서 수행하려는 작업이 다소 불투명합니다. 지도에 myclass의 인스턴스를 저장하려고하지만 중복 값이 ​​myclass 일 수 있으므로 고유 키를 생성 할 방법이 필요합니다. 그 대신에 그냥 std::multiset<myclass>을 사용하고 중복 된 것을 저장하는 것이 어떻습니까? myclass의 특정 값을 조회하면 다중 세트는 해당 값을 가진 myclass의 모든 인스턴스에 반복기를 리턴합니다. myclass에 대한 비교 기능을 구현하면됩니다.

Answer 3

왜 간단한 증분 카운터를 자동 생성 키로 사용할 수 없습니까? (삽입시 증가)? 그것을하는 데 문제가없는 것 같습니다.

Answer 4

나는 카운터와 큐를 제안했다. 지도에서 항목을 삭제할 때 키를 대기열에 추가하십시오. 그런 다음 큐는 맵에서 삭제 된 키를 추적하여 다시 사용할 수 있도록합니다. 새 키를 얻으려면 먼저 큐가 비어 있는지 확인합니다. 그렇지 않은 경우 맨 위 색인을 해제하고 사용하십시오. 그렇지 않으면 카운터를 사용하여 다음 사용 가능한 키를 가져옵니다.

Answer 5

• 비 카운터 기반 키를 생성하는 방법을 결정한 후이를 일괄 적으로 생성하는 것이 하나씩 생성하는 것보다 훨씬 효과적이라고 생각하십시오.
• 이 생성기가 "무한"및 "상태 유지"(사용자 요구 사항 임) 인 것으로 판명되면 사용하지 않는 키가 1000 개있는 두 번째 고정 크기 컨테이너를 만들 수 있습니다.
• 지도의 새 항목을이 컨테이너의 키로 제공하고 재활용을 위해 키를 반환합니다.
• "무한"생성기를 사용하여 낮은 수준에 도달하는 키 컨테이너에 반응하고 일괄 적으로 키를 리필하기 위해 낮은 "임계 값"을 설정하십시오.

실제 게시 된 문제는 여전히 "비 카운터 기반 효율적인 생성기를 만드는 방법"입니다. "무한대"요구 사항을 다시 한 번 살펴보고 1000 년과 같이 제한된 기간 동안 64 비트 또는 128 비트 카운터가 여전히 알고리즘을 충족시킬 수 있는지 확인하십시오.

sequence_key_t global_counter; 

std::map<sequence_key_t,myclass> my_map; 

my_map.insert(std::make_pair(++global_counter, myclass())); 

당신은 필요가 없습니다 문제 : 순서의 주요 유형으로 또는 당신이 충분하지

struct sequence_key_t { 
    uint64_t upper; 
    uint64_t lower; 
    operator++(); 
    bool operator<() 
}; 

처럼 될 것이라고 생각하면

Answer 6

사용 uint64_t.

Answer 7

다른 사람들과 마찬가지로 나는 당신이 원하는 것을 정확히 알아 내는데 어려움을 겪고 있습니다. 항목을 찾을 수없는 경우 만들려는 것 같습니다. sdt :: map :: operator [] (const key_type & x)를 사용하면됩니다.

std::map<int, myclass> Map; 
myclass instance1, instance2; 

Map[instance1] = 5; 
Map[instance2] = 6; 

당신이 생각하고있는 것이 맞습니까?

Answer 8

다른 답변과 함께 ID 생성을위한 간단한 카운터를 제안합니다. 완전 정확함에 대해 걱정이된다면 내장형이 아닌 카운터에 임의의 정밀도 정수를 사용할 수 있습니다. 또는 다음과 같이 가능한 모든 문자열을 반복합니다.

void string_increment(std::string& counter) 
{ 
    bool carry=true; 
    for (size_t i=0;i<counter.size();++i) 
    { 
     unsigned char original=static_cast<unsigned char>(counter[i]); 
     if (carry) 
     { 
      ++counter[i]; 
     } 
     if (original>static_cast<unsigned char>(counter[i])) 
     { 
      carry=true; 
     } 
     else 
     { 
      carry=false; 
     } 
    } 
    if (carry) 
    { 
     counter.push_back(0); 
    } 
} 

그래서 당신은 가지고 :

std::string counter; // empty string 
string_increment(counter); // now counter=="\x00" 
string_increment(counter); // now counter=="\x01" 
... 
string_increment(counter); // now counter=="\xFF" 
string_increment(counter); // now counter=="\x00\x00" 
string_increment(counter); // now counter=="\x01\x00" 
... 
string_increment(counter); // now counter=="\xFF\x00" 
string_increment(counter); // now counter=="\x00\x01" 
string_increment(counter); // now counter=="\x01\x01" 
... 
string_increment(counter); // now counter=="\xFF\xFF" 
string_increment(counter); // now counter=="\x00\x00\x00" 
string_increment(counter); // now counter=="\x01\x00\x00" 
// etc.. 

Answer 9

나는 일반적인 경우에, 키가지도에 의해 허용되는 모든 유형을 가질 수 있다고, 이것은 불가능합니다. 사용되지 않는 키가 있는지 여부를 말할 수있는 능력조차도 유형에 대한 지식이 필요합니다.

int를 사용하여 상황을 고려하면 사용되지 않은 키의 연속 세그먼트 집합 (이 세그먼트는 겹치지 않으므로 자연 순서가 사용될 수 있으므로 시작점을 비교하기 만 함)을 저장할 수 있습니다. 새 키가 필요할 때 첫 번째 세그먼트를 가져 와서 첫 번째 인덱스를 잘라내어 나머지를 세트에 배치합니다 (나머지가 비어 있지 않은 경우). 어떤 키가 풀리면, 집합에 이웃 세그먼트가 있는지 (O (log n) 복잡도로 설정 될 수 있기 때문에) 찾아낸 다음 필요하다면 병합을 수행합니다. 그렇지 않으면 [n, n] 세그먼트를 집합에 넣기 만하면됩니다. 지도 요청 역사에 독립적으로 가지고 당신이 확실히 시간 복잡도 및 메모리 소비의 순서와 동일한 순서를해야합니다 이런 식으로

(세그먼트의 수는 map.size 이상이 될 수 없기 때문에() + 1)

이 같은 뭔가 다음이지도에서 실제로 작업 집합 경우

class TKeyManager 
{ 
public: 
    TKeyManager() 
    { 
     FreeKeys.insert(
      std::make_pair(
      std::numeric_limits<int>::min(), 
      std::numeric_limits<int>::max()); 
    } 
    int AlocateKey() 
    { 
     if(FreeKeys.empty()) 
      throw something bad; 
     const std::pair<int,int> freeSegment=*FreeKeys.begin(); 
     if(freeSegment.second>freeSegment.first) 
      FreeKeys.insert(std::make_pair(freeSegment.first+1,freeSegment.second)); 
     return freeSegment.first; 
    } 
    void ReleaseKey(int key) 
    { 
     std:set<std::pair<int,int>>::iterator position=FreeKeys.insert(std::make_pair(key,key)).first; 
     if(position!=FreeKeys.begin()) 
     {//try to merge with left neighbour 
      std::set<std::pair<int,int>>::iterator left=position; 
      --left; 
      if(left->second+1==key) 
      { 
       left->second=key; 
       FreeKeys.erase(position); 
       position=left; 
      } 
     } 
     if(position!=--FreeKeys.end()) 
     {//try to merge with right neighbour 
      std::set<std::pair<int,int>>::iterator right=position; 
      ++right; 
      if(right->first==key+1) 
      { 
       position->second=right->second; 
       FreeKeys.erase(right); 
      } 
     } 
    } 
private: 
    std::set<std::pair<int,int>> FreeKeys; 
}; 

Answer 10

또 다른 옵션, 충분한 카운터가 포장하려고 할 때 키를-생성 다시 다음, 증분 키를 사용하는 것입니다 작다. 이 솔루션은 일시적인 추가 저장 공간 만 필요합니다. 해시 테이블 성능은 변경되지 않으며 키 생성은 if 및 increment 일뿐입니다.

현재 작업 집합의 항목 수는 실제로이 방법이 실행 가능한지 여부를 결정합니다.