Получение индекса элемента в очереди std :: queue по его значению - PullRequest
Новая
       16

Получение индекса элемента в очереди std :: queue по его значению

0 голосов
/ 22 января 2019

Есть ли простой способ получить позицию элемента в std::queue по его значению в C ++?

Например: 

std::queue<int> numbers;

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

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

Ответы [ 4 ]

0 голосов
/ 23 января 2019

Вы также можете получить доступ к базовому защищенному члену std::queue::c, используя следующую функцию, предложенную этими ответами : 

#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);
}

Тогда вы можете получитьИндекс элемента следующим образом.Эта функция может также применяться к другим контейнерам-адаптерам std::stack и std::priority_queue:

DEMO (C ++ 11)

ДЕМО (C ++ 14 и более) 

#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;
}
0 голосов
/ 22 января 2019

Вы можете использовать std::deque вместо: 

#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

Обратите внимание, что std::queue использует std::deque в качестве реализации по умолчанию, поэтому любые операции занимают то же время, что и в очереди.

std::deque также поддерживает произвольный доступ, поэтому names[0] вернет 7. Он также может использоваться как любая другая очередь: 

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
0 голосов
/ 22 января 2019

Альтернативным универсальным способом является определение следующего нового контейнера, который является наследованием std::queue и определяет begin() и end(), возвращающие итераторы защищенного члена std::queue::c.Затем вы можете использовать различные алгоритмы STL с этим контейнером: 

#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(); }
};

... Да, как известно, контейнеры STL не имеют виртуальных деструкторов.Уничтожение этого производного класса с помощью указателей на базовый класс вызывает неопределенное поведение.Таким образом, я хотел бы предложить использовать вышеупомянутый производный класс тогда и только тогда, когда он вам действительно нужен.1012 * 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
0 голосов
/ 22 января 2019

Если вы хотите получить индекс элемента, вам, вероятно, следует рассмотреть возможность использования контейнера std::deque вместо std::queue контейнера адаптера , как уже предлагалось в этот другой ответ .

Если вы по-прежнему хотите использовать контейнерный адаптер std::queue по какой-либо другой причине, вы должны знать, что он обеспечивает доступк базовому контейнеру через защищенный элемент данных c.

Вы можете получить из std::queue для доступа к базовому контейнеру и использовать std::find() шаблон функции для поиска элемента в этом контейнере с таким значением.Затем просто верните позицию этого элемента, используя 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);
   }
// ...
};

Если элемент не найден, индекс будет соответствовать индексу, возвращенному size()функция-член.

Если есть дубликаты, это решение на основе std::find() вернет позицию первого, то есть первого найденного элемента с запрошенным значением val.

...