Shrey
Shrey

Reputation: 2414

C++ container set + array functionality

Which is the best container in C++ which can -

I basically need to to iterate in phase one and collect all the unique elements, order really doesn't matter.

However, in phase two, I then have to provide each element in the container, but can only provide it one by one. Since caller can know the size of my container, it provides me index one by one, such that 0 < idx < size of the container.

Right now, the only solution that comes to my mind is two maintain two containers vector and set, I am wondering is there any container that provides the same?

class MyContainer{
  private:
   std::set<Fruits> setFruits;
   std::vector<Fruits> arrFruits; // can have indexed access

  public:
    void collectFruits(const Fruits& fruit){
       if(setFruits.find(fruit) == setFruits.end()){ 
       // insert only if it doens't contains
          setFruits.insert(fruit);
          arrFruits.push_back(fruit);
       }
     }
 };

Upvotes: 3

Views: 145

Answers (2)

Chris Drew
Chris Drew

Reputation: 15334

You could use a boost flat_set.

I don't think it provides an operator[] but it has random access iterators and has a constant time nth() function that returns an iterator with a particular index.

Inserting may invalidate iterators but providing you do all insertions in phase 1 and then all index access in phase 2 you should be ok.

Upvotes: 2

Barry
Barry

Reputation: 304122

Alex Stepanov, the creator of STL, once said "Use vectors whenever you can. If you cannot use vectors, redesign your solution so that you can use vectors." With that good advice in mind:

Phase 1: Collect the unique elements

std::vector<Foo> elements;

// add N elements
elements.push_back(foo1);
...
elements.push_back(fooN);

// done collecting: remove dupes
std::sort(elements.begin(), elements.end());
elements.erase(std::unique(elements.begin(), elements.end()),
               elements.end());

Phase 2: Well, now we have a vector of our k unique elements, with constant-time index access (with indices 0..k-1).

Upvotes: 4

Related Questions