如何在没有对象副本的情况下使用map :: equal_range？

Question

我有一个性能敏感的功能,它使用a map<string, ...>来存储一些数据.

我需要能够使用其他任何子string元素string作为键来查找值,而不创建中间符string(即,目标是防止堆分配仅仅因为我想要查找某些内容).

显而易见的解决方案是保存两个独立的数据结构(可能是另一个数据结构map,从一些键映射到每个字符串) - 一个用于字符串,一个用于引用这些字符串.

但我想知道,有没有更好的方法只用一个map人做这个,或者我需要另一个数据结构？如果可能的话,我想避免创造太多的额外间接.

Answer 1

很抱歉,如果我误解了,但如果您可以使用查询字符串的"子字符串视图"来搜索多地图而不是普通std::string对象,您的问题是否会得到解决？

在这种情况下,下面的行可以使用(使用基于C++ 11的编码):

定义子字符串视图对象类型.它由字符串和(从,到)偏移量构成,但不会复制子字符串:

class substrview
{
  std::string::const_iterator _from;
  std::string::const_iterator _to;
public:
  substrview(
       const std::string &s,
       const std::size_t from,
       const std::size_t to)
    : _from(s.begin()+from), _to(s.begin()+to)
  { }

  std::string::const_iterator begin() const
  { return _from; }

  std::string::const_iterator end() const
  { return _to; }
};

为了使用子视图搜索多图,我建议使用std::lower_bound和std::upper_bound方法来自<algorithm>:

int main()
{
  std::multimap<std::string,int> map {
    { "hello" , 1 },
    { "world" , 2 },
    { "foo" , 3 },
    { "foobar" , 4 },
    { "foo" , 5 },
  };

  std::string query { "barfoo" };
  /* Search for all suffixes of "barfoo", one after the other: */
  for (std::size_t i = 0 ; i < query.size() ; ++i) {
    substrview subquery { query,i,query.size() };
    auto found_from = std::lower_bound(begin(map),end(map),subquery,cmpL);
    auto found_to   = std::upper_bound(begin(map),end(map),subquery,cmpU);

    /* Now [found_from,found_to) is the match range in the multi-map.
       Printing the matches: */
    while (found_from != found_to) {
      std::cout << found_from->first << ", " << found_from->second << '\n';
      ++found_from;
    }

  }
}

为了实现这一点,我们只需要定义比较运算符cmpL和cmpU(一个用于lower_bound,另一个用于upper_bound- 我们需要两个因为比较是不对称的:将多映射条目与substringviewin cmpL进行比较,并将a substringview与多映射条目进行比较in cmpU):

inline bool cmpL(
    const std::pair<std::string,int> &entry,
    const substrview                 &val)
{
  return std::lexicographical_compare
    (entry.first.begin(),entry.first.end(),val.begin(),val.end());
}

inline bool cmpU(
   const substrview                 &val,
   const std::pair<std::string,int> &entry)
{
  return std::lexicographical_compare
    (val.begin(),val.end(),entry.first.begin(),entry.first.end());
}

完整代码的工作要点:https://gist.github.com/4070189