Skip navigation

In the spelling corrector article we read a whole file in memory and hold it’s data in a std::string object, and then we use a std::map to hold ranges of this big string. Those ranges are created by making copies of the string. While this aproach is satisfatory, it can be greatly improved if we can afford holding the file data while std::map is in the scope.

That’s because we may hold only information about the string range in the map, not the whole copied string, this will greatly improve spelling corrector loading time:


template<class CharT, class Traits = std::char_traits<CharT> >
class basic_const_string_range
{
public:

  typedef CharT value_type;
  typedef Traits traits_type;
  typedef const value_type* const_iterator;
  typedef std::string::size_type size_type;

  size_type size() const { return m_size; }

  basic_const_string_range(const_iterator begin, size_type size)
    : m_begin(begin)
    , m_size(size)
  {
  }

  bool operator<(const basic_const_string_range<CharT>& other) const
  {
    return traits_type::compare(begin(), other.begin(),
      other.size() > size() ? size() : other.size()) < 0;
  }

  const_iterator begin() const { return m_begin;          }
  const_iterator end()   const { return m_begin + size(); }

private:

  const_iterator m_begin;
  size_type m_size;
};

template<class CharT>
basic_const_string_range<CharT> make_range(const CharT* begin, std::string::size_type count)
{
  return basic_const_string_range<CharT>(begin, count);
}

typedef basic_const_string_range<char>    const_string_range;
typedef basic_const_string_range<wchar_t> const_wstring_range;

int main()
{
  std::string str = "apple banana orange ";
  std::map<const_string_range, int> data;

  std::string::size_type first_non_space = 0;
  std::string::size_type last_space      = 0;
  while ((first_non_space = str.find_first_not_of(' ', first_non_space)) != std::string::npos &&
         (last_space      = str.find             (' ', first_non_space)) != std::string::npos)
  {
    data[make_range(&str[first_non_space], last_space - first_non_space)] = first_non_space;
    first_non_space = last_space + 1;
  }
}

This class can be adapted to a TR1 unorderep_map providing the correct hash<> overload. The map will continue valid as long as the string object remains in the memory. Yet it has another use, consider for example this input:


int lookup(const char* data)
{
  return values[data];
}

In a normal std::map<std::string, int> when we called operator[](const std::string&) the variable data would call the std::string constructor and copy all it’s data to the string internal buffer. Using the basic_const_string_range approach we can save that copy using the const char* variable directly.

Advertisements

3 Comments

  1. Oi, vi pesaquisando na internet vi que vc programa usando wiiyourself, vc poderia me dar uma explicação de como configurou, não estou conseguindo usar.Se possivel me envie um e-mail

  2. Gostei do seu projeto do mouse, entre em contato por favor.

  3. Monkeys save continuous: separated thingumabob translations q slightly. http://imynog.com


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: