std :: unordered_set с пользовательским типом ключа позволяет вставлять дубликаты ключей - PullRequest
Новая
       56

std :: unordered_set с пользовательским типом ключа позволяет вставлять дубликаты ключей

0 голосов
/ 11 июня 2018

Код представляет собой простой лучший код для первого поискового тестирования.

У меня есть std::unordered_set с пользовательским ключом.

Но он может вставить два дублирующих ключа!

Вставка защищена условием с функцией find.

И функция insert также возвращает true, как на скриншоте.

duplication inserted

Вот воспроизводимый код, работающий с Visual Studio 15.7.3

Вы можете попробовать его в C ++ Shell по ссылке: http://cpp.sh/4iq27

#include <iostream>
#include <unordered_set>
#include <queue>
#include <cmath>

using namespace std;

long kth(int k) {
  struct Point {
    int x;
    int y;
    int z;
  };

  auto calc = [&](const Point &p) -> size_t {
    return pow(3, p.x) * pow(5, p.y) * pow(7, p.z);
  };

  // min heap
  auto greater_cmp = [&](const Point &l, const Point &r) { return calc(l) > calc(r); };
  priority_queue<Point, vector<Point>, decltype(greater_cmp)> pq(greater_cmp);

  // hash set
  auto point_hash = [&](const Point &p) { return p.x * k * k + p.y * k + p.z; };
  auto point_equal = [&](const Point &l, const Point &r) { return l.x == r.x && l.y == r.y && l.z == r.z; };
  unordered_set<Point, decltype(point_hash), decltype(point_equal)> visited(k, point_hash, point_equal);

  // init
  pq.push({ 1, 1, 1 });
  visited.insert({ 1, 1, 1 });

  auto push = [&](const Point &p) {
    if (visited.find({ p.x, p.y, p.z }) == visited.end()) {
      pq.push({ p.x, p.y, p.z });
      auto res = visited.insert({ p.x, p.y, p.z });
      cout << "insert {" << p.x << ", " << p.y << ", " << p.z << "} " << res.second << endl;
    }
  };

  // expand and generate
  while (k-- != 1) {
    // expand
    auto p = pq.top();
    pq.pop();

    // generate
    push({ p.x + 1, p.y, p.z });
    push({ p.x, p.y + 1, p.z });
    push({ p.x, p.y, p.z + 1 });
  }

  return calc(pq.top());
}

int main() {
  kth(7);
}
...