Efficient search with std::map?

I have a struct, point, which stores (x, y) coordinates. I've created a map, point_map, to hold 256 points. What I need to do is ensure that no two points are the same. The code I've written works, but it is terribly inefficient. There are two problems as I see it. First, even if no two points are equal, it takes a huge amount of time to make even the first round of comparisons. Second, if it does find a duplicate, I have it set to do the entire thing over again.

There must be a better way to do this, but I'm scratching my head trying to figure out what it is. Any help would be much appreciated.

Code:

---

#include <map>
#include <cstdlib>
#include <ctime>

struct point
{
    int x;
    int y;
};

void initialize_points(std::map<int, point> &point_map);

int main()
{
    std::srand(static_cast<int>(time(NULL)));

    std::map<int, point> point_map;
    initialize_points(point_map);

    return 0;
}

void initialize_points(std::map<int, point> &point_map)
{
    for(int index = 0; index < 256; ++index)
    {
        point_map[index].x = std::rand() % 256;
        point_map[index].y = std::rand() % 256;
    }

    bool changed(1);

    while(changed == 1)
    {
        changed = 0;
        for(int current = 0; current < 256; ++current)
        {
            for(int search = current + 1; search < 256; ++search)
            {
                while(point_map[current].x == point_map[search].x)
                {
                    if(point_map[current].y == point_map[search].y)
                    {
                        point_map[search].x = std::rand() % 256;
                        point_map[search].y = std::rand() % 256;
                        changed = 1;
                    }
                }
            }
        }
    }
}

---

If you are going to map the integers from 0 to 255 to unique point objects then perhaps you should not use a std::map. Use an array or std::vector instead. Then, repeatedly sort the array, apply std::unique, and generate objects to replace those "removed" by std::unique until the application of std::unique returns an iterator equal to the one past the end iterator of the entire range.

It may be even better to use a std::set<point> instead, perhaps by overloading operator< for point (or just using std::pair instead).

When using a map the thing that you want to be unique is the thing that is mapped from, not the thing that is mapped to. But then of course you have to consider whether there is anything you even want to map to. If not you use a set instead.

Also, In your case your x and y values only go from 0 to 255. How about using an unsigned char to store them instead of an int?

Some code for that:

Code:

---

typedef std::pair<unsigned char, unsigned char> point;
std::set<point> point_set;

while (point_set.size() < 256)
{
        point_set.insert(std::make_pair<unsigned char, unsigned char>
                (std::rand() &0xFF, std::rand() &0xFF));
}

---

See how the performance changes if you use a vector instead of a map