How to use std::string as key in stxxl::map

2014-04-17
2014-04-20
  • I am trying to use std::string as a key in the stxxl::map The insertion was fine for small number of strings about 10-100. But while trying to insert large number of strings about 100000 in it, i am getting segmentation fault.

    The code is as follows:

    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;
    }

    In here i am unable to identify why i am unable to insert more number of strings. I am getting segmentation fault exactly while inserting "1377". Plus i am able to add any number of integers as key. I feel that the variable size of string might be causing this trouble.

    Also i am unable to understand what to return for max_value of the string. I simply returned a blank string.

     
  • Thank you. but is there any other approach to make a string as key for stxxl::map.

    Could we use a char[] in it's place making key of fixed length.

    Infact stxxl::map have run with string-key for small set of elements(about 100s). But when i am trying to insert large number of keys then it is raising segmentation fault.

     
  • Timo Bingmann
    Timo Bingmann
    2014-04-17

    A fixed struct containing a char[] would work. Thats a POD.
    That small sets of strings work is clear, since they were not written to disk.
    For variable length strings sets a key-value database like BerkeleyDB is a better choice.

     
  • I am trying to add the fixed size string as you said.
    I am facing the problems mentioned below.
    Please have a look at the attachment for better description.

    /////////////// - Problems
    1. Now while adding as follows:
    myMap[fixedString] = i;
    I am getting error as Assertion `it != root_node_.end()' failed.
    This i am able to pass if i am giving numeric_limits<>::min() for get_max() which is wrong cause this should be the max value in bplus tree

    1. Also i am getting a compile time error while trying to use find as follows:
      if(myMap.find(fixedString)!=myMap.end()){}
      btree.h:601:13: error: no match for ‘operator==’ in ‘result.stxxl::btree::btree_iterator<BTreeType>::operator

    Please note that i am able to get the value myMap[fixedString] but am not able to perform myMap.find(fixedString). I am unble to understand why...

     
    Last edit: Sriram Mahavadi 2014-04-18
  • Timo Bingmann
    Timo Bingmann
    2014-04-19

    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;
        }
    };
    
    typedef stxxl::btree::btree<FixedString, double, comp_type, 4096, 4096,
    stxxl::SR> btree_type;
    
    // forced instantiation
    template class stxxl::btree::btree<FixedString, double, comp_type, 4096,
    4096, stxxl::SR>;
    

    Compiles fine.
    Timo

     
  • Thanks. It works perfectly ok.