C++ container set + array functionality

Question

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

store only unique values (such as set)
can lookup those values using index in constant time (such as array)

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

set also orders the values. Do you need them to be ordered, or merely that there be no duplicates? — M.M
– M.M, Commented Aug 4, 2015 at 23:33
unordered set has "Search, insertion, and removal have average constant-time complexity" which means O(1) on average. — Jerry Jeremiah
– Jerry Jeremiah, Commented Aug 4, 2015 at 23:35
You could use a vector, but with an custom insert function that checks for duplicates on insert — M.M
– M.M, Commented Aug 4, 2015 at 23:38
Can you explain a bit about why you want to look up the values with an index? Since you don't require them to have stable order I'm struggling to see what benefit there is to look them up by index. — M.M
– M.M, Commented Aug 4, 2015 at 23:39

Barry · Accepted Answer · 2015-08-05 00:08:43Z

4

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).

answered Aug 5, 2015 at 0:08

Barry

312k32 gold badges736 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

T.C. Over a year ago

This can be expensive if there are lots of duplicates, though.

Shrey Over a year ago

Thanks, Barry! But in that case I can even use set during collection and convert to vector to have constant-time index access..

Barry Over a year ago

@T.C. Absolutely. I'm just going on the [likely completely unfounded] assumption that phase 2 is the important one :)

Chris Drew · Accepted Answer · 2015-08-05 01:22:56Z

2

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.

edited Aug 5, 2015 at 1:22

answered Aug 5, 2015 at 1:11

Chris Drew

15.4k3 gold badges38 silver badges55 bronze badges

Collectives™ on Stack Overflow

C++ container set + array functionality

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related