use openmp in iterating over a map

It could be done also by using a simple index based for loop clubbed with std::advance to reach to a particular map element. OpenMP 2.0 supports index based for loops very well.

#pragma omp parallel for
    for(int i = 0; i < dat.size(); i++) {
        auto datIt = dat.begin();
        advance(datIt, i);
        //construct the distance matrix using iterator datIt
    }

In each thread the iterator datIt will point to a map item and can be used to perform operations on it.

It's likely your implementation of OpenMP is incompatible with STL iterators. While there have been some changes to the standard to make OMP more compatible with the STL, I think you'll find your implementation doesn't support such behaviour. Most OpenMP implementations I've encountered are at most version 2.5, Microsoft C++ is 2.0. The only compiler I'm aware of that supports 3.0 is the Intel C++ compiler.

A few other points, you should use std::begin, and std::end. Also, you either need to declare your loop invariant as private, or have OpenMP figure that out by itself, like so:

#pragma omp parallel for
for(map< int,string >::iterator datIt = std::begin(dat);
    datIt != std::end(dat);
    datIt++)
{
     //construct the distance matrix...
}

But without 3.0 support, this is beside the point.