LFU缓存算法-简单实现

lfu-cache.cpp

/**
 * Author: Wilson Zeng
 */

#define NULL 0

class Element {
public:
	int key;
	int value;
	int visited;
	Element* prev;
	Element* next;
};

class LFUCache {
private:
	int maxSize;
	int size;
	Element* head;
public:
	LFUCache(int capacity) {
		this->maxSize = capacity;
		this->size = 0;
		this->head = NULL;
	}
	
	int get(int key) {
		//find the key
		Element* current = this->head;
		while (current) {
			if (current->key == key) {
				break;
			}
			current = current->next;
		}
		//if exists: move to head, and increase VISITED
		if (current) {
			this->moveToHead(current, true);
			return current->value;
		//if not exists: return -1
		} else {
			return -1;
		}
	}
	
	void put(int key, int value) {
		//find the key (here may record the LEAST-VISITED one's pointer for further use)
		Element* least = this->head;
		Element* current = this->head;
		while (current) {
			if (current->visited <= least->visited) {
				least = current;
			}
			if (current->key == key) { //already found
				break;
			}
			current = current->next;
		}
		//if exists: move to head, and update value
		if (current) {
			current->value = value;
			this->moveToHead(current, true);
		//if not exists (and has itrated all elements, so the `least` is the LEAST-VISITED one): 
		} else if (this->maxSize > 0) {
			//if exceeds maxSize: evict the `least`
			if (this->size >= this->maxSize) {
				this->remove(least);
			}
			//insert before head, and point head to it
			Element* ele = this->createElement(key, value);
			this->moveToHead(ele);
			this->size++;
		}
	}

	void moveToHead(Element* ele, bool touch = false) {
		if (touch) { ele->visited++; }
		if (ele != this->head) { //if it is head already, do nothing
			this->cutoff(ele);
			if (this->head) { //if head exists, then put before head, otherwise, just repoint head
				ele->next = this->head;
				this->head->prev = ele;
			}
			this->head = ele; //replace head
		}
	}

	void remove(Element* ele) {
		if (ele == this->head) { //if current removing is head, re-point this head to the next
			this->head = ele->next;
		}
		this->cutoff(ele);
		delete ele;
		this->size--;
	}
	
	void cutoff(Element* ele) {
		if (ele->prev) {
			ele->prev->next = ele->next;
		}
		if (ele->next) {
			ele->next->prev = ele->prev;
		}
		ele->prev = ele->next = NULL;
	}

	Element* createElement(int key, int value) {
		// Element* ele = (Element*) malloc(sizeof(Element));
		Element* ele = new Element();
		ele->prev = ele->next = NULL;
		ele->key = key;
		ele->value = value;
		ele->visited = 0;
		return ele;
	}
};

int main() {
	// // LFUCache* cache = new LFUCache( 2 /* capacity */ );
	// LFUCache cache(2);
	// int result;
	// cache.put(1, 1);
	// cache.put(2, 2);
	// result = cache.get(1);       // returns 1
	// cache.put(3, 3);    // evicts key 2
	// result = cache.get(2);       // returns -1 (not found)
	// result = cache.get(3);       // returns 3.
	// cache.put(4, 4);    // evicts key 1.
	// result = cache.get(1);       // returns -1 (not found)
	// result = cache.get(3);       // returns 3
	// result = cache.get(4);       // returns 4

	// LFUCache cache(0);
	// int result;
	// cache.put(0, 0);
	// result = cache.get(0);

	LFUCache cache(3);
	int result;
	cache.put(2, 2);
	cache.put(1, 1);
	result = cache.get(2);
	result = cache.get(1);
	result = cache.get(2);
	cache.put(3, 3);
	cache.put(4, 4);
	result = cache.get(3);
	result = cache.get(2);
	result = cache.get(1);
	result = cache.get(4);
	

	// result = cache.get();
	// cache.put(, );

	return 0;
}