[boost::multi-index] improvement suggestion
Hello all, working with boost multi-index container requires sometimes some effort in regards of correct tagging (or at least some typing work ;). I found the following approach to be useful and may be it can be integrated in the multi-index library. First of all the dealing with searchable collections (STL collections are no exception) can be really nasty in regards of finding an iterator and comparing it with the end iterator. The following function can really be of help: /// template function to dermine if the container contains the key specified /// @param T - container type /// @param K - key type /// @param container - container to search for a key /// @param key - key to be found in the container /// \return iterator_range containing the begin and end iterator of the found key. begin iterator equals end iterator the range is empty => nothing found template<class T, class K> inline boost::iterator_range<typename T::const_iterator> find_range(T const& container, K const& key) { return boost::make_iterator_range(container.find(key),container.end ()); } //non-const version follows as well ... Actually iterator_range defines a "bool"- and "!"- (NOT) operators. iterator_range is returned by this function. Therefore constructs like: std::set<std::string> some_set; if(!find_range(some_set, "my_key")) some_set.insert("my_key"); are possible without the need of accesing the underlying iterator types or explicitly comparing the found iterator with the end iterator. The next step dealing with Multi-Index container turned out in multiple typedefs for every tagged type. The main disadvantage in this approach was to constantly retrieve the required container view and related iterator, so I came up the the following class: /// helper class used to retrieve multi-index values dependent on the view tag template<class Tag_, class MultiIndex_> struct value_retrieval { /// type definition used to produce tag dependent view typedef typename MultiIndex_::index<Tag_>::type view_type; /// type definition for the const iterator through the view typedef typename view_type::const_iterator citer_type; /// iterator range used to represent the result typedef boost::iterator_range<citer_type> result_type; /// initializing ctor /// initializes the contained view by using the specified Tag_ type value_retrieval(MultiIndex_ const& mi) : view_(mi.get<Tag_>()) {} /// find a type at the key specified /// @param LookUpType_ - key type /// @param key - key instance to be found template<class LookUpType_> result_type at(LookUpType_ const& key)const { return find_range(view_, key); } private: /// view reference view_type const& view_; }; This class deals with constant views, since I did not require changeable ones, but as one can see the "at"-function can either be used to identify the found iterator range or just to make a check if such a key exists. Dealing with this type is more easier, as to define multi-index accessed view and iterator types. Sample typedef multi_index_container < some_type , indexed_by < .... >
my_container;
typedef value_retrieval<my_container, tag_name> by_name; typedef value_retrieval<my_container, tag_value> by_value; //somewhere in code by_name value_by_name(some_container_inst); //if typename is required prefix it... by_name::result_type r = value_by_name.at("some key"); if(r) /// do smth with r Best Regards, Ovanes
Hello Ovanes, ----- Mensaje original ----- De: Ovanes Markarian <om_boost@keywallet.com> Fecha: Lunes, Agosto 20, 2007 1:35 pm Asunto: [Boost-users] [boost::multi-index] improvement suggestion Para: boost-users@lists.boost.org
Hello all,
working with boost multi-index container requires sometimes some effort in regards of correct tagging (or at least some typing work ;). I found the following approach to be useful and may be it can be integrated in the multi-index library.
First of all the dealing with searchable collections (STL collections are no exception) can be really nasty in regards of finding an iterator and comparing it with the end iterator. The following function can really be of help:
[...]
template<class T, class K> inline boost::iterator_range<typename T::const_iterator> find_range(T const& container, K const& key) { return boost::make_iterator_range( container.find(key),container.end()); }
//non-const version follows as well ...
Actually iterator_range defines a "bool"- and "!"- (NOT) operators. iterator_range is returned by this function. Therefore constructs like: std::set<std::string> some_set;
if(!find_range(some_set, "my_key")) some_set.insert("my_key");
are possible without the need of accesing the underlying iterator types or explicitly comparing the found iterator with the end iterator.
I've got some doubts about your construct: 1. The syntax to check whether a value has been found or not is certainly clearer, but at the expense of a more convoluted expression to get the value found: const std::string& v= *boost::begin(find_range(some_set,"my_key")); And the type of the construct returned by find_range is also somewhat messy to type down (at least until compilers come with decltype and auto): boost::iterator_range<std::set<std::string>::const_iterator> r= find_range(...); 2. If, given the complexities associated to getting the value with find_range, you propose it only as a way to verify whether the value exists, there are simpler alternatives which do not use Boost.Range: template<class T,class K> bool there_exists(T const& container, K const& key) { return container.find(key)!=container.end(); } 3. find_range does return a range, but this range is in no sensible way related to the key passed, except that its first element, if the range is not void, contains the key. But the rest of the elements have nothing to do with the key, and what is worse, elements with the key might not be contained in the range, since find does not guarantee that the element found is the first one with the key. 4. So, if you want a concise syntax to determine whether an element is found or not, plus simple access to this element, maybe you can write an utility of your own exactly suited to this task, rather than relying on Boost.Range. I'm thinking about something like this: // locator can be pointing to an element or not. If the // former, dereferencing it is legal. template<typename Container> struct locator { typedef typename Container::value_type; operator bool()const; bool operator!()const; const value_type& operator*()const; ... }; template<class T,class K> locator<T> find(T const& container, K const& key) { ... } Don't you find this more convenient?
The next step dealing with Multi-Index container turned out in multipletypedefs for every tagged type. The main disadvantage in this approach was to constantly retrieve the required container view and related iterator, so I came up the the following class:
[...] This also could benefit of a more specific locator-based interface, IMHO. Best, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Joaquin, thanks for your reply. I have to think about your suggestions. Some ideas which come up to my mind now are: 1. Locator is clearly a better choice, but not always. In some use cases you might find a range if a container allows multi-indexed values. In this case one would need to make second search to find subsequent values??? Or miss them at all... 2. In the example with: boost::iterator_range<std::set
<std::string>::const_iterator> r= find_range(...);
The class value_retrieval contains a result_type which provides the shortcut to iterator_range<...> 3. My idea in using iterator range relies on fact that one can retrieve a valid or invalid range and operate on it within one search. Your idea with there_exists requires a second search to retrieve the value. Since a typical use case would be: if(there_exists(some_container, "some_key")) some_value = *some_container.find("some_key"); and that is not so efficient as: iter_range range = find_range(some_container, "some_key"); if(range) some_value = range.front(); I will think about other suggestions and mail them later in ;) Many thanks again, Ovanes On 8/21/07, "JOAQUIN LOPEZ MU?Z" <joaquin@tid.es> wrote:
Hello Ovanes,
----- Mensaje original ----- De: Ovanes Markarian <om_boost@keywallet.com> Fecha: Lunes, Agosto 20, 2007 1:35 pm Asunto: [Boost-users] [boost::multi-index] improvement suggestion Para: boost-users@lists.boost.org
Hello all,
working with boost multi-index container requires sometimes some effort in regards of correct tagging (or at least some typing work ;). I found the following approach to be useful and may be it can be integrated in the multi-index library.
First of all the dealing with searchable collections (STL collections are no exception) can be really nasty in regards of finding an iterator and comparing it with the end iterator. The following function can really be of help:
[...]
template<class T, class K> inline boost::iterator_range<typename T::const_iterator> find_range(T const& container, K const& key) { return boost::make_iterator_range( container.find(key),container.end()); }
//non-const version follows as well ...
Actually iterator_range defines a "bool"- and "!"- (NOT) operators. iterator_range is returned by this function. Therefore constructs like: std::set<std::string> some_set;
if(!find_range(some_set, "my_key")) some_set.insert("my_key");
are possible without the need of accesing the underlying iterator types or explicitly comparing the found iterator with the end iterator.
I've got some doubts about your construct:
1. The syntax to check whether a value has been found or not is certainly clearer, but at the expense of a more convoluted expression to get the value found:
const std::string& v= *boost::begin(find_range(some_set,"my_key"));
And the type of the construct returned by find_range is also somewhat messy to type down (at least until compilers come with decltype and auto):
boost::iterator_range<std::set<std::string>::const_iterator> r= find_range(...);
2. If, given the complexities associated to getting the value with find_range, you propose it only as a way to verify whether the value exists, there are simpler alternatives which do not use Boost.Range:
template<class T,class K> bool there_exists(T const& container, K const& key) { return container.find(key)!=container.end(); }
3. find_range does return a range, but this range is in no sensible way related to the key passed, except that its first element, if the range is not void, contains the key. But the rest of the elements have nothing to do with the key, and what is worse, elements with the key might not be contained in the range, since find does not guarantee that the element found is the first one with the key.
4. So, if you want a concise syntax to determine whether an element is found or not, plus simple access to this element, maybe you can write an utility of your own exactly suited to this task, rather than relying on Boost.Range. I'm thinking about something like this:
// locator can be pointing to an element or not. If the // former, dereferencing it is legal.
template<typename Container> struct locator { typedef typename Container::value_type; operator bool()const; bool operator!()const; const value_type& operator*()const; ... };
template<class T,class K> locator<T> find(T const& container, K const& key) { ... }
Don't you find this more convenient?
The next step dealing with Multi-Index container turned out in multipletypedefs for every tagged type. The main disadvantage in this approach was to constantly retrieve the required container view and related iterator, so I came up the the following class:
[...]
This also could benefit of a more specific locator-based interface, IMHO.
Best,
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
----- Mensaje original ----- De: Ovanes Markarian <om_boost@keywallet.com> Fecha: Martes, Agosto 21, 2007 1:27 pm Asunto: Re: [Boost-users] [boost::multi-index] improvement suggestion Para: boost-users@lists.boost.org
Joaquin,
thanks for your reply. I have to think about your suggestions. Some ideaswhich come up to my mind now are: 1. Locator is clearly a better choice, but not always. In some use cases you might find a range if a container allows multi-indexed values. In this caseone would need to make second search to find subsequent values??? Or miss them at all...
I take you meant "duplicate values" rather than "multi-indexed values", right? If so, yes I agree with you a range is the proper object to return, but you'd have to use equal_range instead of find.
2. In the example with: boost::iterator_range<std::set <std::string>::const_iterator> r= find_range(...);
The class value_retrieval contains a result_type which provides the shortcut to iterator_range<...>
Correct, this'd make the syntax terser.
3. My idea in using iterator range relies on fact that one can retrieve a valid or invalid range and operate on it within one search. Your idea with there_exists requires a second search to retrieve the value. Since a typical use case would be:
if(there_exists(some_container, "some_key")) some_value = *some_container.find("some_key");
and that is not so efficient as:
iter_range range = find_range(some_container, "some_key"); if(range) some_value = range.front();
OK, then a locator seems to me to provide a nicer syntax in one single call than your first approach based on ranges. My point is only that your approach has a nice interface for checking if the value exists but not so much for accessing the actual value.
I will think about other suggestions and mail them later in ;)
Thank you for using Boost.MultiIndex and thinking up ways to improve the experience it provides. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Ovanes Markarian <om_boost <at> keywallet.com> writes:
[very useful code]
Can U cut'n'Paste this below <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl? Library_Specific_Pages>, so I can find it again later this year? Markus
participants (3)
-
"JOAQUIN LOPEZ MU?Z" -
Markus Werle -
Ovanes Markarian