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:
- Container must prevent copies to be inserted
- Container must be at least faster than
std::vector - 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