[libcamera-devel] libcamera: utils: Add map_keys() function

Message ID 20200625012335.7717-1-laurent.pinchart@ideasonboard.com
State Accepted
Headers show
Series
  • [libcamera-devel] libcamera: utils: Add map_keys() function
Related show

Commit Message

Laurent Pinchart June 25, 2020, 1:23 a.m. UTC
Add a map_keys() function to the utils namespace to extract keys from a
map.

Signed-off-by: Laurent Pinchart <laurent.pinchart@ideasonboard.com>
---
 include/libcamera/internal/utils.h | 10 ++++++++++
 src/libcamera/utils.cpp            |  7 +++++++
 test/utils.cpp                     | 21 +++++++++++++++++++++
 3 files changed, 38 insertions(+)

Comments

Jacopo Mondi June 25, 2020, 7:47 a.m. UTC | #1
Hi Laurent,
   I still wonder why we don't have this in STL...

On Thu, Jun 25, 2020 at 04:23:35AM +0300, Laurent Pinchart wrote:
> Add a map_keys() function to the utils namespace to extract keys from a
> map.
>
> Signed-off-by: Laurent Pinchart <laurent.pinchart@ideasonboard.com>
> ---
>  include/libcamera/internal/utils.h | 10 ++++++++++
>  src/libcamera/utils.cpp            |  7 +++++++
>  test/utils.cpp                     | 21 +++++++++++++++++++++
>  3 files changed, 38 insertions(+)
>
> diff --git a/include/libcamera/internal/utils.h b/include/libcamera/internal/utils.h
> index 0953423ee8d0..4fe4843922a9 100644
> --- a/include/libcamera/internal/utils.h
> +++ b/include/libcamera/internal/utils.h
> @@ -11,6 +11,7 @@
>  #include <chrono>
>  #include <memory>
>  #include <ostream>
> +#include <set>
>  #include <sstream>
>  #include <string>
>  #include <string.h>
> @@ -36,6 +37,15 @@ const char *basename(const char *path);
>  char *secure_getenv(const char *name);
>  std::string dirname(const std::string &path);
>
> +template<typename T>
> +std::set<typename T::key_type> map_keys(const T &map)

Keys are unique and sorted in maps, can't we return a vector ? Is this
meant to support multimaps too ? If that's not desired, can we use
std::map<class Key, T> as the template parameter ?

(To be honest, calling this on a multimap opens one question: do we
want the -unique- keys, or all the keys ? The number of keys, if
unique, would be less than the number of actual entries in the map...
This makes me feel we want this for maps only)


> +{
> +	std::set<typename T::key_type> keys;
> +	std::transform(map.begin(), map.end(), std::inserter(keys, keys.end()),
> +		       [](const auto &value) { return value.first; });
> +	return keys;
> +}
> +
>  template<class InputIt1, class InputIt2>
>  unsigned int set_overlap(InputIt1 first1, InputIt1 last1,
>  			 InputIt2 first2, InputIt2 last2)
> diff --git a/src/libcamera/utils.cpp b/src/libcamera/utils.cpp
> index d55338fe681a..1eb8970a5bbc 100644
> --- a/src/libcamera/utils.cpp
> +++ b/src/libcamera/utils.cpp
> @@ -127,6 +127,13 @@ std::string dirname(const std::string &path)
>  	return path.substr(0, pos + 1);
>  }
>
> +/**
> + * \fn std::set<typename T::key_type> map_keys(const T &map)
> + * \brief Retrieve the keys of a std::map<>
> + * \param[in] map The map whose keys to retrieve
> + * \return A std::set<> containing the keys of \a map
> + */
> +
>  /**
>   * \fn libcamera::utils::set_overlap(InputIt1 first1, InputIt1 last1,
>   *				     InputIt2 first2, InputIt2 last2)
> diff --git a/test/utils.cpp b/test/utils.cpp
> index 66b91f1203e1..a9d072030f1c 100644
> --- a/test/utils.cpp
> +++ b/test/utils.cpp
> @@ -6,6 +6,8 @@
>   */
>
>  #include <iostream>
> +#include <map>
> +#include <set>
>  #include <sstream>
>  #include <string>
>  #include <vector>
> @@ -144,6 +146,25 @@ protected:
>  		if (TestPass != testDirname())
>  			return TestFail;
>
> +
> +		/* utils::map_keys() test. */
> +		const std::map<std::string, unsigned int> map{
> +			{ "zero", 0 },
> +			{ "one", 1 },
> +			{ "two", 2 },
> +		};
> +		const std::set<std::string> expectedKeys{
> +			"zero",
> +			"one",
> +			"two",
> +		};

How are keys sorted here ?

> +
> +		const std::set<std::string> keys = utils::map_keys(map);
> +		if (keys != expectedKeys) {

This matches the sorting order of expectedKeys by chance ? I see
std::set::operator== assuming lhs and rhs to be sorted equally

> +			cerr << "utils::map_keys() test failed" << endl;
> +			return TestFail;
> +		}
> +
>  		return TestPass;
>  	}
>  };
> --
> Regards,
>
> Laurent Pinchart
>
> _______________________________________________
> libcamera-devel mailing list
> libcamera-devel@lists.libcamera.org
> https://lists.libcamera.org/listinfo/libcamera-devel
Umang Jain June 25, 2020, 8:12 a.m. UTC | #2
Hi Laurent,

I have a query below.

On 6/25/20 6:53 AM, Laurent Pinchart wrote:
> Add a map_keys() function to the utils namespace to extract keys from a
> map.
>
> Signed-off-by: Laurent Pinchart <laurent.pinchart@ideasonboard.com>
> ---
>   include/libcamera/internal/utils.h | 10 ++++++++++
>   src/libcamera/utils.cpp            |  7 +++++++
>   test/utils.cpp                     | 21 +++++++++++++++++++++
>   3 files changed, 38 insertions(+)
>
> diff --git a/include/libcamera/internal/utils.h b/include/libcamera/internal/utils.h
> index 0953423ee8d0..4fe4843922a9 100644
> --- a/include/libcamera/internal/utils.h
> +++ b/include/libcamera/internal/utils.h
> @@ -11,6 +11,7 @@
>   #include <chrono>
>   #include <memory>
>   #include <ostream>
> +#include <set>
>   #include <sstream>
>   #include <string>
>   #include <string.h>
> @@ -36,6 +37,15 @@ const char *basename(const char *path);
>   char *secure_getenv(const char *name);
>   std::string dirname(const std::string &path);
>   
> +template<typename T>
> +std::set<typename T::key_type> map_keys(const T &map)
> +{
> +	std::set<typename T::key_type> keys;
> +	std::transform(map.begin(), map.end(), std::inserter(keys, keys.end()),
I am not able to wrap my head around keys.end() as the beginning 
position for the
insertor? keys.end() points to `past-the-end`element which should not be 
de-referenced,
as claimed in the online docs. Can you explain why we cannot use:

std::inserter(keys, keys.begin()) ?

> +		       [](const auto &value) { return value.first; });
> +	return keys;
> +}
> +
>   template<class InputIt1, class InputIt2>
>   unsigned int set_overlap(InputIt1 first1, InputIt1 last1,
>   			 InputIt2 first2, InputIt2 last2)
> diff --git a/src/libcamera/utils.cpp b/src/libcamera/utils.cpp
> index d55338fe681a..1eb8970a5bbc 100644
> --- a/src/libcamera/utils.cpp
> +++ b/src/libcamera/utils.cpp
> @@ -127,6 +127,13 @@ std::string dirname(const std::string &path)
>   	return path.substr(0, pos + 1);
>   }
>   
> +/**
> + * \fn std::set<typename T::key_type> map_keys(const T &map)
> + * \brief Retrieve the keys of a std::map<>
> + * \param[in] map The map whose keys to retrieve
> + * \return A std::set<> containing the keys of \a map
> + */
> +
>   /**
>    * \fn libcamera::utils::set_overlap(InputIt1 first1, InputIt1 last1,
>    *				     InputIt2 first2, InputIt2 last2)
> diff --git a/test/utils.cpp b/test/utils.cpp
> index 66b91f1203e1..a9d072030f1c 100644
> --- a/test/utils.cpp
> +++ b/test/utils.cpp
> @@ -6,6 +6,8 @@
>    */
>   
>   #include <iostream>
> +#include <map>
> +#include <set>
>   #include <sstream>
>   #include <string>
>   #include <vector>
> @@ -144,6 +146,25 @@ protected:
>   		if (TestPass != testDirname())
>   			return TestFail;
>   
> +
> +		/* utils::map_keys() test. */
> +		const std::map<std::string, unsigned int> map{
> +			{ "zero", 0 },
> +			{ "one", 1 },
> +			{ "two", 2 },
> +		};
> +		const std::set<std::string> expectedKeys{
> +			"zero",
> +			"one",
> +			"two",
> +		};
> +
> +		const std::set<std::string> keys = utils::map_keys(map);
> +		if (keys != expectedKeys) {
> +			cerr << "utils::map_keys() test failed" << endl;
> +			return TestFail;
> +		}
> +
>   		return TestPass;
>   	}
>   };
Niklas Söderlund June 25, 2020, 10:09 a.m. UTC | #3
Hi Laurent,

Thanks for your work.

On 2020-06-25 04:23:35 +0300, Laurent Pinchart wrote:
> Add a map_keys() function to the utils namespace to extract keys from a
> map.
> 
> Signed-off-by: Laurent Pinchart <laurent.pinchart@ideasonboard.com>

Reviewed-by: Niklas Söderlund <niklas.soderlund@ragnatech.se>

> ---
>  include/libcamera/internal/utils.h | 10 ++++++++++
>  src/libcamera/utils.cpp            |  7 +++++++
>  test/utils.cpp                     | 21 +++++++++++++++++++++
>  3 files changed, 38 insertions(+)
> 
> diff --git a/include/libcamera/internal/utils.h b/include/libcamera/internal/utils.h
> index 0953423ee8d0..4fe4843922a9 100644
> --- a/include/libcamera/internal/utils.h
> +++ b/include/libcamera/internal/utils.h
> @@ -11,6 +11,7 @@
>  #include <chrono>
>  #include <memory>
>  #include <ostream>
> +#include <set>
>  #include <sstream>
>  #include <string>
>  #include <string.h>
> @@ -36,6 +37,15 @@ const char *basename(const char *path);
>  char *secure_getenv(const char *name);
>  std::string dirname(const std::string &path);
>  
> +template<typename T>
> +std::set<typename T::key_type> map_keys(const T &map)
> +{
> +	std::set<typename T::key_type> keys;
> +	std::transform(map.begin(), map.end(), std::inserter(keys, keys.end()),
> +		       [](const auto &value) { return value.first; });
> +	return keys;
> +}
> +
>  template<class InputIt1, class InputIt2>
>  unsigned int set_overlap(InputIt1 first1, InputIt1 last1,
>  			 InputIt2 first2, InputIt2 last2)
> diff --git a/src/libcamera/utils.cpp b/src/libcamera/utils.cpp
> index d55338fe681a..1eb8970a5bbc 100644
> --- a/src/libcamera/utils.cpp
> +++ b/src/libcamera/utils.cpp
> @@ -127,6 +127,13 @@ std::string dirname(const std::string &path)
>  	return path.substr(0, pos + 1);
>  }
>  
> +/**
> + * \fn std::set<typename T::key_type> map_keys(const T &map)
> + * \brief Retrieve the keys of a std::map<>
> + * \param[in] map The map whose keys to retrieve
> + * \return A std::set<> containing the keys of \a map
> + */
> +
>  /**
>   * \fn libcamera::utils::set_overlap(InputIt1 first1, InputIt1 last1,
>   *				     InputIt2 first2, InputIt2 last2)
> diff --git a/test/utils.cpp b/test/utils.cpp
> index 66b91f1203e1..a9d072030f1c 100644
> --- a/test/utils.cpp
> +++ b/test/utils.cpp
> @@ -6,6 +6,8 @@
>   */
>  
>  #include <iostream>
> +#include <map>
> +#include <set>
>  #include <sstream>
>  #include <string>
>  #include <vector>
> @@ -144,6 +146,25 @@ protected:
>  		if (TestPass != testDirname())
>  			return TestFail;
>  
> +
> +		/* utils::map_keys() test. */
> +		const std::map<std::string, unsigned int> map{
> +			{ "zero", 0 },
> +			{ "one", 1 },
> +			{ "two", 2 },
> +		};
> +		const std::set<std::string> expectedKeys{
> +			"zero",
> +			"one",
> +			"two",
> +		};
> +
> +		const std::set<std::string> keys = utils::map_keys(map);
> +		if (keys != expectedKeys) {
> +			cerr << "utils::map_keys() test failed" << endl;
> +			return TestFail;
> +		}
> +
>  		return TestPass;
>  	}
>  };
> -- 
> Regards,
> 
> Laurent Pinchart
> 
> _______________________________________________
> libcamera-devel mailing list
> libcamera-devel@lists.libcamera.org
> https://lists.libcamera.org/listinfo/libcamera-devel
Laurent Pinchart June 25, 2020, 2:17 p.m. UTC | #4
Hi Jacopo,

On Thu, Jun 25, 2020 at 09:47:21AM +0200, Jacopo Mondi wrote:
> Hi Laurent,
>    I still wonder why we don't have this in STL...

If you ever find an answer, I'll be interested to know :-)

> On Thu, Jun 25, 2020 at 04:23:35AM +0300, Laurent Pinchart wrote:
> > Add a map_keys() function to the utils namespace to extract keys from a
> > map.
> >
> > Signed-off-by: Laurent Pinchart <laurent.pinchart@ideasonboard.com>
> > ---
> >  include/libcamera/internal/utils.h | 10 ++++++++++
> >  src/libcamera/utils.cpp            |  7 +++++++
> >  test/utils.cpp                     | 21 +++++++++++++++++++++
> >  3 files changed, 38 insertions(+)
> >
> > diff --git a/include/libcamera/internal/utils.h b/include/libcamera/internal/utils.h
> > index 0953423ee8d0..4fe4843922a9 100644
> > --- a/include/libcamera/internal/utils.h
> > +++ b/include/libcamera/internal/utils.h
> > @@ -11,6 +11,7 @@
> >  #include <chrono>
> >  #include <memory>
> >  #include <ostream>
> > +#include <set>
> >  #include <sstream>
> >  #include <string>
> >  #include <string.h>
> > @@ -36,6 +37,15 @@ const char *basename(const char *path);
> >  char *secure_getenv(const char *name);
> >  std::string dirname(const std::string &path);
> >
> > +template<typename T>
> > +std::set<typename T::key_type> map_keys(const T &map)
> 
> Keys are unique and sorted in maps, can't we return a vector ? Is this
> meant to support multimaps too ? If that's not desired, can we use
> std::map<class Key, T> as the template parameter ?
> 
> (To be honest, calling this on a multimap opens one question: do we
> want the -unique- keys, or all the keys ? The number of keys, if
> unique, would be less than the number of actual entries in the map...
> This makes me feel we want this for maps only)

I'd rather make this specific to std::map for now. Returning a vector
would make sense, and I think that's what I'd prefer. Maybe this is why
STL doesn't have a std::map::keys() method, they couldn't decide what
container it should return ;-)

> > +{
> > +	std::set<typename T::key_type> keys;
> > +	std::transform(map.begin(), map.end(), std::inserter(keys, keys.end()),
> > +		       [](const auto &value) { return value.first; });
> > +	return keys;
> > +}
> > +
> >  template<class InputIt1, class InputIt2>
> >  unsigned int set_overlap(InputIt1 first1, InputIt1 last1,
> >  			 InputIt2 first2, InputIt2 last2)
> > diff --git a/src/libcamera/utils.cpp b/src/libcamera/utils.cpp
> > index d55338fe681a..1eb8970a5bbc 100644
> > --- a/src/libcamera/utils.cpp
> > +++ b/src/libcamera/utils.cpp
> > @@ -127,6 +127,13 @@ std::string dirname(const std::string &path)
> >  	return path.substr(0, pos + 1);
> >  }
> >
> > +/**
> > + * \fn std::set<typename T::key_type> map_keys(const T &map)
> > + * \brief Retrieve the keys of a std::map<>
> > + * \param[in] map The map whose keys to retrieve
> > + * \return A std::set<> containing the keys of \a map
> > + */
> > +
> >  /**
> >   * \fn libcamera::utils::set_overlap(InputIt1 first1, InputIt1 last1,
> >   *				     InputIt2 first2, InputIt2 last2)
> > diff --git a/test/utils.cpp b/test/utils.cpp
> > index 66b91f1203e1..a9d072030f1c 100644
> > --- a/test/utils.cpp
> > +++ b/test/utils.cpp
> > @@ -6,6 +6,8 @@
> >   */
> >
> >  #include <iostream>
> > +#include <map>
> > +#include <set>
> >  #include <sstream>
> >  #include <string>
> >  #include <vector>
> > @@ -144,6 +146,25 @@ protected:
> >  		if (TestPass != testDirname())
> >  			return TestFail;
> >
> > +
> > +		/* utils::map_keys() test. */
> > +		const std::map<std::string, unsigned int> map{
> > +			{ "zero", 0 },
> > +			{ "one", 1 },
> > +			{ "two", 2 },
> > +		};
> > +		const std::set<std::string> expectedKeys{
> > +			"zero",
> > +			"one",
> > +			"two",
> > +		};
> 
> How are keys sorted here ?

std::map<> and std::set<> are sorted automatically. I think the test
should actually use a different order in the initializer list of
expectedKeys, just to show it gets sorted.

> > +
> > +		const std::set<std::string> keys = utils::map_keys(map);
> > +		if (keys != expectedKeys) {
> 
> This matches the sorting order of expectedKeys by chance ? I see
> std::set::operator== assuming lhs and rhs to be sorted equally
> 
> > +			cerr << "utils::map_keys() test failed" << endl;
> > +			return TestFail;
> > +		}
> > +
> >  		return TestPass;
> >  	}
> >  };
Laurent Pinchart June 25, 2020, 2:28 p.m. UTC | #5
Hi Umang,

On Thu, Jun 25, 2020 at 08:12:12AM +0000, Umang Jain wrote:
> On 6/25/20 6:53 AM, Laurent Pinchart wrote:
> > Add a map_keys() function to the utils namespace to extract keys from a
> > map.
> >
> > Signed-off-by: Laurent Pinchart <laurent.pinchart@ideasonboard.com>
> > ---
> >   include/libcamera/internal/utils.h | 10 ++++++++++
> >   src/libcamera/utils.cpp            |  7 +++++++
> >   test/utils.cpp                     | 21 +++++++++++++++++++++
> >   3 files changed, 38 insertions(+)
> >
> > diff --git a/include/libcamera/internal/utils.h b/include/libcamera/internal/utils.h
> > index 0953423ee8d0..4fe4843922a9 100644
> > --- a/include/libcamera/internal/utils.h
> > +++ b/include/libcamera/internal/utils.h
> > @@ -11,6 +11,7 @@
> >   #include <chrono>
> >   #include <memory>
> >   #include <ostream>
> > +#include <set>
> >   #include <sstream>
> >   #include <string>
> >   #include <string.h>
> > @@ -36,6 +37,15 @@ const char *basename(const char *path);
> >   char *secure_getenv(const char *name);
> >   std::string dirname(const std::string &path);
> >   
> > +template<typename T>
> > +std::set<typename T::key_type> map_keys(const T &map)
> > +{
> > +	std::set<typename T::key_type> keys;
> > +	std::transform(map.begin(), map.end(), std::inserter(keys, keys.end()),
>
> I am not able to wrap my head around keys.end() as the beginning
> position for the insertor? keys.end() points to `past-the-end`element
> which should not be de-referenced, as claimed in the online docs. Can
> you explain why we cannot use:
> 
> std::inserter(keys, keys.begin()) ?

std::inserter() is a helper that return a std::insert_iterator. An
std::insert_iterator is an iterator that invokes the insert() function of
the container it is related to in its operator=(). Calling

	iter = value;

on an std::insert_iterator results in

	iter = container->insert(iter, value);
	++iter;

while calling operator++() directly on the iterator is a no-op.

The insert() function of STL containers takes an iterator as a parameter
to specify the insertion position. The insertion happens just prior to
iterator. For std::list and std::vector that's guaranteed, while for
std::map and std::set that's just a hint: maps and sets are sorted by
key, so the insertion position depends on the key. Still, passing the
correct hint to insert() for map and set can help with performances.

Using keys.end() will thus result in the new element being inserted just
before the end of the container. As they map is sorted by key, the
std::transform call will insert the keys in the set in increasing order.
end() is thus the correct hint in that case. begin() would work too, but
would result in worse performances, as the insert() function would
realize that the hint is not correct, and will look up the correct
position. See https://en.cppreference.com/w/cpp/container/map/insert
that states

Complexity

[...]

4-6) Amortized constant if the insertion happens in the position just
before the hint, logarithmic in the size of the container otherwise.

> > +		       [](const auto &value) { return value.first; });
> > +	return keys;
> > +}
> > +
> >   template<class InputIt1, class InputIt2>
> >   unsigned int set_overlap(InputIt1 first1, InputIt1 last1,
> >   			 InputIt2 first2, InputIt2 last2)
> > diff --git a/src/libcamera/utils.cpp b/src/libcamera/utils.cpp
> > index d55338fe681a..1eb8970a5bbc 100644
> > --- a/src/libcamera/utils.cpp
> > +++ b/src/libcamera/utils.cpp
> > @@ -127,6 +127,13 @@ std::string dirname(const std::string &path)
> >   	return path.substr(0, pos + 1);
> >   }
> >   
> > +/**
> > + * \fn std::set<typename T::key_type> map_keys(const T &map)
> > + * \brief Retrieve the keys of a std::map<>
> > + * \param[in] map The map whose keys to retrieve
> > + * \return A std::set<> containing the keys of \a map
> > + */
> > +
> >   /**
> >    * \fn libcamera::utils::set_overlap(InputIt1 first1, InputIt1 last1,
> >    *				     InputIt2 first2, InputIt2 last2)
> > diff --git a/test/utils.cpp b/test/utils.cpp
> > index 66b91f1203e1..a9d072030f1c 100644
> > --- a/test/utils.cpp
> > +++ b/test/utils.cpp
> > @@ -6,6 +6,8 @@
> >    */
> >   
> >   #include <iostream>
> > +#include <map>
> > +#include <set>
> >   #include <sstream>
> >   #include <string>
> >   #include <vector>
> > @@ -144,6 +146,25 @@ protected:
> >   		if (TestPass != testDirname())
> >   			return TestFail;
> >   
> > +
> > +		/* utils::map_keys() test. */
> > +		const std::map<std::string, unsigned int> map{
> > +			{ "zero", 0 },
> > +			{ "one", 1 },
> > +			{ "two", 2 },
> > +		};
> > +		const std::set<std::string> expectedKeys{
> > +			"zero",
> > +			"one",
> > +			"two",
> > +		};
> > +
> > +		const std::set<std::string> keys = utils::map_keys(map);
> > +		if (keys != expectedKeys) {
> > +			cerr << "utils::map_keys() test failed" << endl;
> > +			return TestFail;
> > +		}
> > +
> >   		return TestPass;
> >   	}
> >   };
Umang Jain June 26, 2020, 6:14 a.m. UTC | #6
Hi Laurent,

On 6/25/20 7:58 PM, Laurent Pinchart wrote:
> Hi Umang,
>
> On Thu, Jun 25, 2020 at 08:12:12AM +0000, Umang Jain wrote:
>> On 6/25/20 6:53 AM, Laurent Pinchart wrote:
>>> Add a map_keys() function to the utils namespace to extract keys from a
>>> map.
>>>
>>> Signed-off-by: Laurent Pinchart <laurent.pinchart@ideasonboard.com>
>>> ---
>>>    include/libcamera/internal/utils.h | 10 ++++++++++
>>>    src/libcamera/utils.cpp            |  7 +++++++
>>>    test/utils.cpp                     | 21 +++++++++++++++++++++
>>>    3 files changed, 38 insertions(+)
>>>
>>> diff --git a/include/libcamera/internal/utils.h b/include/libcamera/internal/utils.h
>>> index 0953423ee8d0..4fe4843922a9 100644
>>> --- a/include/libcamera/internal/utils.h
>>> +++ b/include/libcamera/internal/utils.h
>>> @@ -11,6 +11,7 @@
>>>    #include <chrono>
>>>    #include <memory>
>>>    #include <ostream>
>>> +#include <set>
>>>    #include <sstream>
>>>    #include <string>
>>>    #include <string.h>
>>> @@ -36,6 +37,15 @@ const char *basename(const char *path);
>>>    char *secure_getenv(const char *name);
>>>    std::string dirname(const std::string &path);
>>>    
>>> +template<typename T>
>>> +std::set<typename T::key_type> map_keys(const T &map)
>>> +{
>>> +	std::set<typename T::key_type> keys;
>>> +	std::transform(map.begin(), map.end(), std::inserter(keys, keys.end()),
>> I am not able to wrap my head around keys.end() as the beginning
>> position for the insertor? keys.end() points to `past-the-end`element
>> which should not be de-referenced, as claimed in the online docs. Can
>> you explain why we cannot use:
>>
>> std::inserter(keys, keys.begin()) ?
> std::inserter() is a helper that return a std::insert_iterator. An
> std::insert_iterator is an iterator that invokes the insert() function of
> the container it is related to in its operator=(). Calling
>
> 	iter = value;
>
> on an std::insert_iterator results in
>
> 	iter = container->insert(iter, value);
> 	++iter;
>
> while calling operator++() directly on the iterator is a no-op.
>
> The insert() function of STL containers takes an iterator as a parameter
> to specify the insertion position. The insertion happens just prior to
> iterator. For std::list and std::vector that's guaranteed, while for
> std::map and std::set that's just a hint: maps and sets are sorted by
> key, so the insertion position depends on the key. Still, passing the
> correct hint to insert() for map and set can help with performances.
Ah Ok. The insertion happening 'just prior to iterator' was the key point
I was missing here. Plus got clear from your explanation about the 
performance
bit of what's happening. Thanks!
>
> Using keys.end() will thus result in the new element being inserted just
> before the end of the container. As they map is sorted by key, the
> std::transform call will insert the keys in the set in increasing order.
> end() is thus the correct hint in that case. begin() would work too, but
> would result in worse performances, as the insert() function would
> realize that the hint is not correct, and will look up the correct
> position. See https://en.cppreference.com/w/cpp/container/map/insert
> that states
>
> Complexity
>
> [...]
>
> 4-6) Amortized constant if the insertion happens in the position just
> before the hint, logarithmic in the size of the container otherwise.
>
>>> +		       [](const auto &value) { return value.first; });
>>> +	return keys;
>>> +}
>>> +
>>>    template<class InputIt1, class InputIt2>
>>>    unsigned int set_overlap(InputIt1 first1, InputIt1 last1,
>>>    			 InputIt2 first2, InputIt2 last2)
>>> diff --git a/src/libcamera/utils.cpp b/src/libcamera/utils.cpp
>>> index d55338fe681a..1eb8970a5bbc 100644
>>> --- a/src/libcamera/utils.cpp
>>> +++ b/src/libcamera/utils.cpp
>>> @@ -127,6 +127,13 @@ std::string dirname(const std::string &path)
>>>    	return path.substr(0, pos + 1);
>>>    }
>>>    
>>> +/**
>>> + * \fn std::set<typename T::key_type> map_keys(const T &map)
>>> + * \brief Retrieve the keys of a std::map<>
>>> + * \param[in] map The map whose keys to retrieve
>>> + * \return A std::set<> containing the keys of \a map
>>> + */
>>> +
>>>    /**
>>>     * \fn libcamera::utils::set_overlap(InputIt1 first1, InputIt1 last1,
>>>     *				     InputIt2 first2, InputIt2 last2)
>>> diff --git a/test/utils.cpp b/test/utils.cpp
>>> index 66b91f1203e1..a9d072030f1c 100644
>>> --- a/test/utils.cpp
>>> +++ b/test/utils.cpp
>>> @@ -6,6 +6,8 @@
>>>     */
>>>    
>>>    #include <iostream>
>>> +#include <map>
>>> +#include <set>
>>>    #include <sstream>
>>>    #include <string>
>>>    #include <vector>
>>> @@ -144,6 +146,25 @@ protected:
>>>    		if (TestPass != testDirname())
>>>    			return TestFail;
>>>    
>>> +
>>> +		/* utils::map_keys() test. */
>>> +		const std::map<std::string, unsigned int> map{
>>> +			{ "zero", 0 },
>>> +			{ "one", 1 },
>>> +			{ "two", 2 },
>>> +		};
>>> +		const std::set<std::string> expectedKeys{
>>> +			"zero",
>>> +			"one",
>>> +			"two",
>>> +		};
>>> +
>>> +		const std::set<std::string> keys = utils::map_keys(map);
>>> +		if (keys != expectedKeys) {
>>> +			cerr << "utils::map_keys() test failed" << endl;
>>> +			return TestFail;
>>> +		}
>>> +
>>>    		return TestPass;
>>>    	}
>>>    };

Patch

diff --git a/include/libcamera/internal/utils.h b/include/libcamera/internal/utils.h
index 0953423ee8d0..4fe4843922a9 100644
--- a/include/libcamera/internal/utils.h
+++ b/include/libcamera/internal/utils.h
@@ -11,6 +11,7 @@ 
 #include <chrono>
 #include <memory>
 #include <ostream>
+#include <set>
 #include <sstream>
 #include <string>
 #include <string.h>
@@ -36,6 +37,15 @@  const char *basename(const char *path);
 char *secure_getenv(const char *name);
 std::string dirname(const std::string &path);
 
+template<typename T>
+std::set<typename T::key_type> map_keys(const T &map)
+{
+	std::set<typename T::key_type> keys;
+	std::transform(map.begin(), map.end(), std::inserter(keys, keys.end()),
+		       [](const auto &value) { return value.first; });
+	return keys;
+}
+
 template<class InputIt1, class InputIt2>
 unsigned int set_overlap(InputIt1 first1, InputIt1 last1,
 			 InputIt2 first2, InputIt2 last2)
diff --git a/src/libcamera/utils.cpp b/src/libcamera/utils.cpp
index d55338fe681a..1eb8970a5bbc 100644
--- a/src/libcamera/utils.cpp
+++ b/src/libcamera/utils.cpp
@@ -127,6 +127,13 @@  std::string dirname(const std::string &path)
 	return path.substr(0, pos + 1);
 }
 
+/**
+ * \fn std::set<typename T::key_type> map_keys(const T &map)
+ * \brief Retrieve the keys of a std::map<>
+ * \param[in] map The map whose keys to retrieve
+ * \return A std::set<> containing the keys of \a map
+ */
+
 /**
  * \fn libcamera::utils::set_overlap(InputIt1 first1, InputIt1 last1,
  *				     InputIt2 first2, InputIt2 last2)
diff --git a/test/utils.cpp b/test/utils.cpp
index 66b91f1203e1..a9d072030f1c 100644
--- a/test/utils.cpp
+++ b/test/utils.cpp
@@ -6,6 +6,8 @@ 
  */
 
 #include <iostream>
+#include <map>
+#include <set>
 #include <sstream>
 #include <string>
 #include <vector>
@@ -144,6 +146,25 @@  protected:
 		if (TestPass != testDirname())
 			return TestFail;
 
+
+		/* utils::map_keys() test. */
+		const std::map<std::string, unsigned int> map{
+			{ "zero", 0 },
+			{ "one", 1 },
+			{ "two", 2 },
+		};
+		const std::set<std::string> expectedKeys{
+			"zero",
+			"one",
+			"two",
+		};
+
+		const std::set<std::string> keys = utils::map_keys(map);
+		if (keys != expectedKeys) {
+			cerr << "utils::map_keys() test failed" << endl;
+			return TestFail;
+		}
+
 		return TestPass;
 	}
 };