Доступ к последнему элементу unordered_set в C ++ - PullRequest
Новая
       85

Доступ к последнему элементу unordered_set в C ++

1 голос
/ 28 апреля 2020

Я создал unordered_set с [2,3,5] и хочу получить доступ в порядке FIFO, как это возможно с unordered_set, попытался сделать это, но получил ошибку компиляции. 

int showFirstUnique() {
    if(unique.empty())
        return -1;
    else{
        unordered_set<int> :: iterator itr=unique.end();
        itr--;
        return *itr;
   }
}

Ответы [ 4 ]

3 голосов
/ 28 апреля 2020

Доступ к последнему элементу unordered_set в C ++

Вы можете получить доступ к последнему элементу неупорядоченных ассоциативных контейнеров так же, как и к последнему элементу списка пересылки: путем итерации элементов пока вы не достигнете его.

Асимптотика c Сложность выполнения этого, конечно, линейна, и это не то, что обычно делают с неупорядоченным контейнером. 

itr--;

Это не работает, потому что неупорядоченные контейнерные итераторы являются прямыми итераторами. Они не могут быть повторены в обратном направлении.

Я хочу получить доступ в порядке FIFO

Элементы неупорядоченных контейнеров не сохраняются в порядке FIFO. Последний элемент такого контейнера не имеет ничего общего с порядком, в котором эти элементы были вставлены.

Вместо этого можно использовать, например, std::queue, чтобы получить заказ FIFO.

1 голос
/ 28 апреля 2020

Вы можете использовать boost::multi_index, чтобы иметь неупорядоченный поиск и последовательность вставки. 

template<typename T>
using fifo_set = boost::multi_index_container<T, 
  boost::multi_index::indexed_by<
    boost::multi_index::random_access<>,
    boost::multi_index::unordered_unique<boost::multi_index::identity<T>>
  >>;
0 голосов
/ 28 апреля 2020

Спасибо всем.

Я понял, что неупорядоченный набор не работает упорядоченным образом и, следовательно, реализовал то же самое с помощью очереди. Полное решение выглядит так, эта проблема была на самом деле У вас есть очередь целых чисел, вам нужно получить первое уникальное целое число в очереди. 

class FirstUnique {
public:
    queue<int> q;
    map<int,int> mp;
public:
    FirstUnique(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            add(nums[i]);
        }
    }

    int showFirstUnique() {
        while(!q.empty()){
            int f=q.front();
            if (mp[f]==1)
                return f;
            q.pop();
        }
        return -1;
    }

    void add(int value) {
        if(mp.find(value)!=mp.end())
            mp[value]++;
        else{
            mp.insert(pair<int, int>(value,1));
            q.push(value);
        }
    }

};
0 голосов
/ 28 апреля 2020

Если я правильно понимаю ваш вопрос, вы можете получить только уникальные элементы в исходном порядке, используя две переменные - выходной контейнер (здесь std::queue) и помощник std::(unordered_)set

std::vector<int> input {3, 6, 3, 2, 0, 2, 6};
std::queue<int> fifo;
std::unordered_set<int> helper;

for (int i: input) {
    auto [_, wasInserted] = helper.insert(i); //C++17
    if (wasInserted) {
        fifo.push(i);
    }
}

while (!fifo.empty()) {
    std::cout << fifo.front() << " ";
    fifo.pop();
}

//output 3 6 2 0

Вы можно использовать любой другой контейнер вместо std::queue - std::vector будет работать так же хорошо. std::queue говорит читателю «этот контейнер предназначен для использования в режиме FIFO», что вы можете или не хотите.

...