stxxl :: map에서 std :: string을 키로 사용하는 방법

Question

stxxl :: map에서 std :: string을 키로 사용하려고합니다.10-100 정도의 작은 문자열에 삽입해도 문제가 없습니다. 그러나 그것에 약 100000 문자열을 삽입하는 동안 세그먼트 오류가 발생하고 있습니다. 여기에서

struct CompareGreaterString { 
    bool operator() (const std::string& a, const std::string& b) const { 
     return a > b; 
    } 
    static std::string max_value() { 
     return ""; 
    } 
}; 

// template parameter <KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy (optional)> 
typedef stxxl::map<std::string, unsigned int, CompareGreaterString, DATA_NODE_BLOCK_SIZE, DATA_LEAF_BLOCK_SIZE> name_map; 
name_map strMap((name_map::node_block_type::raw_size)*3, (name_map::leaf_block_type::raw_size)*3); 
for (unsigned int i = 0; i < 1000000; i++) { /// Inserting 1 million strings 
    std::stringstream strStream; 
    strStream << (i); 
    Console::println("Inserting: " + strStream.str()); 
    strMap[strStream.str()]=i; 
} 

은 내가 문자열의 많은 수를 삽입 할 수없는 나는 이유를 식별 할 수없는 나는 다음과 같이

코드입니다. "1377"을 삽입하는 동안 정확히 세그먼테이션 오류가 발생합니다. 또한 정수로 임의의 숫자를 추가 할 수 있습니다. 문자열의 가변 크기가 이러한 문제를 일으킬 수 있다고 생각합니다.

또한 max_value 문자열에 대해 반환 할 내용을 이해할 수 없습니다. 간단히 빈 문자열을 반환했습니다. documentation에 따르면

Answer 1

나는 Timo bingmann, user2079303 및 Martin Ba의 도움으로 마침내 문제를 해결했습니다. 고맙습니다.

나는 그것을 당신과 나누고 싶습니다.

먼저 stxxl은 POD 만 지원합니다. 즉, 고정 된 크기의 구조 만 저장할 수 있습니다. 따라서 std :: string은 키가 될 수 없습니다. stxxl :: map은 실제 메모리 자체에 포함되어 있기 때문에 약 100-1000 개의 문자열에서 작동했습니다. 더 많은 문자열이 삽입되면 내부적으로 몇 가지 문제를 일으키는 디스크에 기록해야합니다.

static const int MAX_KEY_LEN = 16; 

class FixedString { 
public: 
    char charStr[MAX_KEY_LEN]; 

    bool operator< (const FixedString& fixedString) const { 
     return std::lexicographical_compare(charStr, charStr+MAX_KEY_LEN, 
      fixedString.charStr, fixedString.charStr+MAX_KEY_LEN); 
    } 

    bool operator==(const FixedString& fixedString) const { 
     return std::equal(charStr, charStr+MAX_KEY_LEN, fixedString.charStr); 
    } 

    bool operator!=(const FixedString& fixedString) const { 
     return !std::equal(charStr, charStr+MAX_KEY_LEN, fixedString.charStr); 
    } 
}; 

struct comp_type : public std::less<FixedString> { 
    static FixedString max_value() 
    { 
     FixedString s; 
     std::fill(s.charStr, s.charStr+MAX_KEY_LEN, 0x7f); 
     return s; 
    } 
}; 

모든 사업자들이 주로 (!(), ==, =) 모든 재정의 (override) 할 필요가 있습니다 :

는 따라서 우리는 다음과 같은 문자는 []를 사용하여 고정 된 문자열을 사용합니다 다음과 같이 stxxl ::지도 기능은 이제 우리는지도를 위해 fixed_name_map 정의 할 수 있습니다 작동합니다 :

typedef stxxl::map<FixedString, unsigned int, comp_type, DATA_NODE_BLOCK_SIZE, DATA_LEAF_BLOCK_SIZE> fixed_name_map; 
fixed_name_map myFixedMap((fixed_name_map::node_block_type::raw_size)*5, (fixed_name_map::leaf_block_type::raw_size)*5); 

지금 프로그램이 잘 컴파일되고 아무 문제없이 약 10^8 문자열을 받고있다. 또한 myFixedMap을 std :: map 자체처럼 사용할 수 있습니다. {예 : myFixedMap [fixedString] = 10}

Answer 2

:

또한 빈 문자열로 발생

때문에지도에 저장된 키보다 큰 타입에 KeyType의 값을 돌려주는 static MAX_VALUE 방법을 제공해야합니다 CompareType 다른 문자열보다 작은 것으로 비교하면이 전제 조건을 벗어나 지정되지 않은 동작을 일으킬 수 있습니다.

다음은 작동해야하는 max_value입니다. MAX_KEY_LEN은지도가 가질 수있는 가능한 가장 긴 문자열 키의 길이보다 크거나 같은 정수입니다.

Answer 3

C++ 11을 사용하는 경우 FixedString 클래스의 대안으로 std::array<char, MAX_KEY_LEN>을 사용할 수 있습니다. 보통 고정 크기 C 배열의 맨 위에있는 STL 계층이며 std :: string에서 사용한 것처럼 비교 및 ​​반복기를 구현하지만 은 POD 유형이므로 STXXL이 지원해야합니다.

또는 TPIE에서 serialization_sort를 사용할 수 있습니다. std::pair<std::string, unsigned int> 유형의 요소를 정렬 할 수 있기 때문에 모든 것을 대량으로 삽입 한 다음 대량으로 액세스하면 필요한 경우 케이스가 충분합니다 (정확한 케이스에 따라 더 빠름).