Очередь с уникальными записями в С++
Мне нужно реализовать очередь, содержащую уникальные записи (без дубликатов) на C или С++. Я думаю о поддержании ссылки на элементы, уже доступные в очереди, но это кажется очень неэффективным.
Пожалуйста, дайте мне знать ваши предложения, чтобы решить эту проблему.
Ответы
Ответ 1
Как насчет дополнительной структуры данных для отслеживания уникальности:
std::queue<Foo> q;
std::set<std::reference_wrapper<Foo>> s;
// to add:
void add(Foo const & x)
{
if (s.find(x) == s.end())
{
q.push_back(x);
s.insert(std::ref(q.back())); // or "s.emplace(q.back());"
}
}
Или, наоборот, измените роли очереди и набора:
std::set<Foo> s;
std::queue<std::reference_wrapper<Foo>> q;
void add(Foo const & x)
{
auto p = s.insert(x); // std::pair<std::set<Foo>::iterator, bool>
if (s.second)
{
q.push_back(std::ref(*s.first)); // or "q.emplace_back(*s.first);"
}
}
Ответ 2
очереди:
- используйте std:: set для поддержки набора уникальных элементов
- добавить любой элемент, который вы могли бы добавить в std:: set в std:: queue
освобождение пакета из очереди:
- удалить элемент из std:: queue и std:: set
Ответ 3
std::queue
является адаптером контейнера и использует относительно мало членов базового Container
. Вы можете легко реализовать пользовательский контейнер, содержащий оба: a unordered_map
из reference_wrapper<T>
и a deque<T>
. Ему нужны хотя бы члены front
и push_back
. Проверьте внутри hash_map
, когда push_back
вашего контейнера вызывается и соответственно отклоняется (возможно, выбрасывает). Чтобы привести полный пример:
#include <iostream>
#include <set>
#include <deque>
#include <queue>
#include <unordered_set>
#include <functional>
namespace std {
// partial specialization for reference_wrapper
// is this really necessary?
template<typename T>
class hash<std::reference_wrapper<T>> {
public:
std::size_t operator()(std::reference_wrapper<T> x) const
{ return std::hash<T>()(x.get()); }
};
}
template <typename T>
class my_container {
// important: this really needs to be a deque and only front
// insertion/deletion is allowed to not get dangling references
typedef std::deque<T> storage;
typedef std::reference_wrapper<const T> c_ref_w;
typedef std::reference_wrapper<T> ref_w;
public:
typedef typename storage::value_type value_type;
typedef typename storage::reference reference;
typedef typename storage::const_reference const_reference;
typedef typename storage::size_type size_type;
// no move semantics
void push_back(const T& t) {
auto it = lookup_.find(std::cref(t));
if(it != end(lookup_)) {
// is already inserted report error
return;
}
store_.push_back(t);
// this is important to not have dangling references
lookup_.insert(store_.back());
}
// trivial functions
bool empty() const { return store_.empty(); }
const T& front() const { return store_.front(); }
T& front() { return store_.front(); }
void pop_front() { lookup_.erase(store_.front()); store_.pop_front(); }
private:
// look-up mechanism
std::unordered_set<c_ref_w> lookup_;
// underlying storage
storage store_;
};
int main()
{
// reference wrapper for int ends up being silly
// but good for larger objects
std::queue<int, my_container<int>> q;
q.push(2);
q.push(3);
q.push(2);
q.push(4);
while(!q.empty()) {
std::cout << q.front() << std::endl;
q.pop();
}
return 0;
}
EDIT:. Вы хотите сделать my_container
подходящую модель контейнера (возможно, также распределители), но это еще один полный вопрос. Благодаря Кристиану Рау за указание ошибок.
Ответ 4
Существует один очень важный момент, о котором вы не упоминали в своем вопросе, и это то, что ваша очередь элементов отсортирована или имеет какой-то порядок (называемый a очередь приоритетов) или несортированный (называемый простым FIFO). Решение, которое вы выберете, будет зависеть только от ответа на этот вопрос.
-
Если ваша очередь не сортирована, то сохранение дополнительной структуры данных в дополнение к вашей очереди будет более эффективным. Использование второй структуры, которая каким-то образом упорядочена для хранения содержимого вашей очереди, позволит вам проверить, существует ли элемент в вашей очереди или не намного быстрее, чем сканирование самой очереди. Добавление в конец несортированной очереди занимает постоянное время и может быть выполнено очень эффективно.
-
Если ваша очередь должна быть отсортирована, то размещение объекта в очереди требует, чтобы вы знали позицию position в очереди, что требует, чтобы очередь проверялась в любом случае. Как только вы знаете позицию позиции, вы знаете, является ли элемент дублирующимся, потому что если он дублирует, то элемент уже будет существовать в этой позиции в очереди. В этом случае вся работа может выполняться оптимально в самой очереди и не требует никакой дополнительной структуры данных.
Выбор структур данных зависит от вас. Однако для (1) вторичная структура данных не должна быть никаким списком или массивом, в противном случае будет более неэффективно сканировать ваш вторичный индекс, чтобы сканировать исходную очередь.