C ++: структура данных «уникальный вектор» - PullRequest
Новая
       11

C ++: структура данных «уникальный вектор»

0 голосов
/ 12 февраля 2019

Мне нужна структура данных, такая как std :: vector или std :: list, элементы которой будут уникальными.В большинстве случаев я буду вызывать push_back, иногда, возможно, стереть.Когда я вставляю элемент, который уже существует, мне нужно получить уведомление либо по логическому, либо по исключению.

И самое важное свойство, которое оно должно иметь: порядок вставок.Каждый раз, когда я перебираю его, он должен возвращать элементы в том порядке, в котором они были вставлены.

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

Какая структура данных лучше всего подходит для моих нужд?

Ответы [ 4 ]

0 голосов
/ 12 февраля 2019

Вы можете использовать Boost.MultiIndex для этого:

Live On Coliru 

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>

using namespace boost::multi_index;

template<typename T>
using unique_list=multi_index_container<
 T,
 indexed_by<
   sequenced<>,
   hashed_unique<identity<T>>
 >
>;

#include <iostream>

int main()
{
  unique_list<int> l;

  auto print=[&](){
    const char* comma="";
    for(const auto& x:l){
      std::cout<<comma<<x;
      comma=",";
    }
    std::cout<<"\n";
  };

  l.push_back(0);
  l.push_back(1);
  l.push_back(2);
  l.push_back(0);
  l.push_back(2);
  l.push_back(4);

  print();
}

Выход 

0,1,2,4
0 голосов
/ 12 февраля 2019

Используйте структуру с обычным std :: vector и std :: set.

Когда вы нажимаете, проверяйте набор на наличие элемента.Когда вам нужно выполнить итерацию, выполните итерацию по вектору.Если вам нужно стереть из вектора, а также стереть из набора.

В основном, используйте набор как запас, только для быстрой проверки «наличия элемента». 

// either make your class a template or use a fixed type of element
class unique_vector
{
    public:
        // implement the various operator you need like operator[]
        // alternatively, consider inheriting from std::vector
    private:
        std::set<T> m_set; // fast lookup for existence of elements
        std::vector<T> m_vector; // vector of elements
};
0 голосов
/ 12 февраля 2019

Я бы предпочел использовать std :: unordered_set для хранения существующих элементов в std :: vector, и он имеет более быстрое время поиска O (1), тогда как время поиска std :: set равно O (logn).

0 голосов
/ 12 февраля 2019

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

. Будет возвращена пара pair<iterator,bool> при вызове метода insert.Значение bool в паре ложно, если элемент уже существует в наборе (в этом случае элемент не будет добавлен).

...