If I'm compiling a C program with gcc, I can safely assume that the functions in regex.h are available. Is there a regex library I can assume is there if someone is compiling with microsoft's C compiler?
No, I don't think MSVC comes bundled with any regex library.
Regex isn't part of the C/C++ standard library, so you shouldn't rely on any compiler providing such a library by default. It's best to get hold of a separate regex library for C (I'm sure there are tons available) and include it with your code.
C++ only, but may be something you can use (or wrap):
Visual C++ 2010 includes the TR1 regex library support.
It's also available for VC++ 2008 in a feature pack:
If you want POSIX-compatible regular expression semantics (and the same API too!) then the best regex library is TRE: http://laurikari.net/tre/
Unlike most regex implementations, it follows POSIX exactly in regards to the matches it returns for parenthesized subexpressions, and it's O(n)
whereas most implementations are O(2^n)
in time.
Google also has a new regex implementation that uses Perl-compatible syntax if you prefer that. You can find a link on the TRE website.
Edit: By the way, TRE seems to come with project files to build it under MSVC.