[C++]Why can't I use find()?


  • 0
    Y

    Here is my code(Accepted):

    class LRUCache{
    public:
    int num;
    int max;
    list<int> latest_key;
    unordered_map<int, int> cache;
    
    LRUCache(int capacity) {
    	num = 0;
    	max = capacity;
    }
    
    int get(int key) {
    	unordered_map<int, int>::iterator it = cache.find(key);
    	list<int>::iterator iter;
    	if (it == cache.end())
    		return -1;
    	else
    	{
    		iter = latest_key.begin();
    		while (*iter != key)
    			iter++;
    		latest_key.erase(iter);
    		latest_key.push_back(key);
    		return it->second;
    	}
    }
    
    void set(int key, int value) {
    	unordered_map<int, int>::iterator it = cache.find(key);
    	list<int>::iterator iter;
    	if (it != cache.end())
    	{
    		it->second = value;
    		iter = latest_key.begin();
    		while (*iter != key)
    			iter++;
    		latest_key.erase(iter);
    		latest_key.push_back(key);
    	}
    	else
    	{
    		if (num<max)
    		{
    			num++;
    			cache.insert(std::pair< int, int >(key, value));
    			latest_key.push_back(key);
    		}
    		else
    		{
    			int latest = latest_key.front();
    			cache.erase(latest);
    			latest_key.pop_front();
    			cache.insert(std::pair< int, int >(key, value));
    			latest_key.push_back(key);
    		}
    	}
    }
    };
    

    But if I change the code

    iter = latest_key.begin();
    while (*iter != key)
    	iter++;
    

    into:

    iter=find(latest_key.begin(),latest_key.end(),key);
    

    It will go wrong:

    Time Limit Exceeded

    Last executed input: 2048,[set(1178,3401),set(903,6060).....


  • 1
    S

    It is because 'find' takes O(n) time while both get and set should be done in O(1). Using 'while' may grant you a borderline pass, since it avoids the overhead introduced by find. Instead of a map from int to int, you may want to use a map from int to a list iterator. That way you will be able to find where the value is in the list in O(1) on average.


  • 0
    Y

    Thanks a lot. But I see the source code of std::find:
    find(_InputIterator __first, _InputIterator __last,
    const _Tp& __val, input_iterator_tag)
    {
    while (__first != __last && !(*__first == __val))
    ++__first;
    return __first;
    }
    As you can see, the time complexity is almost the same as 'while'. So, could you please tell me more details about 'find' and 'while'? Thanks!


  • 0
    S

    Time complexity-wise, yes they are the same (equally bad). However, calling a function would cost slightly more time on copying the arguments and saving the current state of the caller. The overhead may seem trivial, but could result in a pass/fail difference for the hard threshold set by Leetcode. Say the threshold is 900ms; If the 'while' version takes 896ms, and the 'find' version 915ms, then you will get a lucky pass with 'while', but it does not mean that it is the optimal solution. You should consider a O(1) solution instead.


  • 0
    Y

    Thank you so much!


Log in to reply
 

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