C ++ container set + array functionality
What's the best container in C ++ that can -
- store only unique values (for example
set
) - can search for these values using index at constant time (for example
array
)
I basically need to iterate over in the first phase and collect all the elements unique
, the order doesn't really matter.
However, in the second phase, I have to provide each item in the container, but I can only provide it one by one. Since the caller can know the size of my container, it provides me index
one by one, so 0 <idx <container size.
Right now the only solution that comes to my mind is two backed containers vector
and set
I'm wondering if there is any container that provides the same thing?
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);
}
}
};
source to share
Alex Stepanov, the creator of the STL, once said, "Use vectors whenever you can. If you can't use vectors, rework your solution so you can use vectors." With this good advice in mind:
Phase 1: Collect Unique Items
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());
Stage 2: Now we have vector
our k
unique elements with constant access by index (with indexes 0..k-1).
source to share
You can use boost flat_set
.
I don't think it provides operator[]
, but it has random access iterators and has a constant function nth()
that returns an iterator at a specific index.
Insertion can invalidate the iterators, but assuming you do all the inserts in phase 1, and then all the index access in phase 2, you should be fine.
source to share