Detailed explanation of the usage scenarios of list in C++

template <class T>
struct __list_node {
    __list_node* prev;
    __list_node* next;
    T data;
};

// High frequency insertion and deletion examplestd::list<Order> order_book;

// Insert new order (O(1))auto it = order_book.begin();
std::advance(it, 100);  // Position to the 100th positionorder_book.insert(it, new_order);

// Delete specific orders (O(1))order_book.erase(found_order);

std::list<Player> game_players;
auto player_it = game_players.begin();

// The original iterator is still valid even if the element is inserted/deleted in another locationgame_players.push_back(Player());  // Does not affect player_itgame_players.pop_front();          // Does not affect player_it
// Unless the element pointed to by the iterator is deletedplayer_it = game_players.erase(player_it);  // Return to the next valid iterator

class LargeObject {
    char data[1024*1024]; // 1MB data    // ...Other members};

std::list<LargeObject> big_data_store;

// Insert will not cause element movement (vector will cause reallocation and copying)big_data_store.push_back(LargeObject());

std::list<int> list1 = {1, 3, 5};
std::list<int> list2 = {2, 4, 6};

// Merge two ordered lists(list2);  // list1 becomes {1,2,3,4,5,6}, list2 is empty
// Transfer elementsstd::list<int> list3 = {10, 20};
auto it = ();
std::advance(it, 2);
(it, list3);  // list1: {1,2,10,20,3,4,5,6}

// Continuous access to list elements (poor performance)std::list<int> nums(1000000);
int sum = 0;
for (int n : nums) {  // cache miss can be cache every time you visit    sum += n;
}

// Under 64-bit systemsizeof(std::list<int>::node) == 
    sizeof(int) + 2*sizeof(void*) = 4 + 16 = 20byte（Usually aligned to24byte）

// Store 1 million ints:vectorMemory：~4MB
listMemory：~24MB

#include <iostream>
#include <list>
#include <vector>
#include <chrono>

const int SIZE = 1000000;

void test_list_traversal() {
    std::list<int> lst(SIZE, 1);
    
    auto start = std::chrono::high_resolution_clock::now();
    long sum = 0;
    for (auto n : lst) sum += n;
    auto end = std::chrono::high_resolution_clock::now();
    
    std::cout << "list traversal: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count() 
              << "ms\n";
}

void test_vector_traversal() {
    std::vector<int> vec(SIZE, 1);
    
    auto start = std::chrono::high_resolution_clock::now();
    long sum = 0;
    for (auto n : vec) sum += n;
    auto end = std::chrono::high_resolution_clock::now();
    
    std::cout << "vector traversal: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count() 
              << "ms\n";
}

int main() {
    test_list_traversal();
    test_vector_traversal();
    return 0;
}

list traversal: 12ms
vector traversal: 2ms

template <typename K, typename V>
class LRUCache {
    std::list<std::pair<K, V>> items;
    std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> key_map;
    size_t capacity;
    
public:
    LRUCache(size_t cap) : capacity(cap) {}
    
    void put(const K& key, const V& value) {
        auto it = key_map.find(key);
        if (it != key_map.end()) {
            (it->second);
            key_map.erase(it);
        }
        
        items.push_front({key, value});
        key_map[key] = ();
        
        if (() > capacity) {
            key_map.erase(().first);
            items.pop_back();
        }
    }
    
    bool get(const K& key, V& value) {
        auto it = key_map.find(key);
        if (it == key_map.end()) return false;
        
        ((), items, it->second);
        value = it->second->second;
        return true;
    }
};

class Process {
    int pid;
    int remaining_time;
    // ...Other attributes};

class Scheduler {
    std::array<std::list<Process>, 5> queues; // 5 priority queues    
public:
    void add_process(Process&& p, int priority) {
        queues[priority].push_back(std::move(p));
    }
    
    void schedule() {
        for (auto& queue : queues) {
            if (!()) {
                auto& process = ();
                // Execute a time slice                process.remaining_time--;
                
                if (process.remaining_time <= 0) {
                    queue.pop_front(); // Finish                } else if (&queue != &()) {
                    // Downgrade to the next priority                    queues[&queue - &queues[0] + 1].splice(
                        queues[&queue - &queues[0] + 1].end(),
                        queue, ());
                }
                break;
            }
        }
    }
};

std::list<int> lst = {1, 2, 3};
// Error: list does not support operator[]// int x = lst[1];  

// The correct way to do itauto it = ();
std::advance(it, 1);  // O(n) operationint x = *it;

// Storing small elements is extremely unpaidstd::list<char> char_list;  // Each char consumes 24+ bytes (64-bit system)

std::list<std::string> names;
// O(n) lookup - poor performanceauto it = std::find((), (), "Alice");

// Large object + frequent insertion and deletionstd::list<Matrix> matrix_pool;
// Small object + frequent traversalstd::vector<int> counters;

std::list<ExpensiveObject> obj_list;
obj_list.emplace_back(args...);  // Directly construct to avoid copy/move

template <typename T>
class PoolAllocator { /*...*/ };

std::list<int, PoolAllocator<int>> pooled_list;

#include <memory_resource>
std::pmr::list<int> pmr_list{std::pmr::monotonic_buffer_resource()};