为什么 bitset 抛出 out_of_range 错误？

Question

我正在使用 C++ 中的位集实现布隆过滤器以找出恶意 URL。我有一个 100 位的位集和一个简单的哈希函数。但我仍然收到此错误。

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define m 100
#define k 1

ll hash1(string str)
{   
    ll value=0;
    for(ll i=0;i<str.size();i++)
    {
        value=(value+str[i])%m;
    }
    return value;
}

int main(int argc, char *argv[])
{   
    vector<bitset<m>>v(1);
    ifstream fin;
    fin.open(argv[1]);

    string line;
    string temp;
    while(getline(fin,line))
    {   
        vector<string>row;
        stringstream s(line);
        string word;
        while(getline(s ,word, ','))
        {
            row.push_back(word);
        }
        if(row.size()!=2) continue;
        for(ll i=0;i<k;i++)
        {
            if(row[1]=="bad")
            {   
                v[0].set(hash1(row[0]));
                cout<<row[0]<<" inserted into bloom filter\n";
            }
        }
        row.clear();
    }
    //Now bitset contains all the malicious urls
    //Generating validation dataset
    fin.clear();
    fin.seekg(0);

    vector<vector<string>>validation;
        
    while(getline(fin,line))
    {
        vector<string>row;
        
        ll x=rand()%10;
        if(x>0) continue;
        
        string word;
        stringstream s(line);
        while(getline(s,word,','))
        {
            row.push_back(word);
        }
        validation.push_back(row);
        row.clear();
    }

    for(ll i=0;i<validation.size();i++)
    {   
        if(v[0].test(hash1(validation[i][0])))
        { 
            if(validation[i][1]=="bad")
            {
                cout<<i+1<<" : True Positive\n";
            }
            else
            {
                cout<<i+1<<" : False Positive\n";
            }
        }
        else 
        {
            cout<<i+1<<" : True Negative\n";
        }
    }
    return 0;
}

错误是：- 在抛出 'std::out_of_range' 的实例后终止调用 what(): bitset::set: __position （即 18446744073709551587）>= _Nb（即 100）已中止（核心已转储）

数据集包含 2 列，即。网址和 good/bad.

这是对数据集的 link。 https://www.kaggle.com/antonyj453/urldataset

Answer 1

仔细阅读后认为原因可能是签名字符。如果涉及签名字符，

for (char i : str) {
    value = (value + i) % m;
}

可能会导致负散列。然而，这实际上不太可能发生，因为 urls 不经常包含高 ascii（实际上你会期望他们的 IDNA 编码版本在列表中）。

A quick check reveals 70 such domains in the list

xn---21-6cdxogafsegjgafgrkj4opcf2a.xn--p1ai/images/aaa/,bad
xn--cafsolo-dya.de/media/header/A.php,bad
xn--b1afpdqbb8d.xn--p1ai/web/data/mail/-/aaaaa/Made.htm,bad
xn-----6kcbb3dhfdcijbv8e2b.xn--p1ai/libraries/openid/Auth/OpenID/sec/RBI/index/index.htm,bad

etc.

如果不是这样，那么 else 就会抛出 out_of_range。没有/应该/因为 operator[] 没有根据标准。

然而，也许有些实现会在调试版本中进行边界检查（看在 MSVC here 中，他们默认启用了各种迭代器调试方式调试构建，所以也许这也是？）。

Ironically you could use some bounds-checking yourself e.g. here:
int main(int argc, char* argv[]) {
    std::vector<std::string_view> const args(argv, argv + argc);
    std::string const filename(args.at(1));
This way you don't just invoke Undefined Behaviour when the command line argument is not given.

行结束

行尾有一个陷阱。这些文件是 CRLF，所以你解析的方式 columns 导致最后一列包含 "bad\r"，而不是 "bad" Linux.

Review/Simplify

在寻找其他错误的过程中，我简化了代码。它会表现很多现在好点了。这是运行-down 的改进建议。

包括。只包含您需要的内容，真的

#include <bitset>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

不需要奇怪的类型或宏。

static constexpr size_t m = 100;
static constexpr size_t k = 1; // unused for now

如前所述，防止签名字符结果：

static size_t hash1(std::string_view str) {
   size_t value = 0;
   for (unsigned char i : str) {
       value = (value + i) % m;
   }
   return value;
}

也如前所述防止尾随特殊字符分类文字：

enum goodbad { good, bad, invalid }; // The Good, The Bad and ...

static goodbad to_classification(std::string_view text) {
    if (text == "bad") return bad;
    if (text == "good") return good;
    return invalid;
}

接下来，一个大的。您两次解析同一个文件。并重复代码。不要吧。而是有一个解析它的函数，并将它传递给回调决定如何处理已解析的数据。

当我们在做的时候，让我们停止无处不在vector<vector<vector<string> > > 疾病。真的，您知道有多少列以及它们的含义。这也减少了很多分配。

void process_csv(std::string filename, auto callback) {
    std::ifstream fin(filename);

    std::stringstream ss;
    for (std::string line; getline(fin, line);) {
        std::string_view row(line);

        // eat line end remnants
        row = row.substr(0, row.find_last_not_of("\r\n") + 1);

        if (auto comma = row.find_last_of(','); comma + 1) {
            auto url     = row.substr(0, comma);
            auto goodbad = row.substr(comma + 1);
            auto classif = to_classification(goodbad);

            if (classif == invalid)
                std::cerr << "Ignored unclassified line '" << row << "'\n";
            else
                callback(url, to_classification(goodbad));
        }
    }
}

就是这样。请注意我们仅使用 last 逗号进行拆分的关键见解。因为如果 url 包含逗号，您会得到错误的结果。

现在，您可以拼凑主程序了：
```
int main(int argc, char* argv[]) {
    std::vector const args(argv, argv + argc);
    std::string const filename(args.at(1));
```
从前面提到的使用命令行参数的安全方式开始，
```
std::bitset<m> bloom;
```
减少冗长 vector<vector<> > 综合症（并改进名称 - v?!）

文件读取第一关来了：

size_t bloom_size = 0;
process_csv(filename,
    [&](std::string_view url, goodbad classification) {
        if (classification == bad) {
            bloom_size += 1;
            bloom.set(hash1(url));
            //std::cout << url << " inserted into bloom filter\n";
        }
    });

我决定没有必要（而且很慢）打印所有 bad urls，所以让我们打印它们的数量：

// Now bitset contains all the malicious urls
std::cerr << "Bloom filter primed with " << bloom_size << " bad urls\n";

现在验证通过：

// do a 1 in 10 validation check
process_csv(filename,
    [&bloom, line = 0](std::string_view url,
                       goodbad classification) mutable {
        line += 1;
        if (rand() % 10) return; // TODO #include <random>

        auto hit      = bloom.test(hash1(url));
        bool expected = (classification == bad);

        std::cout << line << ": " << std::boolalpha
                  << (hit == expected)
                  << (hit ? " positive" : " negative") << "\n";
    });
}

现场演示

Live On Coliru

#include <bitset>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

static constexpr size_t m = 100;
//static constexpr size_t k = 1;

static size_t hash1(std::string_view str) {
    size_t value = 0;
    for (unsigned char i : str) {
        value = (value + i) % m;
    }
    return value;
}

enum goodbad { good, bad, invalid }; // The Good, The Bad and ...

static goodbad to_classification(std::string_view text) {
    if (text == "bad") return bad;
    if (text == "good") return good;
    return invalid;
}

void process_csv(std::string filename, auto callback) {
    std::ifstream fin(filename);

    std::stringstream ss;
    for (std::string line; getline(fin, line);) {
        std::string_view row(line);

        // eat line end remnants
        row = row.substr(0, row.find_last_not_of("\r\n") + 1);

        if (auto comma = row.find_last_of(','); comma + 1) {
            auto url     = row.substr(0, comma);
            auto goodbad = row.substr(comma + 1);
            auto classif = to_classification(goodbad);

            if (classif == invalid)
                std::cerr << "Ignored unclassified line '" << row << "'\n";
            else
                callback(url, to_classification(goodbad));
        }
    }
}

int main(int argc, char* argv[]) {
    std::vector const args(argv, argv + argc);
    std::string const filename(args.at(1));

    std::bitset<m> bloom;

    size_t bloom_size = 0;
    process_csv(filename, [&](std::string_view url, goodbad classification) {
        if (classification == bad) {
            bloom_size += 1;
            bloom.set(hash1(url));
        }
    });

    // Now bitset contains all the malicious urls
    std::cerr << "Bloom filter primed with " << bloom_size << " bad urls\n";

    // do a 1 in 10 validation check
    process_csv(filename,
        [&bloom, line = 0](std::string_view url,
                           goodbad classification) mutable {
            line += 1;
            if (rand() % 10) return;

            auto hit      = bloom.test(hash1(url));
            bool expected = (classification == bad);

            std::cout << line << ":" << std::boolalpha
                      << (hit == expected)
                      << (hit ? " positive" : " negative") << "\n";
        });
}

在 Coliru 上只有不好的数据集适合，所以我们从来没有得到任何积极的结果

g++ -std=c++2a -O2 -Wall -pedantic -pthread main.cpp
./a.out bad.csv  | cut -d: -f2 | sort | uniq -c | sort -n

版画

Ignored unclassified line 'url,label'
Bloom filter primed with 75643 bad urls
Ignored unclassified line 'url,label'
   7602 true positive

在我自己的系统上：

~~哦，它运行s 在 0.4s 而不是之前的 3.7s。~~

解析错误修复后更快：完整集平均 0.093 秒。

为什么 bitset 抛出 out_of_range 错误？

Why is bitset throwing out_of_range error?

c++

coredump

std

bloom-filter

bitset

行结束

Review/Simplify

现场演示