Using C++-AMP to reduce runtime of unsorted vector search

Question

I have written a program that does a lot of searching through an unsorted vector of struct to find indices of unique elements. This searching is done multiple times each iteration in a for-loop and also the data inside the vector changes multiple times during the for-loop iteration (data is only added, nothing is removed). Now the program does what I want it to do, but it is rather slow, so after I let VS2012 analyze the performance of my program I found that more than 80% of the time the program is searching through the unsorted vector, so naturally I want to optimize the searching. I know the best I can get is O(n), because it is an unsorted vector (every element is unique and the order of the elements cannot change once they are inserted), but I am hoping to reduce the runtime somehow.

I've been thinking of using parallel processing to reduce the programs runtime and Microsoft's AMP library looks promising. By the looks of it you can use parallel processing to iterate through an array to find an element in the array. But the data in the unsorted vector changes a lot, so won't this move the bottleneck from iterating the vector to data transfer from CPU to GPU or has AMP build-in optimizations to cope with this? Remember: the data in the vector is only added at the end of the vector, nothing is removed.

Just in case it helps: here is the vector and the search function I use:

struct VertexData
{
    VertexData( unsigned int pos, unsigned int norm, unsigned int tex )
        : posIdx(pos), normIdx(norm), texIdx(tex) {}

    unsigned int posIdx;
    unsigned int normIdx;
    unsigned int texIdx;

    inline bool operator<( const VertexData &rhs ) const
    {
        return std::tie(posIdx, normIdx, texIdx) < std::tie(rhs.posIdx, rhs.normIdx, rhs.texIdx);
    }

    inline bool operator==( const VertexData &rhs ) const
    {
        return std::tie(posIdx, normIdx, texIdx) == std::tie(rhs.posIdx, rhs.normIdx, rhs.texIdx);
    }
};

std::vector<VertexData> verts;

int findIndex( const std::vector<VertexData> &vec, const VertexData &val ) const
{
    std::vector<VertexData>::const_iterator it;
    int idx = 0;
    for ( it = vec.begin(); it != vec.end(); ++it, ++idx )
        if ( *it == val )
            return idx;

    return -1;
}

Answer 1

Could you use something like boost::multi-index array to hold a sorted unique set of indices to your unsorted vector? That way you avoid the extra work each time.

Algorithmic fixes are always better than brute force, as a rule.