How to store unique values (pointers)

[Nico]

Hello,

I am looking for a way to create a list of pointers to make a que. I am looking for something with the following properties:
- if a pointer is already in the list it should not be added again (every value should be unique)
- it is possible to get the pointer at the front of the list (this may remove the pointer from the list)
- it is possible to remove the pointer at the front of the list (not required if this was already a result of getting that pointer)
- it is possible to add any number of new pointers at the end of the list
- the pointers remain in the order in which they were inserted

A std::deque allows to add at the end and pull from the front, but you can add duplicate values in it.
A std::map allows to reject duplicate keys, but it also sorts based on the key so the order would get mixed up.

Does anyone know other alternatives that could be recommended for this situation?

[doug4]

One option is, use a std::deque, but before you insert, traverse the deque to see if there is a duplicate.

If the traversal of the deque is too expensive, you could have 2 data structures--a std::queue of the pointers and a std::set (or std::map or std::unordered_set/map) of the pointers to check for duplicates. Do your lookups in the set/map, but do your pops from the queue. Whenever you add to or remove from the queue, do the same to the set/map.

[Nico]

Thank you, I ended up with this class and it seems to work fine.

#ifndef MYQUE_H
#define MYQUE_H

#include <mutex>                                // std::mutex, std::unique_lock
#include <deque>                                // std:: deque<T>
#include <set>                                  // std::set<T>

/** \brief A que that preserves the order in which objects are added, but rejects duplicates */

template<class T>
class MyQue
{
    public:
        MyQue() {}
        virtual ~MyQue() {}
        void push_back(T data)
        {
            std::unique_lock<std::mutex> locker(addDataMutex);  // only 1 thread at a time can be allowed
            auto ret = duplicateCheck.insert(data);
            if (ret.second==true) orderedQue.push_back(data);
        }

        T front()
        {
            std::unique_lock<std::mutex> locker(useDataMutex);  // only one thread at a time can be allowed
            T temp = orderedQue.front();
            orderedQue.pop_front();
            duplicateCheck.erase(temp);
            return temp;
        }

//        void pop_front()
//        {
//            // no op, because we already delete the pointer in the front() call.
//            // only added this function to ensure that I can use the same interface as when I used a reqular deque during testing
//        }

        size_t size()
        {
            std::unique_lock<std::mutex> locker(addDataMutex);
            return orderedQue.size();
        }

    protected:
    private:
        std::deque<T>               orderedQue;
        std::set<T>                 duplicateCheck;
        std::mutex                  addDataMutex;
        std::mutex                  useDataMutex;
};

#endif // MYQUE_H 

[doug4]

// only added this function to ensure that I can use the same interface as when I used a reqular deque

This is a false statement. You have the same interface functions, but they don't do the same things. If you really want to have the same interface, then front() should be only lines 25, 26 and 29, but pop_front should be lines 25, 27 and 28.

The front() function on a queue/deque allows the user to look at the first node as many times as needed. When the first node is no longer needed, the user pops it off.

There are some variants of queues where the pop function returns the value that was popped off of the front. Your front() function does that, but the function name confuses the user as to what the function does.

[Nico]

You are right, I should have cleaned that up when I was done with my testing.