c++ - std::map<key_type, value_type>::find(different_key_type)

coder 2024-02-19 原文

我有一张 map :

std::map<TyString, int> myMap;

但是，在某些情况下，我想通过比较 TyString == TyStringRef 来std::map::find 一个条目，即

myMap.find(TyStringRef("MyString"));

原因是 TyString 包装了一个它自己分配和释放的 const char *。但是，为了只找到一个条目，我不喜欢分配一个新的字符串，而是我只想使用引用(TyStringRef 只包装一个 const char * 而不分配或释放内存)。

当然，我可以将 TyStringRef 转换为 TyString，但这样我就有了上述的内存开销。

有解决这个问题的智能方法吗？

谢谢!

最佳答案

请注意 std::map::find使用 operator<默认情况下，或用户定义的比较仿函数。所以除非你重载 operator<对于 TyString和 TyStringRef ，您无法在对数时间内查找 key 。与 operator==重载时，您仍然可以在线性时间 内查找，但不能使用std::map::find .

为此，您应该使用 #include <algorithm> 中的通用算法，它独立于容器类。它可以采用任何类型 T并使用 operator== 进行比较关于 operator*() 的结果您传入的迭代器的数量。

std::find(sequence.begin(), sequence.end(), myKey);

但是，有一个问题:既然你有一个 std::map ，它使用对作为迭代器，键值对将被比较。所以你必须使用 std::find_if ，它采用谓词而不是值来搜索。此谓词应返回 true对于您正在寻找的元素。您想要 first == myKey 的元素(对) , 所以你最终得到这样的代码:

std::find_if(myMap.begin(), myMap.end(), [](const std::pair<TyString,int> & pair) {
    return pair.first == TyStringRef("MyString");
};

这在概念上可行，但它不会使用 std::map 中的二叉树.因此，与 std::map::find 的对数时间相比，它需要线性时间 .

还有一个替代方案，一开始看起来有点奇怪，但它的优点是它将进行对数时间查找。 需要你重载operator<(TyString,TyStringRef) . 您可以使用std::lower_bound根据给定的比较函数，找到第一个不小于(大于或等于)某个元素的元素。

std::lower_bound(myMap.begin(), myMap.end(), TyStringRef("MyString"),
    [](const std::pair<TyString,int> & entry, const & TyStringRef stringRef) {
        return entry.first < stringRef;
    }
);

找到“下界”后，您仍然需要测试键比较是否相等。如果他们不这样做，则找不到该元素。由于所有元素都可能与您要查找的元素相比较少，因此返回的迭代器可能是结束迭代器，不应取消引用。所以完整的代码变成了这个，类似于std::map::find如果未找到 key ，则返回结束迭代器:

template<class Map, class KeyCompareType,
         class Iterator = typename Map::const_iterator>
Iterator findInMap(const Map &map, const KeyCompareType &key)
{
    typedef typename Map::value_type value_type;
    auto predicate = [](const value_type & entry, const KeyCompareType & key) {
        return entry.first < key;
    };
    Iterator it = std::lower_bound(map.begin(), map.end(), key, predicate);
    if (it != map.end()) {
        if (!(it->first == key))
            it = map.end();
    }
    return it;
}

Live example

关于c++ - std::map<key_type, value_type>::find(different_key_type)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16863426/

有关c++ - std::map<key_type, value_type>::find(different_key_type)的更多相关文章

ruby-on-rails - Rails 3.2.1 中 ActionMailer 中的未定义方法 'default_content_type=' - 2
我在我的项目中添加了一个系统来重置用户密码并通过电子邮件将密码发送给他，以防他忘记密码。昨天它运行良好(当我实现它时)。当我今天尝试启动服务器时，出现以下错误。=>BootingWEBrick=>Rails3.2.1applicationstartingindevelopmentonhttp://0.0.0.0:3000=>Callwith-dtodetach=>Ctrl-CtoshutdownserverExiting/Users/vinayshenoy/.rvm/gems/ruby-1.9.3-p0/gems/actionmailer-3.2.1/lib/action_mailer
ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
ruby - 使用 `+=` 和 `send` 方法 - 2
如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:
ruby-on-rails - Rails 单表继承 : How to override the value written to the type field - 2
在我的系统中，我已经定义了STI。Dog继承自Animal，在animals表中有一个type列，其值为"Dog"。现在我想让SpecialDog继承自dog，只是为了在某些特殊情况下稍微修改一下行为。数据还是一样。我需要通过SpecialDog运行的所有查询，以返回数据库中类型为Dog的值。我的问题是因为我有一个type列，rails将WHERE"animals"."type"IN('SpecialDog')附加到我的查询中，所以我不能获取原始的Dog条目。所以我想要的是以某种方式覆盖rails在通过SpecialDog访问数据库时使用的值，使其表现得像Dog。有没有办法覆盖用于类型
ruby - 如何计算 Liquid 中的变量 +1 - 2
我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。最佳答案因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我
ruby-on-rails - Ruby - 如何从 ruby 上的 .pfx 文件中提取公钥、rsa 私钥和 CA key - 2
我有一个.pfx格式的证书，我需要使用ruby提取公共(public)、私有(private)和CA证书。使用shell我可以这样做:#ExtractPublicKey(askforpassword)opensslpkcs12-infile.pfx-outfile_public.pem-clcerts-nokeys#ExtractCertificateAuthorityKey(askforpassword)opensslpkcs12-infile.pfx-outfile_ca.pem-cacerts-nokeys#ExtractPrivateKey(askforpassword)o
ruby-on-rails - ActiveRecord 的 find_or_create* 方法是否存在根本性缺陷？ - 2
有几种方法:first_or_create_by、find_or_create_by等，它们的工作原理是:与数据库对话以尝试找到我们想要的东西如果我们找不到，就自己做保存到数据库显然，并发调用这些方法可能会使两个线程都找不到它们想要的东西，并且在第3步中一个线程会意外失败。似乎更好的解决方案是，创建或查找即:提前在您的数据库中创建合理的唯一性约束。如果你想保存一些东西，就保存它如果有效，那就太好了。如果它因为RecordNotUnique异常而无法工作，它已经存在，太好了，加载它那么在什么情况下我想使用Rails内置的东西而不是我自己的(看起来更可靠)create_or_find？
ruby-on-rails - 为什么方法 column_types 在 Rails 5.0 中未定义？ - 2
我正在为一个类赋值，它在rspec测试中使用了column_types方法。it"Userdatabasestructureinplace"doexpect(User.column_names).toinclude"password_digest","username"expect(User.column_types["username"].type).toeq:stringexpect(User.column_types["password_digest"].type).toeq:stringexpect(User.column_types["created_at"].type).t
arrays - Ruby 数组 += vs 推送 - 2
我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“
ruby-on-rails - self 在 Rails 模型中的值(value)是什么？为什么没有明显的实例方法可用？ - 2
我的rails3.1.6应用程序中有一个自定义访问器方法，它为一个属性分配一个值，即使该值不存在。my_attr属性是一个序列化的哈希，除非为空白，否则应与给定值合并指定了值，在这种情况下，它将当前值设置为空值。(添加了检查以确保值是它们应该的值，但为简洁起见被删除，因为它们不是我的问题的一部分。)我的setter定义为:defmy_attr=(new_val)cur_val=read_attribute(:my_attr)#storecurrentvalue#makesureweareworkingwithahash,andresetvalueifablankvalueisgiven

c++ - std::map<key_type, value_type>::find(different_key_type)

有关c++ - std::map<key_type, value_type>::find(different_key_type)的更多相关文章

随机推荐