c++ - 使用 char* 作为 unordered_map 的键不能识别重复的键

Question

我正在构建一个 De Bruijn Assembly 示例，用于组装基因组(或任何字符串)，方法是获取字符串长度为 n 的每个可能的单词，然后通过比较每个单词的结尾部分找到正确的读取路径节点。它接受一个序列和每个序列读取的大小作为参数，它首先将所有读取收集到一个大小为 [kmer_size][3] 的数组中，[3] 索引 0=完整读取 1=读取的最右边字符以外的所有字符 2=读取的最左边字符以外的所有字符。

组装 reads 的部分按预期工作，它被分成一个函数并且这些 reads 被正确打印。

然后我创建了一个 unordered_map，使用 char* 作为键，另一个 map 作为值，该映射由 char* 键控并由 int 赋值。

应该发生的是它应该检查除了最左边的字符之外的读取部分是否与彼此读取的相同部分匹配，如果它们匹配，则获取匹配读取的右侧排除部分并创建一个新条目在由您正在测试的读取的左排除部分键入的内部映射中，将该元素的值增加 1。

如果您查看输出，您会发现当我在一个单独的循环中打印嵌套 map 的内容时，外部 map 和内部 map 中都有重复的条目。具有相同字符串值的 char* 键不会将项目放入同一个桶中，而是创建一个具有相同名称的新桶。我假设这是因为 char* 实际上是一个字符串值，而是一个地址，它们指向不同的地址。

我将如何修改此代码以允许我的 map 每个字符串只有 1 个桶

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<bits/stdc++.h> 
#include<unordered_map>

using namespace std;

void extractReads(char* kmers[][3], int num_kmers, int kmer_size, char* seq);

int main(int nargs, char* args[]){
    if(nargs!=3){
        cout<<"INVALID ARGUMENTS"<<endl;
        cout<<"dba <kmer_size> <sequence>"<<endl;
    }
    char* seq = args[2];
    int kmer_size = atoi(args[1]);
    int num_kmers = strlen(seq)-(kmer_size -1);
    char* kmers[num_kmers][3];
    unordered_map<char*, unordered_map<char*, int> > nodes;

    extractReads(kmers, num_kmers, kmer_size, seq);

    for(int i=0; i< num_kmers; i++)
    {
        for(int j=0; j<num_kmers; j++)
        {
            if(strcmp(kmers[i][2], kmers[j][2]) == 0 )
            {
                // cout<<" match"<<endl;
                nodes[kmers[i][2]][kmers[j][1]]++;
            }

        }
    }

    for(auto node: nodes)
    {
        cout<<node.first<<endl;
        for (auto n: node.second)
        {
            cout<<" "<<n.first<<" "<<n.second<<endl;
        }
    }

    return 0;
}



void extractReads(char* kmers[][3], int num_kmers, int kmer_size, char* seq)
{
    cout<<"READS"<<endl<<"==========="<<endl;
    for (int i=0; i<num_kmers; i++){
        kmers[i][0] = (char*) malloc(kmer_size);
        kmers[i][1] = (char*) malloc(kmer_size-1);
        kmers[i][2] = (char*) malloc(kmer_size-1);
        strncpy(kmers[i][0], seq+i, kmer_size);
        strncpy(kmers[i][1], kmers[i][0], kmer_size-1);
        strncpy(kmers[i][2], kmers[i][0]+1, kmer_size-1);
        cout<<kmers[i][0]<<" : "<<kmers[i][1]<<" "<<kmers[i][2]<<endl;
    }    
    cout<<"==========="<<endl;

}

Answer 1

您的代码有很多问题(正如对问题的评论所暗示的那样)，我将在答案末尾列出它们，因为它们与问题的核心无关。

正如您所怀疑的那样，有问题的行是:

unordered_map<char*, unordered_map<char*, int> > nodes

如你所说

this is because char* is actually a string value but an address and they are pointing to different addresses.

换句话说，您的字符串 (kmers) 作为指针进行比较。如果两个char *对象分配有两个不同的 malloc 调用，然后它们具有不同的地址。 unordered_map只比较地址，而不比较地址处的字符集。

解决方案是开始使用 C++ 字符串而不是 C 零终止字符串:

std::unordered_map<std::string, std::unordered_map<std::string, int> > nodes

这将解决您的代码存在的其他问题:

1. 您的代码存在内存泄漏。它使用 malloc 分配内存并且从不释放它。使用 std::string解决问题。
2. kmers 往往是相对较短的字符串(大多数少于 12 个字母)。 std::string正是针对这种情况进行了优化，并完全避免了这些字符串的堆内存。使用 std::string 代码将运行得更快通过避免不必要的堆分配。

另一种不太理想的选择是提供您自己的 Hash 和 KeyEqual 函数:

class cstr_hash
{
   public:
      std::size_t operator()(const char *cstr) const
      {
          std::size_t hash = 5381;
          for ( ; *cstr != '\0' ; ++cstr)
             hash = (hash * 33) + *cstr;
          return hash;
      }
};
class cstr_eq
{
   public:
     using value_type = const char*;
     bool operator()(const char* a, const char *b) const
     { return strcmp(a, b) == 0; }
};

然后使用 map :

 std::unordered_map<const char *, int, cstr_hash, cstr_eq> nodes;

但这种方法是不可取的，因为它更难避免内存泄漏，并且不会优化像 std::string 这样的短字符串。做。

---

您的代码存在的其他一些不相关的问题:

 char* kmers[num_kmers][3];

这不是 C++。大多数编译器都支持 VLA(可变长度数组)，但它不是标准的一部分。更好用std::vector<std::string> .

内存泄漏。您使用 malloc 分配字符串，并且从不释放它们。最好使用 std::string 并传递它，这样代码中就不再使用 malloc。

unordered_map通常效率低于 std::map对于少于 10,000 个元素的容器。对于基因组数据，您有可能遇到 std::unordered_map 的情况。值得，但我会对此进行测试(尤其是对于内部容器)。

另一个问题是使用 std::endl ，这会使您的代码运行速度慢 2-10 倍。你应该使用 '\n'而不是 endl .什么endl所做的是刷新行尾的输出。在许多情况下，额外的系统调用会在性能方面产生很大的不同。当然，如果这只是调试代码那就无所谓了。