Различное поведение между deque и списком - PullRequest
Новая
       73

Различное поведение между deque и списком

0 голосов
/ 01 апреля 2020

Я мог бы успешно реализовать LRU-кеш, используя список и (ха sh) карту. Мне интересно, почему было неправильное поведение, когда я использовал deque вместо списка. Позвольте мне кратко объяснить мой подход.

  1. Найдите значение, используя ключ на карте. Карта возвращает итератор списка или deque, который содержит его значение.
  2. Итератор должен быть обновлен 2.1. Сотрите существующий узел с карты и списка или deque. 2.2. Pu sh новый узел в начале списка, и карта также содержит ключ и итератор нового узла в качестве значения.

Итак, мой вопрос: почему я получил неправильный результат, когда я использовал deque вместо списка? Я полагаю, что у внутренней библиотеки есть список чанков, и это создаст проблему. Но я не уверен, что причина root.

Вот воспроизводимый код. Ожидаемый результат - «9 29 9», и я мог видеть правильный ответ при использовании списка. Но неправильный результат "9 29 29" возвращается при использовании deque. 

#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

using pii = pair<int, int>;
#if 1
using List = deque<pii>;
#else
using List = list<pii>;
#endif
using ListIter = List::iterator;
using Map = unordered_map<int, ListIter>;

class LRUCache {
  size_t capacity;
  List lru_list;
  Map map;

public:
  LRUCache(size_t capacity) : capacity(capacity) {}

  void put(int key, int value) {
    Map::iterator miter = map.find(key);
    promote(key, value, miter != map.end() ? miter->second
      : (lru_list.size() == capacity) ? --lru_list.end() : lru_list.end());
  }
  int get(int key) {
    Map::iterator miter = map.find(key);
    if (miter == map.end()) return -1;
    pii v = *(miter->second);
    promote(v.first, v.second, miter->second);
    return v.second;
  }

  void promote(int key, int value, ListIter iter) {
    if (iter != lru_list.end()) lru_list.erase(iter);
    lru_list.push_front({key, value});
    map[key] = lru_list.begin();
  }
};

void run(LRUCache& cache, vvi& vv) {
  for (auto& e : vv) {
    if (e.size() > 1) cache.put(e[0], e[1]);
    else cout << cache.get(e[0]) << endl;
  }
}

void test1() {
  LRUCache cache(10);
  vvi vv {
    {10,27}, {8,10}, {6,29}, {1,9},
    {1}, {6}, {1}
  };
  run(cache, vv);
}

int main() {
  test1();

  return 0;
}

1 Ответ

0 голосов
/ 03 апреля 2020

Я не пробовал ваш код, но я предполагаю, что ваша проблема заключается в аннулировании итератора. В promote вы либо push_front, либо erase элемент из базового контейнера. Если контейнер list, никакие итераторы не будут признаны недействительными. Если контейнер deque, то некоторые из итераторов будут признаны недействительными.

CppReference содержит раздел о недействительности итератора.

...