Можно ли удалить элемент очереди по значению? - PullRequest
Новая
       22

Можно ли удалить элемент очереди по значению?

6 голосов
/ 09 октября 2011

Я хочу удалить элемент из очереди с определенным значением. Как это сделать? (Я пытаюсь создать одновременную смесь карты и очереди, и в настоящее время я пытаюсь реализовать на этот ответ )

Так что у меня сейчас такой код: 

#ifndef CONCURRENT_QUEUED_MAP_H
#define CONCURRENT_QUEUED_MAP_H

#include <map>
#include <deque>
#include <boost/thread.hpp>
#include <boost/thread/locks.hpp>

template <class map_t_1, class map_t_2>
class concurrent_queued_map
{
private:
    std::map<map_t_1, map_t_2> _ds;
    std::deque<map_t_1> _queue;
    mutable boost::mutex mut_;
public:
    concurrent_queued_map() {}

    map_t_2 get(map_t_1 key) {
        boost::mutex::scoped_lock lock(mut_);
        return _ds[key];
    }

    map_t_1 put(map_t_1 key, map_t_2 value) {
        boost::mutex::scoped_lock lock(mut_);
        _ds.insert(std::pair<map_t_1, map_t_2>(key,value));
        _queue.push_back(key);
        return key;
    }

    map_t_2 get_last(map_t_1 key) {
        boost::mutex::scoped_lock lock(mut_);
        const map_t_1 k = _queue.front();
        return _ds[k];
    }

    void remove_last(map_t_1 key) {
        boost::mutex::scoped_lock lock(mut_);
        const map_t_1 k = _queue.front();
        _ds.erase(k);
        _queue.pop_front();
    }

    void remove(map_t_1 key) {
        boost::mutex::scoped_lock lock(mut_);
        _queue.erase(std::remove(_queue.begin(), _queue.end(), key), _queue.end());
        _ds.erase(k);
    }

    int size() {
        boost::mutex::scoped_lock lock(mut_);
        return _ds.size();
    }

};

#endif // CONCURRENT_QUEUED_MAP_H

Так что мне делать? Как убрать из очереди по значению? Или есть какой-либо компонент STL или Boost, который похож на очередь? То есть он будет иметь .front(), pop_front(); и push_back(key);, а также будет поддерживать поиск и стирание по значению?

Ответы [ 2 ]

19 голосов
/ 09 октября 2011

Deque - это контейнер последовательности, поэтому вы можете удалять элементы только по значению , что лучше всего делать с помощью идиомы удаления / стирания: 

std::deque<T> q;
T val;

q.erase(std::remove(q.begin(), q.end(), val), q.end());

Если вы используетеstd::queue, то вы вообще не сможете этого сделать, поскольку адаптер предоставляет только интерфейс front / back и не предназначен для семантики итерации или поиска.

Если вы решите реализовать свою очередьв качестве std::list, затем используйте функцию-член remove().

2 голосов
/ 09 октября 2011

Сделайте так: и очередь, и карта удаляют преимущества использования любого из них и сохраняют недостатки обоих (по крайней мере, с точки зрения производительности). Я бы просто использовал deque<std::pair<map_t_1, map_t_2> > для представления карты и deque. Тогда поиск или редактирование карты требует просмотра всей deque, так что это не очень эффективно.

Более эффективное решение будет труднее достичь, так как вы пытаетесь справиться с двумя различными схемами индексации - по ключу (карта) и по индексу (требуется при заказе природы od deque). Чтобы сделать это эффективно, я бы предложил самореализованный двойной связанный список (как очередь) с картой ключей для записей связанного списка. Записи двойного связанного списка также будут содержать ключ для поиска на карте при добавлении / добавлении очереди.

...