- Boost - lists.boost.org

Re: [boost] Review Result: Indexed Set
by JOAQUIN LOPEZ MU?Z 05 Apr '04

05 Apr '04

----- Mensaje original ----- De: Pavel Vozenilek <pavel_vozenilek(a)hotmail.com> Fecha: Lunes, Abril 5, 2004 0:05 am Asunto: [boost] Review Result: Indexed Set > Indexed set library by Joaquín Mª López Muñoz > has been accepted into Boost. > First of all I'd like thank Pavel, without whose encouragement over many months the library wouldn't have reached the review stage. Thanks also to all the people who participated in the review: it's been a lot of fun and a number of interesting issues have been raised. I plan to deliver a post-review version during April, addressing all of the minor pending requests. As for the new features (ranked indices, bimap, etc.) I guess I'll wait till the first official Boost release in order to gain some feedback first. It is my understanding that noone opposed to new features being postponed until a first official version has been released. A couple of features will probably make it before, though: utilities for composition of key extractors (which are now in the examples only) and serialization support. The naming issues are still not closed, as I'm growing more doubtful that we should embed the library into boost::container. I'll probably post a revised naming scheme during this week or the following. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

1 0

[BGL] forced client complexity
by Provisional Dissonance 05 Apr '04

05 Apr '04

If one accepts the axiom that "a picture is worth a thousand words," then it naturally follows that discussion of graphs is always overly prolix. Sadly, the same reasoning is also applicable to the code of graph libraries. Boost.Graph seems to expose and require an unnecessarily large amount of complexity, though. Whereas libraries like Spirit go to great lengths to make hard things easy, BGL seems to try only to make hard things possible. The amount of scaffolding required to use BGL for even the simplest of projects often dwarfs the code size of a naive, yet functional, special-purpose implementation. While I understand that the BGL is deeply entrenched in boost culture, certain academic circles, and even publications, I nonetheless suggest that BGL lacks the ease of use necessary for widespread adoption. Even knowing that ease-of-use is not a criterion for acceptance into boost, looking at what is required of the client to use the BGL always leaves me feeling perplexed. Is there any particular reason that a simplified interface is not made available? Perhaps a container adapter could be packaged with the library allowing a compromise of functionality and flexibility for simplicity? If a graphing problem is trivial, shouldn't BGL provide a trivial solution? Why are the simplest useful examples several hundred lines of code? I apologize for all of my vague criticisms - my intention is not to flame but rather to test the waters. It is difficult for me to assess whether the simplicity I yearn for isn't present for stylistic reasons or whether it would rather necessitate a sacrifice of flexibility, functionality or implementation clarity. Nor is it clear to me to what extent these criteria can be compromised to promote clarity of client code. For what it is worth, the kind of ease-of-use I'm imagining might look like: #include <less_than_10_graph_headers> ... digraph<some_node_type,some_edge_context_type> g; g << "vertex" << make_pair("vertex", "implicit_vertex"); g.add_edge("brother", "sister", "sibling"); if(g.find(make_pair("brother", "sister"))) related = true; Could someone please elucidate on why it is impossible/impractical/unnecessary/whatever for a graph library to have such an interface? Should I accept that the BGL is not the magic bullet graph library and move on, or can this kind of simplicity be somehow found within? Thanks in advance, prs __________________________________ Do you Yahoo!? Yahoo! Finance Tax Center - File online. File on time. http://taxes.yahoo.com/filing.html

3 7

Re: Re: Re: C++ subranges
by Brian Martin 05 Apr '04

05 Apr '04

Maciej - I need to think deeply about some of the things that have been pointed out. At the moment (this week) there's a project I want to progress a bit so won't be able to do that just yet. One thing I might do immmediately is to do something about that conversion operator. I think it's causing some problems with the stream operators, just for starters. You sometimes get ambiguities in certain contexts and, as you said, these operators can do that. I have a fix, but am not totally satisfied. I've attached the "fixed" version. The comment at the top has also been corrected. Nice to have comments that don't tell porkies.

1 0

Traits and Policies
by Malcolm Smith 05 Apr '04

05 Apr '04

Hi, I am new to this list and saw the messages related to traits and policies. I am an experienced C++ developer but have a limited knowledge of the STL and even less of boost - I've joined this list in an effort to become more familiar. I understand policy classes but am not very familiar with traits. Can someone recommend a link for me to follow so I can better understand what they are as well as when, why and how to use them. TIA. Malcolm Smith MJ Freelancing http://www.mjfreelancing.com Borland Technology Partner

4 4

1.31.1?
by Stephan T. Lavavej 05 Apr '04

05 Apr '04

I remember hearing shortly after its release that 1.31.0 had some serious problems and that 1.31.1 was in the works. Whatever happened to that? Stephan T. Lavavej http://nuwen.net

3 2

Re: C++ subranges
by Brian Martin 05 Apr '04

05 Apr '04

Brian Martin wrote: >I'll have another think about some of the compile time check issues. I have and have done the following: 1) Compile time checks would be nice but are basically impossible. At least the ones that count. Such as: subrange<int, 1, 20> sub_20(30); or sub_20 = 300; Pascal traps this kind of thing but C++ can't, as far as I can see. Runtime only, I'm afraid. I am of the opinion that the compile time checks that were given in Maciej's example code are of limited use since the real benefit of subranges is runtime (in my humble opinion). In the example code, it was possible to assign/copy different subrange types, provided the source had a range inside the destination. For now, my subrange doesn't allow different subrange types to mix. 2) Agonised over whether or not to remove the typename T (I call it a "base type" a la Pascal terminology) from the template. In my previous post I said that it allows any type to be stored in the subrange, forgetting of course that you can't have doubles, classes and C strings as non-type template parameters. Doh! Actually, this is what I want since subranges of classes is a bit odd. Floating point subranges would have been nice, but Pascal doesn't allow them either. There is a way of doing it, but it messes up the syntax. I've kept the base type because you waste storage if you're storing anything smaller than a long. There's no class overhead (on my compiler) so this doesn't make the wastage trivial. The waste is ok if you're only using a few subranges but in one project I'm storing potentially large numbers of subranges (of shorts) in STL containers and then reading/writing them in binary from/to files. Didn't like the files being 2 times bigger than they should be. So, reluctantly, I've kept the base type. 3) I've used a conversion operator. I usually avoid these but in this case it integrates subranges nicely into the type system so that built in types and subranges can mix freely in expressions. The template is, after all, supposed to be a (restricted) integral type. 4) Removed operator~(). It always fails since the value gets its upper bits set to 1 which will exceed the subrange unless you've set the upper limit to the maximum the type can store. There are obvious problems with signed types too. 6) Have attached some code - the subrange class itself and a test program for anyone who wants to give it a go.

3 2

Re:Re: [boost] Serialization: versioning and XML.
by Robert Ramey 05 Apr '04

05 Apr '04

Anatoli Tubman wrote: >Robert Ramey wrote: >> I briefly considered this approach. I imagined that upon archive >> creation the XML input could be parsed into a node tree. (insert plug >> for spirit >> here) The load_override function would be altered to search the >> correct part of the tree. So this would work and be pretty clean. >> I'm sure other approaches such as using SAX or DOM to parse the tree would work as well. >> Maybe there's another way I never thought of. >> >> The main reason I rejected the idea was that I didn't see it working >> with arbitrarily size streams. I envision serialization being used with stream >> much larger then available memory. This suggested to me an "on the fly" >> loader rather than a "pre-loaded". >Loading the entire archive is not necessary. The other approach is to >acquire a *description* of the data structure being deserialized, and >process the XML stream sequentially. That is, operator<< does not do >deserialization by itself, but inserts a member *descriptor* into a map. >When all data members are collected in this fashion, they are deserialized >as corresponding tags come in. >IOW one needs random access to *either* the data stream *or* to the data >structure being deserialized. Data streams are too big, so we should choose >data structures instead. >One doesn't need the entire tree of data structures either, only the node >currently being processed, because descendants changing parent nodes are >not supported. I don't see how to do this while keeping archive and serialization descriptions independent. >This works because a typical class is much smaller than a typical data >stream, which usually contains many instances of the same class. >I have some experience with one (pre-XML, pre-C++) serialization library >that does (approximately) just that. It uses a custom tagged format, but >there's no reason why it shouldn't work with XML and C++. My focus was finding the most expedient and efficient way to use XML format with the rest of the serialization library. In the course of investigating my options, I had occasion to look more deeply into XML. One thing that occurred to me was the possibility of making an archive implementation which generated an XML schema rather than the XML data. This would generate and XML data schema either in parallel with the XML data archive or as a separate operation. An XML tagged input implementation might make use this as well. I would guess others might find a use for such a schema that would automatically be in sync with the program code that generated the data. Robert Ramey

2 1

Re: Re: [BGL] forced client complexity
by Johnny Yune 05 Apr '04

05 Apr '04

"Vladimir Prus" <ghost(a)cs.msu.su> wrote: > Hi, > (btw, if possible, it would be nice to > know your real name, so that I could > write "Hi <your real name>") Ah, excuse me. It would please me for you to call me Johnny Yune. <snip> > In fact, something like > > typedef graph<City, Road> Road_map; > > looks quite reasonable to me. > > > If the node's "index" is > > related to the object, why would it not be a natural > > member of the node-type's class? > > I don't think "index" should be type of 'City' class. Nor does it seem a logical candidate for a member. In fact, as a client, you shouldn�t and needn�t know anything about it. > > If, instead, it is a > > synthesized construct for communication between a > > graph and the algorithm operating over it, why should > > the client be responsible for its maintenance instead > > of the framework? What are the advantages of this > > approach? What are the disadvantages of simplifying > > things for the client? This is the type of design > > issue that I intended to question with my initial > > post. > > I think the biggest problem is: It seems like you�re looking at this from the framework side instead of the client side. That�s fine, but it still isn�t clear to me why adding another layer of abstraction should affect the internal workings so heavily. I�ll try to address your questions with respect to how I would probably do it, though. >how do you identify vertices? If you use > "City&" you'd have some problems: > > 1. How vertices are really identified? Using operator==? Really identified by whom and for what purpose? >Is it possible to > insert two 'City' objects which are equal? I think that should probably depend on the underlying graph type. > If not, how to insure uniqueness? I guess you would want to make sure to not insert duplicate vertices. > Do we really want 0(log n) lookup on each 'add_vertex'. Huh? I admit to not being intimate with BGL�s internals, but it seems like a hashed set of Cities to indexes or whatever the underlying graph structure wants to use to identify nodes would be reasonable and speedy. > > 2. Even if 'City' objects in a graph are unique, how will add_edge be > implemented? Do you need O(log n) lookup to find internal adjacency >lists? Again, using a City as a node-type shouldn�t affect the runtime. If you can think of a way to define a vertex that allows o(1) lookup, I can probably give you a city->your_vertex_type hashmap that allows you to maintain that speed. > > 3. What's edge, and how it is identified? I would leave that up to the underlying container. You�ll notice that in my original post, my scratchy pseudocode declared a graph as g<vertex_type, edge_context_type>. I kind of imagined edge_context as being some sort of arbitrary meta-data about the link, generally useful only to the client. Maybe the edge context could be a simple member of the graph-managed property map? >For example, 'Road' might not > contain source/target vertices, but still we need to be able to find > source/target vertices. The whole point of the abstraction is to free the client from trying to figure out how to fit cities into roads. The underlying container could certainly keep a mapping from one to another. > > One possible solution that I see is the make > vertex_descriptor be always > pointer type. It will point at some > internal structure but also provide > operator* which will return 'City'. Would that simplify things for the client? >Or, maybe, it should be possible to > iterate over values of 'City', not only over values of >vertex_descriptor. Iterating over cities sounds absolutely reasonable to me. Much more so than iterating over some arbitrary vertex_descriptors, even. > > I still don't know if using City to identifiy vertices is feasible. I have no reason to think otherwise and I do think it sounds simpler from a client-side perspective. Food for thought. Thanks, prs __________________________________ Do you Yahoo!? Yahoo! Small Business $15K Web Design Giveaway http://promotions.yahoo.com/design_giveaway/

2 1

Spirit skip parser questions.
by Jia Pu 05 Apr '04

05 Apr '04

I am trying to write a parser which skipps white space and C, Java style comments. To get familiar with spirit, I did some experiments, here is a question. First, I write a simple grammar to accept some non-white space chars. //////////////////////////////////////////////////////////////////////////////// struct FOO_GRAMMAR : public grammar<FOO_GRAMMAR> { template <typename ScannerT> struct definition { typedef rule<ScannerT> rule_t; definition(ABNF_GRAMMAR const & self) { r_LETTER = range_p('a','z') | range_p('A','Z') | '.'; r = (+r_LETTER); } rule_t r, r_LETTER; rule_t const& start() const { return r; } }; }; //////////////////////////////////////////////////////////////////////////////// I used FOO_GRAMMAR with space_p as skip parser: ////////////////////////////////////////////////////////////////////////////// FOO_GRAMMAR g; std::string line = "This is a test parser."; parse_info<> info = parse(line.begin(),line.end(), g, space_p); //////////////////////////////////////////////////////////////////////////////// This works perfectly. Then, I tried to wrap the skip parser in a skip grammar, since eventually I need a more complicated parser. So I wrote the skip grammar as: /////////////////////////////////////////////////////////////////////////////// struct SKIP_GRAMMAR : public grammar<SKIP_GRAMMAR> { template <typename ScannerT> struct definition { typedef rule<ScannerT> rule_t; definition(SKIP_GRAMMAR const & self) { rule_t r_SKIP = space_p; } rule_t r_SKIP; rule_t const& start() const { return r_SKIP; } }; }; ///////////////////////////////////////////////////////////////////////// I tried to parse the same sentence as before: /////////////////////////////////////////////////////////////////////////// FOO_GRAMMAR g; SKIP_GRAMMAR skip; std::string line = "This is a test parser."; parse_info<> info = parse(line.begin(),line.end(), g, skip); ////////////////////////////////////////////////////////////////////////// This time the parsing failed. Can anyone tell me why? I thought grammars are just like rules. And any suggestion on building a parser skipping certain pattern? I just can figure it out by reading the doc. Thank you. _________________________________________________________________ Persistent heartburn? Check out Digestive Health & Wellness for information and advice. http://gerd.msn.com/default.asp

2 1

lexical_cast<wstring>(string)
by Jared McIntyre 05 Apr '04

05 Apr '04

Some time ago I read a discussion about possibly adding the ability to perform a lexical_cast of a regular to a wide string, and vice-versa. There was also discussion of possibly adding similar functionality to string_algo (though I tend to like the lexical_cast better for this). Has anyone looked more deeply into solving this problem? I've found these operations to be extremely common in my work on applications that are written in unicode, but may have to talk with non-unicode network protocols, libraries, etc. Jared

1 0