Formal Review: Indexed Set
The review of Indexed Set library, written by Joaquín M López Muñoz starts today (March 20) and runs for 10 days. Latest version (9.4) of the library is available on: http://groups.yahoo.com/group/boost/files/indexed_set.zip (328 kB) What it is? indexed_set is generic, STL compliant container providing one or more views on its data. These views allow to use data sorted according to different criteria. Change in container data is automatically propagated into all views. How many views and what ordering is applied is specified in declarative way, as template parameter. What it is good for? - it can replace multiple collections of data and hand-written code keeping them in sync. - it can replace standard containers (as std::set or std::list) if these may not meet future reqirements. - it can serve as basic for other libraries. For example RTL (relational tables library) may use indexed_set to hold its data. Other features of indexed_set: - sorting can be performed on result of member function (similar to calculated indexes in RDBMS). - indexed_set can be used as 'wrapper' over other data structures, e.g you can see data in std::vector as being sorted in set-like structure (but without structures being synchronized). - many, many others ... Future development: - planned functionality is described on its own page in documentation. - indexed_set may also implement access to its data in the same way as std::deque, with random O(1) access History of the project: - it started as 'bimap' library more than year ago, - some two dozen iterations were released, - several Boost people expressed their interest or did suggest features. Boost-wide reusable parts of the library: - indexed_set includes (nearly verbatim) copy of Andrei Alexandresu ScopeGuard. It is intended as stop-gap until Boost wide library emerges. - maybe auto_space.hpp can be liften into utilities. Portability: - see document page for list of compilers and their issues - Can someone try to run tests under release mode of VC 6.5? We got different results with different machines. Word from the autor: "Thank you for reviewing indexed_set. There are several points, mostly concerning naming, that I'd like to be discussed during the review. You can find these at the URL http://groups.yahoo.com/group/boost/files/indexed_set_review_notes.html If you evaluate the library and deem it acceptable for Boost, please walk the extra mile and express your opinions about the issues brought forward in the review notes. Naming issues are quite sensitive, and I'd like to reach as general a consensus as possible." Your review comments are welcomed. Found problems and suggestions for documentation are highly sought. Requests for new features requests may shape way indexed_set will evolve in future. As naming questions can generate lot of mail-list traffic, I'll start separate thread to deal with them. /Pavel
On Fri, Mar 19, 2004 at 11:53:08PM +0100, Pavel Vozenilek wrote:
The review of Indexed Set library, written by Joaqu�n M L�pez Mu�oz starts today (March 20) and runs for 10 days.
Latest version (9.4) of the library is available on: http://groups.yahoo.com/group/boost/files/indexed_set.zip (328 kB)
I spent an hour or two today looking at the docs and trying out the library on some very simple examples. Here are my comments. What is your evaluation of the design? Looks good; I have wished for a container along these lines in the past, and the interface that indexed_set presents seems satisfactory. What is your evaluation of the implementation? I didn't look at it. What is your evaluation of the documentation? I read the "tutorial" and only glanced at the other sections. The documentation is quite good. A few quick comments: Some of the code examples in the tutorial have lines longer than 80 chars and they don't render well in my browser. Breaking the long lines into multiple lines will easily fix this. At one point in the tutorial it says "nth_indexed_type" instead of "nth_index_type". The same (extra "ed") bug is repeated again shortly after the first one. I had to manually #include "boost/indexed_set/sequenced_index.hpp" in addition to #include "boost/indexed_set.hpp" in order to get "sequenced" to work. Not sure if this is a bug in the docs or a bug in the library itself; either it should be included automatically, or else the docs should mention including it manually. The docs mention #define BOOST_INDEXED_SET_ENABLE_INVARIANT_CHECKING for both "safe mode" and "invariant checking mode". I did not look into this enough to decide if there is (or is supposed to be) a different separate flag to set for "safe mode". What is your evaluation of the potential usefulness of the library? At least once in the past I have wanted this functionality myself, and also once others have asked me if I knew a good library for doing this. So I think it will be useful. Did you try to use the library? Yes. With what compiler? g++-3.1.1 Did you have any problems? Of course. :) I uncovered a compiler bug, which was annoying, but irrelevant to the review. (Had to say "es.template get<by_name>()" rather than "es.get<by_name>()", even though it was in a non-dependent context.) At one point, when using tags, I did something like struct by_seq {}; ... sequenced<by_seq> ... // oops, should be sequenced<tag<by_seq> > and got a compiler error. (BTW, the docs are not totally clear here; they should say that you need tag<...>.) Fortunately it was a BOOST_STATIC_ASSERT failure, and inspecting the failing line of code inside the library: ... template <typename TagList=tag<> > struct sequenced { BOOST_STATIC_ASSERT(detail::is_tag<TagList>::value); // this line ... gave me enough of a clue to figure out the problem on my own, so that was very happy. I noted with some dismay that duplicate tags are not detected. That is, you are allowed to say struct by_id {}; struct by_name {}; struct by_foo {}; typedef indexed_set< employee, index_list< unique<tag<by_id,by_foo>,identity<employee> >, non_unique<tag<by_name,by_foo>, member<employee,std::string,&employee::name> > >
employee_set;
where I have named both indices "by_foo". I would prefer it if the library detected this as a BOOST_STATIC_ASSERT-able error. Other than that, things worked pretty smoothly. How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? I spent an hour or two today looking at the docs and trying out the library on some very simple examples. Are you knowledgeable about the problem domain? Not really; I have used std::list and std::set, but never really used a real multiply-indexed data structure or tried to implement one on my own. Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion. Yes. -- -Brian McNamara (lorgon@cc.gatech.edu)
On Fri, 19 Mar 2004 23:53:08 +0100, Pavel Vozenilek wrote
The review of Indexed Set library, written by Joaquín M López Muñoz starts today (March 20) and runs for 10 days.
Latest version (9.4) of the library is available on: http://groups.yahoo.com/group/boost/files/indexed_set.zip (328 kB)
I was unable to unzip this file on Linux -- $ unzip indexed_set.zip Archive: indexed_set.zip End-of-central-directory signature not found. Either this file is not a zipfile, or it constitutes one disk of a multi-part archive. In the latter case the central directory and zipfile comment will be found on the last disk(s) of this archive. Is the sandbox also up to date? It looks like there have been recent changes there. Jeff
Latest version (9.4) of the library is available on: http://groups.yahoo.com/group/boost/files/indexed_set.zip (328 kB)
I was unable to unzip this file on Linux --
It worked for me (RH8; using both file-roller and unzip). The file I have is 336,074 bytes. Did you get a bad download? Darren
On Mon, 22 Mar 2004 07:46:12 +0900, Darren Cook wrote
It worked for me (RH8; using both file-roller and unzip). The file I have is 336,074 bytes. Did you get a bad download?
Yes, that is the problem -- the download I was getting was actually an yahoogroups html login page. Sorry for the noise... Jeff
* What is your evaluation of the design? Looks very useful for 'relational database-ish' tasks (especially if, as is likely, it can be combined with the up-coming serialization library.). * What is your evaluation of the implementation? Not examined, but examples and performance tests look fine. Most compilers work, and all the important 'compilant' ones work without any problems. Extensive tests - also useful examples (I didnt find a link from the documentation which would be easy to provide and prevent people ignoring tests as a source of many helpful examples). Looks (and from version number and history, is) 'mature'. * What is your evaluation of the documentation? Nicely written and accessible tutorial with examples that cover some useful application areas. Covers a wide range of compilers. (The word 'multiindex' doesn't look nice to me - would 'multi-index' be better?) * What is your evaluation of the potential usefulness of the library? Promises to extend the usefulness of STL containers significantly, with hardly any run-time cost. * Did you try to use the library? No use. * How much effort did you put into your evaluation? A long glance. * Are you knowledgeable about the problem domain? Not seriously. * Do you think the library should be accepted as a Boost library? Yes. Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539 561830 +44 7714 330204 mailto: pbristow@hetp.u-net.com | -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of Pavel Vozenilek | Sent: 19 March 2004 22:53 | To: boost@lists.boost.org | Subject: [boost] Formal Review: Indexed Set | | | The review of Indexed Set library, written by | Joaquín M López Muñoz starts today (March 20) | and runs for 10 days. | | | Latest version (9.4) of the library is available on: | http://groups.yahoo.com/group/boost/files/indexed_set.zip | (328 kB) | | | What it is? | indexed_set is generic, STL compliant container | providing one or more views on its data. These views | allow to use data sorted according to different criteria. | Change in container data is automatically | propagated into all views. | | How many views and what ordering is applied is | specified in declarative way, as template parameter. | | | What it is good for? | - it can replace multiple collections of data and | hand-written code keeping them in sync. | - it can replace standard containers (as std::set or | std::list) if these may not meet future reqirements. | - it can serve as basic for other libraries. | For example RTL (relational tables library) may use | indexed_set to hold its data. | | | Other features of indexed_set: | - sorting can be performed on result of member function | (similar to calculated indexes in RDBMS). | - indexed_set can be used as 'wrapper' over other data | structures, e.g you can see data in std::vector | as being sorted in set-like structure (but without | structures being synchronized). | - many, many others ... | | | Future development: | - planned functionality is described on its own page | in documentation. | - indexed_set may also implement access to its data | in the same way as std::deque, with random O(1) access | | | History of the project: | - it started as 'bimap' library more than year ago, | - some two dozen iterations were released, | - several Boost people expressed their interest | or did suggest features. | | | Boost-wide reusable parts of the library: | - indexed_set includes (nearly verbatim) copy | of Andrei Alexandresu ScopeGuard. It is intended | as stop-gap until Boost wide library emerges. | - maybe auto_space.hpp can be liften into utilities. | | | Portability: | - see document page for list of compilers and their issues | - Can someone try to run tests under release mode of VC 6.5? | We got different results with different machines. | | | Word from the autor: | "Thank you for reviewing indexed_set. There are several | points, mostly concerning naming, that I'd like to be discussed | during the review. You can find these at the URL | http://groups.yahoo.com/group/boost/files/indexed_set_review_notes.html If you evaluate the library and deem it acceptable for Boost, please walk the extra mile and express your opinions about the issues brought forward in the review notes. Naming issues are quite sensitive, and I'd like to reach as general a consensus as possible." Your review comments are welcomed. Found problems and suggestions for documentation are highly sought. Requests for new features requests may shape way indexed_set will evolve in future. As naming questions can generate lot of mail-list traffic, I'll start separate thread to deal with them. /Pavel _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Thank you for reviewing indexed_set! Paul A Bristow <boost <at> hetp.u-net.com> writes:
* What is your evaluation of the design?
Looks very useful for 'relational database-ish' tasks (especially if, as is likely, it can be combined with the up-coming serialization library.).
I'll write the serialization stuff as soon as time permits and Robert's library gets accepted. [...]
Extensive tests - also useful examples (I didnt find a link from the documentation which would be easy to provide and prevent people ignoring tests as a source of many helpful examples).
Care to ellaborate? I don't quite get what exactly you are suggesting to include. [...]
* Do you think the library should be accepted as a Boost library?
Yes.
Great! thank you again for the reviewing effort. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
| -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of Joaquin M | Lopez Munoz | Sent: 23 March 2004 14:39 | To: boost@lists.boost.org | Subject: [boost] Re: Formal Review: Indexed Set | | > Extensive tests - also useful examples (I didn't find a | link from the | > documentation which would be easy to provide and prevent | people ignoring | > tests as a source of many helpful examples). | | Care to ellaborate? I don't quite get what exactly you | are suggesting to include. Just a hyperlink from the documentation to the tests directory, or a docs section describing the tests a bit, which would in turn hyperlink to the actual code (.cpp files). But I am sure many people will find the tests useful examples anyway. Paul Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539 561830 +44 7714 330204 mailto: pbristow@hetp.u-net.com
Paul A Bristow <boost <at> hetp.u-net.com> writes:
Just a hyperlink from the documentation to the tests directory, or a docs section describing the tests a bit, which would in turn hyperlink to the actual code (.cpp files).
Maybe you have overlooked the Examples section of the docs? (home->Examples link) Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
No - links to the examples are fine - but links to the tests might also be useful. Paul | -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of Joaquin M | Lopez Munoz | Sent: 24 March 2004 10:54 | To: boost@lists.boost.org | Subject: [boost] Re: Formal Review: Indexed Set | | | Paul A Bristow <boost <at> hetp.u-net.com> writes: | | > | > Just a hyperlink from the documentation to the tests directory, or a | > docs section describing the tests a bit, which would in | turn hyperlink | > to the actual code (.cpp files). | | Maybe you have overlooked the Examples section of the docs? | (home->Examples link) | | Joaquín M López Muñoz | Telefónica, Investigación y Desarrollo | | | _______________________________________________ | Unsubscribe & other changes: | http://lists.boost.org/mailman/listinfo.cg| i/boost | |
Paul A Bristow <boost <at> hetp.u-net.com> writes:
No - links to the examples are fine - but links to the tests might also be useful.
My bad, I wasn't realizing it was the tests you meant. Good idea, I've sketched a test section in the docs, consider it included in the next package. Thanks Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Hello,
The review of Indexed Set library, written by Joaquín M López Muñoz starts today (March 20) and runs for 10 days.
Latest version (9.4) of the library is available on: http://groups.yahoo.com/group/boost/files/indexed_set.zip (328 kB)
Downloaded and installed it sucessfully.
What it is? indexed_set is generic, STL compliant container providing one or more views
I still regard these views more as indices, because they are populated at insertion time IIUC.
on its data. These views allow to use data sorted according to different criteria. Change in container data is automatically propagated into all views.
How many views and what ordering is applied is specified in declarative way, as template parameter.
This I like.
What it is good for? - it can replace multiple collections of data and hand-written code keeping them in sync. - it can replace standard containers (as std::set or std::list) if these may not meet future reqirements. - it can serve as basic for other libraries. For example RTL (relational tables library) may use indexed_set to hold its data.
To try it out I ported the example from http://www.cs.rpi.edu/~musser/stl-book/source/ex18-01.cpp.txt to use indexed_set<>. Port attached. I didn't see a performance penalty. But the test could be IO bound and I didn't profile.
Other features of indexed_set: - sorting can be performed on result of member function (similar to calculated indexes in RDBMS). - indexed_set can be used as 'wrapper' over other data structures, e.g you can see data in std::vector as being sorted in set-like structure (but without structures being synchronized). - many, many others ...
I miserably failed to define a composite unique key for my indexed_set. Should this be possible? One more question: is there an (easy?) way to iterate over the distinct values of an index (or to define the index as the set of distinct values of the related attribute(s))?
Future development: - planned functionality is described on its own page in documentation. - indexed_set may also implement access to its data in the same way as std::deque, with random O(1) access
I'd have to do much more homework to understand the current version.
History of the project: - it started as 'bimap' library more than year ago, - some two dozen iterations were released, - several Boost people expressed their interest or did suggest features.
Good that they did.
Boost-wide reusable parts of the library: - indexed_set includes (nearly verbatim) copy of Andrei Alexandresu ScopeGuard. It is intended as stop-gap until Boost wide library emerges. - maybe auto_space.hpp can be liften into utilities.
Hm.
Portability: - see document page for list of compilers and their issues - Can someone try to run tests under release mode of VC 6.5? We got different results with different machines.
Still somebody developing for that compiler? Incredible.
Word from the autor: "Thank you for reviewing indexed_set. There are several points, mostly concerning naming, that I'd like to be discussed during the review. You can find these at the URL
http://groups.yahoo.com/group/boost/files/indexed_set_review_notes.html
If you evaluate the library and deem it acceptable for Boost,
Yes, I do.
please walk the extra mile and express your opinions about the issues brought forward in the review notes. Naming issues are quite sensitive, and I'd like to reach as general a consensus as possible."
If Joaquín is going to invent indexed_map, too, then indexed_set is OK. Otherwise we seem to be working with something like an indexed_table or table IMHO. Namespace boost would be OK for me. Regular indices are OK, because I didn't need sequenced ones until now ;-). Ordered_(non)_unique would be OK to resolve the std:: name clash, but no strong preference here. No opinion regarding nth_index_type and update/modify/replace. No problem with header dependencies. Best regards, Joerg
Joerg Walter <jhr.walter <at> t-online.de> writes:
Hello,
Hi Joerg, rhanks for reviewing indexed_set! [...]
To try it out I ported the example from http://www.cs.rpi.edu/~musser/stl-book/source/ex18-01.cpp.txt to use indexed_set<>. Port attached. I didn't see a performance penalty. But the test could be IO bound and I didn't profile.
Is it only me, or did you forget to attach the code? [...]
I miserably failed to define a composite unique key for my indexed_set. Should this be possible? One more question: is there an (easy?) way to iterate over the distinct values of an index (or to define the index as the set of distinct values of the related attribute(s))?
Not sure if this is what you're looking for, but please take a look at the compose_key class in example 6 of the examples section. Darren Cook expressed his interest in compose_key being promoted to the library (now it is only part of the example.) [...]
If you evaluate the library and deem it acceptable for Boost,
Yes, I do.
Fine! Thank you.
If Joaquín is going to invent indexed_map, too, then indexed_set is OK.
What should we do then with the namespace indexed_sets? (mind the final 's') Thank you again for your review. Best, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
To try it out I ported the example from http://www.cs.rpi.edu/~musser/stl-book/source/ex18-01.cpp.txt to use indexed_set<>. Port attached. I didn't see a performance penalty. But
Hi Joaquin, you wrote: the
test could be IO bound and I didn't profile.
Is it only me, or did you forget to attach the code?
I miserably failed to define a composite unique key for my indexed_set. Should this be possible? One more question: is there an (easy?) way to iterate over the distinct values of an index (or to define the index as
Nope, we either have a mailing list or an OE problem. Uploaded to http://groups.yahoo.com/group/boost/files/tcs.cpp the
set of distinct values of the related attribute(s))?
Not sure if this is what you're looking for, but please take a look at the compose_key class in example 6 of the examples section.
I already had. Trying to define typedef is::indexed_set< study, is::index_list< is::non_unique<is::tag<student_tag>, is::identity<study>, advisor_comparer>, is::non_unique<is::tag<advisor_tag>, is::identity<study>, date_comparer> is::unique<is::tag<pk_tag>, compose_key< BOOST_INDEXED_SET_MEMBER(study, string, name), BOOST_INDEXED_SET_MEMBER(study, string, advisor) > >,
tcs_genealogy;
failed to compile in compose_key's template<typename Arg> result_type operator()(Arg& arg)const; and I didn't see how to adapt it. [...]
If Joaquín is going to invent indexed_map, too, then indexed_set is OK.
What should we do then with the namespace indexed_sets? (mind the final 's')
If namespace boost is not OK, then namespace boost::container probably would be a better choice. Best, Joerg
Joerg Walter <jhr.walter <at> t-online.de> writes: [...]
Is it only me, or did you forget to attach the code?
Nope, we either have a mailing list or an OE problem. Uploaded to http://groups.yahoo.com/group/boost/files/tcs.cpp
Thanks
I miserably failed to define a composite unique key for my indexed_set.
[...]
I already had. Trying to define
typedef is::indexed_set< study, is::index_list< is::non_unique<is::tag<student_tag>, is::identity<study>, advisor_comparer>, is::non_unique<is::tag<advisor_tag>, is::identity<study>, date_comparer> is::unique<is::tag<pk_tag>, compose_key< BOOST_INDEXED_SET_MEMBER(study, string, name), BOOST_INDEXED_SET_MEMBER(study, string, advisor) > >,
tcs_genealogy;
failed to compile in compose_key's
template<typename Arg> result_type operator()(Arg& arg)const;
Now I think I know what you're after. compose_key composes two keys the way mathematical composition of functions work, i.e. comp_key(arg) := key1(key2(arg)) and this is not what you want to do (if I understood you right.) Instead, you may use lex_compare (as you are already doing in your TCS port.) [...]
If namespace boost is not OK, then namespace boost::container probably would be a better choice.
But I think auxiliary components (index_list, unique, tag, etc.) should have a namespace of their own. They're too specific to inhabit boost::container, IMHO. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On Wed, 24 Mar 2004 10:49:27 +0000 (UTC), Joaquin M Lopez Munoz wrote
If namespace boost is not OK, then namespace boost::container probably would be a better choice.
I believe boost::container would be consistent with the recent move to put string algorithms in boost::algorithm.
But I think auxiliary components (index_list, unique, tag, etc.) should have a namespace of their own. They're too specific to inhabit boost::container, IMHO.
Probably so... Jeff
Hi Joaquin, you wrote:
I miserably failed to define a composite unique key for my indexed_set. [...]
I already had. Trying to define
typedef is::indexed_set< study, is::index_list< is::non_unique<is::tag<student_tag>, is::identity<study>, advisor_comparer>, is::non_unique<is::tag<advisor_tag>, is::identity<study>, date_comparer> is::unique<is::tag<pk_tag>, compose_key< BOOST_INDEXED_SET_MEMBER(study, string, name), BOOST_INDEXED_SET_MEMBER(study, string, advisor) > >,
tcs_genealogy;
failed to compile in compose_key's
template<typename Arg> result_type operator()(Arg& arg)const;
Now I think I know what you're after. compose_key composes two keys the way mathematical composition of functions work, i.e.
comp_key(arg) := key1(key2(arg))
and this is not what you want to do (if I understood you right.) Instead, you may use lex_compare (as you are already doing in your TCS port.)
Yes, something like typedef is::indexed_set< study, is::index_list< is::unique<is::tag<student_tag>, is::identity<const study>, advisor_comparer>, is::non_unique<is::tag<advisor_tag>, is::identity<const study>, date_comparer>
tcs_genealogy;
does what I want. Thanks! [...]
If namespace boost is not OK, then namespace boost::container probably would be a better choice.
But I think auxiliary components (index_list, unique, tag, etc.) should have a namespace of their own. They're too specific to inhabit boost::container, IMHO.
OTOH it might be surprising to search for the components of one library in different namespaces. Two more remarks: 1. Documentation My linux browser (konqueror) has difficulties to correctly display the indexed_set documentation. HTML tidy shows a couple of problems. 2. Performance test Compiling the performance tests with ICC 8.0 uncovered a problem in indexed_set.hpp: 67,69c67,69 < template <typename,typename,typename,typename> friend class detail::index_base; < template <typename,typename> friend class detail::header_holder; < template <typename,typename> friend class detail::converter; ---
template <typename,typename,typename> friend class detail::index_base; template <typename,typename> friend class detail::header_holder; template <typename,typename> friend class detail::converter;
Test results for GCC 3.3.2 1 regular index 10^3 elmts: 141.24% 10^4 elmts: 147.67% 10^5 elmts: 152.57% space gain: 100.00% 1 sequenced index 10^3 elmts: 154.99% 10^4 elmts: 157.43% 10^5 elmts: 153.71% space gain: 100.00% 2 regular indices 10^3 elmts: 108.23% 10^4 elmts: 124.78% 10^5 elmts: 121.79% space gain: 90.00% 1 regular index + 1 sequenced index 10^3 elmts: 123.96% 10^4 elmts: 137.12% 10^5 elmts: 145.98% space gain: 87.50% 3 regular indices 10^3 elmts: 100.11% 10^4 elmts: 119.70% 10^5 elmts: 129.12% space gain: 86.67% 2 regular indices + 1 sequenced index 10^3 elmts: 99.25% 10^4 elmts: 113.62% 10^5 elmts: 116.37% space gain: 84.62% Test results for ICC 8.0 1 regular index 10^3 elmts: 105.45% 10^4 elmts: 106.74% 10^5 elmts: 105.98% space gain: 100.00% 1 sequenced index 10^3 elmts: 112.29% 10^4 elmts: 112.20% 10^5 elmts: 111.43% space gain: 100.00% 2 regular indices 10^3 elmts: 63.17% 10^4 elmts: 67.35% 10^5 elmts: 71.65% space gain: 90.00% 1 regular index + 1 sequenced index 10^3 elmts: 65.19% 10^4 elmts: 69.00% 10^5 elmts: 72.62% space gain: 87.50% 3 regular indices 10^3 elmts: 49.76% 10^4 elmts: 57.97% 10^5 elmts: 60.94% space gain: 86.67% 2 regular indices + 1 sequenced index 10^3 elmts: 49.07% 10^4 elmts: 52.71% 10^5 elmts: 51.55% space gain: 84.62% I don't have an explanation for the difference. Best, Joerg
I forgot to answer one of your questions. Here it comes: Joerg Walter <jhr.walter <at> t-online.de> writes:
One more question: is there an (easy?) way to iterate over the distinct values of an index
You can do it as you would with a std::multiset: typedef indexed_set<...> indexed_t; typedef indexed_t::index_type<...>::type index_t; indexed_t iset; index_t& index=iset.get<...>(); for(index::iterator it=index.begin();it!=index.end()){ // do what you want to with the value // get next value it2=index.upper_bound(index.key_extractor()(*it)); it=it2; }
(or to define the index as the set of distinct values of the related attribute(s))?
This would call for a new type of index, IHMO. Gotta think it over. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Hi Joaquin, you wrote:
I forgot to answer one of your questions. Here it comes:
Joerg Walter <jhr.walter <at> t-online.de> writes:
One more question: is there an (easy?) way to iterate over the distinct values of an index
You can do it as you would with a std::multiset:
typedef indexed_set<...> indexed_t; typedef indexed_t::index_type<...>::type index_t;
indexed_t iset; index_t& index=iset.get<...>();
for(index::iterator it=index.begin();it!=index.end()){ // do what you want to with the value
// get next value it2=index.upper_bound(index.key_extractor()(*it)); it=it2; }
Understood, a non_unique key has multi_set characteristics, whereas a unique key has set characteristics.
(or to define the index as the set of distinct values of the related attribute(s))?
This would call for a new type of index, IHMO. Gotta think it over.
On a second thought: such a beast would be more of a view (losing the relation to indexed_set's original data) and therefore possibly out of scope for your library? Thanks, Joerg
Joerg Walter <jhr.walter <at> t-online.de> writes: [...]
(or to define the index as the set of distinct values of the related attribute(s))?
This would call for a new type of index, IHMO. Gotta think it over.
On a second thought: such a beast would be more of a view (losing the relation to indexed_set's original data) and therefore possibly out of scope for your library?
Maybe. Anyway, this is not going to be implemented anytime soon (the roadmap has other top-priority tasks, most notably serialization support and hashed indices.) Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Hi, Here is my review of indexed_set. What is your evaluation of the design? Fine. I'd have liked an option to be able to attach indexes at run-time as well, but that is probably a completely different container. I'd like to see greater uniformity between sequenced and normal indexes, so I can write generic functions that can take either. I especially did not like that the container as a whole inherits the interface of the first named index. I think this is asking for trouble, and I want to be forced to write get<mytag> for all indexes. What is your evaluation of the implementation? I didn't look at the source code. The error messages were *very* long, even by STL standards. What is your evaluation of the documentation? Fine. I'd like to see more examples. What is your evaluation of the potential usefulness of the library? I have uses in mind for it, mainly for statically analyzing data where I currently tend to use PHP with an SQL back-end: I need something much quicker when the data set gets large; I don't need multi-user access or multiple tables or joins. Did you try to use the library? With what compiler? Yes, with gcc 3.2 (RedHat 8 version). I wrote a test script with a sequenced index, and 5 non-unique indexes. I used a 2nd indexed_set to store counts of occurrences (I could have used a multimap, but I found using indexed_set no harder, and I like that it is expandable). I didn't get around to trying project, or unique indexes, or inserts, or loading it with lots of data. Did you have any problems? Yes, which were all answered by Joaquin. So it worked as I wanted in the end. How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? I read all the docs except the reference page, and then spent about 4 hrs developing my test script. Are you knowledgeable about the problem domain? I've used stl containers before :-). Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion. Yes. Naming? Someone mentioned boost::table, or indexed_table. I like that as it is not too long, is descriptive, and is more suitable now the library is more than just a super std::set. I mentioned before I want to lose one of the "type" words from: index_type<C,T>::type In my test program I had a using namespace boost::indexed_sets; at the top. However the container is unusable without a typedef, and I wrote helper template functions for just about everything I wanted to do, so I can probably not need to do that. Which is a long-winded way of saying I don't care what the namespace name is. Darren
"Darren Cook" <darren@dcook.org> wrote
Here is my review of indexed_set.
Thanks for your review.
Fine. I'd have liked an option to be able to attach indexes at run-time as well, but that is probably a completely different container.
Not really sure I talk about the same thing but it is possible to use indexed_set as 'view' to other containers. E.g: std::vector<MyClass*> x; indexed_set<MyClass*, ...> y; ... fill in y with pointers from x... ... use y ...
I especially did not like that the container as a whole inherits the interface of the first named index. I think this is asking for trouble, and I want to be forced to write get<mytag> for all indexes.
It is feature which allow to use indexed_set instead of set/list/etc. Maybe there some dummy index without any interface could be added into library. /Pavel
Darren Cook <darren <at> dcook.org> writes:
Hi, Here is my review of indexed_set.
Hello Darren, thank you for your contribution! [...]
I'd like to see greater uniformity between sequenced and normal indexes, so I can write generic functions that can take either.
I sketched a little proposal to add some "alias" memfuns to sequenced indices so that the common interface of regular and sequenced indices is broader. The sketch is in a response by mw to Gary Powell yesterday. Have you seen it?
I especially did not like that the container as a whole inherits the interface of the first named index. I think this is asking for trouble, and I want to be forced to write get<mytag> for all indexes.
Ummm... Nobody else complained. As Pavel has explained in other post, this lets you easily replace old code using a stl container with an indexed_set.
The error messages were *very* long, even by STL standards.
Yes, I'm sorry about that, but I cannot figure out some way to shorten these. The types involved are as compact as possible (in the sense that they are parameterized by the minimum amount of arguments possible), but basically if your test program had six indices then error messages will tend to be up to six times as long as those produced by say a std::set, and three times on average. (indices are stacked up on one another.)
Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion.
Yes.
Thank you!
Naming?
Someone mentioned boost::table, or indexed_table. I like that as it is not too long, is descriptive, and is more suitable now the library is more than just a super std::set.
Now I'm collecting all the suggestions of reviewers concerning naming, I'll try to post a naming candidate by the end of the review. So far indexed_set, multi_container, multicontainer, indexed_table and table have been mentioned. table or indexed_table I don't specially like since they are too broad and could clash with future, more SQL-oriented libraries (there are people working on such libraries). My personal leaning is probably multicontainer.
I mentioned before I want to lose one of the "type" words from: index_type<C,T>::type
Yes, me too. I have proposed in a response to Gary Powell an alternative that I like myself: template<int N> struct nth_index; template<typename Tag> struct index; template<int N> struct nth_index_iterator; template<int N> struct nth_index_const_iterator; template<typename Tag> struct index_iterator; template<typename Tag> struct index_const_iterator; Do you love/hate it? Thank you again for the reviewing effort. Best, Joaquín M López Muñoz Telefónica, Investigación y Desarollo
I mentioned before I want to lose one of the "type" words from: index_type<C,T>::type
Yes, me too. I have proposed in a response to Gary Powell an alternative that I like myself:
template<int N> struct nth_index; template<typename Tag> struct index; template<int N> struct nth_index_iterator; template<int N> struct nth_index_const_iterator; template<typename Tag> struct index_iterator; template<typename Tag> struct index_const_iterator;
I currently have (C is indexed_set container type, c is instance of that container, T is index tag): const typename index_type<C,T>::type& myindex=get<T>(c); typename index_type<C,T>::type::const_iterator i=myindex.begin(); Does this become this? const typename index<C,T>& myindex=get<T>(c); typename index_const_iterator<C,T> i=myindex.begin(); Those are both shorter and more readable, so I like them. Darren
Hi Darren Darren Cook ha escrito:
I mentioned before I want to lose one of the "type" words from: index_type<C,T>::type
Yes, me too. I have proposed in a response to Gary Powell an alternative that I like myself:
template<int N> struct nth_index; template<typename Tag> struct index; template<int N> struct nth_index_iterator; template<int N> struct nth_index_const_iterator; template<typename Tag> struct index_iterator; template<typename Tag> struct index_const_iterator;
I currently have (C is indexed_set container type, c is instance of that container, T is index tag): const typename index_type<C,T>::type& myindex=get<T>(c); typename index_type<C,T>::type::const_iterator i=myindex.begin();
Does this become this? const typename index<C,T>& myindex=get<T>(c); typename index_const_iterator<C,T> i=myindex.begin();
Not exactly. It'd be const typename index<C,T>::type& myindex=get<T>(c); typename index_const_iterator<C,T>::type i=myindex.begin(); The "_type" is omitted, but the "::type" cannot be eliminated. BTW, there are alternative wordings to the lines above: const typename C::index<T>::type& myindex=get<T>(c); typename C::index_const_iterator<T>::type i=myindex.begin(); Regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
* What is your evaluation of the design? Well conceived, but I dislike the inheritance of index zero's interface. (More below.) * What is your evaluation of the implementation? The aspects revealed in the documentation are solid. I have not inspected the code. * What is your evaluation of the documentation? Overall: excellent. Some points later. * What is your evaluation of the potential usefulness of the library? It strikes me as a very useful library. There have been many occasions when I've handcrafted a solution for which this library would have sufficed. Indeed, there is a current class we use daily that provides for a runtime selectable sorting criteria, but only offers one choice among several upon instantiation. If the overhead is minimal, it would be advantageous to use Indexed Set to provide multiple views of the underlying data as there are clients that want differing views now. * Did you try to use the library? With what compiler? Did you have any problems? No. * How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? I read the documentation pretty carefully over the course of an hour or two. (As I did it on different days and between other tasks, I can't say with certainty how much time I spent. Writing these comments as I went increased the duration as well.) * Are you knowledgeable about the problem domain? Given that I've created ad hoc solutions in the same vein, yes. However, I have not created a Boosted library, so some aspects exceed my expertise. * Do you think the library should be accepted as a Boost library? Yes, Boost should accept this library. ---------------------- Documentation Issues. The main page mentions "STL-like indices," but I don't think of the Standard Library as providing indices, so this doesn't mean anything to me. While it will complicate matters somewhat, I'd prefer to see the examples written as if "namespace is = boost::indexed_sets" (or similar) were in effect. That would highlight the functionality not already in namespace boost. "Lookup" is only one word when it is used as a noun. When used as a verb, it is spelled "look up." The initial discussion of "regular indices" in the tutorial gave me no idea what they were. Even after the example, I was left wondering what that "regular index" thing actually was. I didn't see anything called "regular index" in the example code. It wasn't until the "Index types" section that I find the definition of a "regular index." Your discussion of modify_key doesn't mention any impact on the Index Set should the new key change the sort order or violate a unique index. I didn't find the use of "far pointer" helpful. It connotes the pointer types germane to segmented memory architectures (old Intel, for example). Since the only thing you're trying to convey is that the pointer-like type indexed_set may see chains to another pointer-like type which may chain to yet another, ad infinitum, may I suggest "chained pointer" instead? Your "safe mode" name is inconsistent with the "invariant-checking mode." The latter clearly indicates what is being checked, whereas the other doesn't. I expected that "safe mode" would be a superset, but it is orthogonal. How about naming it "precondition-checking mode?" A related issue is that you say that invariant-checking can be turned on separately from "safe mode" and that the former indicates an internal error. However, I don't see how you can assert that the failure to maintain an invariant is an internal error if you don't ensure the preconditions were met. IOW, shouldn't turning on invariant-checking mode imply turning on precondition-checking? In Debugging support:Invariant-checking mode, in the advanced topics page, you write:
It is recommended that users of Boost.IndexedSet always set the invariant-checking mode. By default (i.e. if the user has not provided a definition for BOOST_INDEXED_SET_INVARIANT_ASSERT), this mode will not perform any check at all in NDEBUG builds, but it does not have a significant impact in the compiled binary either, so you need not set off invariant-checking for release compilations.
I have two questions. First, why is this information buried in the advanced topics page? The mode should be highlighted in the main documentation path. Second, if the overhead is so small, why not leave it on by default in all builds and then give users a means to disable it? Users can then decide whether to disable it in all builds or only release builds. Both the tutorial and the advanced topics pages claim indexed_set's simulation of std::set, for example, is as efficient as the real thing, yet the performance page shows a 10-20% overhead. You should qualify your claims of equal performance such that you say indexed_set has "nearly" as good performance. ---------------------- Naming Issues. I, too, find "mix" too cute, so "multi_container" is better, but that is rather indicative of implementation and doesn't clearly convey the idea of multiply indexing data. Thus, I'm in favor of "multi_index," but the most recent "multi-index container" notion may be the best course to remove all confusion. I don't like the "non_unique" stuff. I wonder whether it could be dropped altogether, leaving "unique" as a modifier when that property is present. Otherwise, how about "dup" (short for duplicate, in case it wasn't obvious) as a modifier? (You could also use "multi" to mirror the idea behind multiset and multimap.) I think that "get<>" should be named "get_index<>" as that it will read better in use: ... = es.get_index<1>(); "member" and "const_mem_fun" seem to overlap based soley on the names. I suggest that "member" be renamed "data_member" to avoid confusion regarding the use of "member" to invoke a member function. From: Joaquin M Lopez Munoz <joaquin@tid.es>
I think I have something that may please everybody:
template<int N> struct nth_index; template<typename Tag> struct index; template<int N> struct nth_index_iterator; template<int N> struct nth_index_const_iterator; template<typename Tag> struct index_iterator; template<typename Tag> struct index_const_iterator;
I like that approach. ---------------------- Design Issues I don't really like that index 0 is the default behavior. I'd rather an Index Set not behave like any of its indexes. Yes that means you must say get(_index)<0>() when you want the first index, but I like the idea of that being explicit. There's no opportunity to change a typedef from std::list, for example, to boost::indexed_set and silently use the wrong index or silently change the complexities. I don't see indexed_set as a drop-in replacement for existing types, so I don't want it to be easy to do that. I don't like the assymmetry between get<> and the pair nth_indexed_type<> and indexed_type<>. I'd prefer that indexed_type<> be used, like get<>, for either a number or a tag. Why does tag<> accept multiple "names?" Is there a motivating example for why a single name isn't sufficient? I ask because the class is more complicated than it otherwise needs to be. That translates into more documentation to explain it and longer -- by however much -- compilation times. ---------------------- Documentation Nitpicks (Sorry, no diffs.) ------ Tutorial: Rationale:
STL containers are designed about the concept that each ^^^^^ Unless this is a Queen's English way to phrase it, that should be "around."
Introduction:Multiple sorts on a single set: print_out_by_name() in the example code has a comment referencing "i" which should reference "name_index" instead. A bidirectional list with fast lookup:
When performance is a concern, we will need an additional data structure that indexes the elements in tc, presumably by ^^ in
alphabetical order. Boost.IndexedSet allows precisely to do ^^^^^^^^^^^^^^^^^^^^^^ does precisely
this through the combination of sequenced and regular indices:
A bidirectional list with fast lookup:
Now, occurrences and delete_word have logarithmic complexity. The programmer can use index #0 for accessing the text as with std::list, and resort to index #1 when logarithmic ^^^^^^
From the context, the reader may read that as "sort again" rather than "fall back on." I suggest changing "resort to" to "use" to avoid the confusion.
Index specification:
In general, we can specify an arbitrary number of indices: each of the arguments of index_list is called an index specifier. Depending of the type of index being specified, the ^^ on
corresponding specifier will need additional information: for ^^^^^ . For
instance, the specifiers unique and non_unique are provided
Tagging:
If no tag is provided for an index (as it is the case for index ^^^^^ is
#0 of the previous example), accessing to that index can only ^^^^^^^^^ access
Index types:
Regular indices, which sorts the elements like std::sets do, and provide a similar interface. There are unique and
Change to, "Regular indices sort their elements like std::sets do and provide a similar interface."
non-unique variants: the former does not allow for duplicates, ^^^^ do
while the latter permits them (like std::multiset.) ^^^^^^^ permit
Index types:
Sequenced indices are modelled after the semantics and ^^^^^^^^ "modeled" is, to my eye, and the ordering given at m-w.com, the more normal spelling. YMMV.
Index types:Regular indices:Unique and non-unique variants:
For instance, if we augment employee to include an additional member for the Social Security number, which is reasonably ^^^^^^^^^^^^^^^^^^^ enough to be treated as unique, the following captures this ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Either, "which is reasonably treated as unique," or, "which is reasonable enought to treat as unique." Index types:Regular indices:Specification:
The first optional argument is used if tags are associated to ^^ with
Index types:Regular indices:Key extraction:
* The whole element serves as the key, as it is the case of the ^^^^^ is
Index types:Regular indices:Key extraction:
specifies by means of identity that the whole element objects ^^^^^^^^^^^^^^^^^^^^^ element objects themselves
Index types:Regular indices:Key extraction:
Consider the following extension of our example where sorting on the third index is based upon the lenght of the name field: ^^^^^^ length
Index types:Regular indices:Comparison predicates:
These comparison predicates are not different to those used by ^^ from
Index types:Regular indices:Special lookup operations:
Regular STL containers fail to provide this functionality, which often leads to inelegant workarounds: consider for instance the problem of determining the employees whose IDs fall on the range [0,100]. ^^ in
Index types:Regular indices:Special lookup operations:
and write now the search as ^^^^^^^^^ now write
Index types:Regular indices:Special lookup operations:
Here were are not only passing IDs instead of employee objects: ^^^^ we
Index types:Regular indices:Updating:
Updating is a powerful capability not provided by standard STL containers, and one that comes specially handy when strong ^^^^^^^^^^^^^^^ is especially
In the case of update, the original value is kept and the method returns without altering the container, but modify cannot afford such approach, since the modifying functor leaves ^^^^^ such an
no trace of the previous value of the element. Integrity constraints considerations thus lead to the following policy: ^^^^^^^^^^^^^^^^^^^ thus
when a collision happens in the process of calling modify, the element is erased and the method returns false. This difference in behavior between update and modify has to be considered by the programmer on a case-per-case basis. ^^^ by
------ Boost.IndexedSet Advanced topics: Advanced features of Boost.IndexedSet key extractors:
The Key Extractor concept allows for a same object being a key extractor from several different types, possibly through suitably defined overloads of operator():
If I understand what you meant, this makes more sense: The Key Extractor concept allows the same object to extract keys from several different types, possibly through suitably defined overloads of operator(): Use of member_offset:
In these cases, a replacement utility member_offset has been provided that does the work of member at the expense of a less ^^^^ of
convenient notation and the possibility of incurring in ^^^^^^^^^^^^^^^ of
non-conformances with the standard. ^^^^^^^^^^^^ conformance
Debugging support:
C++ does not enjoy direct support for Design by Contract techniques: these are customarily implemented as assertion code, oftenly turned off in release mode for performance ^^^^^^^
often Debugging support:
Boost.IndexedSet safe mode is set by globally defining the macro BOOST_INDEXED_SET_ENABLE_INVARIANT_CHECKING. Error ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ BOOST_INDEXED_SET_ENABLE_SAFE_MODE?
Debugging support:
Warning: Safe mode adds a very important overhead to the ^^^^^^^^^^^^^^^^^^^^^ adds
Simulating standard containers with indexed_set:Simulation of associative containers:
an so the substitution rules are: ^^ and
Metaprogramming and indexed_set:MPL analysis:
Given an indexed_set instantiation, the following nested types are provided for compile-time inspection of the various types concurring in the definition of the indexed_set: ^^^^^^^^^^ occurring
Metaprogramming and indexed_set:MPL analysis:
An subtle but important distinction exists between ^^ A
Metaprogramming and indexed_set:MPL synthesis:
Unfortunately, the intantiation syntax of indexed_set is not oriented to this sort of tasks: ^^^^^ task
Metaprogramming and indexed_set:MPL synthesis:
In the example, mpl_index_list<index_list_t> works as a synonim ^^^^^^^ synonym
-- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;
Hello Rob, thank you for reviewing indexed_set. Rob Stewart ha escrito: [snipped stuffed not needing further comments]
* Do you think the library should be accepted as a Boost library?
Yes, Boost should accept this library.
Fine! I'm glad you like the library. Thank you.
---------------------- Documentation Issues.
The main page mentions "STL-like indices," but I don't think of the Standard Library as providing indices, so this doesn't mean anything to me.
Well the meaning is that indices (italicized as the term is first introduced) have STL-like characteristics. I'd be happy to rewrite this in a cleaner way if only you provided me with a different wording.
While it will complicate matters somewhat, I'd prefer to see the examples written as if "namespace is = boost::indexed_sets" (or similar) were in effect. That would highlight the functionality not already in namespace boost.
I don't quite get it. The docs are written as if the library is already in Boost. Other tutorials in Boost also apply the implicit using policy.
"Lookup" is only one word when it is used as a noun. When used as a verb, it is spelled "look up."
Yep, right. Fixed, thank you.
The initial discussion of "regular indices" in the tutorial gave me no idea what they were. Even after the example, I was left wondering what that "regular index" thing actually was. I didn't see anything called "regular index" in the example code. It wasn't until the "Index types" section that I find the definition of a "regular index."
I'm not sure what I could do to improve this part. Any specific suggestion. I thought it'd be clear indices are wht one specifies with unique<> etc.
Your discussion of modify_key doesn't mention any impact on the Index Set should the new key change the sort order or violate a unique index.
OK. Added a phrase stating this. In case it wasn't clear to you, modify_key has the same semantics as modify (collision->element is erased).
I didn't find the use of "far pointer" helpful. It connotes the pointer types germane to segmented memory architectures (old Intel, for example). Since the only thing you're trying to convey is that the pointer-like type indexed_set may see chains to another pointer-like type which may chain to yet another, ad infinitum, may I suggest "chained pointer" instead?
Pavel also hated the name for the same connotation problems. Well, I'll add it to my list, will change it if I no one else complains.
Your "safe mode" name is inconsistent with the "invariant-checking mode." The latter clearly indicates what is being checked, whereas the other doesn't.
I retained the name "safe mode" because users are likely familiar with the name as given in STLport.
I expected that "safe mode" would be a superset, but it is orthogonal. How about naming it "precondition-checking mode?" A related issue is that you say that invariant-checking can be turned on separately from "safe mode" and that the former indicates an internal error. However, I don't see how you can assert that the failure to maintain an invariant is an internal error if you don't ensure the preconditions were met. IOW, shouldn't turning on invariant-checking mode imply turning on precondition-checking?
I'd like to give maximum flexibility to the user. Your reasoning is correct, but then again you can follow your own advice in your program and never enable invariant-checking without enabling safe mode also. I guess you're for stricter enforcing of this.
In Debugging support:Invariant-checking mode, in the advanced topics page, you write:
It is recommended that users of Boost.IndexedSet always set the invariant-checking mode. By default (i.e. if the user has not provided a definition for BOOST_INDEXED_SET_INVARIANT_ASSERT), this mode will not perform any check at all in NDEBUG builds, but it does not have a significant impact in the compiled binary either, so you need not set off invariant-checking for release compilations.
I have two questions. First, why is this information buried in the advanced topics page? The mode should be highlighted in the main documentation path.
I thought the tutorial was hard enough as it was and decided to move all the non-essential stuff to a different page. Admittedly, other topics covered in this section are really much more advanced.
Second, if the overhead is so small, why not leave it on by default in all builds and then give users a means to disable it? Users can then decide whether to disable it in all builds or only release builds.
I think I'll remove this piece of advice: invariant-checking can be left on in release builds, but it won't do anything unless BOOST_INDEXED_SET_INVARIANT_ASSERT has been defined by the user). To sum it up, it's a pretty useless recommendation: withouth redefining the assert macro, users won't get anything by leaving the mode set on in release mode.
Both the tutorial and the advanced topics pages claim indexed_set's simulation of std::set, for example, is as efficient as the real thing, yet the performance page shows a 10-20% overhead. You should qualify your claims of equal performance such that you say indexed_set has "nearly" as good performance.
You're right. Added the "nearly" qualifier in the tutorial bit. In the advanced topics section, the efficient is said to be "comparable", which is IMHO fair enough.
---------------------- Naming Issues.
I, too, find "mix" too cute, so "multi_container" is better, but that is rather indicative of implementation and doesn't clearly convey the idea of multiply indexing data. Thus, I'm in favor of "multi_index," but the most recent "multi-index container" notion may be the best course to remove all confusion.
I don't like the "non_unique" stuff. I wonder whether it could be dropped altogether, leaving "unique" as a modifier when that property is present. Otherwise, how about "dup" (short for duplicate, in case it wasn't obvious) as a modifier? (You could also use "multi" to mirror the idea behind multiset and multimap.)
I don't like the idea of having "_unique" and no counterpart for non-unique indices (this was discussed here months ago, and the (IMHO correct) conclusion is that both variants should have a qualifying suffix. I'm for descriptive names, so dup seems just too obscure. non_unique resonates well with people into RDBMS stuff.
I think that "get<>" should be named "get_index<>" as that it will read better in use:
... = es.get_index<1>();
"member" and "const_mem_fun" seem to overlap based soley on the names. I suggest that "member" be renamed "data_member" to avoid confusion regarding the use of "member" to invoke a member function.
Thanks for all comments regarding naming. I'll try to balance everybody's opinions and come up with some final proposal to post to the list. get_index<> I like, though get<> was chosen for sympathy with Boost.Tuple (similar names for similar concepts.) [...]
---------------------- Design Issues
I don't really like that index 0 is the default behavior. I'd rather an Index Set not behave like any of its indexes. Yes that means you must say get(_index)<0>() when you want the first index, but I like the idea of that being explicit. There's no opportunity to change a typedef from std::list, for example, to boost::indexed_set and silently use the wrong index or silently change the complexities. I don't see indexed_set as a drop-in replacement for existing types, so I don't want it to be easy to do that.
Darren also disliked this approach. To me it has some value: in a sense, the first index is treated as the primary one (which in many situations really is). Put another way, what disadvantages do you find in having the default behavior?
I don't like the assymmetry between get<> and the pair nth_indexed_type<> and indexed_type<>. I'd prefer that indexed_type<> be used, like get<>, for either a number or a tag.
I'd prefer it also, but AFAIK it cannot be done. You just cannot "overload" a template to accept type and non-type arguments.
Why does tag<> accept multiple "names?" Is there a motivating example for why a single name isn't sufficient? I ask because the class is more complicated than it otherwise needs to be. That translates into more documentation to explain it and longer -- by however much -- compilation times.
No movitating example that I know of. It was implemented like that cause having multiple tags was no harder than having just one.
---------------------- Documentation Nitpicks
[...] Man, you did a *thorough* proofreading. Thanks so much for the nitpicking, I'll validate and apply your changes. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
From: =?iso-8859-1?Q?Joaqu=EDn=20M=AA=20L=F3pez=20Mu=F1oz?= <joaquin@tid.es>
Rob Stewart ha escrito:
The main page mentions "STL-like indices," but I don't think of the Standard Library as providing indices, so this doesn't mean anything to me.
Well the meaning is that indices (italicized as the term is first introduced) have STL-like characteristics. I'd be happy to rewrite this in a cleaner way if only you provided me with a different wording.
Rereading the text, I think that you're trying to say that the various indices one can configure in an indexed_set have interfaces like those of the container types provided in the STL, making using them familiar.
While it will complicate matters somewhat, I'd prefer to see the examples written as if "namespace is = boost::indexed_sets" (or similar) were in effect. That would highlight the functionality not already in namespace boost.
I don't quite get it. The docs are written as if the library is already in Boost. Other tutorials in Boost also apply the implicit using policy.
Other documentation notwithstanding, I'm suggesting that all of the pieces that come from your library be highlighted by an "is::" prefix so they stand apart from the other components used in the examples. IOW, any lambda, mpl, tuples, etc. code would be unqualified, through the use of "using namespace ..." and the Indexed Set code would be distinct.
The initial discussion of "regular indices" in the tutorial gave me no idea what they were. Even after the example, I was left wondering what that "regular index" thing actually was. I didn't see anything called "regular index" in the example code. It wasn't until the "Index types" section that I find the definition of a "regular index."
I'm not sure what I could do to improve this part. Any specific suggestion. I thought it'd be clear indices are wht one specifies with unique<> etc.
Here's what you've written: "Boost.IndexedSet features regular indices, designed to help programmers in need of sequences of elements for which more than one sorting criteria are relevant." I note that "regular indices" is a forward link to the definition, but this still leaves the reader confused here. That is, if the reader doesn't want to jump to another context, but wants to continue reading the tutorial here, then there's no help to understand "regular indices." Here is a suggestion for rewriting that sentence: Boost.IndexedSet features "regular" indices, which are sorted by keys using predicates, and were designed to help programmers in need of sequences of elements for which more than one sorting criteria are relevant. The difference is the "short and sweet" definition of a "regular" index that allows the reader to continue in the current context.
Your "safe mode" name is inconsistent with the "invariant-checking mode." The latter clearly indicates what is being checked, whereas the other doesn't.
I retained the name "safe mode" because users are likely familiar with the name as given in STLport.
I've never used STLport, so that carries no significance for me. I'm still in favor of being explicit and consistent.
I expected that "safe mode" would be a superset, but it is orthogonal. How about naming it "precondition-checking mode?" A related issue is that you say that invariant-checking can be turned on separately from "safe mode" and that the former indicates an internal error. However, I don't see how you can assert that the failure to maintain an invariant is an internal error if you don't ensure the preconditions were met. IOW, shouldn't turning on invariant-checking mode imply turning on precondition-checking?
I'd like to give maximum flexibility to the user. Your reasoning is correct, but then again you can follow your own advice in your program and never enable invariant-checking without enabling safe mode also. I guess you're for stricter enforcing of this.
You're right, the user can decide to always enable "safe mode" when using "invariant-checking mode" but if they are likely to get incorrect information, why allow them to avoid it?
In Debugging support:Invariant-checking mode, in the advanced topics page, you write:
It is recommended that users of Boost.IndexedSet always set the invariant-checking mode. By default (i.e. if the user has not provided a definition for BOOST_INDEXED_SET_INVARIANT_ASSERT), this mode will not perform any check at all in NDEBUG builds, but it does not have a significant impact in the compiled binary either, so you need not set off invariant-checking for release compilations.
I have two questions. First, why is this information buried in the advanced topics page? The mode should be highlighted in the main documentation path.
I thought the tutorial was hard enough as it was and decided to move all the non-essential stuff to a different page. Admittedly, other topics covered in this section are really much more advanced.
The point is that this issue isn't "advanced." It is part of normal usage of the library. Indeed, it is quite possibly of more use to less advanced users.
Both the tutorial and the advanced topics pages claim indexed_set's simulation of std::set, for example, is as efficient as the real thing, yet the performance page shows a 10-20% overhead. You should qualify your claims of equal performance such that you say indexed_set has "nearly" as good performance.
You're right. Added the "nearly" qualifier in the tutorial bit. In the advanced topics section, the efficient is said to be "comparable", which is IMHO fair enough.
Right.
---------------------- Design Issues
I don't really like that index 0 is the default behavior. I'd rather an Index Set not behave like any of its indexes. Yes that means you must say get(_index)<0>() when you want the first index, but I like the idea of that being explicit. There's no opportunity to change a typedef from std::list, for example, to boost::indexed_set and silently use the wrong index or silently change the complexities. I don't see indexed_set as a drop-in replacement for existing types, so I don't want it to be easy to do that.
Darren also disliked this approach. To me it has some value: in a sense, the first index is treated as the primary one (which in many situations really is). Put another way, what disadvantages do you find in having the default behavior?
First, it depends upon how one views indexed_set. On the one hand, you can see it as a drop-in replacement for another container that happens to permit adding additional indices. Thus, the original code is largely unaffected by the substitution and new code can be written to take advantage of the new capabilities. OTOH, you can see indexed_set as a completely different animal with different performance characteristics that happens to work similarly to existing containers. The similarity means that programming with an indexed_set is familiar, but the new capabilities require conscious application to ensure the differences are properly accounted for. My view is the second one, but I can understand the value of the first.
I don't like the assymmetry between get<> and the pair nth_indexed_type<> and indexed_type<>. I'd prefer that indexed_type<> be used, like get<>, for either a number or a tag.
I'd prefer it also, but AFAIK it cannot be done. You just cannot "overload" a template to accept type and non-type arguments.
I haven't looked at the code, but I'm confused. How can one use type and non-type arguments with get<> but not with the others?
Why does tag<> accept multiple "names?" Is there a motivating example for why a single name isn't sufficient? I ask because the class is more complicated than it otherwise needs to be. That translates into more documentation to explain it and longer -- by however much -- compilation times.
No movitating example that I know of. It was implemented like that cause having multiple tags was no harder than having just one.
The explanation of indexed_set, if not its implementation, is more difficult. Without any reason for this "feature," it adds unwarranted complexity. Granted, you've said it wasn't any harder to support multiple tags, and the tutorial section on multiple tag support is very short. Still, it smacks of a solution in search of a problem. Perhaps someone else can envision a good use for this feature? -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;
Hi Rob Rob Stewart ha escrito:
From: =?iso-8859-1?Q?Joaqu=EDn=20M=AA=20L=F3pez=20Mu=F1oz?= <joaquin@tid.es>
Rob Stewart ha escrito:
The main page mentions "STL-like indices," but I don't think of the Standard Library as providing indices, so this doesn't mean anything to me.
Well the meaning is that indices (italicized as the term is first introduced) have STL-like characteristics. I'd be happy to rewrite this in a cleaner way if only you provided me with a different wording.
Rereading the text, I think that you're trying to say that the various indices one can configure in an indexed_set have interfaces like those of the container types provided in the STL, making using them familiar.
Yeah. Rephrased it, hope it reads better now: "The Boost.IndexedSet library provides a class template named indexed_set which enables the construction of containers maintaining one or more indices with different sorting and access semantics. Indices provide interfaces similar to those of STL containers, making using them familiar." [...]
Other documentation notwithstanding, I'm suggesting that all of the pieces that come from your library be highlighted by an "is::" prefix so they stand apart from the other components used in the examples. IOW, any lambda, mpl, tuples, etc. code would be unqualified, through the use of "using namespace ..." and the Indexed Set code would be distinct.
Ummm... gotta think of it.
Boost.IndexedSet features "regular" indices, which are sorted by keys using predicates, and were designed to help programmers in need of sequences of elements for which more than one sorting criteria are relevant.
The difference is the "short and sweet" definition of a "regular" index that allows the reader to continue in the current context.
OK, I'll change that.
Your "safe mode" name is inconsistent with the "invariant-checking mode." The latter clearly indicates what is being checked, whereas the other doesn't.
I retained the name "safe mode" because users are likely familiar with the name as given in STLport.
I've never used STLport, so that carries no significance for me. I'm still in favor of being explicit and consistent.
I dissent here. Safe mode IMHO is popular enough. [...]
I have two questions. First, why is this information buried in the advanced topics page? The mode should be highlighted in the main documentation path.
I thought the tutorial was hard enough as it was and decided to move all the non-essential stuff to a different page. Admittedly, other topics covered in this section are really much more advanced.
The point is that this issue isn't "advanced." It is part of normal usage of the library. Indeed, it is quite possibly of more use to less advanced users.
I'll think of it. I don't feel comfortable with this section being in the tutorial, which is more about concepts than configuration. [...]
I don't like the assymmetry between get<> and the pair nth_indexed_type<> and indexed_type<>. I'd prefer that indexed_type<> be used, like get<>, for either a number or a tag.
I'd prefer it also, but AFAIK it cannot be done. You just cannot "overload" a template to accept type and non-type arguments.
I haven't looked at the code, but I'm confused. How can one use type and non-type arguments with get<> but not with the others?
get<> is a function template, index_type is a class template. Future revisions of the language may allow for class template overloading, if I'm not wrong. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
From: =?iso-8859-1?Q?Joaqu=EDn=20M=AA=20L=F3pez=20Mu=F1oz?= <joaquin@tid.es>
Rob Stewart ha escrito:
From: =?iso-8859-1?Q?Joaqu=EDn=20M=AA=20L=F3pez=20Mu=F1oz?= <joaquin@tid.es>
Rob Stewart ha escrito:
Yeah. Rephrased it, hope it reads better now:
"The Boost.IndexedSet library provides a class template named indexed_set which enables the construction of containers maintaining one or more indices with different sorting and access semantics. Indices provide interfaces similar to those of STL containers, making using them familiar."
That is better.
I have two questions. First, why is this information buried in the advanced topics page? The mode should be highlighted in the main documentation path.
I thought the tutorial was hard enough as it was and decided to move all the non-essential stuff to a different page. Admittedly, other topics covered in this section are really much more advanced.
The point is that this issue isn't "advanced." It is part of normal usage of the library. Indeed, it is quite possibly of more use to less advanced users.
I'll think of it. I don't feel comfortable with this section being in the tutorial, which is more about concepts than configuration.
I think the problem is you have two extremes: tutorial and advanced. A third category of documentation, normal, could alleviate the problem. Most of the documentation should be part of the normal category, some of it -- simplified, glossing over details -- goes in the tutorial, and some of it -- the stuff most won't care to know or won't need except for certain circumstances -- goes in the advanced section. Thus, your tutorial section could be pared down, with some of the existing content moved to the "normal" section. Also, some of the "advanced" content can move to the "normal" section. Having done that, the mode control fits nicely in the "normal" section. What do you call the "normal" documentation? I don't know. Maybe the key is to have more, smaller sections referenced in the TOC such that "Tutorial" and "Advanced Topics" are just two of the entries.
I don't like the assymmetry between get<> and the pair nth_indexed_type<> and indexed_type<>. I'd prefer that indexed_type<> be used, like get<>, for either a number or a tag.
I'd prefer it also, but AFAIK it cannot be done. You just cannot "overload" a template to accept type and non-type arguments.
I haven't looked at the code, but I'm confused. How can one use type and non-type arguments with get<> but not with the others?
get<> is a function template, index_type is a class template. Future revisions of the language may allow for class template overloading, if I'm not wrong.
Not only is that little detail obvious from the name (the "_type") but looking back at the tutorial, it is clear that indexed_type is a class template. Furthermore, get is always called, so it is obviously a function template. All I can say is, doh! I'm sorry for the noise. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;
Rob Stewart <stewart <at> sig.com> writes:
First, it depends upon how one views indexed_set. On the one hand, you can see it as a drop-in replacement for another container that happens to permit adding additional indices. Thus, the original code is largely unaffected by the substitution and new code can be written to take advantage of the new capabilities.
OTOH, you can see indexed_set as a completely different animal with different performance characteristics that happens to work similarly to existing containers. The similarity means that programming with an indexed_set is familiar, but the new capabilities require conscious application to ensure the differences are properly accounted for.
My view is the second one, but I can understand the value of the first.
I thought that the value of this facility was when you could replace an existing STL container with an indexed_set when you had a need to a second index, without disrupting the code that was already accessing the existing container. In this situation, the existing code, unchanged, uses the default index, while new code can be added which explicitly uses the additional index/indices to gain the advantages of the new characteristics. While it seems to increase the chance of erroneous usage, it strikes me as a useful characteristic.
No movitating example that I know of. It was implemented like that cause having multiple tags was no harder than having just one.
The explanation of indexed_set, if not its implementation, is more difficult. Without any reason for this "feature," it adds unwarranted complexity. Granted, you've said it wasn't any harder to support multiple tags, and the tutorial section on multiple tag support is very short. Still, it smacks of a solution in search of a problem.
Perhaps someone else can envision a good use for this feature?
I can't. Not only does it make indexed_set harder to understand, it becomes more difficult to understand code which uses indexed_sets with multiply-tagged indices. Whilst reading someone else's code, it would be confusing to find that searches tagged 'named' are really exactly the same as searches tagged 'by_name'... I think this facility should be removed, unless there's a compelling argument in its favour. Matt
Hi Matthew Matthew Vogt ha escrito: [multiple tags per index]
Perhaps someone else can envision a good use for this feature?
I can't. Not only does it make indexed_set harder to understand, it becomes more difficult to understand code which uses indexed_sets with multiply-tagged indices.
Whilst reading someone else's code, it would be confusing to find that searches tagged 'named' are really exactly the same as searches tagged 'by_name'...
I think this facility should be removed, unless there's a compelling argument in its favour.
Well, your arguments seem convincing. I'll remove the facility (thus allowing just one tag per index) unless someone else complains. After all, this can be plugged again in the future should the necessity arise. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
I believe you should leave in the support for multiple tags per index. Possible use cases include: - Including the key type as an index tag. - Using tags to flag various fields for some other algorithm -- in this case, different fields could be flagged for use by various different algorithms. - Easier for generic programming. -- Jeremy Maitin-Shepard
From: Matthew Vogt <mvogt@juptech.com>
Rob Stewart <stewart <at> sig.com> writes:
First, it depends upon how one views indexed_set. On the one hand, you can see it as a drop-in replacement for another container that happens to permit adding additional indices. Thus, the original code is largely unaffected by the substitution and new code can be written to take advantage of the new capabilities.
OTOH, you can see indexed_set as a completely different animal with different performance characteristics that happens to work similarly to existing containers. The similarity means that programming with an indexed_set is familiar, but the new capabilities require conscious application to ensure the differences are properly accounted for.
My view is the second one, but I can understand the value of the first.
I thought that the value of this facility was when you could replace an existing STL container with an indexed_set when you had a need to a second index, without disrupting the code that was already accessing the existing container.
In this situation, the existing code, unchanged, uses the default index, while new code can be added which explicitly uses the additional index/indices to gain the advantages of the new characteristics.
You're right. That does sound valuable, but I didn't walk away from reading the documentation with that idea. I just saw it as inconsistent treatment of the first index. Maybe it was there and I'm just blind.
While it seems to increase the chance of erroneous usage, it strikes me as a useful characteristic.
That is useful, but only if the resulting indexed_set is sufficiently semantically similar to the container it replaces. indexed_set doesn't provide the subscript operator, so the replacement won't be seamless if you use that operator on a map. There are other differences which may cause problems. However, I haven't got any experience with these problems or with it working well, so I'm speaking entirely theoretically. If there are important behavioral differences between std::set and an indexed_set configured like a set, or between std::map and an indexed_set configured like a set (other than the missing operator, which will simply fail to compile), or between std::list and an indexed_set configured like a list, then silent substitution doesn't seem appropriate. If the differences are unimportant semantically or if they only change a constant in the complexity guarantees, for example, then silent substitution is appropriate. I'm not qualified to judge this, but I'm sure Joaquín is. IIRC, get<0>() works, but is not necessary. Given that, generic code won't have to treat the first index differently than the others, so that aspect seems fine, regardless of whether it inherits the interface of the first index. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;
Rob Stewart ha escrito:
From: Matthew Vogt <mvogt@juptech.com>
I thought that the value of this facility was when you could replace an existing STL container with an indexed_set when you had a need to a second index, without disrupting the code that was already accessing the existing container.
In this situation, the existing code, unchanged, uses the default index, while new code can be added which explicitly uses the additional index/indices to gain the advantages of the new characteristics.
You're right. That does sound valuable, but I didn't walk away from reading the documentation with that idea. I just saw it as inconsistent treatment of the first index. Maybe it was there and I'm just blind.
FWIW, this was a concious decision, not an implementation artifact (removing it would involve substituting a "protected" for a "public", that's all). Although not explicitly stated, the idea is certainly that one can replace an STL container with indexed_set and have most of the original code working without surprises. Please take a look at the section "A bidirectional list with fast lookup" in the tutorial, where it is shown how replacing std::list with indexed_set<string,index_list<sequenced<>,...> > keeps preexisting user code usable. A more philosopical rationale behind this decision is that the first index is thought of as the "primary" one, and probably the user will access this index more frequently than the others. For instance indexed_set< int, index_list< unique<identity<int> >, sequenced<>
can be regarded as a set with an insertion log, while indexed_set< int, index_list< sequenced<>, unique<identity<int> >
will more likely be thought of as a list with fast lookup. However, both types are tecnhically the same, save the default get<0>() thing.
While it seems to increase the chance of erroneous usage, it strikes me as a useful characteristic.
That is useful, but only if the resulting indexed_set is sufficiently semantically similar to the container it replaces. indexed_set doesn't provide the subscript operator, so the replacement won't be seamless if you use that operator on a map. There are other differences which may cause problems. However, I haven't got any experience with these problems or with it working well, so I'm speaking entirely theoretically.
If there are important behavioral differences between std::set and an indexed_set configured like a set, or between std::map and an indexed_set configured like a set (other than the missing operator, which will simply fail to compile), or between std::list and an indexed_set configured like a list, then silent substitution doesn't seem appropriate. If the differences are unimportant semantically or if they only change a constant in the complexity guarantees, for example, then silent substitution is appropriate. I'm not qualified to judge this, but I'm sure Joaquín is.
The situation wrt drop-in replacement is summarized in the advanced topics, section "Simulating standard containers with indexed_set". Briefly put, sets are emulated exactly, multisets with tiny syntactic differences, and lists with the main drawback that elements are no longer mutable (save with update() and modify()). Map simulation, OTOH, is probably not suitable for drop-in replacement. Also, AFAICS replacement is safe in the sense that the original code either no longer compiles or works with the original semantics (complexity changes, though.)
IIRC, get<0>() works, but is not necessary. Given that, generic code won't have to treat the first index differently than the others, so that aspect seems fine, regardless of whether it inherits the interface of the first index.
That's exact. Regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
From: =?iso-8859-1?Q?Joaqu=EDn=20M=AA=20L=F3pez=20Mu=F1oz?= <joaquin@tid.es>
Rob Stewart ha escrito:
From: Matthew Vogt <mvogt@juptech.com>
I thought that the value of this facility was when you could replace an existing STL container with an indexed_set when you had a need to a second index, without disrupting the code that was already accessing the existing container.
You're right. That does sound valuable, but I didn't walk away from reading the documentation with that idea. I just saw it as inconsistent treatment of the first index. Maybe it was there and I'm just blind.
Although not explicitly stated, the idea is certainly that one can replace an STL container with indexed_set and have most of the original code working without surprises. Please take a look
I think it should be stated explicitly. If nothing else, it will beat folks like me over the head with the obvious!
at the section "A bidirectional list with fast lookup" in the tutorial, where it is shown how replacing std::list with indexed_set<string,index_list<sequenced<>,...> > keeps preexisting user code usable.
I remember reading that, but I didn't think of it in terms of, "See? You can switch to indexed_set without changing existing code plus you can start using additional indices." I do recall reading that one might choose to use an indexed_set just to get the added capabilities aside from extra indices.
A more philosopical rationale behind this decision is that the first index is thought of as the "primary" one, and probably the user will access this index more frequently than the others. For instance
You're probably right that the "primary" index is likely to be the first one specified, when there is a primary index. However, there are just as likely to be uses of indexed_set in which none of the indices is preeminent.
indexed_set< int, index_list< unique<identity<int> >, sequenced<>
can be regarded as a set with an insertion log, while
indexed_set< int, index_list< sequenced<>, unique<identity<int> >
will more likely be thought of as a list with fast lookup. However, both types are tecnhically the same, save the default get<0>() thing.
In a sense, though, that's an argument against inheriting the first index's interface. By promoting one over the others, you give it special significance which it actually doesn't have (beyond syntax, of course).
If there are important behavioral differences between std::set and an indexed_set configured like a set, or between std::map and an indexed_set configured like a set (other than the missing operator, which will simply fail to compile), or between std::list and an indexed_set configured like a list, then silent substitution doesn't seem appropriate. If the differences are unimportant semantically or if they only change a constant in the complexity guarantees, for example, then silent substitution is appropriate. I'm not qualified to judge this, but I'm sure Joaquín is.
The situation wrt drop-in replacement is summarized in the advanced topics, section "Simulating standard containers with indexed_set". Briefly put, sets are emulated exactly, multisets with tiny syntactic differences, and lists with the main drawback that elements are no longer mutable (save with update() and modify()). Map simulation, OTOH, is probably not suitable for drop-in replacement. Also, AFAICS replacement is safe in the sense that the original code either no longer compiles or works with the original semantics (complexity changes, though.)
Since the performance degradation of single-index indexed_sets relative to "normal" containers is documented, one has to assume that the switch from a "normal" container to an indexed_set was done considering performance to gain something else. Therefore, the only remaining issue is whether user code can silently change behavior when switching to indexed_set. Your sense is that this is not a problem, so I withdraw my complaint over making index 0 default. It wouldn't hurt to remove the default, but it doesn't concern me anymore. However, if subsequent broader usage reveals problems with it, I think you should change it so that users must make a conscious choice to use index 0. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;
Hi This is my review of the indexed set library. * What is your evaluation of the design? Overall I find the design well thought out. I'm impressed by the amount of functionality available without "bloat". I don't feel quite comfortable with the assymetry of index-0 not needing a get<> accessor. I'd prefer forcing the use of get<> everywhere but I guess I can live with it if thats decided. More real-world usage should reveal wether a substantional amount of use-cases naturally benefit from this bias. I also second the requests for lifting an implementation of a bidirectional_map/set to official status. But I don't expect nor demand this to be added before acceptance, I'm fine with it being a reasonable prioritized roadmap feature. Serialization support is also high on my wish-list (but with same remarks as above). * What is your evaluation of the implementation? I only browsed the source and it looked good (but see the coding style issue below) -I think it would be better if the iterators (index_iterator.hpp) were generated using boost.iterator_facade/adapter instead of the boost.operators helper. This would make it easier to adapt and for example directly support the new iterator concepts. -This is more of a "feeling", but could perhaps (parts of?) the 'member' functionality be refactored to use boost::bind/mem_fn code instead? * What is your evaluation of the documentation? I found the documentation to be very good. Stylish, with nice examples and "bonus-material" like a performance section and an encouraging roadmap! Some nitpicks: -In the example at the end of the tutorials section ('Projection of iterators') I think it would be clearer if it would use equal_range instead. -I find the coding style to be slightly too compact. No space after ',' and '&' etc makes it more difficult to quickly browse. Why not just follow the semi-official boost coding guidelines? (currently found in the file area) -Several of the code example in the tutorial section could be slightly reformatted to use less horizontal screen space (see for example the 'Key extraction' part). I'd rather scroll vertically than horizontally! Simply pulling in some of the end of line comments would fix most of it. * What is your evaluation of the potential usefulness of the library? Very useful! Many times I've had the need for a container like this. (I even found an old sketchbook of mine illustrating this storage<->views concept, (it was marked Todo.. ;-)Synchronized views, bidirectionality etc can now quickly and _robustly_ be added to programs, greatly simplifiying code And improving efficiency. * Did you try to use the library? With what compiler? Did you have any problems? Yes, altough not as much as I hoped :( I did some simpler tests based on examples and then I added bidirectional lookup to a smaller program previously using a std::set<> + brute-force.. ;-) I used VC7.1 and experienced no particular problems. Hope to be able to use it in larger scale shortly. * How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? Something inbetween, diffucult estimating nr of hours. I did download and browsed docs etc of many of the intermediate versions appearing during the development also. * Are you knowledgeable about the problem domain? I'm fairly fluent in STL and most of Boost. I've had ideas for this kind of storage previously but never got around to research and implement anything this comprehensive. * Do you think the library should be accepted as a Boost library? Yes, I vote for acceptance. I'm sure I'll be using this fine lib in many apps to come. I thank Joaquín for his efforts! Regards //Fredrik Blomqvist (I pass the naming issues since I don't feel I've anything to add that hasn't been said already.)
participants (12)
-
Brian McNamara -
Darren Cook -
Fredrik Blomqvist -
Jeff Garland -
Jeremy Maitin-Shepard -
jhr.walter＠t-online.de -
Joaquin M Lopez Munoz -
Joaquín Mª López Muñoz
-
Matthew Vogt -
Paul A Bristow -
Pavel Vozenilek -
Rob Stewart