力扣146. LRU缓存机制

力扣题库146题，需要时间复杂度是O(1)，c++实现

用双向链表保存数据

struct dataStru
{
	int key;
	int value;
	struct dataStru* prev;
	struct dataStru* next;

	dataStru(int k, int v)
		: key(k), value(v), prev(nullptr), next(nullptr)
	{
		std::cout << "data ctor: " << key << "," << value << std::endl;
	}

	~dataStru()
	{
		std::cout << "data dtor: " << key << "," << value << std::endl;
	}
};
           

实现基本的get，put函数，用unordered_map保证时间复杂度

class LRUCache
{
public:
	LRUCache(int capacity)
		: capacity_(capacity), head_(nullptr), tail_(nullptr)
	{
	}

	~LRUCache()
	{
		clear();
		cache_.clear();
	}

	int get(int key)
	{
		auto it = cache_.find(key);
		if (it == cache_.end())
		{
			return -1;
		}

		refresh(it->second);
		return it->second->value;
	}

	void put(int key, int value)
	{
		auto it = cache_.find(key);
		if (it != cache_.end())
		{
			it->second->value = value;
			refresh(it->second);
			return;
		}

		if (cache_.size() >= capacity_)
		{
			removeHead();
		}

		put(new struct dataStru(key, value));
	}

private:
	void refresh(struct dataStru* pd)
	{
		if (pd == tail_)
		{
			return;
		}

		if (pd == head_)
		{
			head_ = pd->next;
			head_->prev = nullptr;
		}
		else
		{
			pd->prev->next = pd->next;
			pd->next->prev = pd->prev;
		}

		tail_->next = pd;
		pd->prev = tail_;
		pd->next = nullptr;
		tail_ = pd;
	}

	void put(struct dataStru* pd)
	{
		if (!head_)
		{
			head_ = pd;
			tail_ = pd;
		}
		else
		{
			tail_->next = pd;
			pd->prev = tail_;
			tail_ = pd;
		}
		cache_[pd->key] = pd;
	}

	void removeHead()
	{
		struct dataStru* pd = head_;
		head_ = pd->next;
		if (head_) 
			head_->prev = nullptr;
		if (tail_ == pd)
			tail_ = nullptr;

		removeOne(pd);
	}

	inline void removeOne(struct dataStru* pd)
	{
		removeFromCache(pd->key);
		delete pd;
	}

	inline void removeFromCache(int key)
	{
		cache_.erase(key);
	}

	void clear()
	{
		while (head_)
		{
			struct dataStru* pd = head_;
			head_ = pd->next;
			removeOne(pd);
		}
	}

	void printCache()
	{
		std::cout << "cache:";
		struct dataStru* pd = head_;
		while (pd)
		{
			std::cout << " " << pd->value;
			pd = pd->next;
		}::
		std::cout << std::endl;
	}

private:
	std::unordered_map<int, struct dataStru*> cache_;
	struct dataStru* head_;
	struct dataStru* tail_;
	int capacity_;
};
           

简单测试：

创建LRUCache，capacity是1

put(2, 1)

get(2) // 值是1

put(3,2) // (2,1) 被删除

get(2) // (2,1)已经被删除，所以返回-1

get(3) // 值是2

int main()
{
	LRUCache lru(1);
	lru.put(2, 1);
	std::cout << lru.get(2) << std::endl;
	lru.put(3, 2);
	std::cout << lru.get(2) << std::endl;
	std::cout << lru.get(3) << std::endl;
}