Geek asks and answers

List of Unique Items

I need a container where:

  • when I add a new item that does not exist yet, it is added to the top of the list
  • when I add an item that already exists, it is not added, and I get its index in the list
  • after an element is inserted, it always has the same index and can be accessed using this index

std::setnot enough, because I cannot access the elements with [index]. std::listno, because it does not store unique items only.

I used a mixed solution with listand map, but maybe there is a standard standard template for this?

I do not want to use boost. A call list::uniqueafter each insert is not a solution.

+3
source share
1 answer

If you use only std::list(or std::vector, for that matter) you are not going to conduct a linear search, if you do not want to avoid duplication, but you want to keep the original order. It just std::vectormight 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 assumes that it Tsupports <. If not, you will need to set custom criteria. Or use unordered_mapand define a hash code for it.)

+3
source

More articles:


All Articles