代码之家 › 专栏 › 技术社区 › forumulator

无序映射中的C++远程键

unordered-map hashmap c++

forumulator · 技术社区 · 7 年前

我想使用 std::unordered_map ,以存储以前是否遇到过每条线的映射。

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

例如,如果字符串为 "abcd" ,那么关键是 “abcd” 但在确定它以前不存在于地图中后,它将存储为 36 例如,其中 36 是的起始位置 “abcd” 在文件中。

有没有办法用内置的 std::无序的\u映射 (或另一个hashmap数据结构)而不实现我自己的?

此外,如果没有,我自己实现它的最佳方式是什么? 我在考虑使用 std::unordered_map<size_t, vector<int>> ,其中 size_t 关键是 std::hash 向量存储文件中的位置 readline 并进行比较。有更好的方法吗?

2 回复 | 直到 7 年前

Öö Tiib 7 年前

假设您有一个名为 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();
    }
};

因此,您可以设置您的内容并实例化无序的\u集:

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

所以Q.E.D.使用自定义比较器和哈希器很简单?

forumulator 7 年前

我在这里发布我的解决方案,以防它对任何人都有帮助。这是基于 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 ,用于读取该行并对其字符串进行哈希运算的functor。

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