February 2004 - Boost - lists.boost.org

Re: 4 more associative containers.
by Rich Sposato 03 Feb '04

03 Feb '04

Maxim Yegorushkin wrote: > I had difficulty storing and finding boost::intrusive_ptr<> in std::set<>. > When I wanted to check if an arbitrary pointer value was in that set like: > struct some {/*...*/}; > typedef boost::intrusive_ptr<some> some_ptr; > typedef std::set<some_ptr> some_set; > some_set set; > bool exists(some const* s) > { > return set.find(s) != set.end(); > } > void foo() > { > bool b = exists(reinterpret_cast<some*>(0xdeadbeaf)); // boom > } > as std::set::find() requires a key value, it ended up with constructing the > smart pointer from a bogus value trying to do add_ref() and then release() > on that value which led to runtime errors. > If std::set<> had been able to use not a key value for find() but a key > comparable value I would not have had any problems with that code. I had similar problems with a conversion constructor getting invoked when I wanted to pass a pointer or value into std::set::find or std::multiset::count. That was one of the dificulties which led me to create flex_set and its related classes. Since flex_set does not require a temporary object, it also does not silently invoke a conversion constructor. Rich

1 0

Re: 4 more associative containers.
by Rich Sposato 03 Feb '04

03 Feb '04

On Mon, Feb 02, 2004 at 11:50:45PM -0800, Rich Sposato wrote: > > The containers are called flex_set, flex_map, flex_multiset, and > > flex_multimap. They are similar to the 4 STL associative containers. > > There are two important differences between the STL containers and these: > > 1. You can search on any type that is comparable to the key_type, rather > > than just the key_type. (The STL associative containers only allows > > searches on the same type as the key.) > > 2. You do *not* need to create a temporary object of key_type to search > > through the containers. (The STL containers require you to create one > > temporary object to search for another.) > A good idea. I recall wishing for something like this a while ago; I > don't remember if it stemmed from an actual problem in practice or just > general unhappiness with the std:: interface in theory. > (It might be even more swell if comparators could know about > 'equivalence' as well, so you could test for equivalence using one > user-defined function, rather than two calls like !c(x,y)&&!c(y,x).) This seems like a good suggestion since it would provide a slight efficiency since the comparison will only be done once rather than twice. When I looked through flex_set implementation, I found only two places where equivalence is tested. Both of those are inside insert member functions. So, there is a benefit to adding an equivalence function to the comparison functor. Since there is no reason to templatize the insert functions, the equivalence function will not need to be overloaded as the function operators are. Using the Employee example to define an equivalence function, I guess it will look like this: struct CompareEmployees : std::binary_function< const Employee *, const Employee *, bool > { // rest of functor as shown in the introductory message. inline bool equivalent( const Employee * l, const Employee * r ) const { return ( l->GetName() == r->GetName() ); } }; Would anybody prefer a different function name beside equivalent? > Do you have have documentation of the new 'concepts'? Specifically it > seems like flex_xxxx<T> uses a new ComparableTo<T,U> concept to place > requirements on both the Comparator and the template arguments to > methods like find(). The only any documentation on it so far is what is on my website, and what I wrote for the journal, Overload. Most of my website's description of flex_set is already mentioned in the introductory post to this mail list. The ComparableTo< T, U > concept is enforced by the compiler and the comparator. In theory, the templated member functions can work with any type. But in practice, the compiler can only use one of the overloaded function operators in the comparator with a specific call to one of the templated member functions of flex_set. To designate that a specific type is comparable to the flex_set's key_type, just add another overloaded operator to the comparator. Say, if I wanted to compare an Employee object to a Customer object, I would just add two more functions like this: struct CompareEmployees : std::binary_function< const Employee *, const Employee *, bool > { // rest of functor as shown in the introductory message. inline bool operator () ( const Employee * l, const Customer * r ) const { return ( l->GetName() < r->GetName() ); } inline bool operator () ( const Customer * l, const Employee * r ) const { return ( l->GetName() < r->GetName() ); } }; Rich Sposato

1 0

Re: [boost] Re: 4 more associative containers.
by JOAQUIN LOPEZ MU?Z 03 Feb '04

03 Feb '04

----- Mensaje original ----- De: "David B. Held" <dheld(a)codelogicconsulting.com> Fecha: Martes, Febrero 3, 2004 8:00 pm Asunto: [boost] Re: 4 more associative containers. > "Jeremy Maitin-Shepard" <jbms(a)attbi.com> wrote in message > news:87u128yr3g.fsf@jbms.ath.cx... > > I believe that a library named ``indexed_set,'' which has been > > proposed and is pending formal review, provides this functionality > > in addition to supporting multiple indices. > > Are you sure it does the same thing? I was under the impression > that Joaquin's library lets you define *additional* indexes, but what > if you just want to use an existing index, but it is comparable to > something other than the key_type? > indexed_set does provide this functionality (multiple indices aside.) See http://tinyurl.com/2vu5g, section "Special lookup operations". See also http://tinyurl.com/3dyzh, section "Index set operations" for a formal definition of the kind of special lookup operations provided. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

1 0

4 more associative containers.
by Rich Sposato 03 Feb '04

03 Feb '04

Hi Everyone, This is my debut post on Boost, and I would like to introduce some container classes I made so they can be considered for inclusion into Boost. (I made a similar post on STLport, but members of STLport suggested that Boost would be a better forum because STLport only has standard containers.) The containers are called flex_set, flex_map, flex_multiset, and flex_multimap. They are similar to the 4 STL associative containers. There are two important differences between the STL containers and these: 1. You can search on any type that is comparable to the key_type, rather than just the key_type. (The STL associative containers only allows searches on the same type as the key.) 2. You do *not* need to create a temporary object of key_type to search through the containers. (The STL containers require you to create one temporary object to search for another.) The flex_set and related containers do not have these limitations because: a) several of the member functions are template member functions, b) and that allows the comparison functor used with the containers to be overloaded for each type that can be used for searching. Listing 1 shows the two limitations of std::set and the other associative containers. For this example, assume you have an Employee class, and you store them in a set which is ordered by employee name. Listing 1: class Employee { public: const std::string & GetName() const; // . . . other functions }; struct CompareEmployees : std::binary_function< const Employee *, const Employee *, bool > { // Can only do a comparison of one Employee record // to another Employee record. Can't compare to any // other type. inline bool operator () ( const Employee * l, const Employee * r ) const { return ( l->GetName() < r->GetName() ); } }; typedef std::set< Employee *, CompareEmployees > EmployeeSet; EmployeeSet employees; Employee * FindEmployee( const std::string & name ) { // This bogus object is just a temporary to find the real // object. All I want is to find an Employee record that // matches the given name, rather make such a record. Employee bogus( name ); EmployeeSet::iterator it( employees.find( &bogus ) ); return ( employees.end() == it ) ? 0 : *it; } Listing 2 shows all the member functions which are now templated. The non-templated versions of these functions inside std::set use the key_type. The Compare_Type template parameter in the flex_set functions is *not* one of the template parameters for the class itself. Listing 2: template < class Key, class Compare, class Alloc > class flex_set { // . . . other parts of flex_set class public: template< class Compare_Type > size_type erase( const Compare_Type & x ); template< class CompareType > size_type count( const CompareType & x ) const; template< class Compare_Type > iterator find( const Compare_Type & x ); template< class Compare_Type > const_iterator find( const Compare_Type & x ) const; template< class Compare_Type > iterator lower_bound ( const Compare_Type & x ); template< class Compare_Type > const_iterator lower_bound( const Compare_Type & x ) const; template< class Compare_Type > iterator upper_bound( const Compare_Type & x ); template< class Compare_Type > const_iterator upper_bound( const Compare_Type & x ) const; template< class Compare_Type > pair< iterator, iterator > equal_range( const Compare_Type & x ); template< class Compare_Type > pair< const_iterator, const_iterator > equal_range( const Compare_Type & x ) const; }; Other than accepting a reference to a const Compare_Type in some functions, the flex_set class is identical to the std::set. Even the basic implementation is the same. Like the std::set class, flex_set uses the comparison functor as a little policy class to determine how the elements are sorted. Although the std::set has no need for an overloaded functor, the flex_set's real flexibility comes into play when using overloaded functors. I can design into my functor the mechanism by which an Employee record can be compared to a std::string or to a C-style string. Listing 3 shows the overloaded comparison functor. Listing 3: struct CompareEmployees : std::binary_function< const Employee *, const Employee *, bool > { inline bool operator () ( const Employee * l, const Employee * r ) const { return ( l->GetName() < r->GetName() ); } inline bool operator () ( const Employee * l, const std::string & r ) const { return ( l->GetName() < r ); } inline bool operator () ( const std::string & l, const Employee * r ) const { return ( l < r->GetName() ); } inline bool operator () ( const Employee * l, const char * r ) const { return ( l->GetName() < r ); } inline bool operator () ( const char * l, const Employee * r ) const { return ( l < r->GetName() ); } }; The example shown in Listing 1 now becomes the function shown in Listing 4. Listing 4: typedef flex_set< Employee *, CompareEmployees > EmployeeSet; EmployeeSet employees; Employee * FindEmployee( const std::string & name ) { // No unnecessary temporary objects here! // And the code shows my intent of searching by name. EmployeeSet::iterator it( employees.find( name ) ); return ( employees.end() == it ) ? 0 : *it; } I just published an article describing these containers in issue #58 of Overload magazine http://www.accu.org/c++sig/public/Overload.html. The article explains various design decisions about the classes, and goes into more detail about the containers. You can also find a zip file of my implementation at http://www.richsposato.com/FlexSet.html along with a zip file containing a demo project. The implementation was made as a drop-in replacement for the associative containers that come with the GCC compiler. I made the demo project using MinGW. Because my implementation was designed for GCC's version of the STL, the classes don't compile cleanly with some other implementations of the STL. For that reason, they will be reimplemented for Boost, if they are accepted. Thanks for your consideration, Rich Sposato

6 7

RE: [boost] [filesystem] size() on directory?
by Beman Dawes 03 Feb '04

03 Feb '04

At 12:48 PM 2/3/2004, Powell, Gary wrote: >Beman wrote: > >How should size( "foo" ) behave if "foo" is a directory? > >1) Throw. The function should be renamed file_size(). > >2) Return 0. Directories don't strictly speaking have a size. > >3) Return the number of entries in the directory. Directories are really >just containers; so of course they have a size. >------------------------------------------------- >Gary Replies: > #1, while an OS can implement directories as a file of information, I >think its conceptually wrong for this function to ask for its "size". When >iterating through a file system you should first guarantee that the file >name is a file and not that of a sub directory. > > The 4th answer would be to return the total size of all the files within >the directory. But I think that's also conceptually confusing as well. Agreed. (1) is the behavior in the preliminary version that is now in CVS. --Beman

1 0

[test] typos in documentation
by Jonathan Turkanis 03 Feb '04

03 Feb '04

Hello, Looking through the Boost.Test docs, I see that execution_monitor.htm contains two occurrences of 'overwrite' which probably should be 'override' or 'implement'. Also, test_tools.htm contains five occurrences of 'conformation message' which should probably read 'confirmation message' and one occurrence of 'massages' which should probably be 'messages'. Jonathan

2 2

RE: [boost] [filesystem] size() on directory?
by Powell, Gary 03 Feb '04

03 Feb '04

Beman wrote: How should size( "foo" ) behave if "foo" is a directory? 1) Throw. The function should be renamed file_size(). 2) Return 0. Directories don't strictly speaking have a size. 3) Return the number of entries in the directory. Directories are really just containers; so of course they have a size. ------------------------------------------------- Gary Replies: #1, while an OS can implement directories as a file of information, I think its conceptually wrong for this function to ask for its "size". When iterating through a file system you should first guarantee that the file name is a file and not that of a sub directory. The 4th answer would be to return the total size of all the files within the directory. But I think that's also conceptually confusing as well. Yours, -Gary-

1 0

RE: [boost] 4 more associative containers.
by Powell, Gary 03 Feb '04

03 Feb '04

I'm interested. I ran into the same issues with std::set that you have and because of it, switched to a map when it wasn't really necessary. Regarding acceptance by boost... I'm interested and will take a look at the code. -Gary-

1 0

RE: [boost] should boost::ref forward some operators?
by Powell, Gary 03 Feb '04

03 Feb '04

-------------------------------------------- I ran into the following problem. I have an algorithm which looks like: template<typename in_t, typename out_t> void Alg (in_t in, in_t inend, out_t out) { for (; in != inend; in++, out++) do_something() } Now if I want to call this algorithm more than once, it would be convenient to pass out by ref, so it would be incremented: Alg (v.begin(), v.end(), boost::ref (out)) that is, pass a reference to some kind of output iterator this fails, because boost::ref doesn't have operator++ defined for reference_wrapper. My question is, should boost::ref forward operators like ++ so that this would work? ---------------------------------------------- Gary Replied: I think you need a different tool, either FC++ or Lambda. "ref()" is just a simple wrapper to make something act like a reference. What you need is the whole operator set and Lambda and FC++ have those. Alg(v.begin(), v.end(), boost::lambda::var(out) ); Should work as you want. Yours, -Gary-

1 0

[filesystem] file_size() added
by Beman Dawes 03 Feb '04

03 Feb '04

I've added a file_size() function to the CVS HEAD. It has been tested only on Windows. It hasn't even been compiled on other systems. Testing is a bit difficult. The regular operations_test has been updated to cover several cases, but it would place a burden on testers to test the cases of file sizes requiring 32-bit and greater than 32-bit representations. In other words: * File sizes between 2,147,483,648 and 4,294,967,295. * File sizes greater than 4,294,967,295. boost-root/libs/filesystem/example now contains a program file_size.cpp and a simple Jamfile to build it. Of course it can also be build with your favorite make tool or IDE. When invoked from the command line with a (native) file path, it will display the size of the file in bytes. To know if the value is correct, you have to look at the file size with some system specific tool such as "dir", "ls", or a graphical file explorer. It works with large files on Windows, using Borland 0x0564, CodeWarrior 8.3, GCC 3.3.1 cygming special, Intel 8.0, Microsoft 7.0 and 7.1. It fails to compile on VC++6.0 because of limited 64-bit support. I'd appreciate hearing test results on other systems, particularly a variety of POSIX systems. If it doesn't work for large files on your system, suggestions to get it working will be much appreciated. Thanks, --Beman

1 0