vendredi 22 mai 2015

How to store 2D geometry vectors in std::set

I've recently attended programming competition. One task was about geometry. Solution, that I invented was to use container of 2D vectors, where each vector is unique. The fastest container, which throws out copies is std::unordered_set. But I forgot how to make custom hash, so I used std::set:

struct Vector
{
    int x;
    int y;

    bool operator<(const Vector& rhs) const
    {
        return x < rhs.x && y < rhs.y;
    }
}

std::set<Vector> geometry;

Of course it is wrong. I understand why it is wrong. It was one of six tasks in competition with time limit of 2 hours. So I assume, that this task could be completed in ~20min. I can use std::vector with check for uniquenes, but tester has time limit, and it can be slow(O(n^2)).

So I have these requirments:

  1. Container must prevent copies to be inserted
  2. Container must be at least faster than std::vector
  3. Code should be simple and small enough to write and debug it in ~10 minutes

So, with all these requirments, how to store 2D vectors this way?

Aucun commentaire:

Enregistrer un commentaire