unordered_map 中的 C++ 远程键

Question

我想解决从大文件中删除重复行的问题，使用 std::unordered_map 来存储每行之前是否遇到过的映射。

为了解决文件过大的问题，我希望map中的key是一个std::string，但是不是为了它存储在内存中，而是在文件是实际存储的值，然后比较器将只读取该位置的一行并与当前键进行比较。

例如，如果字符串是"abcd"，那么key就是"abcd"，但是在确定它之前不存在于map中之后，它会被存储为[=15] =] 例如，其中 36 是文件中 "abcd" 的起始位置。

有没有什么方法可以使用内置的 std::unordered_map（或其他 hashmap 数据结构）而不实现我自己的？

此外，如果没有，我自己实现它的最佳方法是什么？我正在考虑使用 std::unordered_map<size_t, vector<int>>，其中size_t 键是我的字符串的 std::hash，向量存储文件中的位置，我可以 readline 与之进行比较。有没有更好的方法？

Answer 1

假设您有 class 命名为 Stuff，其对象仅存储 size_t 但可以找出实际的文本行（如您所述）：

struct Stuff // the naming here is arbitrary and the code illustrative
{
    static WhateverYouNeedToReadRealRata same_to_all_stuff;
    size_t pos;
    std::string getText() const
    {
        return same_to_all_stuff.read_line_somehow_for(pos);
    }
};

然后你写自定义哈希：

struct HashStuff
{
    size_t operator()(Stuff const& stuff) const
    {
        return std::hash<std::string>()(stuff.getText());
    }
};

然后你编写自定义比较器：

struct CompareStuff
{
    bool operator()(Stuff const& left, Stuff const& right) const
    {
        return left.getText() == right.getText();
    }
};

然后你可以设置你的东西并实例化你的 unordered_set:

Stuff::same_to_all_stuff = yourSpecialCase(); 
std::unordered_set<Stuff,HashStuff,CompareStuff> stuffSet;

等等 Q.E.D。使用自定义比较器和哈希器是微不足道的吗？

Answer 2

我在这里发布我的解决方案以防它对任何人有帮助。这是基于Oo Tiib在他上面的回答中给出的想法。

首先是两个类，Line代表行。

class Line {
    streampos pos_;
    ifstream &file_;
    mutable streampos tpos_;
    mutable ios_base::iostate state_;

    void SavePos(streampos pos) const {
        tpos_ = file_.tellg();
        state_ = file_.rdstate();
        file_.clear();
        file_.seekg(pos);
    }

    void RestorePos() const {
        file_.setstate(state_);
        file_.seekg(tpos_);
    }
public:
    Line(ifstream &f, streampos pos): pos_(pos), file_(f) { }

    string GetText() const {
        string line;
        SavePos(pos_);
        getline(file_, line);
        RestorePos();
        return line;
    }

    const bool operator==(const Line& other) const {
        return (this->GetText() == other.GetText());
    }
};

然后，HashLine 仿函数读取该行并将其散列为字符串。

class HashLine {
public:
    const size_t operator() (const Line& l) const {
        return std::hash<string>()(l.GetText());
    }
};

最后是 rm_dups 函数，它创建哈希表并使用上面的类删除重复行：

int rm_dups(const string &in_file, const string &out_file) {
    string line;
    unordered_set<Line, HashLine> lines;
    ifstream file(in_file);
    ofstream out(out_file);
    if (!file || !out) {
        return -1;
    }
    streampos pos = file.tellg();
    while (getline(file, line)) {
        Line l(file, pos); 
        if (lines.find(l) == lines.end()) {
            // does not exist so far, add this new line
            out << l.GetText() << '\n';
            lines.insert(l);
        }
        pos = file.tellg();
    }
    return 0;
}

unordered_map 中的 C++ 远程键

C++ remote key in unordered_map

c++

unordered-map

hashmap