CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    Apr 2010
    Posts
    1

    Lightbulb Suggest a good method with least lookup time complexity

    I have a structure which has 3 identifier fields and one value field. I have a list of these objects. To give an analogy, the identifier fields are like the primary keys to the object. These 3 fields uniquely identify an object.

    Class
    {
    int a1;
    int a2;
    int a3;
    int value;
    };

    I would be having a list of say 1000 object of this datatype. I need to check for specific values of these identity key values by passing values of a1, a2 and a3 to a lookup function which would check if any object with those specific values of a1, a2 and a3 is present and returns that value. What is the most effective way to implement this to achieve a best lookup time?

    One solution I could think of is to have a 3 dimensional matrix of length say 1000 and populate the value in it. This has a lookup time of O(1). But the disadvantages are. 1. I need to know the length of array. 2. For higher identity fields (say 20), then I will need a 20 dimension matrix which would be an overkill on the memory. For my actual implementation, I have 23 identity fields.

    Can you suggest a good way to store this data which would give me the best look up time?

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Suggest a good method with least lookup time complexity

    Quote Originally Posted by amrish_deep View Post
    Can you suggest a good way to store this data which would give me the best look up time?
    Use a hash table (sometimes called an associate array).

    In C++ hash based containers will be introduced in the upcoming standard but most compilers already support them. Check out std::tr1::unordered_set.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured