----- Original Message ----- From: "Victor A. Wagner Jr." <vawjr@rudbek.com> To: <boost@lists.boost.org>; <boost@lists.boost.org> Sent: Thursday, June 02, 2005 9:25 AM Subject: Re: [boost] set arithmetic proposal

At 16:16 2005-05-26, Dominic Herity wrote:

...

I've often wished that STL sets supported set arithmetic operations.

Me too.

...

Addition, multiplication and subtraction operators could be overloaded with set union, intersection and difference respectively.

For example: set<char> s1; // s1 <- {} s1 += 'a'; // s1 <- {a} set<char> s2 = s1 + 'b'; // s2 <- {a,b} set<char> s3 = s2 - s1; // s3 <- {b} set<char> s4 = s1 * s2; // s4 <- {a}

Achieving the above results with the existing STL library is by comparison cumbersome, error-prone and unclear.

I have a char_set class to contribute, which behaves as above. (and is released under the boost license) at http://www.ootl.org/yard/yard_char_set.hpp.htm . A more recent version is available at http://www.ootl.org/ootl-0-3-0.zip char_set x1('a', 'c'); // a..c char_set x2('d', 'f'); // d..f char_set x3(x1 & x2); // a..f char_set x4(char_set('a','z') | x3); // g..z assert(!x4['a']); assert(x4['z']); There is also a compile-time version of the char_set which allows the construction of compile_time sets: For instance: typedef char_set_range<'a', 'c'> x1_t; typedef char_set_range<'d', 'f'> x2_t; typedef char_set_union<x1_t, x2_t> x3_t; typedef char_set_intersection<char_set_range<'a','z'>, x3_c> x4_t; const x4_t X4; assert(!X4['a']); assert(X4['z']);

...

Although this proposal does not follow the STL design philosophy, it meets a real developer need. It can be implemented using global operator overloads, which should avoid conflicts with other uses of STL sets.

Comments and suggestions welcome.

I guess you and I must be the only two former Pascal programmers hanging around boost.

Me too!

It seems to me that "set of" from Pascal wasn't ever popular with anyone but those who really _really_ used them heavily (e.g. Ada dropped them when it was derived from Pascal).

I used them heavily for writing a Heron compiler in Delphi.

I argued (unsuccessfully) that when the boost::dynamic_bitset<> was proposed that the _least_ we could do would be to fix the mis-characterization of operators <= and >= with regards to sets (for those who haven't studied sets, {b,c,d} <= {a,b,c,d} but that's not how it will evaluate with either std::set or boost::dynamic_bitset). Absent that oddity, I suspect that you could rather easily overload some global operators to handle what you want using any of std::set, std::bitset, or boost::dynamic_bitset (the backwardness of the comparison operators would still bother me, though). Hmmmm, maybe I should look more closely at the "unordered collections" (hash_set) proposal further and see if that correctly manages the set concept.

It might be very interesting to also overload comma to return sets, thus allowing: namespace true_sets { assert((1, 2, 3) + (4, 5) < (1,2,3,4,5,6)} assert((1, 2) == (2, 1)} assert(range(1, 3) == (2, 1, 3)} } -Christopher Diggins

"Victor A. Wagner Jr." ha escrito:

Hmmmm, maybe I should look more closely at the "unordered collections" (hash_set) proposal further and see if that correctly manages the set concept.

AFAIK, unordered_sets are not (required to be) comparable, but your suggestion of defining comparison of unordered containers based on the set-theoretic concept makes much sense to me. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

Victor A. Wagner Jr. wrote:

I argued (unsuccessfully) that when the boost::dynamic_bitset<> was proposed that the _least_ we could do would be to fix the mis-characterization of operators <= and >= with regards to sets (for those who haven't studied sets, {b,c,d} <= {a,b,c,d} but that's not how it will evaluate with either std::set or boost::dynamic_bitset).

Well, it's true that in boolean algebra, <= can be interpretted to mean inclusion. But then, + is also sometimes used to mean OR. I think using the operators in this unconventional (as far as C++ is concerned) would just lead to confusion. Jonathan