Reputation: 2414
Which is the best container in C++ which can -
set
)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);
}
}
};
Upvotes: 3
Views: 145
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
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