[Formal review] Collection Traits library

Hi all, The review of the Collection Traits library, written by Thorsten Ottosen starts today (April 28th, 2004) and runs for 10 days (until May 7th, 2004). The Latest version of the library is available at (yahoo files sections): http://tinyurl.com/ysbaj (72 kB) or in the Boost sandbox. What is it? The Collection Traits library is mainly a tool for writing generic algorithms that work on External Collections. A Collection is a subset of the container requirements; it is so small and essential that it can be made to work with standard containers, iterator-views, built-in arrays and strings by defining a new requirement, the External Collection Concept, where typedefs and functions have been made free-standing instead of members. The library consists of two components: (1) type generators and (2) free-standing functions. The type-generators provide types such as iterators and size_type of external collections whereas the Free-standing functions are for extracting iterators and size of the external collections. Here is a small example: // Example: extracting bounds in generic algorithms template< typename ExternalCollection, typename T > inline typename boost::iterator_of<ExternalCollection>::type find( ExternalCollection& c, const T& value ) { return std::find( boost::begin( c ), boost::end( c ), value´); } template< typename ExternalCollection, typename T > inline typename boost::const_iterator_of<ExternalCollection>::type find( const ExternalCollection& c, const T& value ) { return std::find( boost::begin( c ), boost::end( c ), value´); } // replace first value and return its index template< typename EC, typename T > inline typename boost::size_type_of< EC >::type my_generic_replace( EC& c, const T& value, const T& replacement ) { boost::iterator_of<EC>::type found = find( c, v ); *found = replacement; return std::distance( boost::begin( c ), found ); } // usage std::vector<int> my_vector; typedef vector<int>::iterator iterator; std::pair<iterator,iterator> my_view( my_vector.begin(), my_vector.begin() + N ); char str[] = "a string"; // ... std::cout << my_generic_replace( my_vector, 4, 2 ) << my_generic_replace( my_view, 4, 2 ) << my_generic_replace( str, 'a', 'b' ); As the External Concepts idea is a rather new one, I would like to ask you to comment on this. Please always state in your review, whether you think the library should be accepted as a Boost library! Additionally please consider giving feedback on the following general topics: - What is your evaluation of the design? - What is your evaluation of the implementation? - What is your evaluation of the documentation? - What is your evaluation of the potential usefulness of the library? - Did you try to use the library? With what compiler? Did you have any problems? - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? - Are you knowledgeable about the problem domain? Regards Hartmut Review Manager

Please always state in your review, whether you think the library should be accepted as a Boost library!
Yes. I'd use this library today if it were part of Boost.
As the External Concepts idea is a rather new one, I would like to ask you to comment on this.
It strikes me as a new name for an idiom that's been known for some time but which never had a good name. I'm not convinced that External Concept is a good name, but it's a start. I'd like to see a more formal treatment of the definition of External Concept than is provided by the documentation included with this library. The documentation that's provided I found sufficient, it's just of a different style than other concept documentation.
Additionally please consider giving feedback on the following general topics:
- What is your evaluation of the design? - What is your evaluation of the implementation?
No criticism. For the most part, the design and implementation is straightforward and easy to understand. Workarounds are apparently provided for less-capable compilers (although I didn't evaluate any such compilers). I'm happy to see that this library is almost completely self contained which makes it much easier to understand and use (especially when confronted with compiler errors, for example).
- What is your evaluation of the documentation?
Sufficient. It's a simple library with simple documentation.
- What is your evaluation of the potential usefulness of the library?
Very useful.
- Did you try to use the library? With what compiler? Did you have any problems?
I built all of the supplied test programs with both VC7.1 and VC8 (alpha, build 40309). The algorithm_example program crashed on exit when built with the VC8 alpha, but that's likely a VC8 problem and not a problem with this library. I intend to test again with a newer build when I have a chance.
- How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
I spent about an hour, reading all of the supplied documentation, all of the referenced documentation, most of the test programs and much of the implementation code.
- Are you knowledgeable about the problem domain?
Sufficiently knowledgeable :-) -cd

Hi Carl, Thanks for your review. There is one special issue, you mentioned. | > As the External Concepts idea is a rather new one, I would like to | > ask you | > to comment on this. | | It strikes me as a new name for an idiom that's been known for some time but | which never had a good name. I'm not convinced that External Concept is a | good name, but it's a start. I'll all open to suggestions. I guess the options are these: 1. Don't define External Concepts at all; treat this library as a special case that don't happen that often 2. Define External Concepts, but find a better name - Freestanding Concept ? - Canonical Concept ? | I'd like to see a more formal treatment of the | definition of External Concept than is provided by the documentation | included with this library. ok. | The documentation that's provided I found | sufficient, it's just of a different style than other concept documentation. ok. I don't think the definition of concepts are that much more elaborate. What could be much better is the example which could follow normal concept standards. Is that what you had in mind? br Thorsten

Thorsten Ottosen wrote:
The documentation that's provided I found sufficient, it's just of a different style than other concept documentation.
ok. I don't think the definition of concepts are that much more elaborate. What could be much better is the example which could follow normal concept standards. Is that what you had in mind?
Yes. -cd

Hartmut Kaiser <hartmutkaiser <at> t-online.de> writes:
Please always state in your review, whether you think the library should be accepted as a Boost library!
Yes, it should be accepted.
- What is your evaluation of the design? The CollectionConcept appears well defined and useful. The ExternalConcept approach taken is immediatley easy to understand.
- What is your evaluation of the implementation? Only glanced at it. Looks clean/straightforward.
- What is your evaluation of the documentation? Good. It was possible to get an immediate feel for what the library could do and how to use it. More detailed information was easy to find, and quite sufficient.
- What is your evaluation of the potential usefulness of the library? I could immediately see potential applications eg. I have used the iterator adaptors library to produce a flattening iterator, which allows an (outer) container of (inner) containers to be accessed as if it were a single container of the inner type. The library would make extending this adaptor to support collections (inner and outer) that are not containers very stright forward.
- Did you try to use the library? With what compiler? Did you have any problems? I have yet to try to use the library.
- How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? A quick reading.
- Are you knowledgeable about the problem domain? Reasonably, as an STL user.
Regards Darryl.

The review of the Collection Traits library, written by Thorsten Ottosen starts today (April 28th, 2004) and runs for 10 days (until May 7th, 2004).
I think the library should become part of Boost. It would be useful to have many more examples in documentation, showing how to use it together with other Boost libraries. I collected few notes (mostly nitpicks) on the code and docs, bellow. /Pavel _______________________________________________________ 1. config.hpp: #ifdef __BORLANDC__ #define BOOST_CT_DEDUCED_TYPENAME #else #define BOOST_CT_DEDUCED_TYPENAME BOOST_DEDUCED_TYPENAME #endif ==>> #include <boost/detail/workaround.hpp> // BCB (6.4) has problems here with keyword 'typename' and these // problems are not always fixed by simply using BOOST_DEDUCED_TYPENAME. #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) # define BOOST_CT_DEDUCED_TYPENAME #else # define BOOST_CT_DEDUCED_TYPENAME BOOST_DEDUCED_TYPENAME #endif #if _MSC_VER <= 1200 #define BOOST_CT_NO_ARRAY_SUPPORT #endif ====>> (probably) #if BOOST_WORKAROUND(BOOST_MSVC, <= 1200) # define BOOST_CT_NO_ARRAY_SUPPORT #endif The macros as BOOST_CT_NO_ARRAY_SUPPORT may be better named BOOST_COLLECTION_TRAITS_NO_ARRAY_SUPPORT. The CT thing is rather nonintuitive and may clash. The macros here should have some description - some of them look rather obscure, like BOOST_ARRAY_REF. BOOST_ARRAY_REF: should it be BOOST_COLLECTION_TRAITS_ARRAY_REF? _______________________________________________________ 2. docs: shouldn't there be index.html somewhere? Collection.html should be collection.html. The *.php files are maybe not needed for users to see. _______________________________________________________ 3. Collection.html: - "associated" should be explained - more models can be added - the email at the bottom may be better obfuscated _______________________________________________________ 4. external_concepts.html: the docs doesn't say _where_ the free standing function should be, aboyt their visibility. It should be also noted whether ADL lookup may kick in here or not. _______________________________________________________ 5. docs: maybe instead of showing 'raw' source code in examples syntax colorized HTML can be shown (both 'inline' and external examples). _______________________________________________________ 6. examples in docs: each example should have at the end expected output as comment. _______________________________________________________ 7. iterator_of name: wouldn't just iterator be sufficient? Dtto size_type_of etc. _______________________________________________________ 8. collection_traits.html, first example: typename boost::const_iterator_of<EC>::type found = find( c, value ); *found = replacement; Will it always work with const iterator? And even if it will, shouldn't there be non-const iterator for peace in mind? What if nothing is found in the example? my_generic_replace ==>> my_replace_first _______________________________________________________ 9. collection_traits.html, Reference section: are slist/hash_XXX/rope supported? Will boost::unordered_map/set be supported? boost::bitset, boost::array, spirit iterators? circular_buffer and maybe multi_index_container? ptr_containers? _______________________________________________________ 10. collection_traits.html, Semantics section, tables: it doesn't make sense to me what middle column contains. _______________________________________________________ 11. examples/iterator.cpp: const char* this_file = "iterator.cpp"; ==>> const char* this_file = __FILE__; Some comments in the file would be useful. _______________________________________________________ 12. collection_traits.html, Portability section: bcc6 ==>> BCB 6.4 _______________________________________________________ 13. collection_traits.html: I would definitely welcome many more small code snippets as examples. _______________________________________________________ 14. collection_traits.html: there are many <br> at the end of HTML text. It feels as if something was cut from the file. maybe <br><i>EOF</i> can be there. _______________________________________________________ 15. I hope string algorithms library will re-use this library before it gets into official Boost distribution. _______________________________________________________ 16. I once thought about having typedef boost::end and containers with overload of operator[]. It would allow to write: a_container[boost::end - 1] to access last element of container. a_container[boost::end - 2] would be one before the last one. Python has such feature. Is there some way to have such support in Container Traits? Maybe the library can provide function as boost::last(c, int n): int x = boost::last(vec, -2); _______________________________________________________ 17. collection_traits.hpp: the name of macro guard BOOST_CONTAINER_TRAITS_HPP should be changed. Dtto elsewhere. _______________________________________________________ 18. value_type.hpp: comments as ////////////////////////////////////////////////////////////////////////// // pair ////////////////////////////////////////////////////////////////////////// are not particularly valuable. If necessary, it should be complete sentence. _______________________________________________________ 20. value_type.hpp: do overloads for volatile make sense in this library? (I ask only for completeness and prefere not to clutter library with them.) _______________________________________________________ 21. value_type.hpp: shouldn't there be #include <iosfwd> or so for istream definition? OTOH why is #include <cstddef> there? (Dtto elsewhere.) _______________________________________________________ 22. sizer.hpp: is the template< std::size_t sz > class container_traits_size { char give_size[sz]; }; immune against padding/alignement? The file sizer may be moved into details and names size_calculator.hpp or so. _______________________________________________________ 23. headers: in guard like #if defined(_MSC_VER) && (_MSC_VER >= 1020) # pragma once #endif sometimes value 1020 and sometimes value 1200 is used. Both are OK from practical point of view but it would feel better if the same. _______________________________________________________ 24. docs: there should be step-by-step example how to add support for new container (e.g. scattered array consisting of few subarrays). _______________________________________________________ 25. end.hpp: what is #undef BOOST_END_IMPL doing here? Why such dangerous name is used? _______________________________________________________ 26. testing Unicode string for being empty: I read somewhere Unicode files have two characters at the beginning to indicate endianess. I do not know if this applies to strings in memory as well. If so, then maybe Container Traits or String Algos should take care about this. (I could talk complete nonsense on this topic.) _______________________________________________________ 27. functions.hpp: what is BOOST_STRING_TYPENAME and where does it come from? _______________________________________________________ 28. implementation_help.hpp: strlen() should be used instead of for( ; s[0] != end; ) ++s; strlen/wstrlen may be better optimized. In inline T* array_end( T BOOST_ARRAY_REF[sz], char_or_wchar_t_array_tag ) { return array + sz - 1; } there should be static assert sz > 0. GCC allows zero size arrays. _______________________________________________________ 29. sfinae.hpp: isn't the file name misleading? _______________________________________________________ 30. result_iterator.hpp: what does the "give up" note there mean? _______________________________________________________ 31. functions.hpp\: some commenst should be added. The source has 21 kB. The MPL expressions here are quite complex... _______________________________________________________ 32. functions.hpp: in list of types char, signed char, unsigned char, signed short, unsigned short, signed int, unsigned int, signed long, shouldn't floats and long long/__int64 be there as well? _______________________________________________________ 33. each header should have short comment on the top what is it for, especially the ones in detail/ _______________________________________________________ 34. functions.hpp: is the reference e.g. in template< typename P > static result_iterator begin( P& p ) { return p; } necessary? I assume 'p' is always pointer. If not, maybe call_traits<P>::valuue_type cvan be used. _______________________________________________________ 35. naming conventions: maybe names as iterator_ should be replaced with something else. Underscore is easy to miss and is quite unusual. _______________________________________________________ EOF

Hi Pavel, Thanks for your comments. They are very thoughrough as usual. | It would be useful to have many more examples in documentation, | showing how to use it together with other Boost libraries. Can you give an example of what you have in mind? | _______________________________________________________ | 1. config.hpp: [snip proper code] I haven't studied the config very much, so thanks for your tutorial. | The macros as BOOST_CT_NO_ARRAY_SUPPORT may be better | named BOOST_COLLECTION_TRAITS_NO_ARRAY_SUPPORT. | | The CT thing is rather nonintuitive and may clash. agree. | BOOST_ARRAY_REF: should it be BOOST_COLLECTION_TRAITS_ARRAY_REF? that seems reasonable. | _______________________________________________________ | 2. docs: shouldn't there be index.html somewhere? There should be one. Hartmut said it should be in the "root" ie. libs/collection_traits/index.html. | The *.php files are maybe not needed for users to see. he he, no. | _______________________________________________________ | 3. Collection.html: | | - "associated" should be explained yeah. I guess what it says it that reference_type_of<T>::type need only be convertible to T&. I am inclined to remove that requirement because I fail to see why it is useful. | - more models can be added any container, since it is weaker than the container requirement | - the email at the bottom may be better obfuscated yeah :-) I would think it wouldn't work anymore. | _______________________________________________________ | 4. external_concepts.html: the docs doesn't say _where_ | the free standing function should be, aboyt their | visibility. that should be added. 1. they can be anywhere since ADL will find the right version 2. It only makes sense for a public interface | It should be also noted whether ADL lookup may kick in here | or not. it must ... which implies the implementation for different types can reside in different namespace as long as client code uses *unqualified* calls to the functions. this means that I need to explain how to add support for more types. Eg, begin() should be overloaded in namespace boost. _______________________________________________________ | 5. docs: maybe instead of showing 'raw' source code in examples | syntax colorized HTML can be shown (both 'inline' and external | examples). yes. | _______________________________________________________ | 6. examples in docs: each example should have at the end | expected output as comment. yes. | _______________________________________________________ | 7. iterator_of name: wouldn't just iterator be sufficient? | | Dtto size_type_of etc. people have expressed concern for those short names when they were class in namespace boost, so I changed it. but I'm sure the review manager will record your opinion. | _______________________________________________________ | 8. collection_traits.html, first example: | | typename boost::const_iterator_of<EC>::type found = find( c, value ); | *found = replacement; | | Will it always work with const iterator? And even if | it will, shouldn't there be non-const iterator | for peace in mind? its a doc error. The actual example uses iterator_of<> as it should. | What if nothing is found in the example? | | my_generic_replace ==>> my_replace_first yeah, that should be fixed... if( found != boost::end( c ) ) ... else ; | _______________________________________________________ | 9. collection_traits.html, Reference section: | are slist/hash_XXX/rope supported? | | Will boost::unordered_map/set be supported? | | boost::bitset, boost::array, spirit iterators? | | circular_buffer and maybe multi_index_container? | | ptr_containers? all standard compliant containers work without problems. That's the first bullet in the reference section. I guess I should stress that the container need not be part of the standard. So that include AFAICT slist, robe, array, unordered_map/set, circular_buffer, ptr_container bitsets don't have iterators, so they are not included. multi_index_container? I can't remember if it fulfills the standard container requirements. spirit iterators...only if they inherit from std::iterator. (I can see my iterator implementation is actually broken :-() _______________________________________________________ | 10. collection_traits.html, Semantics section, tables: | it doesn't make sense to me what middle column contains. ok, would a table with --------------Abbreviations----------- SC = std container T = the type used in arrays P = std::pair etc help ? | _______________________________________________________ | 11. examples/iterator.cpp: | | const char* this_file = "iterator.cpp"; | | ==>> | | const char* this_file = __FILE__; | | Some comments in the file would be useful. ok. | _______________________________________________________ | 12. collection_traits.html, Portability section: | | bcc6 ==>> BCB 6.4 I'm just curious, did you compile the test with that compiler? | _______________________________________________________ | 13. collection_traits.html: I would definitely welcome | many more small code snippets as examples. ok. If any other reviewer wants to donate examples, please do. | _______________________________________________________ | 14. collection_traits.html: there are many <br> at the | end of HTML text. It feels as if something was cut | from the file. maybe <br><i>EOF</i> can be there. ok. | _______________________________________________________ | 15. I hope string algorithms library will re-use this | library before it gets into official Boost distribution. I'm working with Pavol on that as we speak. But I think it is boost policy not to include a library accepted too close to the new version, so maybe Pavol needs to use an internal version anyway. | _______________________________________________________ | 16. I once thought about having typedef boost::end | and containers with overload of operator[]. | | It would allow to write: | | a_container[boost::end - 1] | | to access last element of container. | | a_container[boost::end - 2] would be one before | | the last one. Python has such feature. | | | Is there some way to have such support in Container | Traits? so you're describing a search facility for [] containers. it will work a bit strange with map, wouldn't it? we can't use boost::end, but maybe boost::last. In some sense it correponds to typename reverse_iterator_of<T>::type i; i[0] = .. i[1] = .. or rbegin()[0] = ...; rbegin()[1] = ...; Maybe that could justify having reverse_iterator_of<> and const_reverse_iterator_of<> + rbegin(), rend(). ? | Maybe the library can provide function as | boost::last(c, int n): | | int x = boost::last(vec, -2); I guess you would want this to work with any collection. And it seems to be another way to search. Anyway, would'nt we need to versions: n_before_end( 2, vec ); n_after_begin( 2, vec ); ? | _______________________________________________________ | 17. collection_traits.hpp: the name of macro guard | BOOST_CONTAINER_TRAITS_HPP should be changed. | | Dtto elsewhere. yep. | _______________________________________________________ | 18. value_type.hpp: comments as | | | ////////////////////////////////////////////////////////////////////////// | // pair | | ////////////////////////////////////////////////////////////////////////// | | are not particularly valuable. | If necessary, it should be complete sentence. they are mostly a way to seperate code in blocks. | _______________________________________________________ | 20. value_type.hpp: do overloads for volatile make sense | in this library? (I ask only for completeness and prefere | not to clutter library with them.) I'm not sure, but I think they don't make sense. What will happen is that you will iterate over volatile vector<int> vec; using normal iterators. As usual--we don't have volatile_iterator vector<T>::begin() volatile either. | _______________________________________________________ | 21. value_type.hpp: | shouldn't there be #include <iosfwd> or so | for istream definition? it should be enough with <iterator> when I fix the implementation. | OTOH why is #include <cstddef> there? (Dtto elsewhere.) std::size_t | _______________________________________________________ | 22. sizer.hpp: is the | | template< std::size_t sz > | class container_traits_size | { | char give_size[sz]; | }; | | immune against padding/alignement? no. It's not part of the official interface. The real version should be something like char sizer( T (&array)[sz] )[sz] but I decided not to include it. I failed to see it as particular important. a macro a la BOOST_ARRAY_SIZE( a ) \ sizeof((a)) / sizeof((a[0])) \ seems to be far more portable. | The file sizer may be moved into details and | names size_calculator.hpp or so. yeah. | _______________________________________________________ | 23. headers: in guard like | | #if defined(_MSC_VER) && (_MSC_VER >= 1020) | # pragma once | #endif | | sometimes value 1020 and sometimes value 1200 is used. | Both are OK from practical point of view but | it would feel better if the same. I would like to know which one to use. I think the "right" one is 1200. | _______________________________________________________ | 24. docs: there should be step-by-step example how to add | support for new container (e.g. scattered array consisting | of few subarrays). ok | _______________________________________________________ | 25. end.hpp: what is #undef BOOST_END_IMPL doing here? | Why such dangerous name is used? to be removed. | _______________________________________________________ | 26. testing Unicode string for being empty: I read | somewhere Unicode files have two characters at the | beginning to indicate endianess. I do not know if | this applies to strings in memory as well. | | If so, then maybe Container Traits or String Algos | should take care about this. | | (I could talk complete nonsense on this topic.) my understanding is that both char and wchar_t has a trailing null and nothing else. Unicode charactors is not supported right now. I have about zero understanding about unicode chars and what to expect for them...eg...will std::char_traits exists for them etc. | _______________________________________________________ | 27. functions.hpp: what is BOOST_STRING_TYPENAME and where | does it come from? A leftover from Pavol. To be removed. | _______________________________________________________ | 28. implementation_help.hpp: | | strlen() should be used instead of | for( ; s[0] != end; ) | ++s; | | strlen/wstrlen may be better optimized. ok. how? | In | inline T* array_end( T BOOST_ARRAY_REF[sz], | char_or_wchar_t_array_tag ) | { | return array + sz - 1; | } | | | there should be static assert sz > 0. ok. | GCC allows zero size arrays. | does not? | _______________________________________________________ | 29. sfinae.hpp: isn't the file name misleading? you tell me.:-) It's basically sfinae for use in my type-traits. | _______________________________________________________ | 30. result_iterator.hpp: what does the "give up" | note there mean? I can't implement that. | _______________________________________________________ | 31. functions.hpp\: some commenst should be added. | The source has 21 kB. The MPL expressions here | are quite complex... isn't that overkill? | _______________________________________________________ | 32. functions.hpp: in list of types | | char, | signed char, | unsigned char, | signed short, | unsigned short, | signed int, | unsigned int, | signed long, | | shouldn't floats and long long/__int64 be there as well? hm...I think you're looking in a file that is depricated.. detail/function.hpp is not officially part of the dist. | _______________________________________________________ | 33. each header should have short comment on the top what | is it for, especially the ones in detail/ ok. | _______________________________________________________ | 34. functions.hpp: is the reference e.g. in | | template< typename P > | static result_iterator begin( P& p ) | { | return p; | } | | necessary? I assume 'p' is always pointer. yeah. It should be changed. | _______________________________________________________ | 35. naming conventions: maybe names as iterator_ should | be replaced with something else. Underscore is easy | to miss and is quite unusual. _impl ? br Thorsten

Thorsten Ottosen wrote:
| _______________________________________________________ | 23. headers: in guard like | | #if defined(_MSC_VER) && (_MSC_VER >= 1020) # pragma once #endif | | sometimes value 1020 and sometimes value 1200 is used. | Both are OK from practical point of view but it would feel better if | the same.
I would like to know which one to use. I think the "right" one is 1200.
The correct one is 1000 (implemented since V10.0 / VC++4) Regards Hartmut

Hartmut Kaiser wrote:
Thorsten Ottosen wrote:
_______________________________________________________ 23. headers: in guard like
#if defined(_MSC_VER) && (_MSC_VER >= 1020) # pragma once #endif
sometimes value 1020 and sometimes value 1200 is used. Both are OK from practical point of view but it would feel better if the same.
I would like to know which one to use. I think the "right" one is 1200.
The correct one is 1000 (implemented since V10.0 / VC++4)
Microsoft's own headers use 1020 (VC 4.2).

Hello Thorsten,
| It would be useful to have many more examples in documentation, | showing how to use it together with other Boost libraries.
Can you give an example of what you have in mind?
I mean snippet for each of function provided by the library, applied to more exotic containers - just to show it works with them and how. _______________________________________________________
multi_index_container? I can't remember if it fulfills the standard container requirements.
Yes, it does. _______________________________________________________
| 10. collection_traits.html, Semantics section, tables: | it doesn't make sense to me what middle column contains.
ok, would a table with
--------------Abbreviations----------- SC = std container T = the type used in arrays P = std::pair etc
help
?
Yes. _______________________________________________________
| 12. collection_traits.html, Portability section: | | bcc6 ==>> BCB 6.4
I'm just curious, did you compile the test with that compiler?
Tried now. I got error: [C++ Error] end.hpp(78): E2285 Could not find a match for 'collection_traits_detail::array_end<T,sz>(int *)' Full parser context end.hpp(77): decision to instantiate: int * int * end<int,10>(int ( &)[10]) --- Resetting parser context for instantiation... algorithm_example.cpp(1): #include C:\Temp\boost-sandbox\boost\collection_traits.hpp collection_traits.hpp(14): #include C:\Temp\boost-sandbox\boost/collection_traits/functions.hpp functions.hpp(15): #include C:\Temp\boost-sandbox\boost/collection_traits/end.hpp end.hpp(27): namespace boost end.hpp(29): namespace collection_traits end.hpp(77): parsing: int * int * end<int,10>(int ( &)[10]) fixed with: #if BOOST_WORKAROUND( __BORLANDC__, BOOST_TESTED_AT(0x564)) # undef BOOST_CT_NO_ARRAY_SUPPORT #endif in config.hpp (or something like this). ------------------ BCB doesn't like to move function via using directive. E.g. in begin.hpp: } // namespace 'collection_traits' using collection_traits::begin; <<<=== this makes BCB crash } // namespace boost Either BCB will be unsupported or the inner namespace needs to be conditionally removed for this compiler. If you want to try the port, it should maybe wait all other problems get fixed. ------------------ There are other problems with MPL and type traits I reported. | _______________________________________________________
| 16. I once thought about having typedef boost::end | and containers with overload of operator[]. | | It would allow to write: | | a_container[boost::end - 1] | | to access last element of container. | | a_container[boost::end - 2] would be one before | | the last one. Python has such feature. | | | Is there some way to have such support in Container | Traits?
so you're describing a search facility for [] containers. it will work a bit strange with map, wouldn't it? we can't use boost::end, but maybe boost::last. In some sense it correponds to
I regret boost::end is taken. I'll think about boost::last. I guess there's no way for vector<int> v; v[boost::end - 1]; to compile and give what I'd like, now.
Maybe that could justify having reverse_iterator_of<> and const_reverse_iterator_of<> + rbegin(), rend(). ?
Yes, this looks as good idea. _______________________________________________________
| 31. functions.hpp\: some commenst should be added. | The source has 21 kB. The MPL expressions here | are quite complex...
isn't that overkill?
I guess it isn't. Maybe pseudocode for the MPL expressions can be added, as it is with Serialization. | _______________________________________________________
| 32. functions.hpp: in list of types | | char, | signed char, | unsigned char, | signed short, | unsigned short, | signed int, | unsigned int, | signed long, | | shouldn't floats and long long/__int64 be there as well?
hm...I think you're looking in a file that is depricated.. detail/function.hpp is not officially part of the dist.
??? I use the zip from Boost Files section, downloaded just today. _______________________________________________________
| 35. naming conventions: maybe names as iterator_ should | be replaced with something else. Underscore is easy | to miss and is quite unusual.
_impl ?
Can be. /Pavel

"Pavel Vozenilek" <pavel_vozenilek@hotmail.com> wrote in message news:Sea2-DAV34aYaZlbB9u0000cd78@hotmail.com... | > | It would be useful to have many more examples in documentation, | > | showing how to use it together with other Boost libraries. | > | > Can you give an example of what you have in mind? | > | I mean snippet for each of function provided by the library, | applied to more exotic containers - just to show it works | with them and how. ok. | _______________________________________________________ | > | 10. collection_traits.html, Semantics section, tables: | > | it doesn't make sense to me what middle column contains. | > | > ok, would a table with | > | > --------------Abbreviations----------- | > SC = std container | > T = the type used in arrays | > P = std::pair | > etc | > | > help | > | > ? | > | Yes. ok. | _______________________________________________________ | > | 12. collection_traits.html, Portability section: | > | | > | bcc6 ==>> BCB 6.4 | > | > I'm just curious, did you compile the test with that compiler? | > | Tried now. I got error: [snip] | fixed with: | | #if BOOST_WORKAROUND( __BORLANDC__, BOOST_TESTED_AT(0x564)) | # undef BOOST_CT_NO_ARRAY_SUPPORT | #endif | | in config.hpp (or something like this). thanks. | ------------------ | BCB doesn't like to move function via using directive. E.g. in begin.hpp: | | } // namespace 'collection_traits' | using collection_traits::begin; <<<=== this makes BCB crash | } // namespace boost | | Either BCB will be unsupported or the inner namespace needs to be | conditionally removed for this compiler. If you want to try the port, | it should maybe wait all other problems get fixed. yes, lets wait a bit. | > Maybe that could justify having reverse_iterator_of<> and | > const_reverse_iterator_of<> | > + rbegin(), rend(). ? | > | Yes, this looks as good idea. ok. | > hm...I think you're looking in a file that is depricated.. | > detail/function.hpp | > is not officially part of the dist. | > | ??? I use the zip from Boost Files section, downloaded just today. well, its my mistake that the file is part of the distribution, but its not intended to be there. br Thorsten

| > hm...I think you're looking in a file that is depricated.. | > detail/function.hpp | > is not officially part of the dist. | > | ??? I use the zip from Boost Files section, downloaded just today.
well, its my mistake that the file is part of the distribution, but its not intended to be there.
Can you change the zip? Other can get mislead too. /Pavel

| Can you change the zip? Other can get mislead too. | doing it right now... br Thorsten

I wonder whether Collection Traits can also use Filter Iterator (http://www.boost.org/libs/iterator/doc/filter_iterator.html) as 'collection'. Or even whether it can simplify use of Filter Iterator a bit. /Pavel

"Pavel Vozenilek" <pavel_vozenilek@hotmail.com> wrote in message news:c6s7rh$fc9$1@sea.gmane.org... | I wonder whether Collection Traits can also use Filter Iterator | (http://www.boost.org/libs/iterator/doc/filter_iterator.html) | as 'collection'. nope. The requierement is that a default constructed iterator denotes the end. | Or even whether it can simplify use of Filter Iterator a bit. I think the key for simpler use of all of the iterators in Boost.Iterator is to define special range versions of make_XX. I hope John and Matthew will do this in their range lib. For example make_filter_range( is_positive_number(), coll ); Using Collection Traits that should be simple. So eventually we can write std::copy( boost::make_filter_range( is_positive_number(), numbers ), std::ostream_iterator<int>( std::cout, " " ) ) instead of std::copy(boost::make_filter_iterator<is_positive_number>(numbers, numbers + N), boost::make_filter_iterator<is_positive_number>(numbers + N, numbers + N), std::ostream_iterator<int>(std::cout, " ")); Ans similar for other iterators. br Thorsten

Thorsten Ottosen wrote:
"Pavel Vozenilek" <pavel_vozenilek@hotmail.com> wrote in message news:c6s7rh$fc9$1@sea.gmane.org... | I wonder whether Collection Traits can also use Filter Iterator | (http://www.boost.org/libs/iterator/doc/filter_iterator.html) | as 'collection'.
nope. The requierement is that a default constructed iterator denotes the end.
I think it's possible to create iterator adaptor which makes default constructed iterator denote the end. Hey, it's 10 mins effort, see http://zigzag.cs.msu.su:7813/implicit_eof_iterator I'm not yet sure if this is better/worse than views, but definitely Collection Traits need to have special support for Filter iterator. Either we need views, or we need such wrapper iterator.
| Or even whether it can simplify use of Filter Iterator a bit.
I think the key for simpler use of all of the iterators in Boost.Iterator is to define special range versions of make_XX. I hope John and Matthew will do this in their range lib.
Where can I look at this lib, and how it's different/related to the views library in the sandbox?
For example
make_filter_range( is_positive_number(), coll );
Using Collection Traits that should be simple. So eventually we can write
std::copy( boost::make_filter_range( is_positive_number(), numbers ), std::ostream_iterator<int>( std::cout, " " ) )
Yes, that's what I'd like. Only, I *really* think that the function should be called just 'filter'. But that's just personal opinion. - Volodya

"Vladimir Prus" <ghost@cs.msu.su> wrote in message news:c6ssbr$fvu$1@sea.gmane.org... | > | Or even whether it can simplify use of Filter Iterator a bit. | > | > I think the key for simpler use of all of the iterators in Boost.Iterator | > is to define | > special range versions of make_XX. I hope John and Matthew will do this in | > their range | > lib. | | Where can I look at this lib, and how it's different/related to the views | library in the sandbox? ask John Torjo john_AT_torjo.com | > make_filter_range( is_positive_number(), coll ); | > | > Using Collection Traits that should be simple. So eventually we can write | > | > std::copy( boost::make_filter_range( is_positive_number(), numbers ), | > std::ostream_iterator<int>( std::cout, " " ) ) | | Yes, that's what I'd like. Only, I *really* think that the function should | be called just 'filter'. But that's just personal opinion. IMO, filter is to generic. The iterator library consistently uses make_XX_iterator. So therefore think make_XX_range would be consistent. Pavol's string lib has a make_iterator_range(), not range(). Perhaps make can be dropped, but range says something about what the function returns. br Thorsten

Vladimir Prus wrote:
Thorsten Ottosen wrote:
"Pavel Vozenilek" <pavel_vozenilek@hotmail.com> wrote in message news:c6s7rh$fc9$1@sea.gmane.org... | I wonder whether Collection Traits can also use Filter Iterator | (http://www.boost.org/libs/iterator/doc/filter_iterator.html) | as 'collection'.
nope. The requierement is that a default constructed iterator denotes the end.
I think it's possible to create iterator adaptor which makes default constructed iterator denote the end. Hey, it's 10 mins effort, see
http://zigzag.cs.msu.su:7813/implicit_eof_iterator
I'm not yet sure if this is better/worse than views, but definitely Collection Traits need to have special support for Filter iterator. Either we need views, or we need such wrapper iterator.
| Or even whether it can simplify use of Filter Iterator a bit.
I think the key for simpler use of all of the iterators in Boost.Iterator is to define special range versions of make_XX. I hope John and Matthew will do this in their range lib.
Where can I look at this lib, and how it's different/related to the views library in the sandbox?
www.torjo.com/code/for_boost.zip (note, it contains several also other things) it's more general ;) at this time, it uses the traverable range concept, like this; for( crange<some_container> r(c); r; ++r) do_whatever(r); it contains the STL algorithms adapted for ranges, and you can compose ranges. Example: filtered(transformed(c,some_transform),some_filter); When we'll have the time, we'll post an update to the Ranges Library. Unfortunately I think this will only happen in a few months :( -- John Torjo Freelancer -- john@torjo.com -- http://www.torjo.com/logview/ - viewing/filtering logs is just too easy!

Thorsten Ottosen wrote:
"Pavel Vozenilek" <pavel_vozenilek@hotmail.com> wrote in message news:c6s7rh$fc9$1@sea.gmane.org... | I wonder whether Collection Traits can also use Filter Iterator | (http://www.boost.org/libs/iterator/doc/filter_iterator.html) | as 'collection'.
nope. The requierement is that a default constructed iterator denotes the end.
| Or even whether it can simplify use of Filter Iterator a bit.
I think the key for simpler use of all of the iterators in Boost.Iterator is to define special range versions of make_XX. I hope John and Matthew will do this in their range lib. For example
he he ;) they're already there ;) check them out if you have the time (www.torjo.com/code/for_boost.zip) Best, John -- John Torjo Freelancer -- john@torjo.com -- http://www.torjo.com/logview/ - viewing/filtering logs is just too easy!

Hi, Here is my review of the collection traits library. I have been working with the library quite a long time. I have seen it evolving to the current state. Former version of the library is already incorporated as a part of the string algorithm library.
- What is your evaluation of the design?
Desing is simple and good. I found it sufficient for the utility like this on. Design allows to integrate other non-stl containers with ease. I wonder it somebody would try to adapt f.e. MFC CString.
- What is your evaluation of the implementation?
Implementation works on compliant compilers and there is a handful of workarounds for defficient compilers. Currently restricted implementation only supports char and wchar_t arrays. The string_algo version is more powerful, but it is questionable, if the addtional effort put into workaround is wort it.
- What is your evaluation of the documentation?
Documentation is rather simple. It explains the basic concepts and definitions of the library. I found it sufficient as a reference. It might help it there would be more examples of potential usefulness of the library. Potential is great, however it is not easy to uncover it.
- What is your evaluation of the potential usefulness of the library?
From my own experience, this library has at least halved the number of overloads in the string algo library. For instance, boost regex
Library is very useful. It allows to write a large set of algorithms without resticting to a concreate type of the container. Non-intrusive nature of the library interface allows to use also uncommon containers, with these algorithms. library provide at two-three overloads for every algorithm. (std::basic_string, char* and iterator-base). With collection_traits (and a little help of iterator_range class) it was possible to have just one variant that handle all these three cases and even more.
- Did you try to use the library? With what compiler? Did you have any problems?
A have tried to switch string_algo library to use the collection_traits instead of build-in version. After a couple of bug fixes provided by Thorsten, string_algo library passed all tests under vc7.1 and gcc3.3.1 Unfortunately I was not able to test less compliant compilers like vc7.0
- How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
Throughout study with a large implemetation case.
- Are you knowledgeable about the problem domain?
As far as I can tell, I am.
Please always state in your review, whether you think the library should be accepted as a Boost library!
I vote to ACCEPT the library to boost collection. Regards, Pavol

Hartmut Kaiser wrote:
- What is your evaluation of the design?
Clean and simple
- What is your evaluation of the implementation?
Straightforward
- What is your evaluation of the documentation?
Sufficient.
- What is your evaluation of the potential usefulness of the library?
Phoenix V2 uses something like it. It would be nice to replace the implementation with something more general.
- Did you try to use the library? With what compiler? Did you have any problems?
I haven't tried the library, but based on what I see, and my experience with such metafunctions, I see no problem whatsoever.
- How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
I've studied the code once before. I didn't do a second study. The library is simple.
- Are you knowledgeable about the problem domain?
Yes. I vote "YES". Please accept the library into boost. -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net

Hartmut Kaiser wrote:
The Latest version of the library is available at (yahoo files sections): http://tinyurl.com/ysbaj (72 kB) or in the Boost sandbox.
Sandbox is out of sync (missing detail/implementation_help.hpp), so I tested collection_traits.zip using MSVC++ 7.0 and gcc 3.3.1 (cygwin).
Please always state in your review, whether you think the library should be accepted as a Boost library!
Definitely YES!
- What is your evaluation of the design? - What is your evaluation of the implementation?
Elegant and current state-of-the-art.
- What is your evaluation of the documentation?
From the docs: "It is worth noticing that some functionality requires partial template specialization, in particular, full array support does" It would be nice if the doc states in more detail *which* functions require partial template specialization. "(remark: this is a very small problem since one would use boost::array<> anyway)" Well, if I knew the size of the array at compile-time; which brings me to
- What is your evaluation of the potential usefulness of the library?
Highly useful if one often deals with container-like collections. What I miss is support for scoped_array<> and shared_array<>; I guess, however, that it is difficult or even impossible to obtain the number of elements of a shared_array<> - correct?
- Did you try to use the library? With what compiler? Did you have any problems?
See above.
- Are you knowledgeable about the problem domain?
Since other Boosters already gave more elaborate feedback on the design etc., I further focused on a special aspect of collection_traits. My primary interest is the boost/view library (also in the sandbox). Since views are meant to be lightweight wrappers with a collection-like interface, they should work together with collection_traits - and, in fact, all views submitted so far pass this test (see attached file). I further noticed that one view (range_view) became obsolete, and that other views might be easier to implement now with the help of collection_traits. - Roland #include <boost/config.hpp> #include <boost/test/minimal.hpp> #include <boost/collection_traits.hpp> #include <boost/static_assert.hpp> #include <boost/type_traits/is_same.hpp> #include <vector> #include <deque> #include <cmath> #include <boost/array.hpp> #include <boost/shared_array.hpp> #include <boost/view/filter_view.hpp> #include <boost/view/function_view.hpp> #include <boost/view/permutation_view.hpp> #include <boost/view/range_view.hpp> #include <boost/view/transform_view.hpp> #include <boost/view/window_view.hpp> template<class ContainerT> void test_container_traits_types( ContainerT c ) { typedef ContainerT CT; BOOST_STATIC_ASSERT( ( boost::is_same< boost::value_type_of<CT>::type, typename CT::value_type >::value ) ); BOOST_STATIC_ASSERT( ( boost::is_same< boost::iterator_of<CT>::type, typename CT::iterator >::value ) ); BOOST_STATIC_ASSERT( ( boost::is_same< boost::const_iterator_of<CT>::type, typename CT::const_iterator >::value ) ); BOOST_STATIC_ASSERT( ( boost::is_same< boost::difference_type_of<CT>::type, typename CT::difference_type >::value ) ); BOOST_STATIC_ASSERT( ( boost::is_same< boost::size_type_of<CT>::type, typename CT::size_type >::value ) ); BOOST_STATIC_ASSERT( ( boost::is_same< boost::result_iterator_of<CT>::type, typename CT::iterator >::value ) ); BOOST_STATIC_ASSERT( ( boost::is_same< boost::result_iterator_of<const CT>::type, typename CT::const_iterator >::value ) ); BOOST_STATIC_ASSERT( ( boost::is_same< boost::value_type_of<const CT>::type, typename CT::value_type >::value ) ); BOOST_STATIC_ASSERT( ( boost::is_same< boost::iterator_of<const CT>::type, typename CT::iterator >::value ) ); BOOST_STATIC_ASSERT( ( boost::is_same< boost::const_iterator_of<const CT>::type, typename CT::const_iterator >::value ) ); BOOST_STATIC_ASSERT( ( boost::is_same< boost::difference_type_of<const CT>::type, typename CT::difference_type >::value ) ); BOOST_STATIC_ASSERT( ( boost::is_same< boost::size_type_of<const CT>::type, typename CT::size_type >::value ) ); } template<class ContainerT> void test_container_traits_functions( ContainerT c ) { BOOST_CHECK( boost::begin( c ) == c.begin() ); BOOST_CHECK( boost::end( c ) == c.end() ); BOOST_CHECK( boost::empty( c ) == c.empty() ); BOOST_CHECK( boost::size( c ) == c.size() ); } template<class ContainerT> void test_container_traits_const_functions( ContainerT c ) { const ContainerT cc = c; BOOST_CHECK( boost::begin( cc ) == cc.begin() ); BOOST_CHECK( boost::end( cc ) == cc.end() ); BOOST_CHECK( boost::empty( cc ) == cc.empty() ); BOOST_CHECK( boost::size( cc ) == cc.size() ); } template<class ContainerT> void test_container_traits( ContainerT c ) { test_container_traits_types( c ); test_container_traits_functions( c ); test_container_traits_const_functions( c ); } // Skipped test_array_traits_types() template<class ArrayT> void test_array_functions( ArrayT a ) { #ifndef BOOST_MSVC typedef boost::value_type_of<ArrayT>::type value_type; const int N = sizeof(a)/sizeof(value_type); BOOST_CHECK( boost::begin( a ) == a ); BOOST_CHECK( boost::end( a ) == a + N ); BOOST_CHECK( boost::empty( a ) == ( boost::size( a ) == 0 ) ); BOOST_CHECK( boost::size( a ) == N ); #endif } struct linear: public std::unary_function<double,double> { linear( double theK = 1., double theD = 0. ) : k( theK ), d( theD ) { } double operator()( double x ) const { return k*x + d; } double k; double d; }; struct is_positive_number { bool operator()(int x) { return x > 0; } }; int test_main(int, char *[]) { typedef int int_array[7]; int_array a = { 0, -1, 4, -3, 5, 8, -2 }; const int N = sizeof(a)/sizeof(int); //test_array_functions( a ); // Does NOT compile with gcc test_array_functions<int_array>( a ); std::vector<int> v( a, a + N ); test_container_traits( v ); boost::array<int,7> ba = {{ 0, -1, 4, -3, 5, 8, -2 }}; test_container_traits( ba ); boost::shared_array<int> sa( new int[7] ); //test_array_functions( sa ); // Wishful thinking. boost::view::range_view<int*, const int*> rv( a, a+7 ); test_container_traits( rv ); boost::view::window_view< std::vector<int> > wv( v, v.begin(), 3 ); test_container_traits_types( wv ); test_container_traits_functions( wv ); //test_container_traits_const_functions( wv ); boost::view::function_view< linear, int > lv( 0, 10, linear( 2., -3. ) ); test_container_traits( lv ); boost::view::filter_view< std::vector<int>, is_positive_number > fv( v ); test_container_traits( fv ); std::deque<int> r; // the re-indexing scheme for( int i = 0; i < v.size(); ++i ) { r.push_back( (2*i) % N ); } boost::view::permutation_view< std::vector<int>, std::deque<int> > pv( v, r ); test_container_traits( pv ); double (*doubleAbs)(double) = fabs; // Tell VC++ 7.0 which fabs to take to prevent an internal error. std::pointer_to_unary_function<double,double> absf( doubleAbs ); boost::view::transform_view< std::vector<int>, std::pointer_to_unary_function<double,double> > tv( v, absf ); test_container_traits( tv ); return 0; }

Hmm...
//test_array_functions( a ); // Does NOT compile with gcc test_array_functions<int_array>( a );
I have quite similar problem, actually. GCC does not allow implicit type conversions in somewhat complex function overloads. This can really be quite annoying. And there boost::get_pointer comes to mind. Question to Peter Dimov. Is it possible and rational to modify code in mem_fn_template.hpp so that get_pointer(u) would be called as get_pointer<U>(u) ? I believe this should not brake existing code, on the other hand, it would be easier to provide so-needed get_pointer overloads. Actually, my problem is: I have, say, type T, and I'd like to write an implicit converter to templatized type Y so that: T::value_type * get_pointer(const Y<T> &p). Of course, all required enable_ifs are applied so that this overload is not visible for other types that do not meet some certain archetype. Then invocation of function get_pointer would create temporary object of type Y<T> which would be destroyed on exit from method call scope. That would be fine because in my case, Y c-tor locks mutex and d-tor - unlocks mutex. This would allow type T<A> to model pointers to A and create thread-safe bind functors. Another alternative I have is to specialize mf0, cmf0, .... etc. (partial function specializations are still non-existant). But this is unacceptable, I think. Regards, Justinas V.D.

Justinas V.D. wrote:
Question to Peter Dimov. Is it possible and rational to modify code in mem_fn_template.hpp so that get_pointer(u) would be called as get_pointer<U>(u) ?
I believe this should not brake existing code, on the other hand, it would be easier to provide so-needed get_pointer overloads.
It will break, at minimum, all get_pointer overloads that are not templates.
Actually, my problem is:
I have, say, type T, and I'd like to write an implicit converter to templatized type Y so that: T::value_type * get_pointer(const Y<T> &p). Of course, all required enable_ifs are applied so that this overload is not visible for other types that do not meet some certain archetype.
Then invocation of function get_pointer would create temporary object of type Y<T> which would be destroyed on exit from method call scope. That would be fine because in my case, Y c-tor locks mutex and d-tor - unlocks mutex.
You can use my_locking_ptr<T> get_pointer(T & t); Of course my_locking_ptr<> must support operator->* for this to work.

Hi Roland, Thanks for your review. | > - What is your evaluation of the documentation? | | From the docs: | | "It is worth noticing that some functionality requires partial template | specialization, in particular, full array support does" | | It would be nice if the doc states in more detail *which* functions require | partial template specialization. ok, its all functions and type-gerators for T[] when T is not char or wchar_t. I guess I should just remove "some" and type "all". | "(remark: this is a very small problem since one would use boost::array<> | anyway)" | | Well, if I knew the size of the array at compile-time; which brings me to well, you always know the size of T[sz] at compile time. | What I miss is support for scoped_array<> and shared_array<>; | I guess, however, that it is difficult or even impossible to obtain the | number of elements of a shared_array<> - correct? yes. Only strings are null-terminated. | Since other Boosters already gave more elaborate feedback on the design etc., | I further focused on a special aspect of collection_traits. | | My primary interest is the boost/view library (also in the sandbox). | Since views are meant to be lightweight wrappers with a collection-like | interface, they should work together with collection_traits - and, in | fact, all views submitted so far pass this test (see attached file). | | I further noticed that one view (range_view) became obsolete, and | that other views might be easier to implement now with the help of | collection_traits. great. If you are the man in charge of the view library, I think you should contact this Tom Houlder thoulder@houlder.net . He is working on something similar. You might also want to contact John Torjo (john@torjo.com). | template<class ContainerT> | void test_container_traits_functions( ContainerT c ) | { why are you passing by value? | boost::shared_array<int> sa( new int[7] ); | //test_array_functions( sa ); // Wishful thinking. not if the smart pointer would save its size and have a .size() function. br Thorsten

Hi Thorsten, about the name of the library: Not sure why it's called collection traits, since IMO it should better be called either sequence traits, container traits, range traits or array traits.
Please always state in your review, whether you think the library should be accepted as a Boost library!
it should be accepted into boost. I vote YES.
- What is your evaluation of the design? - What is your evaluation of the implementation? - What is your evaluation of the documentation?
quite ok. Small suggestios: - in collection_traits.html/"Semantics" You say '...c is an object of that type. SC will denote a standard container...'. I think bullets would be quite ok here.
- What is your evaluation of the potential usefulness of the library?
very useful in generic programming.
- Did you try to use the library? With what compiler? Did you have any problems?
yes, vc7.1, no problems.
- How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
about two hours
- Are you knowledgeable about the problem domain?
yes I love the result_iterator_of. Very useful. I don't like the idiom of using begin() and end() for iterators which default-constructed denote the end of a range. I think there are very few iterator classes which match this concept: std::istringstream, filesystem::directory_iterator, anything else? Maybe we could make it more explicit, when using such iterator classes, to have a different set of functions: end_it, begin_it? Since we have value_of, iterator_of, etc., why not reference_of, const_reference_of? Best, John -- John Torjo Freelancer -- john@torjo.com -- http://www.torjo.com/logview/ - viewing/filtering logs is just too easy!

Hi John, Thanks for you review. | about the name of the library: | Not sure why it's called collection traits, since IMO it should better | be called either sequence traits, container traits, range traits or | array traits. 1. sequence traits is part of Pavol's string library, IIRC. 2. there is no array concept that quite fits the functionality 3. its name was changed to collection traits because we found out that Jeremy had made such a concept range traits is not to bad. I would love to hear other's oppinion about it. Some has said "range" is too generic since we are strictly speaking talking about iterator-ranges. Hence Pavol named his class in the string library iterator_range. So maybe iterator-range traits? Anyway, let' hear what people think. | quite ok. Small suggestios: | - in collection_traits.html/"Semantics" | You say '...c is an object of that type. SC will denote a standard | container...'. I think bullets would be quite ok here. yes, Pavel already wanted one. | I love the result_iterator_of. Very useful. ok, originally I only used this with buggy compilers that could not differentiate between const& and & overloads. So you could instead have just one function with a & parameter. So you loosed the the binding of rvalues. May I ask what you use it for? | I don't like the idiom of using begin() and end() for iterators which | default-constructed denote the end of a range. I think there are very | few iterator classes which match this concept: std::istringstream, | filesystem::directory_iterator, anything else? I assume there would be others. Can anybody mention others? | Maybe we could make it | more explicit, when using such iterator classes, to have a different set | of functions: end_it, begin_it? perhaps. we loose the possibility of using rng::copy( istream_iterator<char>( is ), ... ); at leastv some people wanted that idiom to work. | Since we have value_of, iterator_of, etc., why not reference_of, | const_reference_of? As I write in the faq, reference_of<T>::type can just be value_type_of<T>::type &. I find code that would rely on something else to be very subtle. FWIW, I think there can be made improvements in this area. Dietmar Kuhl has been talking about using property maps or something to make the requirements for iterator indirection useful in other ways. The new iterator library by Dave, Jeremy and Thomas might solve such problems. As I see it, we need to see algorithms that rely on guarantees about reference_of + iterator indirection to implement something better/correct. br Thorsten

Thorsten Ottosen wrote:
Hi John,
Thanks for you review.
| about the name of the library: | Not sure why it's called collection traits, since IMO it should better | be called either sequence traits, container traits, range traits or | array traits.
1. sequence traits is part of Pavol's string library, IIRC. 2. there is no array concept that quite fits the functionality 3. its name was changed to collection traits because we found out that Jeremy had made such a concept
range traits is not to bad. I would love to hear other's oppinion about it. Some has said "range" is too generic since we are strictly speaking talking about iterator-ranges. Hence Pavol named his class in the string library iterator_range. So maybe iterator-range traits? Anyway, let' hear what people think.
| quite ok. Small suggestios: | - in collection_traits.html/"Semantics" | You say '...c is an object of that type. SC will denote a standard | container...'. I think bullets would be quite ok here.
yes, Pavel already wanted one.
| I love the result_iterator_of. Very useful.
ok, originally I only used this with buggy compilers that could not differentiate between const& and & overloads. So you could instead have just one function with a & parameter. So you loosed the the binding of rvalues. May I ask what you use it for?
when designing templated classes template<class container> struct widget { typedef result_iterator_of<container> iterator; };
| Maybe we could make it | more explicit, when using such iterator classes, to have a different set | of functions: end_it, begin_it?
perhaps. we loose the possibility of using
rng::copy( istream_iterator<char>( is ), ... );
instead of istream_iterator, just make an istream_range class. It's more consistent IMO.
at leastv some people wanted that idiom to work.
| Since we have value_of, iterator_of, etc., why not reference_of, | const_reference_of?
As I write in the faq, reference_of<T>::type can just be value_type_of<T>::type &.
As I remember, that's not necessary true for new iterator types... Best, John -- John Torjo Freelancer -- john@torjo.com -- http://www.torjo.com/logview/ - viewing/filtering logs is just too easy!

"John Torjo" <john.lists@torjo.com> wrote in message news:4098BDCE.6060202@torjo.com... | Thorsten Ottosen wrote: | >| I love the result_iterator_of. Very useful. | > | >ok, originally I only used this with buggy compilers that could not differentiate between | >const& and & overloads. So you could instead have just one function with a & parameter. | >So you loosed the the binding of rvalues. May I ask what you use it for? | > | > | when designing templated classes | | template<class container> struct widget { | typedef result_iterator_of<container> iterator; | }; I see :-) I hadn't thought of that. I'll add a note to the docs. Is it a problem that result_reference_of<> is not available? | >| Maybe we could make it | >| more explicit, when using such iterator classes, to have a different set | >| of functions: end_it, begin_it? | > | >perhaps. we loose the possibility of using | > | >rng::copy( istream_iterator<char>( is ), ... ); | > | > | > | instead of istream_iterator, just make an istream_range class. It's more | consistent IMO. I presume you mean rng::copy( istream_range<char>( is ), ... ); ? | >at leastv some people wanted that idiom to work. I don't know how to settle this. I remember at least Alisdair wanted direct iterator support. So instead of intrinsic support for iterators in collection-traits we would make a range class for each such iterator-type. The benefit would be, you would argue, that we needed that range class anyway. Some would say they don't need a range class at all, so its just extra work. As far as my implementation would be concerned, it would simplify things a great deal. I would have to write code to recognize each type of iterator because a std::iterator<...> partial template speciaization will not pick up iterators derived from std::iterator<...>. Anyway, if yours and Matthew's range lib will provide range_adapters that makes it super easy to define a range for such iterators, I don't see why I shouldn't just throw my iterator support away. [remark: I see two distinct libs emerging in your work: (1) range-stuff (2) range algorithms] | >| Since we have value_of, iterator_of, etc., why not reference_of, | >| const_reference_of? | > | >As I write in the faq, reference_of<T>::type can just be value_type_of<T>::type &. | > | > | > | As I remember, that's not necessary true for new iterator types... True. I don't think it is holds for existing iterators. But it must be convertible value_type. Hence const reference_type_of<T>::type& can be used to bind a temporary. I just don't see how coding with reference_type_of<T>::type in an algorithm will buy you anything. I might be wrong. br Thorsten

I presume you mean
rng::copy( istream_range<char>( is ), ... );
yup
?
| >at leastv some people wanted that idiom to work.
I don't know how to settle this. I remember at least Alisdair wanted direct iterator support.
So instead of intrinsic support for iterators in collection-traits we would make a range class for each such iterator-type. The benefit would be, you would argue, that we needed that range class anyway. Some would say they don't need a range class at all, so its just extra work.
As far as my implementation would be concerned, it would simplify things a great deal. I would have to write code to recognize each type of iterator because a std::iterator<...> partial template speciaization will not pick up iterators derived from std::iterator<...>.
Anyway, if yours and Matthew's range lib will provide range_adapters that makes it super easy to define
In general you need to create a wrapper, which is not very hard. I could have a range_adapter which will work exactly for this type of iterators.
[remark: I see two distinct libs emerging in your work: (1) range-stuff (2) range algorithms]
;)
| >| Since we have value_of, iterator_of, etc., why not reference_of, | >| const_reference_of? | > | >As I write in the faq, reference_of<T>::type can just be value_type_of<T>::type &. | > | > | > | As I remember, that's not necessary true for new iterator types...
True. I don't think it is holds for existing iterators. But it must be convertible value_type. Hence const reference_type_of<T>::type& can be used to bind a temporary. I just don't see how coding with reference_type_of<T>::type in an algorithm will buy you anything. I might be wrong.
I haven't thought that far. I guess if someone will need, will just tell you in the future. So, lets wait and see ;) Best, John -- John Torjo Freelancer -- john@torjo.com -- http://www.torjo.com/logview/ - viewing/filtering logs is just too easy!

John Torjo wrote:
Hi Thorsten,
about the name of the library: Not sure why it's called collection traits, since IMO it should better be called either sequence traits, container traits, range traits or array traits.
I agree. I think sequence traits is most appropriate. Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net

On Wed, May 05, 2004 at 09:10:48AM +0800, Joel de Guzman wrote:
John Torjo wrote:
Hi Thorsten,
about the name of the library: Not sure why it's called collection traits, since IMO it should better be called either sequence traits, container traits, range traits or array traits.
I agree. I think sequence traits is most appropriate.
You are not quite right. Sequence concept is precisely defined in C++ standard. Collection traits are not implementig this concept, they don't even implement full Container concept. So if would be very misleading to use the name of it. Collection traits are working with structures that model Collection concept, therfore they should be named after it IMHO. As Thorsten already mentioned in the other post, name sequence traits is already used elsewhere (in the string_algo library) to refine properties of sequences. Regards, Pavol

"Pavol Droba" <droba@topmail.sk> wrote in message news:20040505070727.GA27321@lenin.felcer.sk... | | As Thorsten already mentioned in the other post, name sequence traits is already | used elsewhere (in the string_algo library) to refine properties of sequences. just a remark: is the sequence traits ready to be a library on its own? br Thorsten

On Wed, May 05, 2004 at 08:11:25PM +1000, Thorsten Ottosen wrote:
"Pavol Droba" <droba@topmail.sk> wrote in message news:20040505070727.GA27321@lenin.felcer.sk... | | As Thorsten already mentioned in the other post, name sequence traits is already | used elsewhere (in the string_algo library) to refine properties of sequences.
just a remark: is the sequence traits ready to be a library on its own?
They might be, but the documentation is not ready and it is questionable, it they would be usable outside of the string_algo lib.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Pavol Droba writes:
On Wed, May 05, 2004 at 09:10:48AM +0800, Joel de Guzman wrote:
John Torjo wrote:
Hi Thorsten,
about the name of the library: Not sure why it's called collection traits, since IMO it should better be called either sequence traits, container traits, range traits or array traits.
I agree. I think sequence traits is most appropriate.
You are not quite right. Sequence concept is precisely defined in C++ standard.
Yes, and that's unfortunate, because it is essentially a dead concept -- "nobody" writes generic code that relies on it -- that has occupied a good name. In fact, "Collection" is exactly the word that would perfectly fit to describe what the standard choose to refer to as "Sequence". I don't think going the other way around would be a good call. In CS terminology, collections are inherently associated with storage; using the term to name the concept that explicitly aims at representing sequences that do not necessarily have any is IMO a bad idea.
Collection traits are not implementig this concept, they don't even implement full Container concept. So if would be very misleading to use the name of it. Collection traits are working with structures that model Collection concept, therfore they should be named after it IMHO.
"Collection" is an unfortunate name for the concept. Not having "Sequence" at our disposal, it should be called "Iterator Range" or something along these lines. -- Aleksey Gurtovoy MetaCommunications Engineering

On Wed, May 05, 2004 at 06:35:31AM -0500, Aleksey Gurtovoy wrote:
Pavol Droba writes:
On Wed, May 05, 2004 at 09:10:48AM +0800, Joel de Guzman wrote:
John Torjo wrote:
Hi Thorsten,
about the name of the library: Not sure why it's called collection traits, since IMO it should better be called either sequence traits, container traits, range traits or array traits.
I agree. I think sequence traits is most appropriate.
You are not quite right. Sequence concept is precisely defined in C++ standard.
Yes, and that's unfortunate, because it is essentially a dead concept -- "nobody" writes generic code that relies on it -- that has occupied a good name. In fact, "Collection" is exactly the word that would perfectly fit to describe what the standard choose to refer to as "Sequence". I don't think going the other way around would be a good call. In CS terminology, collections are inherently associated with storage; using the term to name the concept that explicitly aims at representing sequences that do not necessarily have any is IMO a bad idea.
Collection traits are not implementig this concept, they don't even implement full Container concept. So if would be very misleading to use the name of it. Collection traits are working with structures that model Collection concept, therfore they should be named after it IMHO.
"Collection" is an unfortunate name for the concept. Not having "Sequence" at our disposal, it should be called "Iterator Range" or something along these lines.
Well I cannot judge the standard naming, however I think, that some standardization is better then none. So if there is a definition we should change the standard of stick to it. Later is probably more feasible. I found collection easy to understand. I don't understand what is wrong with it. It very well fits into the standard concept hierarchy Collection < Container < Sequence < Associative container Unlike container, that have an ownership of its elements, collection might be just a reference to values. So it describes a "collection" of values organized in an arbitrary structure. Collection concept specifies an interface to access these values. Regrads, Pavol

Pavol Droba wrote:
On Wed, May 05, 2004 at 06:35:31AM -0500, Aleksey Gurtovoy wrote:
Pavol Droba writes:
On Wed, May 05, 2004 at 09:10:48AM +0800, Joel de Guzman wrote:
John Torjo wrote:
Hi Thorsten,
about the name of the library: Not sure why it's called collection traits, since IMO it should better be called either sequence traits, container traits, range traits or array traits.
I agree. I think sequence traits is most appropriate.
You are not quite right. Sequence concept is precisely defined in C++ standard.
Yes, and that's unfortunate, because it is essentially a dead concept -- "nobody" writes generic code that relies on it -- that has occupied a good name. In fact, "Collection" is exactly the word that would perfectly fit to describe what the standard choose to refer to as "Sequence". I don't think going the other way around would be a good call. In CS terminology, collections are inherently associated with storage; using the term to name the concept that explicitly aims at representing sequences that do not necessarily have any is IMO a bad idea.
Collection traits are not implementig this concept, they don't even implement full Container concept. So if would be very misleading to use the name of it. Collection traits are working with structures that model Collection concept, therfore they should be named after it IMHO.
"Collection" is an unfortunate name for the concept. Not having "Sequence" at our disposal, it should be called "Iterator Range" or something along these lines.
Well I cannot judge the standard naming, however I think, that some standardization is better then none. So if there is a definition we should change the standard of stick to it. Later is probably more feasible.
I found collection easy to understand. I don't understand what is wrong with it. It very well fits into the standard concept hierarchy
Collection < Container < Sequence < Associative container
in my mind, when I say collection, I always think of a map/multimap (associative container). For instance, just think of VB's Collection class. Best, John -- John Torjo Freelancer -- john@torjo.com -- http://www.torjo.com/logview/ - viewing/filtering logs is just too easy!

Pavol Droba writes:
You are not quite right. Sequence concept is precisely defined in C++ standard.
Yes, and that's unfortunate, because it is essentially a dead concept -- "nobody" writes generic code that relies on it -- that has occupied a good name. In fact, "Collection" is exactly the word that would perfectly fit to describe what the standard choose to refer to as "Sequence". I don't think going the other way around would be a good call. In CS terminology, collections are inherently associated with storage; using the term to name the concept that explicitly aims at representing sequences that do not necessarily have any is IMO a bad idea.
Collection traits are not implementig this concept, they don't even implement full Container concept. So if would be very misleading to use the name of it. Collection traits are working with structures that model Collection concept, therfore they should be named after it IMHO.
"Collection" is an unfortunate name for the concept. Not having "Sequence" at our disposal, it should be called "Iterator Range" or something along these lines.
Well I cannot judge the standard naming, however I think, that some standardization is better then none. So if there is a definition we should change the standard of stick to it. Later is probably more feasible.
I wasn't suggesting to re-define the standard's Sequence concept to mean what we want (although that's not entirely impossible). Rather, I was saying that "Collection" is a bad substitute for the occupied term.
I found collection easy to understand. I don't understand what is wrong with it.
There is nothing wrong with the word per se. It just has a commonly accepted meaning that is in conflict with the definition we are giving to the identically named concept. In particular, like I said earlier, "Collection" commonly implies storage, while the concept in question specifically aims to represent sequences that don't have any. Compare, for instance, http://tinyurl.com/32fmb and http://tinyurl.com/3h23s.
It very well fits into the standard concept hierarchy
Collection < Container < Sequence < Associative container
Looks like a total mess to me. If anything, it should be Sequence < Collection < Container < Associative Container < View
Unlike container, that have an ownership of its elements, collection might be just a reference to values. So it describes a "collection" of values organized in an arbitrary structure.
That's not a correct definition of the concept we are trying to name, though. The "structure" might not even exists -- think 'range_view(0, 100)', for instance. Which only exemplifies my point; the word has wrong connotations.
Collection concept specifies an interface to access these values.
I understand what the definition of the concept is. I am saying that its _name_ is unfit and misleading. -- Aleksey Gurtovoy MetaCommunications Engineering

On Thu, May 06, 2004 at 04:33:54AM -0500, Aleksey Gurtovoy wrote: [snip]
I wasn't suggesting to re-define the standard's Sequence concept to mean what we want (although that's not entirely impossible). Rather, I was saying that "Collection" is a bad substitute for the occupied term.
I found collection easy to understand. I don't understand what is wrong with it.
There is nothing wrong with the word per se. It just has a commonly accepted meaning that is in conflict with the definition we are giving to the identically named concept. In particular, like I said earlier, "Collection" commonly implies storage, while the concept in question specifically aims to represent sequences that don't have any. Compare, for instance, http://tinyurl.com/32fmb and http://tinyurl.com/3h23s.
It very well fits into the standard concept hierarchy
Collection < Container < Sequence < Associative container
Looks like a total mess to me. If anything, it should be
Sequence < Collection < Container < Associative Container < View
I don't agree, that sequence is a good candidate for this concept as you're suggestion. Sequence directlu implies that elements are sequentialy organized. There are operations that are natural only to sequences like push_front/back() front/back() pop_front()/back. There is nothing like front() for map, yet it can be enumarated, Maybe the best name for the concept should be "Enumerable". That designates, the primar goal of this conceps, i.e. to be able to enumerate the elementes of an arbitrary collection/container or what ever you name it. Regards, Pavol

Pavol Droba <droba@topmail.sk> writes:
On Thu, May 06, 2004 at 04:33:54AM -0500, Aleksey Gurtovoy wrote:
[snip]
I wasn't suggesting to re-define the standard's Sequence concept to mean what we want (although that's not entirely impossible). Rather, I was saying that "Collection" is a bad substitute for the occupied term.
I found collection easy to understand. I don't understand what is wrong with it.
There is nothing wrong with the word per se. It just has a commonly accepted meaning that is in conflict with the definition we are giving to the identically named concept. In particular, like I said earlier, "Collection" commonly implies storage, while the concept in question specifically aims to represent sequences that don't have any. Compare, for instance, http://tinyurl.com/32fmb and http://tinyurl.com/3h23s.
It very well fits into the standard concept hierarchy
Collection < Container < Sequence < Associative container
Looks like a total mess to me. If anything, it should be
Sequence < Collection < Container < Associative Container < View
I don't agree, that sequence is a good candidate for this concept as you're suggestion. Sequence directlu implies that elements are sequentialy organized.
Anything with iterators is sequentially organized.
There are operations that are natural only to sequences like push_front/back() front/back() pop_front()/back.
Those are not sequence operations. Alex Stepanov defined "Sequence" for us long before this library: http://www.sgi.com/tech/stl/Sequence.html and the standard contains this definition: Table 67---Sequence requirements (in addition to container) ______________________________________________________________________________ expression return type pre/post-condition assertion/note ______________________________________________________________________________ ______________________________________________________________________________ X(n, t) post: size() == n. X a(n, t); constructs a sequence with n copies of t. ______________________________________________________________________________ X(i, j) post: size() == distance between i and j. X a(i, j); constructs a sequence equal to the range [i,j). ______________________________________________________________________________ a.insert(p,t) iterator inserts a copy of t before p. ______________________________________________________________________________ a.insert(p,n,t) void inserts n copies of t before p. ______________________________________________________________________________ a.insert(p,i,j) void pre: i,j are not iterators into a. inserts copies of elements in [i,j) before p. ______________________________________________________________________________ a.erase(q) iterator erases the element pointed to by q. ______________________________________________________________________________ a.erase(q1,q2) iterator erases the elements in the range [q1,q2). ______________________________________________________________________________ a.clear() void erase(begin(), end()) post: size() == 0. ______________________________________________________________________________
There is nothing like front() for map, yet it can be enumarated,
Maybe the best name for the concept should be "Enumerable". That designates, the primar goal of this conceps, i.e. to be able to enumerate the elementes of an arbitrary collection/container or what ever you name it.
I'd say "Iterable" if we have to use an "-able" term. 24.1/7 suggests to me that "Range" might be OK: Most of the library's algorithmic templates that operate on data structures have interfaces that use ranges. A range is a pair of iterators that designate the beginning and end of the computation. A range [i, i) is an empty range; in general, a range [i, j) refers to the elements in the data structure starting with the one pointed to by i and up to but not including the one pointed to by j. Range [i, j) is valid if and only if j is reachable from i. The result of the application of functions in the library to invalid ranges is undefined. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

On Thu, May 06, 2004 at 08:32:32AM -0400, David Abrahams wrote:
Pavol Droba <droba@topmail.sk> writes:
[snip]
There are operations that are natural only to sequences like push_front/back() front/back() pop_front()/back.
Those are not sequence operations. Alex Stepanov defined "Sequence" for us long before this library:
http://www.sgi.com/tech/stl/Sequence.html
and the standard contains this definition:
Table 67---Sequence requirements (in addition to container) ______________________________________________________________________________ expression return type pre/post-condition assertion/note ______________________________________________________________________________ ______________________________________________________________________________ X(n, t) post: size() == n. X a(n, t); constructs a sequence with n copies of t. ______________________________________________________________________________ X(i, j) post: size() == distance between i and j. X a(i, j); constructs a sequence equal to the range [i,j). ______________________________________________________________________________ a.insert(p,t) iterator inserts a copy of t before p. ______________________________________________________________________________ a.insert(p,n,t) void inserts n copies of t before p. ______________________________________________________________________________ a.insert(p,i,j) void pre: i,j are not iterators into a. inserts copies of elements in [i,j) before p. ______________________________________________________________________________ a.erase(q) iterator erases the element pointed to by q. ______________________________________________________________________________ a.erase(q1,q2) iterator erases the elements in the range [q1,q2). ______________________________________________________________________________ a.clear() void erase(begin(), end()) post: size() == 0. ______________________________________________________________________________
Actualy they are: Std 23.1.1 Table 68: Optional Sequence Operation. Sure, not every sequence must have them, but for non-sequencial containers, they have no sense and that's what I wanted to say.
I'd say "Iterable" if we have to use an "-able" term. 24.1/7 suggests to me that "Range" might be OK:
Most of the library's algorithmic templates that operate on data structures have interfaces that use ranges. A range is a pair of iterators that designate the beginning and end of the computation. A range [i, i) is an empty range; in general, a range [i, j) refers to the elements in the data structure starting with the one pointed to by i and up to but not including the one pointed to by j. Range [i, j) is valid if and only if j is reachable from i. The result of the application of functions in the library to invalid ranges is undefined.
So it seems, that Range is the clear winner here. Regards, Pavol

"Aleksey Gurtovoy" <agurtovoy@meta-comm.com> wrote in message news:073d01c43295$1d7354b0$6401a8c0@metacomm.com... | Pavol Droba writes: | > You are not quite right. Sequence concept is precisely defined in C++ standard. | | Yes, and that's unfortunate, because it is essentially a dead concept -- "nobody" | writes generic code that relies on it -- that has occupied a good name. In fact, | "Collection" is exactly the word that would perfectly fit to describe what the | standard choose to refer to as "Sequence". I don't think going the other way | around would be a good call. what would you use for sequence then? | In CS terminology, collections are inherently | associated with storage; can give any examples of this CS terminology? br Thorsten

Thorsten Ottosen writes:
"Aleksey Gurtovoy" <agurtovoy@meta-comm.com> wrote in message news:073d01c43295$1d7354b0$6401a8c0@metacomm.com... | Pavol Droba writes:
| > You are not quite right. Sequence concept is precisely defined in C++ standard. | | Yes, and that's unfortunate, because it is essentially a dead concept -- "nobody" | writes generic code that relies on it -- that has occupied a good name. In fact, | "Collection" is exactly the word that would perfectly fit to describe what the | standard choose to refer to as "Sequence". I don't think going the other way | around would be a good call.
what would you use for sequence then?
Well, I don't have an ultimate answer, but here's a couple of candidates: Range Iterator Range View Series Succession
| In CS terminology, collections are inherently | associated with storage;
can give any examples of this CS terminology?
http://tinyurl.com/yr3bb -- Aleksey Gurtovoy MetaCommunications Engineering

On Thu, May 06, 2004 at 05:15:56AM -0500, Aleksey Gurtovoy wrote:
Thorsten Ottosen writes:
"Aleksey Gurtovoy" <agurtovoy@meta-comm.com> wrote in message news:073d01c43295$1d7354b0$6401a8c0@metacomm.com... | Pavol Droba writes:
| > You are not quite right. Sequence concept is precisely defined in C++ standard. | | Yes, and that's unfortunate, because it is essentially a dead concept -- "nobody" | writes generic code that relies on it -- that has occupied a good name. In fact, | "Collection" is exactly the word that would perfectly fit to describe what the | standard choose to refer to as "Sequence". I don't think going the other way | around would be a good call.
what would you use for sequence then?
Well, I don't have an ultimate answer, but here's a couple of candidates:
Range Iterator Range View Series Succession
These terms are not synonymous. Some imply an ordering, others do not. The standard's "Sequence" concept has a definite ordering, neither "Collection" not "Container" imply any ordering. My dictionary defines collection as "an accumulated assortment of things of a particular type" - which sounds ok for this concept. There's no implication of containing or owning the things, so the fact that VB (or CS in general) have used the term to describe ownership is a fault in VB, not the word!
| In CS terminology, collections are inherently | associated with storage;
can give any examples of this CS terminology?
I don't think there's a good case for either side of the argument. Several of the sites you give as examples of "Collection" implying storage contradict your point: http://www.cs.man.ac.uk/arch/people/j-sargeant/ufolib/node5.html There Sequence is an ordered Collection, which fits both the STL terms and the proposal for "Collection Traits". IMHO the example of range_view(0,100) could happily be called a ForwardCollection - there's no containment but there's a definite ordering. jon

Jonathan Wakely writes:
On Thu, May 06, 2004 at 05:15:56AM -0500, Aleksey Gurtovoy wrote:
Thorsten Ottosen writes:
"Aleksey Gurtovoy" <agurtovoy@meta-comm.com> wrote in message news:073d01c43295$1d7354b0$6401a8c0@metacomm.com... | Pavol Droba writes:
| > You are not quite right. Sequence concept is precisely defined in C++ standard. | | Yes, and that's unfortunate, because it is essentially a dead concept -- "nobody" | writes generic code that relies on it -- that has occupied a good name. In fact, | "Collection" is exactly the word that would perfectly fit to describe what the | standard choose to refer to as "Sequence". I don't think going the other way | around would be a good call.
what would you use for sequence then?
Well, I don't have an ultimate answer, but here's a couple of candidates:
Range Iterator Range View Series Succession
These terms are not synonymous.
I didn't imply they were.
Some imply an ordering, others do not.
Depending on your definition of ordering none or all of them do.
The standard's "Sequence" concept has a definite ordering,
Doesn't matter what standard's "Sequence" concept has; for one, it's a dead concept. A "sequence" as a word in a programmer's dictionary doesn't imply a definite ordering in the sense in which the term is used in the standard; "random sequence" is a perfect, well, sequence.
neither "Collection" not "Container" imply any ordering.
They all guarantee that the 'end' reachable from 'begin', that is, that by repeatedly incrementing 'begin' you'll go through a range of successive elements until you reach the 'end'. I don't see anything inherent in the word "sequence", or, for that matter, "series" or "succession" that implies more than just that. Again, "random series" or "random succession [of something]".
My dictionary defines collection as "an accumulated assortment of things of a particular type" - which sounds ok for this concept. There's no implication of containing or owning the things, so the fact that VB (or CS in general) have used the term to describe ownership is a fault in VB, not the word!
Programming is all about communication; it doesn't matter what the original meaning of the word is/was; what matters is what your teammates think of when they hear it. I'm claiming that most people think of collection classes, i.e. containers with storage.
| In CS terminology, collections are inherently | associated with storage;
can give any examples of this CS terminology?
I don't think there's a good case for either side of the argument. Several of the sites you give as examples of "Collection" implying storage contradict your point:
http://www.cs.man.ac.uk/arch/people/j-sargeant/ufolib/node5.html
Does it? Seems like a supporting case to me: virtual class Collection[T] inherits Any ** insert a T into the collection insert(t:T) : Self[T] is deferred ^^^^^^^^^^^ If that doesn't imply storage, I don't know what does.
There Sequence is an ordered Collection, which fits both the STL terms and the proposal for "Collection Traits".
IMHO the example of range_view(0,100) could happily be called a ForwardCollection - there's no containment but there's a definite ordering.
My problem is that Collection _does_ imply storage for me, and the connotation is continuously reinforced by a numerous examples from all around. -- Aleksey Gurtovoy MetaCommunications Engineering

On Thu, May 06, 2004 at 07:58:49AM -0500, Aleksey Gurtovoy wrote:
The standard's "Sequence" concept has a definite ordering,
Doesn't matter what standard's "Sequence" concept has; for one, it's a dead concept. A "sequence" as a word in a programmer's dictionary doesn't imply a definite ordering in the sense in which the term is used in the standard; "random sequence" is a perfect, well, sequence.
My apologies - I thought this was a discussion of STL-style concepts and their hierarchy.
Programming is all about communication; it doesn't matter what the original meaning of the word is/was; what matters is what your teammates think of when they hear it. I'm claiming that most people think of collection classes, i.e. containers with storage.
Yes, and since ISO 14882 defines Sequence one way that's how I use it. I'm not fervently arguing for "Collection" as a concept, so I'll shut up. jon -- "If you can't beat them, arrange to have them beaten." - George Carlin

Jonathan Wakely writes:
On Thu, May 06, 2004 at 07:58:49AM -0500, Aleksey Gurtovoy wrote:
The standard's "Sequence" concept has a definite ordering,
Doesn't matter what standard's "Sequence" concept has; for one, it's a dead concept. A "sequence" as a word in a programmer's dictionary doesn't imply a definite ordering in the sense in which the term is used in the standard; "random sequence" is a perfect, well, sequence.
My apologies - I thought this was a discussion of STL-style concepts and their hierarchy.
Not quite. Re-reading the beginning of the thread might help to clarify things.
Programming is all about communication; it doesn't matter what the original meaning of the word is/was; what matters is what your teammates think of when they hear it. I'm claiming that most people think of collection classes, i.e. containers with storage.
Yes, and since ISO 14882 defines Sequence one way that's how I use it.
As you choose. I find a commonly accepted meaning of the word much more useful. In any case, that's not what I was arguing about.
I'm not fervently arguing for "Collection" as a concept, so I'll shut up.
Just to make sure we understood each other, I have nothing against "Collection" being a name for a concept in general ;). I'm opposed to using it to name the particular concept under review. -- Aleksey Gurtovoy MetaCommunications Engineering

Alexey wrote:
Well, I don't have an ultimate answer, but here's a couple of candidates:
Range Iterator Range View Series Succession
These terms are not synonymous.
I didn't imply they were.
If you knew they were not synonymous, yet you suggest them as name candidates for a specific concept. This gives me an uneasy feeling of (at least your notion of) the concept.
Some imply an ordering, others do not.
Depending on your definition of ordering none or all of them do.
Ordering should be intrinsic not coincidental.
The standard's "Sequence" concept has a definite ordering,
Doesn't matter what standard's "Sequence" concept has; for one, it's a dead concept. A "sequence" as a word in a programmer's dictionary doesn't imply a definite ordering in the sense in which the term is used in the standard; "random sequence" is a perfect, well, sequence.
neither "Collection" not "Container" imply any ordering.
They all guarantee that the 'end' reachable from 'begin', that is, that by repeatedly incrementing 'begin' you'll go through a range of successive elements until you reach the 'end'. I don't see anything inherent in the word "sequence", or, for that matter, "series" or "succession" that implies more than just that. Again, "random series" or "random succession [of something]".
Those are coincidental orderings. Sequences have an intrinsic ordering, being part of the conceptual structure of the entity. Since a sequential machine only executes one instruction at a time, ALL structures should then be considered ordered according to you, no? I mean, it all starts and ends ;-)
My dictionary defines collection as "an accumulated assortment of things of a particular type" - which sounds ok for this concept. There's no implication of containing or owning the things, so the fact that VB (or CS in general) have used the term to describe ownership is a fault in VB, not the word!
Programming is all about communication; it doesn't matter what the original meaning of the word is/was; what matters is what your teammates think of when they hear it. I'm claiming that most people think of collection classes, i.e. containers with storage.
I think on a quite different beast when I hear "sequence" (at least from a senior CS and/or IT individual) than when I hear "collection."
| In CS terminology, collections are inherently associated with | storage;
can give any examples of this CS terminology?
I don't think there's a good case for either side of the argument. Several of the sites you give as examples of "Collection" implying storage contradict your point:
http://www.cs.man.ac.uk/arch/people/j-sargeant/ufolib/node5.html
Does it? Seems like a supporting case to me:
virtual class Collection[T] inherits Any ** insert a T into the collection insert(t:T) : Self[T] is deferred ^^^^^^^^^^^
If that doesn't imply storage, I don't know what does.
Could you not say that about any altering operation? That any altering operation on a notion implies storage? I think you have a far too pragmatic view on these things, which does not rhyme very well with proper (GP) conceptualization.
There Sequence is an ordered Collection, which fits both the STL terms and the proposal for "Collection Traits".
IMHO the example of range_view(0,100) could happily be called a ForwardCollection - there's no containment but there's a definite ordering.
My problem is that Collection _does_ imply storage for me, and the connotation is continuously reinforced by a numerous examples from all around.
I probably agree that this specific concept, Collection, bears a strong storage component, but do you consider even proxy structures to have "storage."? /David

David Bergman writes:
Alexey wrote:
Well, I don't have an ultimate answer, but here's a couple of candidates:
Range Iterator Range View Series Succession
These terms are not synonymous.
I didn't imply they were.
If you knew they were not synonymous, yet you suggest them as name candidates for a specific concept. This gives me an uneasy feeling of (at least your notion of) the concept.
I don't see why. Would you have a problem with putting "Cursor" and "Iterator" on the same list, if you were to name a beast with 'current', 'next' and 'done' methods? They are not synonyms either.
Some imply an ordering, others do not.
Depending on your definition of ordering none or all of them do.
Ordering should be intrinsic not coincidental.
How's that related to my statement?
The standard's "Sequence" concept has a definite ordering,
Doesn't matter what standard's "Sequence" concept has; for one, it's a dead concept. A "sequence" as a word in a programmer's dictionary doesn't imply a definite ordering in the sense in which the term is used in the standard; "random sequence" is a perfect, well, sequence.
neither "Collection" not "Container" imply any ordering.
They all guarantee that the 'end' reachable from 'begin', that is, that by repeatedly incrementing 'begin' you'll go through a range of successive elements until you reach the 'end'. I don't see anything inherent in the word "sequence", or, for that matter, "series" or "succession" that implies more than just that. Again, "random series" or "random succession [of something]".
Those are coincidental orderings. Sequences have an intrinsic ordering, being part of the conceptual structure of the entity.
Since a sequential machine only executes one instruction at a time, ALL structures should then be considered ordered according to you, no?
If every instruction in a program is executed just once, it definitely imposes an order relationship on them.
I mean, it all starts and ends ;-)
My dictionary defines collection as "an accumulated assortment of things of a particular type" - which sounds ok for this concept. There's no implication of containing or owning the things, so the fact that VB (or CS in general) have used the term to describe ownership is a fault in VB, not the word!
Programming is all about communication; it doesn't matter what the original meaning of the word is/was; what matters is what your teammates think of when they hear it. I'm claiming that most people think of collection classes, i.e. containers with storage.
I think on a quite different beast when I hear "sequence" (at least from a senior CS and/or IT individual) than when I hear "collection."
Which was exactly my point. [...]
Does it? Seems like a supporting case to me:
virtual class Collection[T] inherits Any ** insert a T into the collection insert(t:T) : Self[T] is deferred ^^^^^^^^^^^
If that doesn't imply storage, I don't know what does.
Could you not say that about any altering operation? That any altering operation on a notion implies storage?
No. Changing range boundaries doesn't, for instance. But again, I don't see how it's related to my point.
I think you have a far too pragmatic view on these things, which does not rhyme very well with proper (GP) conceptualization.
There Sequence is an ordered Collection, which fits both the STL terms and the proposal for "Collection Traits".
IMHO the example of range_view(0,100) could happily be called a ForwardCollection - there's no containment but there's a definite ordering.
My problem is that Collection _does_ imply storage for me, and the connotation is continuously reinforced by a numerous examples from all around.
I probably agree that this specific concept, Collection, bears a strong storage component,
Great!
but do you consider even proxy structures to have "storage."?
What's a proxy structure? -- Aleksey Gurtovoy MetaCommunications Engineering

On Thu, May 06, 2004 at 05:15:56AM -0500, Aleksey Gurtovoy wrote:
Thorsten Ottosen writes:
"Aleksey Gurtovoy" <agurtovoy@meta-comm.com> wrote in message news:073d01c43295$1d7354b0$6401a8c0@metacomm.com... | Pavol Droba writes:
| > You are not quite right. Sequence concept is precisely defined in C++ standard. | | Yes, and that's unfortunate, because it is essentially a dead concept -- "nobody" | writes generic code that relies on it -- that has occupied a good name. In fact, | "Collection" is exactly the word that would perfectly fit to describe what the | standard choose to refer to as "Sequence". I don't think going the other way | around would be a good call.
what would you use for sequence then?
Well, I don't have an ultimate answer, but here's a couple of candidates:
Range Iterator Range View Series Succession
Please, add Enumerable to the list. Pavol

"Pavol Droba" <droba@topmail.sk> wrote in message news:20040506110530.GN27321@lenin.felcer.sk... | On Thu, May 06, 2004 at 05:15:56AM -0500, Aleksey Gurtovoy wrote: | > Thorsten Ottosen writes: | > | > > "Aleksey Gurtovoy" <agurtovoy@meta-comm.com> wrote in message news:073d01c43295$1d7354b0$6401a8c0@metacomm.com... [snip] | > Well, I don't have an ultimate answer, but here's a couple of candidates: | > | > Range | > Iterator Range | > View | > Series Series seems to close to math. power series etc. | > Succession | > | Please, add Enumerable to the list. hard choice...let me throw my dice ... aha ... I think Range would be best. Let's assume this library is to be called Range Traits with RangeConcept, ExternalRangeConcept and, ExternalReversibleRangeConcept, can John/Mathew then find a reasonable name for their concept: crange<T> r = make_range( vector ); while( r ) { ++r; *r; } could they call their stuff TraversableRangeConcept or EnumerableRangeConcept or IteratorRangeConcept? br Thorsten

Thorsten Ottosen wrote:
Let's assume this library is to be called Range Traits with RangeConcept, ExternalRangeConcept and, ExternalReversibleRangeConcept, can John/Mathew then find a reasonable name for their concept:
crange<T> r = make_range( vector ); while( r ) { ++r; *r; }
could they call their stuff TraversableRangeConcept or EnumerableRangeConcept or IteratorRangeConcept?
Why invent a new concept? This is an Iterator that is ConvertibleToBool.

"Peter Dimov" <pdimov@mmltd.net> wrote in message news:00aa01c43369$1959e180$1d00a8c0@pdimov2... | Thorsten Ottosen wrote: | > | > Let's assume this library is to be called Range Traits with | > RangeConcept, ExternalRangeConcept and, | > ExternalReversibleRangeConcept, can John/Mathew then find a | > reasonable name for their concept: | > | > crange<T> r = make_range( vector ); | > while( r ) | > { | > ++r; *r; | > } | > | > could they call their stuff TraversableRangeConcept or | > EnumerableRangeConcept or IteratorRangeConcept? | | Why invent a new concept? This is an Iterator that is ConvertibleToBool. because I assume it will also have member functions that makes it a Range, ie, begin(), end(), empty(), size(). So it merges ranges with iterators. br Thorsten

Thorsten Ottosen wrote:
"Peter Dimov" <pdimov@mmltd.net> wrote in message news:00aa01c43369$1959e180$1d00a8c0@pdimov2...
Thorsten Ottosen wrote:
Let's assume this library is to be called Range Traits with RangeConcept, ExternalRangeConcept and, ExternalReversibleRangeConcept, can John/Mathew then find a reasonable name for their concept:
crange<T> r = make_range( vector ); while( r ) { ++r; *r; }
could they call their stuff TraversableRangeConcept or EnumerableRangeConcept or IteratorRangeConcept?
Why invent a new concept? This is an Iterator that is ConvertibleToBool.
because I assume it will also have member functions that makes it a Range, ie, begin(), end(), empty(), size(). So it merges ranges with iterators.
Range is begin(), end(); Iterator is ++ and *, and ConvertibleToBool is if( x ). A concept only specifies the minimal requirements. If we had to invent new concepts for every combination, we wouldn't be able to get anything else done, combinatorial explosion and all. ;-)

"Peter Dimov" <pdimov@mmltd.net> wrote in message news:003b01c4337c$83b49df0$1d00a8c0@pdimov2... | Thorsten Ottosen wrote: [snip]
because I assume it will also have member functions that makes it a | > Range, ie, begin(), end(), empty(), size(). So it merges ranges with | > iterators. | | Range is begin(), end();
So you want size() and empty() to be removed from the Range Traits? |Iterator is ++ and *, and ConvertibleToBool is | if( x ). A concept only specifies the minimal requirements. Couldn't a concept also specify functions that can be built on top of that minimal set? | If we had to | invent new concepts for every combination, we wouldn't be able to get | anything else done, combinatorial explosion and all. ;-) well, in general we agree. br Thorsten

Thorsten Ottosen wrote:
"Peter Dimov" <pdimov@mmltd.net> wrote in message news:003b01c4337c$83b49df0$1d00a8c0@pdimov2...
Thorsten Ottosen wrote: [snip] because I assume it will also have member functions that makes it a
Range, ie, begin(), end(), empty(), size(). So it merges ranges with iterators.
Range is begin(), end();
So you want size() and empty() to be removed from the Range Traits?
I just omitted them for brevity, but since you ask, size() is essential since it can be O(1) when distance( begin(), end() ) is O(N), but it seems to me that empty() is always begin() == end(), so it can be removed. (begin() and end() should be O(1).)

"Peter Dimov" <pdimov@mmltd.net> wrote in message news:00f601c43438$67a5ab60$1d00a8c0@pdimov2... | Thorsten Ottosen wrote: | > "Peter Dimov" <pdimov@mmltd.net> wrote in message | > news:003b01c4337c$83b49df0$1d00a8c0@pdimov2... | >> Thorsten Ottosen wrote: | > [snip] | >> Range is begin(), end(); | > | > So you want size() and empty() to be removed from the Range Traits? | | I just omitted them for brevity, but since you ask, size() is essential | since it can be O(1) when distance( begin(), end() ) is O(N), but it seems | to me that empty() is always begin() == end(), so it can be removed. | (begin() and end() should be O(1).) hm...empty() is O(N) for strings if implemented as end() - begin(), but O(1) currently. br Thorsten

Thorsten Ottosen wrote:
"Peter Dimov" <pdimov@mmltd.net> wrote in message news:00f601c43438$67a5ab60$1d00a8c0@pdimov2...
Thorsten Ottosen wrote:
"Peter Dimov" <pdimov@mmltd.net> wrote in message news:003b01c4337c$83b49df0$1d00a8c0@pdimov2...
Thorsten Ottosen wrote: [snip]
Range is begin(), end();
So you want size() and empty() to be removed from the Range Traits?
I just omitted them for brevity, but since you ask, size() is essential since it can be O(1) when distance( begin(), end() ) is O(N), but it seems to me that empty() is always begin() == end(), so it can be removed. (begin() and end() should be O(1).)
hm...empty() is O(N) for strings if implemented as end() - begin(), but O(1) currently.
Yes, you are right, I missed that. This however reminds me about a related issue. If I read the implementation correctly, the size of T[N] is usually N, but it's N-1 when T is char or wchar_t. I understand that this is being done to support "character literals", but it obviously has the potential to introduce subtle off by one bugs, especially in generic code.

"Peter Dimov" <pdimov@mmltd.net> wrote in message news:001701c43441$fb8d8150$1d00a8c0@pdimov2... | This however reminds me about a related issue. If I read the implementation | correctly, the size of T[N] is usually N, but it's N-1 when T is char or | wchar_t. I understand that this is being done to support "character | literals", but it obviously has the potential to introduce subtle off by one | bugs, especially in generic code. That would be bad especially since it's supposed to remove off-by-one bugs. Exactly kind of trouple are you talking about? br Thorsten

"Thorsten Ottosen" <nesotto@cs.auc.dk> writes:
"Peter Dimov" <pdimov@mmltd.net> wrote in message news:00f601c43438$67a5ab60$1d00a8c0@pdimov2... | Thorsten Ottosen wrote: | > "Peter Dimov" <pdimov@mmltd.net> wrote in message | > news:003b01c4337c$83b49df0$1d00a8c0@pdimov2... | >> Thorsten Ottosen wrote: | > [snip]
| >> Range is begin(), end(); | > | > So you want size() and empty() to be removed from the Range Traits? | | I just omitted them for brevity, but since you ask, size() is essential | since it can be O(1) when distance( begin(), end() ) is O(N), but it seems | to me that empty() is always begin() == end(), so it can be removed. | (begin() and end() should be O(1).)
hm...empty() is O(N) for strings if implemented as end() - begin(), but O(1) currently.
What kind of string doesn't have random-access iterators? Or are you talking about C-strings which would have an O(N) end() function? I am leery of performance discontinuities like O(N) for end(char const*). Maybe it just shouldn't be provided (or something). -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

| > hm...empty() is O(N) for strings if implemented as end() - begin(), but | > O(1) currently. | | What kind of string doesn't have random-access iterators? Or are you | talking about C-strings which would have an O(N) end() function? yes. | I am leery of performance discontinuities like O(N) for end(char | const*). Maybe it just shouldn't be provided (or something). Pavol uses it havily in his string library. The "dangerous" thing would be not to put computation of the end-iterator out-side the loop, eg. for( iterator_type_of<T>::type i = begin( c ); i != end( c ); ... ) ^^^^^^^^^^ ^ is not good. But one wouldn't do that anyway. And if one did it, what are the chances of the argument being a char*? br Thorsten

"Thorsten Ottosen" <nesotto@cs.auc.dk> writes:
| > hm...empty() is O(N) for strings if implemented as end() - begin(), but | > O(1) currently. | | What kind of string doesn't have random-access iterators? Or are you | talking about C-strings which would have an O(N) end() function?
yes.
| I am leery of performance discontinuities like O(N) for end(char | const*). Maybe it just shouldn't be provided (or something).
Pavol uses it havily in his string library. The "dangerous" thing would be not to put computation of the end-iterator out-side the loop, eg.
for( iterator_type_of<T>::type i = begin( c ); i != end( c ); ... ) ^^^^^^^^^^ ^ is not good. But one wouldn't do that anyway. And if one did it, what are the chances of the argument being a char*?
Too many chances are being taken here, IMO. It doesn't feel right. STL's end is guaranteed O(1) and I'm really concerned about anything that violates that expectation. Maybe the string algorithm library ought to use a different name for this; for example: sentinel_type_of<T>::type f = finish( c ); for (iterator_type_of<T>::type i = begin( c ); i != f; ++i) ... In that case, the same mistake for (iterator_type_of<T>::type i = begin( c ); i != finish(c); ++i) ... wouldn't hurt at all. struct sentinel_ {}; template <class T> sentinel_ finish(T*) { return sentinel_(); } template <class T> typename iterator_type_of<T>::type finish(T& x) { return x.end(); } template <class T> typename iterator_type_of<const T>::type finish(T const& x) { return x.end(); } template <class template <class T> bool operator==(T* x, sentinel_) { return !*x; } template <class T> bool operator==(sentinel_, T* x) { return !*x; } template <class T> bool operator!=(T* x, sentinel_) { return *x; } template <class T> bool operator!=(sentinel_, T* x) { return *x; } -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

| > Pavol uses it havily in his string library. The "dangerous" thing would be not to put | > computation of the end-iterator out-side the loop, eg. | > | > for( iterator_type_of<T>::type i = begin( c ); i != end( c ); ... ) | > ^^^^^^^^^^ ^ | > is not good. But one wouldn't do that anyway. And if one did it, what are the chances of | > the argument being a char*? | | Too many chances are being taken here, IMO. the more chances that are taken, the less the likelihood of it all happening. | It doesn't feel right. | STL's end is guaranteed O(1) and I'm really concerned about anything | that violates that expectation. ok. I have forgotte why Pavol want to support char* at all. I mean, programming with manual insertion of null is really error-prone. If char* is considered a range, one might even say std::string s; my_algo( s.buffer() ); // oops, no terminating null! | Maybe the string algorithm library ought to use a different name for | this; for example: | | sentinel_type_of<T>::type f = finish( c ); | for (iterator_type_of<T>::type i = begin( c ); i != f; ++i) | ... A predicate like yours above is better in that context. I think Eric does that in for each. | template <class T> | typename iterator_type_of<const T>::type finish(T const& x) | { return x.end(); } ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ typename const_iterator_of<T>::type br Thorsten

On Sat, May 08, 2004 at 10:07:30PM +1000, Thorsten Ottosen wrote:
| > Pavol uses it havily in his string library. The "dangerous" thing would be not to put | > computation of the end-iterator out-side the loop, eg. | > | > for( iterator_type_of<T>::type i = begin( c ); i != end( c ); ... ) | > ^^^^^^^^^^ ^ | > is not good. But one wouldn't do that anyway. And if one did it, what are the chances of | > the argument being a char*? | | Too many chances are being taken here, IMO.
the more chances that are taken, the less the likelihood of it all happening.
| It doesn't feel right. | STL's end is guaranteed O(1) and I'm really concerned about anything | that violates that expectation.
ok. I have forgotte why Pavol want to support char* at all. I mean, programming with manual insertion of null is really error-prone. If char* is considered a range, one might even say
std::string s; my_algo( s.buffer() ); // oops, no terminating null!
There is a lot of legacy code out there with no counterpart in c++. I don't think, that we can afford not to support it. Just have a look at the Boost Regex interface. char* is still there, and there are reasons for it. An implication of supporting char* is the requirement, that char[] must be threated the same way. If you consider the way how std::string's end() works you have the current specification of the collection traits for string. An example of usecase for all string variants: #include <iostream> #include <string> #include <boost/algorithm/string.hpp> using namespace std; using namespace boost; int main(int argc, char* argv[]) { // check if the first argument contains "hello" // char* is used for input char[] for search specifier iterator_range<char*> r=find_first(argv[0], "hello"); if( !r.empty() ) { // convert the find result (a pair of char*) to std::string string str(r.begin(), r.end()); str+=" "; str+=str; cout << str << endl; } return 0; } An example may not be very usable, but it shows a common pattern, when char*, char[], and std::string are used in one place. Regards, Pavol

On Sat, May 08, 2004 at 06:06:47AM -0400, David Abrahams wrote:
"Thorsten Ottosen" <nesotto@cs.auc.dk> writes:
| > hm...empty() is O(N) for strings if implemented as end() - begin(), but | > O(1) currently. | | What kind of string doesn't have random-access iterators? Or are you | talking about C-strings which would have an O(N) end() function?
yes.
| I am leery of performance discontinuities like O(N) for end(char | const*). Maybe it just shouldn't be provided (or something).
Pavol uses it havily in his string library. The "dangerous" thing would be not to put computation of the end-iterator out-side the loop, eg.
for( iterator_type_of<T>::type i = begin( c ); i != end( c ); ... ) ^^^^^^^^^^ ^ is not good. But one wouldn't do that anyway. And if one did it, what are the chances of the argument being a char*?
Too many chances are being taken here, IMO. It doesn't feel right. STL's end is guaranteed O(1) and I'm really concerned about anything that violates that expectation.
Maybe the string algorithm library ought to use a different name for this; for example:
sentinel_type_of<T>::type f = finish( c ); for (iterator_type_of<T>::type i = begin( c ); i != f; ++i) ...
In that case, the same mistake
for (iterator_type_of<T>::type i = begin( c ); i != finish(c); ++i) ...
wouldn't hurt at all.
struct sentinel_ {};
template <class T> sentinel_ finish(T*) { return sentinel_(); }
template <class T> typename iterator_type_of<T>::type finish(T& x) { return x.end(); }
template <class T> typename iterator_type_of<const T>::type finish(T const& x) { return x.end(); }
template <class template <class T> bool operator==(T* x, sentinel_) { return !*x; }
template <class T> bool operator==(sentinel_, T* x) { return !*x; }
template <class T> bool operator!=(T* x, sentinel_) { return *x; }
template <class T> bool operator!=(sentinel_, T* x) { return *x; }
This is an elegant solution for this particular problem. However iteration is not the only construct, that uses iterators. If you would have a look into the implementaion of the string_algo library, you will see, that there are very few constructs like this. I'm using collection traits facility mostly to extract begin() and end() iterators, that are later forwarded to the iterator based function. This is clearly not possible with "finish". (you cannot, for instance, do following std::copy(begin(c), finish(c), it) ) Strong requirement that end() have complexity of O(N) rules out C-Strings. This is very unfortunate, because this is one of the best use-cases for the collection_traits library. Special threatment of char[] arrays is needed, so thay bahave in the same way as they char* conterparts. (and std::string too). When I used the collection traits for the first time, I was very surprised, that end(char[]) was pointing after the terminating 0. This is definitely not the expected behaviour, therefor it was changed. Regards, Pavol

Thorsten Ottosen wrote:
"Pavol Droba" <droba@topmail.sk> wrote in message news:20040506110530.GN27321@lenin.felcer.sk... | On Thu, May 06, 2004 at 05:15:56AM -0500, Aleksey Gurtovoy wrote: | > Thorsten Ottosen writes: | > | > > "Aleksey Gurtovoy" <agurtovoy@meta-comm.com> wrote in message news:073d01c43295$1d7354b0$6401a8c0@metacomm.com...
[snip]
| > Well, I don't have an ultimate answer, but here's a couple of candidates: | > | > Range | > Iterator Range | > View | > Series
Series seems to close to math. power series etc.
| > Succession | > | Please, add Enumerable to the list.
hard choice...let me throw my dice ... aha ... I think Range would be best.
Let's assume this library is to be called Range Traits with RangeConcept, ExternalRangeConcept and, ExternalReversibleRangeConcept, can John/Mathew then find a reasonable name for their concept:
we'll manage :) -- John Torjo Freelancer -- john@torjo.com -- http://www.torjo.com/logview/ - viewing/filtering logs is just too easy!

John Torjo <john.lists@torjo.com> writes:
Let's assume this library is to be called Range Traits with RangeConcept, ExternalRangeConcept and, ExternalReversibleRangeConcept, can John/Mathew then find a reasonable name for their concept:
I'm afraid I'm going to object to any name of the form "XXX traits" for this library unless it consists entirely of metafunctions. If not, can we just call it the Range library and leave it at that? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

"David Abrahams" <dave@boost-consulting.com> wrote in message news:u65b93t6e.fsf@boost-consulting.com... | John Torjo <john.lists@torjo.com> writes: | | >>Let's assume this library is to be called Range Traits with | >> RangeConcept, ExternalRangeConcept and, | >> ExternalReversibleRangeConcept, can John/Mathew then find a | >> reasonable name for their concept: | | I'm afraid I'm going to object to any name of the form "XXX traits" | for this library unless it consists entirely of metafunctions. even in tr1 regex_traits<> contains normal functions. | If | not, can we just call it the Range library and leave it at that? I have no problems with that. -Thorsten

On Fri, May 07, 2004 at 02:40:02PM +1000, Thorsten Ottosen wrote:
"David Abrahams" <dave@boost-consulting.com> wrote in message news:u65b93t6e.fsf@boost-consulting.com... | John Torjo <john.lists@torjo.com> writes: | | >>Let's assume this library is to be called Range Traits with | >> RangeConcept, ExternalRangeConcept and, | >> ExternalReversibleRangeConcept, can John/Mathew then find a | >> reasonable name for their concept: | | I'm afraid I'm going to object to any name of the form "XXX traits" | for this library unless it consists entirely of metafunctions.
even in tr1 regex_traits<> contains normal functions.
| If | not, can we just call it the Range library and leave it at that?
I have no problems with that.
Would it make sense to move iterator_range to this library as well? (given the fact it was requested to be separated from the string algo lib during the review) After all, it is a minimal encapsulation of the Range concept. If the library will not be only about the traits, it might be natural to put it there. Just my thoughts. Regards, Pavol

"Pavol Droba" <droba@topmail.sk> wrote in message news:20040507065316.GC20346@lenin.felcer.sk... | Would it make sense to move iterator_range to this library as well? | (given the fact it was requested to be separated from the string algo lib | during the review) yes, I was about to ask about that :-) | After all, it is a minimal encapsulation of the Range concept. If | the library will not be only about the traits, it might be natural to | put it there. yes. How about calling it range<> then? I think back then I suggested to call it range<>, but iterator_range was chosen because it was a range of iterators. br Thorsten

On Fri, May 07, 2004 at 07:31:13PM +1000, Thorsten Ottosen wrote:
"Pavol Droba" <droba@topmail.sk> wrote in message news:20040507065316.GC20346@lenin.felcer.sk...
| Would it make sense to move iterator_range to this library as well? | (given the fact it was requested to be separated from the string algo lib | during the review)
yes, I was about to ask about that :-)
| After all, it is a minimal encapsulation of the Range concept. If | the library will not be only about the traits, it might be natural to | put it there.
yes.
How about calling it range<> then? I think back then I suggested to call it range<>, but iterator_range was chosen because it was a range of iterators.
I would stick with iterator_range. Range for concept is fine. Concept is mainly a documentation issue and there, it is easy to clearly state the affinity to containers. It is not same for code entities like iterator_range is. IMO "range" is too broad term to be used this. Regards, Pavol

| On Fri, May 07, 2004 at 07:31:13PM +1000, Thorsten Ottosen wrote: | > "Pavol Droba" <droba@topmail.sk> wrote in message news:20040507065316.GC20346@lenin.felcer.sk... | It is not same for code entities like iterator_range is. IMO "range" is too broad term to be | used this. but considering the class need to be instatiated with an iterator, it this seems to carry double information: typedef vector<int> container; container v; typedef container::iterator iterator; iterator_range<iterator> my_range = make_iterator_range( v.begin(), v.end() ); while range<iterator> my_range = make_range( v.begin(), v.end() ); irange<iterator> my_range = make_irange( v.begin(), v.end() ); says IMO essentially what it must. br Thorsten

"Thorsten Ottosen" <nesotto@cs.auc.dk> writes:
| I'm afraid I'm going to object to any name of the form "XXX traits" | for this library unless it consists entirely of metafunctions.
even in tr1 regex_traits<> contains normal functions.
Then I don't like that name either. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

David Abrahams wrote:
John Torjo <john.lists@torjo.com> writes:
Let's assume this library is to be called Range Traits with RangeConcept, ExternalRangeConcept and, ExternalReversibleRangeConcept, can John/Mathew then find a reasonable name for their concept:
I'm afraid I'm going to object to any name of the form "XXX traits" for this library unless it consists entirely of metafunctions. If not, can we just call it the Range library and leave it at that?
IMO Range library is a too general name, since this is actually just a tool to find the metadata (traits) about a range. (In other words, how will Matt and me call our library? ;) ) And we can think of end(),begin(),... functions as some helpers built on top of the library. Still, I'm ok with it if this will be the general oppinion. Also, another suggestion: How about a range_traits class: template<class C> struct range_traits { typedef typename iterator_of<C>::type iterator; typedef typename const_iterator_of<C>::type iterator; ...etc }; It seems to me it provides a more unified of finding metadata about a range (and it's a traits class ;)) Has this been suggested already? Best, John -- John Torjo Freelancer -- john@torjo.com -- http://www.torjo.com/logview/ - viewing/filtering logs is just too easy!

On Fri, May 07, 2004 at 09:59:44AM +0200, John Torjo wrote:
David Abrahams wrote:
John Torjo <john.lists@torjo.com> writes:
Let's assume this library is to be called Range Traits with RangeConcept, ExternalRangeConcept and, ExternalReversibleRangeConcept, can John/Mathew then find a reasonable name for their concept:
I'm afraid I'm going to object to any name of the form "XXX traits" for this library unless it consists entirely of metafunctions. If not, can we just call it the Range library and leave it at that?
IMO Range library is a too general name, since this is actually just a tool to find the metadata (traits) about a range. (In other words, how will Matt and me call our library? ;) ) And we can think of end(),begin(),... functions as some helpers built on top of the library.
Still, I'm ok with it if this will be the general oppinion.
Also, another suggestion:
How about a range_traits class:
template<class C> struct range_traits { typedef typename iterator_of<C>::type iterator; typedef typename const_iterator_of<C>::type iterator; ...etc };
It seems to me it provides a more unified of finding metadata about a range (and it's a traits class ;)) Has this been suggested already?
There was a long discussion about this issue some time ago. Monolitic class is not an acceptable solution, due to several reasons. Regards, Pavol

"Pavol Droba" <droba@topmail.sk> wrote in message news:20040507074749.GI20346@lenin.felcer.sk... | On Fri, May 07, 2004 at 09:59:44AM +0200, John Torjo wrote: | > IMO Range library is a too general name, since this is actually just a | > tool to find the metadata (traits) about a range. (In other words, how | > will Matt and me call our library? ;) ) I think that decision is best made sooner than later. | > And we can think of end(),begin(),... functions as some helpers built on | > top of the library. Here's my view of a Boost.Range as John/Matthew are working on. - It is an analog to Boost.Iterator with * adapters for quick coding of ranges * a number of range concepts * a bunch of special ranges like istream_range, indirect_range The other part of Ranges is algorithms that work on them and it need not be bundled with Boost.Range. For example, most string algorithms works on ranges and are part of their own library. Back to our original problem; what do we call this library under review if it's not Boost.Range nor Boost.RangeTraits? Some new possibilities Boost.RangeAdapter Boost.ExternalRange remark: people haven't said much about the name ExternalConcept, but maybe AdaptedConcept would be better? ie this library would be implementing the AdaptedRangeConcept? | > Also, another suggestion: | > | > How about a range_traits class: [snip] | There was a long discussion about this issue some time ago. Monolitic | class is not an acceptable solution, due to several reasons. the reason is IIRC that one can seperate functionality into several independent headers. br Thorsten.

"Thorsten Ottosen" <nesotto@cs.auc.dk> writes:
remark: people haven't said much about the name ExternalConcept, but maybe AdaptedConcept would be better? ie this library would be implementing the AdaptedRangeConcept?
A concept whose name ends in "Concept" is as odious as a type whose name ends in "type" ;-) -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

Mr. Abrahams wrote:
remark: people haven't said much about the name ExternalConcept, but maybe AdaptedConcept would be better? ie this library would be implementing the AdaptedRangeConcept?
A concept whose name ends in "Concept" is as odious as a type whose name ends in "type" ;-)
Unless it is a meta concept in the sense of being concept for modelling types which themselves represent concepts in an automated GP framework (e.g., a diagramming tool for GP programmers)... /David

Mr. Abrahams wrote:
remark: people haven't said much about the name ExternalConcept, but maybe AdaptedConcept would be better? ie this library would be implementing the AdaptedRangeConcept?
A concept whose name ends in "Concept" is as odious as a type whose name ends in "type" ;-)
Unless it is a meta concept in the sense of being concept for modelling types which themselves represent concepts in an automated GP framework (e.g., a diagramming tool for GP programmers)... /David

Mr. Abrahams wrote:
remark: people haven't said much about the name ExternalConcept, but maybe AdaptedConcept would be better? ie this library would be implementing the AdaptedRangeConcept?
A concept whose name ends in "Concept" is as odious as a type whose name ends in "type" ;-)
Unless it is a meta concept in the sense of being concept for modelling types which themselves represent concepts in an automated GP framework (e.g., a diagramming tool for GP programmers)... /David

Mr. Abrahams wrote:
remark: people haven't said much about the name ExternalConcept, but maybe AdaptedConcept would be better? ie this library would be implementing the AdaptedRangeConcept?
A concept whose name ends in "Concept" is as odious as a type whose name ends in "type" ;-)
Unless it is a meta concept in the sense of being concept for modelling types which themselves represent concepts in an automated GP framework (e.g., a diagramming tool for GP programmers)... /David

"Thorsten Ottosen" <nesotto@cs.auc.dk> wrote in message news:c7fm95$pfj$1@sea.gmane.org... | | > How about a range_traits class: | [snip] | | | There was a long discussion about this issue some time ago. Monolitic | | class is not an acceptable solution, due to several reasons. | | the reason is IIRC that one can seperate functionality into several independent headers. And of course, that we wanted mpl compatible type-generators. br Thorsten

From: Pavol Droba <droba@topmail.sk>
On Fri, May 07, 2004 at 09:59:44AM +0200, John Torjo wrote:
How about a range_traits class:
template<class C> struct range_traits { typedef typename iterator_of<C>::type iterator; typedef typename const_iterator_of<C>::type iterator; ...etc };
It seems to me it provides a more unified of finding metadata about a range (and it's a traits class ;)) Has this been suggested already?
There was a long discussion about this issue some time ago. Monolitic class is not an acceptable solution, due to several reasons.
Why not have both? All it takes is a new header that defines this new traits class. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

John Torjo <john.lists@torjo.com> writes:
IMO Range library is a too general name, since this is actually just a tool to find the metadata (traits) about a range. (In other words, how will Matt and me call our library? ;) )
Maybe it's an "iterator range" library?
And we can think of end(),begin(),... functions as some helpers built on top of the library.
Still, I'm ok with it if this will be the general oppinion.
Also, another suggestion:
How about a range_traits class:
template<class C> struct range_traits { typedef typename iterator_of<C>::type iterator; typedef typename const_iterator_of<C>::type iterator; ...etc };
It seems to me it provides a more unified of finding metadata about a range (and it's a traits class ;)) Has this been suggested already?
Degenerate traits "blobs" are a bad idea; they don't interoperate well with MPL for example. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

Do you think the library should be accepted as a Boost library? Definitely. ________________ What is your evaluation of the design? Excellent. ________________ What is your evaluation of the implementation? Generally clean and straightforward. I'd prefer "primary specialization" to "default" in the comments. Lines longer than 80 columns in a number of files. detail/common.hpp is particularly hard to view in 80 columns. Inconsistent indentation among the files. I question the value of separating iterator_of and const_iterator_of in separate files given how similar they are. Wrong comment on std::pair specialization of result_iterator_of. Why isn't result_iterator_of implemented in terms of iterator_of and const_iterator_of? As it stands, it duplicates the code in iterator.hpp and const_iterator.hpp. Collocating their implementation would reduce the chances of maintenance errors. Extra indentation on non-MSVC version of the std::istream_iterator's size function (size.hpp). Couldn't the primary specialization of size_type be to use SFINAE to check for a nested size_type type or else std::size_t? You wouldn't need any specializations then. "Sise" [sic] is misspelled in sizer.hpp. Shouldn't sizer.hpp be in detail? Indentation in the detail files could be lessened with "namespace boost { namespace collection_traits_detail {". Extra "size help" comment block at tail of detail/implementation_help.hpp. ________________ What is your evaluation of the documentation? The documentation is, overall, very good. Some key points are listed here. Detailed comments and corrections appear at the end of this message. The Introduction is missing a motivation section. It goes from a short description to an example. It should help the reader understand why the library is valuable. The Introduction is missing discussion of the use of namespace scope functions to do what heretofore would be done via member functions. Instead, the example and the sentence immediately following it imply this change of syntax. Using the namespace scope functions is central to the library, so it should be stated early and clearly. ________________ What is your evaluation of the potential usefulness of the library? Highly useful. ________________ Did you try to use the library? No. ________________ How much effort did you put into your evaluation? More than an hour. ________________ Are you knowledgeable about the problem domain? Yes. ________________________________________________________________ Documentation Comments ________________ Collection.htm All other HTML files use lowercase names and the .html suffix Collection Description bullet 1: Change "It" to "A Collection" bullet 1: Change "should cover" to "must exceed" bullet 2: "Semantics" is plural, but I'd suggest rewriting as, "There are no requirements for how or whether a Collection is copyable." para 2: Change "by-reference" to "by reference" Associated types row 1: Delete "Otherwise." Unless I'm mistaken, the value type must be CopyConstructible regardless of whether the Collection is mutable. row 2: The iterator type must be *at least* an InputIterator, right? row 3: Change "not to modify" to "not modify" to make it read better row 4: Change "reference" to "non-const reference" for clarity row 6: Change "pointer" to "non-const pointer" for clarity rows 4-6: "Behaves like/as" is rather vague. I'm not entirely certain what you mean to say so I can't offer suggestions at this time. Notation - this appears after the first use of "X" in the preceding table Expression semantics Omit the first column to leave more room for the others; the names are already given in the "Valid expressions" table. row 1-2: "Past-the-end" is not defined and could be interpreted to mean any distance past the end; this is a well understood notion, so there may be no reason to do more than you have. I'm just trying to be thorough. Complexity guarantees empty() should be listed on its own line. Notes What do you mean by "equivalent to?" Clearly, they needn't be the same type, but what operations must the reference type provide to be "equivalent to" the value type? ________________ index.html Introduction para 1: How about "ExtrinsicCollectionConcept" instead of "ExternalCollectionConcept?" para 2: Missing colon at EOL para 3: Change to read, "Here is a small example illustrating the use of Collection Traits (the full example can be found here):" example code: Inconsistent template parameters: "ExternalCollection" versus "EC" para 4: To the casual reader, there are no type generators in the example; everything looks like a "free-standing function." Better might be to change to read, "By using the facilities of this library, my_generic_replace() automatically works for all Collections." para 4: Change the last sentence to read, "See The Forwarding Problem for information on why there are two versions of find() in the example." That way, you don't confuse folks in the Introduction with "we cannot forward a non-const rvalue with reference arguments!" Reference This should be on its own page. You should explain the term, "type generator," by linking to http://www.boost.org/more/generic_programming.html#type_generator bullet 5: Change "denotes" to "denote" para 2: Change the first sentence to read, "It is worth noting that some functionality requires partial template specialization. In particular, full array support requires it, but boost::array is typically a better choice." para 2: Change "special" to "specially" in the last sentence ExternalCollectionConcept para 1: Change the second paragraph to read, "Even though...boost, additions to the library, to support new types, can be done in any namespace." Synopsis comment, between result_iterator_of and begin(): Change "funtions" to "functions" Semantics para 1: Change "an iterator which default" to "an iterator type for which default" table 1, row 3, col 2: Shouldn't "P::first_type" be "const P::first_type?" I think this is addressed by a FAQ. table 1, row 3, col 2: Shouldn't "I" be "const I?" table 2, row 2, col 3: Lines wrap so there is no clear demarcation between the four effects; perhaps you should use an unordered list (bullets) in this column para 2: Change "behaves differently" to "behave differently" para 2: I presume "these cases" refers to size() and end(), but that isn't clear. If that's your intent, then I suggest, "Note that the null pointer is allowed as an argument to size() and end()." Otherwise, you need to clarify the sentence. Portability para 2: Change "rely of" to "rely on" para 2: "...one needs to supply...f it is required" is confusing. Is it required? When? FAQ FAQ 1: The answer isn't satisfying. Why is it not possible in general? Why is it not desirable in general? The last sentence is, I think, meant to be a workaround for the missing functionality, but isn't clear on that point. FAQ 2: Change to read, "Why doesn't the library support type <I>your favorite type</I> or function <I>your favorite function</I>?" ________________ external_concepts.html How about "extrinsic" rather than "external?" Isn't "namespace scope" more appropriate than "free-standing" when describing the functions? para 2: Change "which provides the exact" to "which provide the exact" para 2: Change "the new requirements constitutes" to "the new requirements constitute" para 2: The second to last sentence is lacking. I suggest changing it to, "We say that a type, for which the free-standing functions and typedefs adapt the type to fulfill the requirements of an external concept, conforms to an external concept or that is is a model of an external concept." para 3: Add a heading: "Translating between External Concepts and Concepts" para 3: Change "qulifiers" to "qualifiers" para 3: Change "has the name as the nested typedef with _of appended" to "has the same name as the nested typedef plus a suffix of _of." Example para 1: Change "follwing" to "following" para 3: Change "type-generators exists" to "type-generators exist" -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

Hi Rob. Thanks for you review. | I'd prefer "primary specialization" to "default" in the comments. ok. Is that the correct term? | Lines longer than 80 columns in a number of files. | detail/common.hpp is particularly hard to view in 80 columns. is that a requirement? If so, I will change it. | I question the value of separating iterator_of and | const_iterator_of in separate files given how similar they are. Some like it...others don't. I guess I will use the bigger headers mostly. | Wrong comment on std::pair specialization of result_iterator_of. thanks. | Why isn't result_iterator_of implemented in terms of iterator_of | and const_iterator_of? As it stands, it duplicates the code in | iterator.hpp and const_iterator.hpp. Collocating their | implementation would reduce the chances of maintenance errors. True. But the implementation is so simple, that it hardly helps to put the code thruogh another layer of templates. Doing so might give longer compiles. And some people care about minimal headers. | Couldn't the primary specialization of size_type be to use SFINAE | to check for a nested size_type type or else std::size_t? You | wouldn't need any specializations then. I guess it could. My only problem is that I don't know how portable this is. AFAIK, detecting nested typedefs only works with Comeau. | "Sise" [sic] is misspelled in sizer.hpp. Shouldn't sizer.hpp be | in detail? yes. maybe. I don't find it very useful. But if people do, I can put BOOST_COMPILE_TIME_ARRAY_SIZE() macro in detail/array_size.hpp. | Indentation in the detail files could be lessened with "namespace | boost { namespace collection_traits_detail {". yes. | The Introduction is missing a motivation section. It goes from a | short description to an example. It should help the reader | understand why the library is valuable. IMO the introduction is the motivation. what would you like to see in a motivation section? | The Introduction is missing discussion of the use of namespace | scope functions to do what heretofore would be done via member | functions. Instead, the example and the sentence immediately | following it imply this change of syntax. Wouldn't it only duplicate stuff in the two links to CollectionCocept and ExternalConcepts? | Using the namespace | scope functions is central to the library, so it should be stated | early and clearly. ok. I should add something about extending the lib + how to rely on ADL. | Documentation Comments Thanks. I will look into them when ) update the docs. br Thorsten

From: "Thorsten Ottosen" <nesotto@cs.auc.dk>
| I'd prefer "primary specialization" to "default" in the comments.
ok. Is that the correct term?
A "specialization" of a template is the result of instantiating it, so the more accurate term, as given in Vandevoorde and Josuttis, is "primary template."
| Lines longer than 80 columns in a number of files. | detail/common.hpp is particularly hard to view in 80 columns.
is that a requirement? If so, I will change it.
It's in http://www.boost.org/more/lib_guide.htm#Guidelines.
| Why isn't result_iterator_of implemented in terms of iterator_of | and const_iterator_of? As it stands, it duplicates the code in | iterator.hpp and const_iterator.hpp. Collocating their | implementation would reduce the chances of maintenance errors.
True. But the implementation is so simple, that it hardly helps to put the code thruogh another layer of templates. Doing so might give longer compiles. And some people care about minimal headers.
I should think the minor increase in compilation time this would trigger would be largely unnoticed and the reuse and resultant prevention of future errors would be wise. You might think that the tests will discover any such problem, but only if the maintainer thinks to change all affected tests. Through reuse, any correction made to, say, iterator_of will be a correction to result_iterator_of.
| Couldn't the primary specialization of size_type be to use SFINAE | to check for a nested size_type type or else std::size_t? You | wouldn't need any specializations then.
I guess it could. My only problem is that I don't know how portable this is. AFAIK, detecting nested typedefs only works with Comeau.
I don't know the answer.
| "Sise" [sic] is misspelled in sizer.hpp. Shouldn't sizer.hpp be | in detail?
yes. maybe. I don't find it very useful. But if people do, I can put BOOST_COMPILE_TIME_ARRAY_SIZE() macro in detail/array_size.hpp.
Right now, all code in sizer.hpp is in boost::collection_traits_detail; hence my suggestion.
| The Introduction is missing a motivation section. It goes from a | short description to an example. It should help the reader | understand why the library is valuable.
IMO the introduction is the motivation. what would you like to see in a motivation section?
"When writing generic code that works with Standard Library containers, one often finds it desirable to extend that code to work with other types that offer enough functionality to satisfy the needs of the generic code, but in an altered form. For example, raw arrays are often suitable for use with generic code that works with containers, provided a suitable adapter is used. Likewise, null terminated strings can be treated as containers of characters, if suitably adapted. This library provides the means to adapt Standard Library containers, null terminated strings, std::pairs of iterators, and raw arrays, such that the same generic code can work with them all."
| The Introduction is missing discussion of the use of namespace | scope functions to do what heretofore would be done via member | functions. Instead, the example and the sentence immediately | following it imply this change of syntax.
Wouldn't it only duplicate stuff in the two links to CollectionCocept and ExternalConcepts?
In a sense, yes, but what I'm proposing is a much abbreviated form: "To allow generic code to work with objects that conform to the ExternalCollectionConcept, this library provides a set of namespace scope functions and <A href="http://www.boost.org/more/generic_programming.html#type_generator">type generators</A> that provide a standard interface for the required functionality. Whereas one might write, "c.end()," to get the end iterator from a Standard Library container, c, using this library, it would be written, "boost::end(c)." This change in syntax is necessary to make the same interface possible with the other supported types such as null terminated strings." -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

I'd prefer "primary specialization" to "default" in the comments.
Lines longer than 80 columns in a number of files. detail/common.hpp is particularly hard to view in 80 columns.
why would you want to view it in 80 columns? IMO 80 cols per line is quite a thing of the past. Nowadays, 100 or even more is more appropriate. On my 21" monitor :) I have my IDE set to 110 cols/line. Best, John -- John Torjo Freelancer -- john@torjo.com -- http://www.torjo.com/logview/ - viewing/filtering logs is just too easy!

John Torjo wrote:
I'd prefer "primary specialization" to "default" in the comments.
Lines longer than 80 columns in a number of files. detail/common.hpp is particularly hard to view in 80 columns.
why would you want to view it in 80 columns? IMO 80 cols per line is quite a thing of the past. Nowadays, 100 or even more is more appropriate. On my 21" monitor :) I have my IDE set to 110 cols/line.
I use Vim with one vertical split giving me ~85 cols per file, so IMO 80 isn't a thing of the past, at least not for me.. -- Daniel Wallin

Daniel Wallin wrote:
John Torjo wrote:
I'd prefer "primary specialization" to "default" in the comments.
Lines longer than 80 columns in a number of files. detail/common.hpp is particularly hard to view in 80 columns.
why would you want to view it in 80 columns? IMO 80 cols per line is quite a thing of the past. Nowadays, 100 or even more is more appropriate. On my 21" monitor :) I have my IDE set to 110 cols/line.
I use Vim with one vertical split giving me ~85 cols per file, so IMO 80 isn't a thing of the past, at least not for me..
the thing is that until about 2 years ago I also sticked to the 80 cols/line thing. But, after letting it go, the code became much easier to read (did not have to split it across multiple lines). But that's just me ;) Best, John -- John Torjo Freelancer -- john@torjo.com -- http://www.torjo.com/logview/ - viewing/filtering logs is just too easy!

From: John Torjo <john.lists@torjo.com>
I'd prefer "primary specialization" to "default" in the comments.
Lines longer than 80 columns in a number of files. detail/common.hpp is particularly hard to view in 80 columns.
why would you want to view it in 80 columns? IMO 80 cols per line is quite a thing of the past. Nowadays, 100 or even more is more appropriate. On my 21" monitor :) I have my IDE set to 110 cols/line.
I regularly use a wide emacs with two buffers side by side. 80 columns in each, plus the decorations fits within the confines of my screen. Indeed, I have three such instances of emacs on my right monitor as I type, and another in my left monitor (actually, one each in each of three different virtual desktops on my left monitor). Furthermore, 80 columns is still an appropriate line limit for printing to avoid messy line wrapping or truncation. Still another means of viewing it is e-mail. Many e-mail clients operate in 80 columns. I find longer lines harder to read because the end of one line is harder to match with the beginning of the next. Given a particular fixed width font, sized for comfortable reading, the longer the line, the worse the problem. Finally, as I cited in my reply to Thorsten, its in the Boost Library Guidelines. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

- What is your evaluation of the design? I think it's a correct, lean mapping of the important collection/sequence concepts.
I'm pleased to see that the refactoring to use separate traits-classes/metafunctions as I suggested during a pre-review has been applied. I would also assume mr Stepanov himself would like it since it makes begin()/end() free functions at last :-)
- What is your evaluation of the implementation? Would it make sense to treat a boost two-tuple as a collection similar to std::pair? Perhaps also boost::compressed_pair?
- What is your evaluation of the documentation? Looks OK. I miss an index.html file in the top directory. I like colors, so perhaps use the boost-book stylesheets? Or ideally a full boost-book transfer I guess.
- What is your evaluation of the potential usefulness of the library? A much needed component paving the way for a boost::range_stl(?) and boost::view
Shouldn't the docs and examples recommend using unqualified calls to begin()/end() to support ADL? (present in the 'find' example for example) library and also clean integration of arrays in generic code.
- Did you try to use the library? With what compiler? Did you have any problems? Used VC7.1 for some quick tests with no problems.
- How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? Reading docs and briefly looking at code both for the review version and a couple of the previos versions in sandbox.
- Are you knowledgeable about the problem domain? Yes.
I think the library should be accepted! Regards // Fredrik Blomqvist

Hi Fredrik, Thanks for your review. | >- What is your evaluation of the implementation? | Would it make sense to treat a boost two-tuple as a collection similar to | std::pair? I guess it would. Maybe tuple<X,Y> should inherit from std::pair<X,Y> to make this work no matter where we use std::pair? | Perhaps also boost::compressed_pair? what use would it be if one iterator was missing? | >- What is your evaluation of the documentation? | Looks OK. I miss an index.html file in the top directory. Hartmut told me the index.html should be in the parent dir. | I like colors, so perhaps use the boost-book stylesheets? ok. |Or ideally a full | boost-book transfer I guess. If there is a tool that can convert; otherwise I would be reluctant. | Shouldn't the docs and examples recommend using unqualified calls to | begin()/end() | to support ADL? (present in the 'find' example for example) they should at least discuss the trade-off involved. And I guess unqualified calls should be preferred as in void foo( C& c ) { using namespace boost; bar( begin( c ), end( c ),... ); } br Thorsten

Thorsten Ottosen wrote:
Perhaps also boost::compressed_pair?
what use would it be if one iterator was missing? My thought was that it could perhaps show up as an "artifact" of generic code(?). Don't know if it's worth it though, just an idea.
Shouldn't the docs and examples recommend using unqualified calls to begin()/end() to support ADL?
they should at least discuss the trade-off involved. And I guess unqualified calls should be preferred as in
void foo( C& c ) { using namespace boost; bar( begin( c ), end( c ),... ); }
Yes, exactly. ---- Another thing I just noticed in the code is the use of <boost/detail/iterator_traits.hpp>. I think would be better to rely on the official <boost/iterator/iterator_traits.hpp> instead. Altough the latter _currently_ simply forwards to the former I would expect anything in a 'detail' namespace to be more volatile. Regards // Fredrik Blomqvist

This simple test fails to compile on gcc-3.3.3. Any thoughts? #include <boost/collection_traits.hpp> #include <iostream> #include <iterator> #include <algorithm> using namespace std; int F (int size) { int a[size]; copy (boost::begin (a), boost::end (a), ostream_iterator<int> (cout, " ")); } g++ -o Test -g Test.cc -I /usr/local/src/boost_1_31_0 /usr/local/src/boost_1_31_0/boost/collection_traits/begin.hpp: In function ` const T* boost::collection_traits::begin(const T (&)[sz])': /usr/local/src/boost_1_31_0/boost/collection_traits/begin.hpp:70: error: variable-size type declared outside of any function /usr/local/src/boost_1_31_0/boost/collection_traits/begin.hpp:70: error: variable-size type declared outside of any function /usr/local/src/boost_1_31_0/boost/collection_traits/begin.hpp: In function `T* boost::collection_traits::begin(T (&)[sz])': /usr/local/src/boost_1_31_0/boost/collection_traits/begin.hpp:76: error: variable-size type declared outside of any function /usr/local/src/boost_1_31_0/boost/collection_traits/begin.hpp:76: error: variable-size type declared outside of any function Test.cc: In function `int F(int)': Test.cc:11: error: call of overloaded `begin(int[((size - 1) + 1)])' is ambiguous /usr/local/src/boost_1_31_0/boost/collection_traits/begin.hpp:101: error: candidates are: wchar_t* boost::collection_traits::begin(wchar_t*) <near match> /usr/local/src/boost_1_31_0/boost/collection_traits/begin.hpp:96: error: const wchar_t* boost::collection_traits::begin(const wchar_t*) <near match> /usr/local/src/boost_1_31_0/boost/collection_traits/end.hpp: In function `const T* boost::collection_traits::end(const T (&)[sz])': /usr/local/src/boost_1_31_0/boost/collection_traits/end.hpp:71: error: variable-size type declared outside of any function /usr/local/src/boost_1_31_0/boost/collection_traits/end.hpp:71: error: variable-size type declared outside of any function /usr/local/src/boost_1_31_0/boost/collection_traits/end.hpp: In function `T* boost::collection_traits::end(T (&)[sz])': /usr/local/src/boost_1_31_0/boost/collection_traits/end.hpp:77: error: variable-size type declared outside of any function /usr/local/src/boost_1_31_0/boost/collection_traits/end.hpp:77: error: variable-size type declared outside of any function Test.cc: In function `int F(int)': Test.cc:11: error: call of overloaded `end(int[((size - 1) + 1)])' is ambiguous /usr/local/src/boost_1_31_0/boost/collection_traits/end.hpp:101: error: candidates are: const wchar_t* boost::collection_traits::end(const wchar_t*) <near match> /usr/local/src/boost_1_31_0/boost/collection_traits/end.hpp:91: error: wchar_t* boost::collection_traits::end(wchar_t*) <near match>

Neal D. Becker wrote:
This simple test fails to compile on gcc-3.3.3. Any thoughts?
#include <boost/collection_traits.hpp> #include <iostream> #include <iterator> #include <algorithm>
using namespace std;
int F (int size) { int a[size];
copy (boost::begin (a), boost::end (a), ostream_iterator<int> (cout, " ")); }
Adding these specializations fixes the variable size array problem, at least with gcc-3.4. Is there a reason for not using these? ---------------------------------------- template< typename T > inline const T* begin( const T* array) { return array; } template< typename T > inline T* begin( T* array) { return array; } ----------------------------------------- collections has the more complex: template< typename T, std::size_t sz > inline const T* begin( const T (&array)[sz] ) { return array; } template< typename T, std::size_t sz > inline T* begin( T (&array)[sz] ) { return array; } -------------------------------------------

Hi Neal, "Neal D. Becker" <ndbecker2@verizon.net> wrote in message news:c7g0qv$h1a$1@sea.gmane.org... [snip example] | Adding these specializations fixes the variable size array problem, at least | with gcc-3.4. Is there a reason for not using these? Maybe not for begin(), but end() would still need it. I think however that it would also break code that passes ranges by &. IIRC, T(&)[sz] cannot decay to T*. br Thorsten

"Neal D. Becker" <ndbecker2@verizon.net> wrote in message news:c7fv0m$bs4$1@sea.gmane.org... | This simple test fails to compile on gcc-3.3.3. Any thoughts? the tests works with gcc 3.3.1. | int F (int size) { | int a[size]; ^^^^^^ not legal, size must be a constant. br Thorsten

Thorsten Ottosen wrote:
"Neal D. Becker" <ndbecker2@verizon.net> wrote in message news:c7fv0m$bs4$1@sea.gmane.org... | This simple test fails to compile on gcc-3.3.3. Any thoughts?
the tests works with gcc 3.3.1.
| int F (int size) { | int a[size];
^^^^^^
not legal, size must be a constant.
variable size array are c99 extension. Supported by g++ (supposedly). IIRC under consideration for addition to ANSI c++? Only problem is, I don't know how to write a template that matches a variable size array.

"Neal D. Becker" <ndbecker2@verizon.net> wrote in message news:c7g7r8$3un$1@sea.gmane.org... | variable size array are c99 extension. Supported by g++ (supposedly). IIRC | under consideration for addition to ANSI c++? | | Only problem is, I don't know how to write a template that matches a | variable size array. I don't know either. I can say for sure that my library don't support non-C++ features, at least not on purpose. :-) MOO is that variable size arrays are called std::vector<>. br Thorsten
participants (20)
-
Aleksey Gurtovoy
-
Carl Daniel
-
Daniel Wallin
-
Darryl Green
-
David Abrahams
-
David Bergman
-
Fredrik Blomqvist
-
hartmutkaiser@t-online.de
-
Joel de Guzman
-
John Torjo
-
Jonathan Wakely
-
Justinas V.D.
-
Neal D. Becker
-
Pavel Vozenilek
-
Pavol Droba
-
Peter Dimov
-
Rob Stewart
-
Roland Richter
-
Thorsten Ottosen
-
Vladimir Prus