c++ - 如何在没有对象拷贝的情况下使用 map::equal_range？

Question

我有一个使用 map<string, ...> 的性能敏感函数存储一些数据。

我需要能够使用任何 sub string 查找值 其他一些 string作为 key ，无需创建中间层 string (即，目标是防止仅仅因为我想查找某些东西而发生堆分配)。

显而易见的解决方案是保存两个单独的数据结构(也许旁边还有另一个 map，从某个键映射到每个字符串)——一个用于字符串，一个用于对这些字符串的引用。

但我想知道，是否有更好的方法只使用 map 来做到这一点？单独使用，还是我需要另一种数据结构？如果可能，我想避免创建太多额外的间接寻址。

Answer 1

抱歉，如果我误解了，但是如果您可以使用查询字符串的“子字符串 View ”而不是普通的 std::string 来搜索多映射，您的问题是否会得到解决？对象？

在这种情况下，下面几行内容会起作用(使用基于 C++11 的编码):

定义子字符串 View 对象类型。它由字符串和 (from,to) 偏移构成，但不复制子字符串:

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

为了使用子字符串 View 搜索多映射，我建议使用 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——我们需要两个，因为比较是不对称的:将多映射条目与 substringview 中的 cmpL 进行比较，并将 substringview 与多映射进行比较在 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