Getting index of an element in a std::queue by its value

Question

Is there a simple way to get the position of an element in a std::queue by its value in C++?

For example:

std::queue<int> numbers;

numbers.push(7);
numners.push(4);
numbers.push(11);

int position = numbers.getPosition(4); //should be 1

Answer 1

If you want to get the index of an element you should probably consider using an std::deque container instead of a std::queue container adapter, as already suggested in this other answer.

---

If you still want to stick to to the std::queue container adapter for some other reason, you should know that it does provide access to the underlying container through the protected data member c.

You could derive from std::queue in order to access the underlying container and use the std::find() function template for finding an element in that container with such a value. Then, simply return the position of that element by using std::distance().

#include <algorithm>
#include <queue>

template<typename T>
class Queue: std::queue<T> {
public:
   auto getPosition(const T& val) const {
      auto it = std::find(this->c.begin(), this->c.end(), val);
      return std::distance(this->c.begin(), it);
   }
// ...
};

If the element is not found, the index will correspond to the one returned by the size() member function.

If there are duplicates, this solution based on std::find() will return the position of the first one, i.e., the first element found with the requested value val.

Answer 2

You can use std::deque instead:

#include <algorithm>

std::deque<int> names;

names.push_back(7);
names.push_back(4);
names.push_back(11);

auto it = std::find(names.begin(), names.end(), 4);
if(it != names.end())
    int distance = it - names.begin();
else
    //no element found

Note that std::queue uses std::deque as default implementation, so any operations take the same time as in queue.

std::deque also supports random access, so names[0] will return 7. It can also be used like any other queue:

std::deque<int> myDeque{};
myDeque.push_back(5);
myDeque.push_back(13);
std::cout << myDeque.front(); //5
myDeque.pop_front();
std::cout << myDeque.front(); //13

Answer 3

An alternative generic way is defining the following new container which is an inheritance of std::queue and defines begin() and end() returning iterators of the protected member std::queue::c. Then you can use various STL algorithms with this container:

#include <queue>

template<
    class T,
    class Container = std::deque<T>
>
class Queue : public std::queue<T, Container>
{
public:
    using iterator               = typename Container::iterator;
    using const_iterator         = typename Container::const_iterator;
    using reverse_iterator       = typename Container::reverse_iterator;
    using const_reverse_iterator = typename Container::const_reverse_iterator;

    iterator        begin()       noexcept { return this->c. begin(); }
    const_iterator  begin() const noexcept { return this->c.cbegin(); }
    const_iterator cbegin() const noexcept { return this->c.cbegin(); }

    iterator        end()       noexcept { return this->c. end(); }
    const_iterator  end() const noexcept { return this->c.cend(); }
    const_iterator cend() const noexcept { return this->c.cend(); }

    reverse_iterator        rbegin()       noexcept  { return this->c. rbegin(); }
    const_reverse_iterator  rbegin() const noexcept  { return this->c.crbegin(); }
    const_reverse_iterator crbegin() const noexcept  { return this->c.crbegin(); }

    reverse_iterator        rend()       noexcept  { return this->c. rend(); }
    const_reverse_iterator  rend() const noexcept  { return this->c.crend(); }
    const_reverse_iterator crend() const noexcept  { return this->c.crend(); }
};

...Yes, as it is well known, STL containers have no virtual destructors. The destruction of this derived class through the base class pointers causes undefined behavior. Thus I would suggest using the above derived class if and only if you really need it.

---

For the current position problem, you can find the position where the first element found as follows:

DEMO

#include <algorithm>
#include <iterator>

Queue<int> q;
q.push(7);
q.push(4);
q.push(11);

const auto it = std::find(q.cbegin(), q.cend(), 4);
const auto position = std::distance(q.cbegin(), it); //should be 1

Answer 4

You can also access to the underlying protected member std::queue::c using the following function proposed by these answers:

#include <queue>

template <class ADAPTER>
const auto& get_container(ADAPTER& a)
{
    struct hack : private ADAPTER {
        static auto& get(ADAPTER& a) {
            return a.*(&hack::c);
        }
    };

    return hack::get(a);
}

Then you can get the index of an element as follows. This function can be also applied to other container adapters, std::stack and std::priority_queue:

DEMO(C++11)

DEMO(C++14 and over)

#include <iostream>
#include <algorithm>
#include <iterator>

int main()
{
    std::queue<int> q;
    q.push(7);
    q.push(4);
    q.push(11);

    auto& c = get_container(q);

    const auto it = std::find(c.cbegin(), c.cend(), 4);
    const auto position = std::distance(c.cbegin(), it);
    std::cout << "Position is " << position << "." <<std::endl;

    return 0;
}