What's the differences between set and unordered_set?


  • 1
    C

    The following is my solution for "Longest Consecutive Sequence", it got Wrong Answer.

    But when I changed the unordered_set to set in line 4, it got Accepted.

    Anyone knows why?

    class Solution {
    public:
    	int longestConsecutive(vector<int> &num) {
    		unordered_set<int> s;
    		for (auto p = num.begin(); p != num.end(); p++)
    			s.insert(*p);
    		
    		int ans = 1, pre, first = 1, cnt = 0;
    		for (auto p = s.begin(); p != s.end(); p++)
    		{
    			if (first) first = 0, cnt = 1;
    			else
    			{
    				if (*p == pre + 1) cnt++;
    				else cnt = 1;
    			}
    			pre = *p, ans = max(ans, cnt);
    		}
    		return ans;
    	}
    };

  • -1
    M

    This might be wrong, since C++ is not a language I use, but my PhD is closely related to sets, in particular the importance between them being un-ordered in real life but generally implemented as ordered in computers since it's harder to "not order" a list or collection.

    In C++ a set is modeled as a tree whereas an unordered set is modeled as a hashtable. A hashtable has a key and a value. Generally speaking these are different. You use the key as a quick way to look up the value. Importantly, the key in the unordered set is selected to be the same as the value. The iterator for unordered set seems to return each key in order, which is why your program works.

    I don't know how the iterator returns its values so I can't tell whether your program meets the O(n) complexity, but I'd be very surprised if it worse than O(n).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.