STLAlgorithmExtensions/MapAlgorithms

BOOST WIKI | STLAlgorithmExtensions | RecentChanges | Preferences | Page List | Links List

These three algorithms work on maps.

```#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

Agree, wish I remember where those two algorithms were used by me :-). Okay, it can be converted to
``` template<class Container, class OutputIterator>
void domain(const Container&, OutputIterator r) { ... }
```
As a side note, this is a general problem with stl containers -- passing/returning them by value is slow. Maybe, new code should use `auto_ptr<some_stl_container>` for return type? --People/Vladimir Prus

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]?

BOOST WIKI | STLAlgorithmExtensions | RecentChanges | Preferences | Page List | Links List