List with unique elements
c++, collections
Solution
If you're using just a `std::list` (or `std::vector`, for that matter), you're not going to get around a linear search if you don't want to avoid duplicated, but you want to keep the original order. A simple `std::vector` based solution might be:
int
createIndex( std::vector<T>& references, T const& newValue )
{
int results = std::find( references.begin(), references.end(), newValue )
- references.begin();
if ( results == references.size() ) {
references.push_back( newValue );
}
return results;
}
Alternatively, you can use `std::map`:
int
createIndex( std::map<T, int>& references, T const& newValue )
{
st::map<T, int>::iterator results = references.find( newValue );
if ( results == references.end() ) {
results = references.insert(
std::make_pair( newValue, references.size() ) ).first;
}
return results->second;
}
(This supposes that `T` supports `<`. If not, you'll have to establish an ordering critera. Or use `unordered_map` and define a hash code for it.)
Problem
I need a container, where: - when I add a new element that does not exist yet, it is added to the top of the list - when I add an element that already exists, it is not added and I I get its index in the list - once the element is inserted, it always has the same index and it can be accessed using this index `std::set` alone is insufficient, because I cannot access the elements with `[index]`. `std::list` neither, because it does not store unique only elements. I used a mixed solution with `list` and `map` but maybe there is some standard, generic template for that? I don't want to use boost. Invoking `list::unique` after every insertion is no solution.