Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d9/d65/lfu__cache_8cpp.html below:

TheAlgorithms/C++: others/lfu_cache.cpp File Reference

Implementation for [LFU Cache] (https://en.wikipedia.org/wiki/Least_frequently_used) More...

#include <cassert>
#include <iostream>
#include <unordered_map>

Go to the source code of this file.

Implementation for [LFU Cache] (https://en.wikipedia.org/wiki/Least_frequently_used)

LFU discards the least frequently used value. if there are multiple items with the same minimum frequency then, the least recently used among them is discarded. Data structures used - doubly linked list and unordered_map(hash map).

Hashmap maps the key to the address of the node of the linked list and its current usage frequency. If the element is accessed the element is removed from the linked list of the current frequency and added to the linked list of incremented frequency.

When the cache is full, the last element in the minimum frequency linked list is popped.

Definition in file lfu_cache.cpp.

main function

Returns

0 on exit

Definition at line 301 of file lfu_cache.cpp.

301 {

303 return 0;

304}

static void test()

self test implementation

self test implementation

Returns

void

Definition at line 250 of file lfu_cache.cpp.

250 {

252

253

254 assert(cache.size() == 0);

255 assert(cache.capacity() == 5);

256 assert(cache.empty());

257

258

259 cache.put(1, 10);

260 cache.put(-2, 20);

261

262

263 assert(cache.size() == 2);

264 assert(cache.capacity() == 5);

265 assert(!cache.empty());

266

267

268 assert(cache.get(1) == 10);

269 assert(cache.get(-2) == 20);

270

271 cache.put(-3, -30);

272 cache.put(4, 40);

273 cache.put(5, -50);

274 cache.put(6, 60);

275

276

277 assert(cache.size() == 5);

278 assert(cache.capacity() == 5);

279 assert(!cache.empty());

280

281

282 assert(cache.get(1) == 10);

283 assert(cache.get(-2) == 20);

284

285

286

287

288

289

290 assert(cache.get(4) == 40);

291 assert(cache.get(5) == -50);

292 assert(cache.get(6) == 60);

293

294 std::cout << "test - passed\n";

295}

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4