Least Recently Used Cache Implementation can be written by using maps in C++ or Dictionaries in Python.

Normally, This algorithm is used for n way-associative caches where n is 2,4,6,8 etc.

Let me consider cache is 4 way-associative cache,

Create 4 Dictionaries of the same size Let us assume A, B, C, D

All have the same addresses.

Make one of the 4 sets(A,B,C,D) as the Least Recently Used one and replace swap the values in one of the cache

For Example:

1,2,3,4,5,6,7,8,9 - Address access pattern

Accessing 1

A-

B-

C-

D-1

Acessing 2:

A-

B-

C-1

D-2

Accessing 3:

A-

B-1

C-2

D-3

Accessing 4:

A-1

B-2

C-3

D-4

Accessing 5:(Replaces 1 -- Least Recently Used

A-2

B-3

C-4

D-5

Accessing 6:(Replaces 2 -- Least Recently Used

A - 3

B - 4

C- 5

D - 6

Accessing 7:(Replaces 3 -- Least Recently Used )

A - 4

B - 5

C - 6

D - 7

Accessing 8:(Replaces 4 -- Least Recently Used )

A - 5

B - 6

C - 7

D - 8

If we Access 5 again, Then just rearrange the tags in cache set of the same address

A - 6

B - 7

C - 8

D - 5