Thread: Efficient search with std::map?

  1. #1
    Registered User
    Join Date
    Aug 2006
    Posts
    43

    Question 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;
                        }
                    }
                }
            }
        }
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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));
    }
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Nov 2008
    Posts
    41
    See how the performance changes if you use a vector instead of a map

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Is std::map efficient for this problem?
    By dudeomanodude in forum C++ Programming
    Replies: 12
    Last Post: 04-10-2008, 02:15 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. More efficient: BST or Hash search??
    By aspand in forum C Programming
    Replies: 4
    Last Post: 11-19-2002, 07:42 AM