A few minor points that weren't mentioned:

• A virtual destructor for Map: You didn't specify, but the only reason for Map to have a virtual destructor is if some other class is inheriting from it. If you did it just to make your code "future proof", don't. Follow the YAGNI principle. If you are currently inheriting from Map I would advise against, since you can probably do a better job using composition instead.

• Methods that don't mutate class state should be const. Size() is one. It should be declared:

    size_t Size() const { return size_; }
  

I would also expect Find() to be const. It wouldn't make much sense having a "find" method that change the data structure it operates on.

• size_t in C++ is technically a member of the std namespace (it will also be visible globally if you include any C header like stdlib.h, directly or indirectly). Personally, I find it a pain in the neck using it as std::size_t, but if you want to be pedantic...

• You'll probably want to provide a second version of operator[] that is const and returns a const reference. Something in the lines of:

    const reference operator[] const (const K& key) { ... }
  

• Method Empty() has a misleading name. It seems to be clearing the map. The name you have chosen is very inadequate in a C++ context because almost all standard C++ containers have an empty() method that tests if the container is empty. So it is very likely that users of your Map would assume the same. Clear() would be the best name, IMHO.

• Add(K key, V value): As it is now, using pre-11 C++, you should not pass the parameters by value. Remember that in C++ the default is a copy. Change that function to receive a const reference of the parameters:

    void Add(const K& key, const V& value);
  

This will prevent an extra copy inside the function. This way there should be a single copy once you place it inside the map and nothing else. A future optimization to this would be adding C++11 move semantics.

• I really don't like to see the NULL macro in C++, though before nullptr we either had to use it or use a plain 0. NULL in C++ is actually just a #define for 0, so I used to go with the 0 back then.

A few minor points that weren't mentioned:

• A virtual destructor for Map: You didn't specify, but the only reason for Map to have a virtual destructor is if some other class is inheriting from it. If you did it just to make your code "future proof", don't. Follow the YAGNI principle. If you are currently inheriting from Map I would advise against, since you can probably do a better job using composition instead.

• Methods that don't mutate member state should be const. Size() is one. It should be declared:

    size_t Size() const { return size_; }
  

I would also expect Find() to be const. It wouldn't make much sense having a "find" method that change the data structure it operates on.

• size_t in C++ is technically a member of the std namespace (it will also be visible globally if you include any C header like stdlib.h, directly or indirectly). Personally, I find it a pain in the neck using it as std::size_t, but if you want to be pedantic...

• You'll probably want to provide a second version of operator[] that is const and returns a const reference. Something in the lines of:

    const reference operator[] (const K& key) const { ... }
  

• Method Empty() has a misleading name. It seems to be clearing the map. The name you have chosen is very inadequate in a C++ context because almost all standard C++ containers have an empty() method that tests if the container is empty. So it is very likely that users of your Map would assume the same. Clear() would be the best name, IMHO.

• Add(K key, V value): As it is now, using pre-11 C++, you should not pass the parameters by value. Remember that in C++ the default is a copy. Change that function to receive a const reference of the parameters:

    void Add(const K& key, const V& value);
  

This will prevent an extra copy inside the function. This way there should be a single copy once you place it inside the map and nothing else. A future optimization to this would be adding C++11 move semantics.

• I don't like to see the NULL macro being used in C++, though before nullptr we either had to use it or use a plain 0. NULL in C++ is actually just a #define for 0, so I used to go with the 0 back then.