Ideally, you should always favor templates as the templates allow for generic implementation that is also type safe. Macros don't allow for type-safe implementations and are best avoided.

Normally not as the compiler can infer this for you, given the arguments used in the function call.

This is entirely dependent on the number of types for which the template class has been instantiated. So, if your class has been instantiated for an int, a string, and a custom type X, you can expect three instances of your static variable to be available-one per template instantiation.

A std::vector or a std::deque is perfectly suited to this requirement. Both manage memory and can dynamically scale themselves to an application's increasing requirements.

An associative container like std::map or std::set or the unordered variants thereof are most suited to requirements that involve frequent searches.

An associative container of type std::multimap is suited to this requirement. A multimap can hold nonunique key-value pairs and can offer a quick lookup that is characteristic of associative containers.

Portability is an important constraint and using standard-compliant containers is necessary. hash_map is not part of the C++ standard and therefore may not be supported across all platforms relevant to your application. You may use std::unordered_map if you are using C++11-compliant compilers for all the platforms concerned.

A std::deque. Only a deque simulates a dynamic array and also allows constanttime insertions at the front and at the back of the container. A std::vector does not allow insertions at the beginning and is therefore unsuited.

A std::set or a std::map if you have key-value pairs. If the elements need to be available in duplicates, too, you would choose std::multiset or std::multimap.

Yes. When you instantiate a std::set template, you can optionally supply a second template parameter that is a binary predicate that the set class uses as the sort criterion. Program this binary predicate to criteria that are relevant to your requirements. It needs to be strict-weak ordering compliant.