Хэш-список с STL - Могу ли я указать элемент в списке STL на другой элемент?

Question

Допустим, у меня есть:

std::vector<std::list<Node> >

И скажем, Node:

class Node { 
    Node* next;
    int data;
};

Векторные ячейки соответствуют значениям хэш-функции для быстрого поиска. Идея состоит в том, что вы вставляете свои элементы в вектор, но по-прежнему объединяете их вместе с элементом Node-> next. Таким образом, у вас есть список, в котором можно эффективно искать элементы по ключу с помощью хэш-функции, чтобы найти правильную векторную ячейку, с которой нужно начинать.

Во всяком случае, все это в стороне. Мой вопрос:

Могу ли я, чтобы мои указатели Node :: next указывали на другие узлы в списке (будь то один или другой из другой векторной ячейки) без проблем? Я не был уверен, позволит ли реализация стандартной библиотеки списка. Кажется, у меня проблемы (мой код здесь недоступен), и я хотел посмотреть, может ли это быть причиной.

Answer 1

Если вы хотите, чтобы он указывал на другие узлы в списке, это вполне выполнимо, да. Тем не менее, я бы предложил другой дизайн: std::list<int> и std::unordered_map<int, std::list<int>::iterator>, оба члена класса, единственная цель которого - синхронизировать два контейнера. Это должно быть проще, безопаснее и быстрее, чем (моя интерпретация) ваш текущий план.

Добавление и удаление объектов в обоих списках очень просто:

std::unordered_map<int, std::list<int>::iterator> fast;
std::list<int> linked;

void add(int data) {
    fast[data] = linked.insert(linked.end(), data);
};
std::list<int>::iterator erase(std::list<int>::iterator iter) {
    fast.erase(*iter);
    return linked.erase(iter);        
}

Answer 2

Списки STL дважды связаны и имеют частные предыдущий и следующий указатели. Следующий указатель в вашем элементе не будет связан со следующим указателем списка, поэтому он может быть чем угодно. Вам придется управлять этим самостоятельно. Похоже, что вы реализуете хеш со связанным списком для коллизий хешей (говорит Clippy). Вы смотрели на контейнер карты?