STLAlgorithmExtensions/MapAlgorithms

#include <map>
#include <utility>
#include <stdexcept>

template<class Container>
        std::set<typename Container::key_type>
        domain(const Container &container)
        {
            std::set<typename Container::key_type> result;
            for (typename Container::const_iterator i = container.begin();
                 i != container.end(); i++)
                result.insert(i->first);
            return result;
        }

    template<class Container>
        std::set<typename Container::mapped_type>
        range(const Container &container)
        {
            std::set<typename Container::mapped_type> result;
            for (typename Container::const_iterator i = container.begin();
                i != container.end(); i++)
                result.insert(i->second);
            return result;
        }


template<class Key1, class Data1, class Compare1, class Allocator1,
         class Key2, class Data2, class Compare2, class Allocator2>
 void reverse_map(const std::map<Key1, Data1, Compare1, Allocator1>& src,
    std::map<Key2, Data2, Compare2, Allocator2>& dst)
 {
     std::map<Key1, Data1, Compare1, Allocator1>::const_iterator si;
     std::map<Key2, Data2, Compare2, Allocator2>::iterator di;

     for (si = src.begin(); si != src.end(); ++si) {
  di = dst.lower_bound(si->second);
  if (di != dst.end() && di->first == si->second)
      throw logic_error("reverse_map: source map is a not bijection.");
  dst.insert(di, std::make_pair(si->second, si->first));
     }
 }

Note that the first two overlap in some degree with [projection iterator], see this [message] for discussion. -- People/Vladimir Prus

Returning the result set by value in the first two functions is probably not a good idea, very inefficient. --People/JeremySiek

 template<class Container, class OutputIterator>
 void domain(const Container&, OutputIterator r) { ... }

I think the right (and usual, and more general ;) way is output iterator. And input too. --Sergei Katkovsky

Following Sergei's (see above) and Dave's (see mailing list message) advice, maybe it could be better to have [select1st] and [select2nd] to be able to use transform. Thus, domain would result into:

 transform(container.begin(), container.end(), destination_iterator,
           select1st<Container::value_type>());

and range into:

 transform(container.begin(), container.end(), destination_iterator,
           select2nd<Container::value_type>());

Now the real issue is if we want to encapsulate this line inside something with a meaningful name, like range or domain. This poses the problem of determining the type to pass to select1st and the only way I know is the following (but it's my ignorance for sure):

 template<typename InputIterator?, typename OutputIterator?, typename ValueType?>
 void domain(InputIterator? first, InputIterator? pastlast, OutputIterator? dest,
                  ValueType?*) {
    transform(first, pastlast, dest, select1st<ValueType?>());
 }
 template<typename InputIterator?, typename OutputIterator?>
 void domain(InputIterator? first, InputIterator? pastlast, OutputIterator? dest) {
    domain(first, pastlast, dest, value_type(first));
 }

I've to admit that this is rather cumbersome and probably inefficient, so it could be better to re-implement transform and get rid of select1st, resuming the first implementation:

 template<typename InputIterator?, typename OutputIterator?>
 void domain(InputIterator? first, InputIterator? pastlast, OutputIterator? dest) {
    for ( ; first != pastlast; ++first, ++dest)
       *dest = (*first).first;
 }

(This pushes a rather philosophical question: is it correct to have a specialised algorithm for all, instead of using function objects like select1st and select2nd? On one side, this improves readability, but on the other side I personally think that:

 transform(container.begin(), container.end(), destination_iterator,
           select1st<Container::value_type>());

is quite clear about the intent of the programmer, i.e. collecting all the "keys" inside container, without the need for another algorithm which "does exactly that operation".) -- [Flavio Poletti]?