- Boost - lists.boost.org

Re: [boost] Re: boost::filter_iterator Model
by JOAQUIN LOPEZ MU?Z 12 Dec '04

12 Dec '04

----- Mensaje original ----- De: Sylvain Pion <Sylvain.Pion(a)sophia.inria.fr> Fecha: Sábado, Diciembre 11, 2004 11:25 pm Asunto: Re: [boost] Re: boost::filter_iterator Model [...] > > I can't find anything in the standard that says that the cost > should be > amortized over the full traversal of the std::set. The only reference I'm aware of about complexity guarantees for iterators is in [lib.iterator.requirements], 24.1.8: "All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized). Therefore, requirement tables for the iterators do not have a complexity column." Admittedly, this quote does not state against which sequence the complexity must be amortized. From my point of view, the intended meaning is that the amortization is done wrt to full traversal: otherwise, even STL iterators cannot be compliant, as your example prove. When working with infinite sequences, "full traversal" does not make sense, but it's obvious how to cover this case with limit considerations. Maybe this is a good question for comp.std.c++? Joaquín M López Muñoz Telefónica, Investigación y Desarrollo PS: I think the std is rather sloppy in this issue. > And it's possible to find sub-ranges which take non-bounded > average time > to traverse, when the size of the std::set increases : > - take the range [ (begin+end)/2 - n ; (begin+end)/2 + n ] in an > std::set of size() = 2^(2^n). This is a sequence of ranges of > size 2n, and which > take at least O(2^n) to traverse, and so definitely not constant > time amortized [over the length of the range]... > > When considering an amortized cost/complexity, it refers to sequences, > whose lengths grow to infinity, but here nothing specifies which > sequenceswe are considering. And if you allow any kind of > infinite sequences, then > set::iterator does not have the required complexity, from the > example above :( > > What am I missing ? > > -- > Sylvain > _______________________________________________ > Unsubscribe & other changes: > http://lists.boost.org/mailman/listinfo.cgi/boost

2 1

[Boost-bugs] [ boost-Bugs-1083760 ] Error in msvc in building inheritance.obj to build hello.pyd
by SourceForge.net 12 Dec '04

12 Dec '04

Bugs item #1083760, was opened at 2004-12-12 01:56 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1083760&group_… Category: Python Group: None Status: Open Resolution: None Priority: 5 Submitted By: AIM (andre_mikulec) Assigned to: David Abrahams (david_abrahams) Summary: Error in msvc in building inheritance.obj to build hello.pyd Initial Comment: Error in msvc in building inheritance.obj to build hello.pyd Hello, I am trying to build the boost 1.31.0 sample extension hello.cpp. I can not compile the file inheritance.cpp because the two files containing some templates: adjacency_list.hpp and mem_fn.hpp can not compile. Does anyone have any solutions? Instead of Visual C++ 6.0 should I use a different compiler? Anyone have any success on any other compiler? Did anyone manage to build a hello.pyd? Thank you very much. Here is my script below (with embedded results). rem I have MSVC 6.0 Service Pack 5 on Windows 2000 Service Pack 3 default installs on F: rem Python is located in F:\Python23 rem Boost is located in W:\boost_1_31_0 rem MSVC stlPort 4.6.2 installed, compiled and rem VC studio include dirs and libraries dirs configured to use it. rem build boost.jam (so I have a bjam.exe for all below) W: vcvars32.bat cd W:\boost_1_31_0\tools\build\jam_src rem below since I have multilple toolsets installed I will always be specific. .\build.bat msvc rem result: 2 minutes later: NO WARN NO ERRORS dir W:\boost_1_31_0\tools\build\jam_src\bin.ntx86\* rem result: OK I have *jam*.exe executables: bjam.exe jam.exe mkjambase.exe yyacc.exe rem build boost (using boost.jam (bjam from above)) W: vcvars32.bat set PYTHON_ROOT=F:\Python23 set PYTHON_VERSION=2.3 set PATH=%PATH%;W:\boost_1_31_0 \tools\build\jam_src\bin.ntx86 rem APPEND THE BJAM PATH ABOVE TO THE SYSTEM ENVRONMENT VARIABLE PATH cd W:\boost_1_31_0 rem below since I have multilple toolsets installed I will always be specific. bjam "-sTOOLS=msvc" install rem about 90 minutes later ERROR RESULTS FOLLOW: <<< errors.txt contents below >>> cl /Zm800 -nologo -GX -c -DNDEBUG -DNDEBUG - DBOOST_PYTHON_DYNAMIC_LIB - DBOOST_PYTHON_SOURCE /Ogity /O2 /Gs /Ob2 /GX /GR /MD -I"bin\boost\libs\python\build" - I"W:\boost_1_31_0" -I"F:\Python23\include" - I"F:\Program Files\Microsoft Visual Studio\VC98 \Include" - Fo"bin\boost\libs\python\build\boost_python.dll\msvc\rele ase\inheritance.obj" -Tp"W:\boost_1_31_0 \libs\python\build\../src/object/inheritance.cpp" rem error below results below ... F:\Program Files\Microsoft Visual Studio\VC98 \Bin>cl /Zm800 -nologo -GX -c -DNDEBUG -DNDEBUG - DBOOST_PYTHON_DYNAMIC_LIB - DBOOST_PYTHON_SOURCE /Ogity /O2 /Gs /Ob2 /GX /GR /MD -I"bin\boost\libs\python\build" - I"W:\boost_1_31_0" -I"F:\Python23\include" -I"F:\Program Files\Microsoft Visual Studio\VC98 \Include" - Fo"bin\boost\libs\python\build\boost_python.dll\msvc\rele ase\inheritance.obj" -Tp"W:\boost_1_31_0 \libs\python\build\../src/object/inheritance.cpp" inheritance.cpp W:\boost_1_31_0\boost/graph/detail/adjacency_list.hpp (1055) : error C2244: 'bidirectional_graph_helper_with_property<Config >::remove_edge' : unable to resolve function overload W:\boost_1_31_0\boost/graph/detail/adjacency_list.hpp (1057) : error C2954: template definitions cannot nest W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2039: 'dm' : is not a member of '_mfi' W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2143: syntax error : missing ';' before '<' W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2501: 'dm' : missing storage-class or type specifiers W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2059: syntax error : ';' W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2059: syntax error : '<' W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2653: 'T' : is not a class or namespace name W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2645: no qualified name for pointer to member (found ':: *') W:\boost_1_31_0\boost/mem_fn.hpp(320) : error C2143: syntax error : missing ';' before '}' W:\boost_1_31_0\boost/mem_fn.hpp(320) : fatal error C1506: unrecoverable block scoping error F:\Program Files\Microsoft Visual Studio\VC98\Bin> W:\boost_1_31_0\boost/graph/detail/adjacency_list.hpp (1055) : error C2244: 'bidirectional_graph_helper_with_property<Config >::remove_edge' : unable to resolve function overload W:\boost_1_31_0\boost/graph/detail/adjacency_list.hpp (1057) : error C2954: template definitions cannot nest rem the problem area in adjacency_list.hpp is here ... template <class Config> inline void bidirectional_graph_helper_with_property<Config>::remov e_edge(typename Config::edge_descriptor e) { typedef typename Config::graph_type graph_type; graph_type& g = static_cast<graph_type&>(*this); boost::remove_edge(source(e, g), target(e, g), *this); } // O(E/V) or O(log(E/V)) template <class EdgeOrIter, class Config> inline void remove_edge(EdgeOrIter e, bidirectional_graph_helper_with_property<Config>& g_) { g_.remove_edge(e); } W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2039: 'dm' : is not a member of '_mfi' W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2143: syntax error : missing ';' before '<' W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2501: 'dm' : missing storage-class or type specifiers W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2059: syntax error : ';' W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2059: syntax error : '<' W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2653: 'T' : is not a class or namespace name W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2645: no qualified name for pointer to member (found ':: *') W:\boost_1_31_0\boost/mem_fn.hpp(320) : error C2143: syntax error : missing ';' before '}' W:\boost_1_31_0\boost/mem_fn.hpp(320) : fatal error C1506: unrecoverable block scoping error rem The problem area in mem_fn.hpp is here ... creating a template class at the end of mem_fn.hpp template<class R, class T> _mfi::dm<R, T> mem_fn(R T::*f) { return _mfi::dm<R, T>(f); } } // namespace boost rem build hello world W: vcvars32.bat set PYTHON_ROOT=F:\Python23 set PYTHON_VERSION=2.3 set PATH=%PATH%;W:\boost_1_31_0 \tools\build\jam_src\bin.ntx86 rem APPEND THE BJAM PATH ABOVE TO THE SYSTEM ENVRONMENT VARIABLE PATH cd W:\boost_1_31_0\libs\python\example\tutorial bjam -sTOOLS=msvc The results are as follows W:\boost_1_31_0\libs\python\example\tutorial>bjam - sTOOLS=msvc ...found 1978 targets... ...updating 7 targets... vc- C++ ..\..\..\..\bin\boost\libs\python\build\boost_python.d ll\msvc\debug\inheritance.obj inheritance.cpp W:\boost_1_31_0\boost/graph/detail/adjacency_list.hpp (1055) : error C2244: 'bidirectional_graph_helper_with_property<Config >::remove_edge' : unable to resolve function overload W:\boost_1_31_0\boost/graph/detail/adjacency_list.hpp (1057) : error C2954: template definitions cannot nest W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2039: 'dm' : is not a member of '_mfi' W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2143: syntax error : missing ';' before '<' W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2501: 'dm' : missing storage-class or type specifiers W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2059: syntax error : ';' W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2059: syntax error : '<' W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2653: 'T' : is not a class or namespace name W:\boost_1_31_0\boost/mem_fn.hpp(315) : error C2645: no qualified name for pointer to member (found ':: *') W:\boost_1_31_0\boost/mem_fn.hpp(320) : error C2143: syntax error : missing ';' before '}' W:\boost_1_31_0\boost/mem_fn.hpp(320) : fatal error C1506: unrecoverable block scoping error "cl" /Zm800 -nologo -GX -c - DBOOST_PYTHON_DYNAMIC_LIB - DBOOST_PYTHON_SOURCE /Z7 /Od /Ob0 /GX /GR /MDd -I"..\..\..\..\bin\boost\libs\python\build" - I"W:\boost_1_31_0" -I"F:\Python23\include" - I"F:\PROGRA~1\MICROS~3\VC98\include" -Fo"..\..\..\.. \bin\boost\libs\python\build\boost_python.dll\msvc\debug \inheritance.obj" -Tp"W:\boost_1_31_0 \libs\python\build\../src/object/inheritance.cpp" ...failed vc- C++ ..\..\..\..\bin\boost\libs\python\build\boost_python.d ll\msvc\debug\inheritance.obj... ...skipped <@boost!libs!python! build\boost_python.dll\msvc\debug>boost_python.CMD for lack of <@boost!libs!python! build\boost_python.dll\msvc\debug>inheritance.obj... ...skipped <@boost!libs!python! build\boost_python.dll\msvc\debug>boost_python.dll for lack of <@boost!libs!python! build\boost_python.dll\msvc\debug>boost_python.CMD... ...skipped <@boost!libs!python! build\boost_python.dll\msvc\debug>boost_python.lib for lack of <@boost!libs!python! build\boost_python.dll\msvc\debug>boost_python.CMD... ...skipped <@boost!libs!python!example! tutorial\hello.pyd\msvc\debug>hello.CMD for lack of <@boost!libs!python! build\boost_python.dll\msvc\debug>boost_python.lib... ...skipped <@boost!libs!python!example! tutorial\hello.pyd\msvc\debug>hello.pyd for lack of <@boost!libs!python! build\boost_python.dll\msvc\debug>boost_python.dll... ...skipped <@boost!libs!python!example! tutorial\hello.pyd\msvc\debug>hello.lib for lack of <@boost!libs!python! build\boost_python.dll\msvc\debug>boost_python.dll... ...failed updating 1 target... ...skipped 6 targets... W:\boost_1_31_0\libs\python\example\tutorial>dir hello*.* rem results: ALL hello.CMD hello.pyd hello.lib NOT FOUND Any Ideas about a possible solution? AIM Andre_Mikulec(a)Hotmail.com ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1083760&group_… ------------------------------------------------------- SF email is sponsored by - The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://productguide.itmanagersjournal.com/ _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

[thread] Why is there a restriction for the runtime libraries?
by Stefan Slapeta 12 Dec '04

12 Dec '04

There are two restrictions in the thread jamfile I don't understand: - the thread lib must be built with static runtime libraries - the thread dll must be built with dynamic runtime libraries What is the reason for that? Why can't I use the shared rt and link boost.thread statically (and vice versa)??? Stefan

5 19

Re: [boost] Re: boost::filter_iterator Model
by JOAQUIN LOPEZ MU?Z 11 Dec '04

11 Dec '04

Hi Dave, ----- Mensaje original ----- De: David Abrahams <dave(a)boost-consulting.com> Fecha: Sábado, Diciembre 11, 2004 9:01 pm Asunto: [boost] Re: boost::filter_iterator Model [...] > Is that the right way to understand the complexity guarantee? > I'm really asking. Consider std::set. As the size of the set > grows, the > average cost of incrementing an iterator grows without bound. This is not correct, IMHO. Consider a set::iterator doing a full traversal from begin to end. From the rb-tree point of view, this is equivalent to visiting the whole tree in an inorder fashion. And it is easy to see that every node will get hopped from at most three times: - when visiting its left subtree. - when visiting its right subtree. - when leaving to an upper level. So the total number of hops is bounded by 3*N, and the average cost of incrementing is constant, which is the same as to say that increment complexity is amortized constant, as required by the std. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

2 1

Re: [boost] Re: boost::filter_iterator Model
by JOAQUIN LOPEZ MU?Z 11 Dec '04

11 Dec '04

----- Mensaje original ----- De: David Abrahams <dave(a)boost-consulting.com> Fecha: Sábado, Diciembre 11, 2004 9:01 pm Asunto: [boost] Re: boost::filter_iterator Model [...] > > >> Is that stretching the definition of an iterator? I'm not sure. > > > > That's too much for me. > > I tend to think that it's stretching what users might expect > when they see > > "constant time amortized operation". > > This is tricky territory. It certainly warrants a note in the > documentation, but I'm not exactly sure what to say. I'm afraid that, generally speaking, filter_iterator<> cannot just guarantee the std-required complexity, and you cannot do anything about it (consider for instance filter_iterator<is_prime<int>, counting_iterator<int> >) To say it bluntly, not all instantiations of filter_iterator<> are iterators. I'd just say it so: "std-mandated complexity guarantees are provided only if the number of skipped elements divided by the length of the base range remains constant in average." Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

1 0

boost::filter_iterator Model
by Bob Bell 11 Dec '04

11 Dec '04

Hi- I was wondering what the rationale was for boost::filter_iterator not modeling anything more than a forward traversal iterator. Recently I was trying to use filter_iterator in a situation where I needed bidirectional traversal, but got stymied by this. Is there something about the notion of filtering that precludes bidirectionality? Or is this something that could be made to work? Thanks, Bob

4 8

Sandbox file vault.
by Rene Rivera 11 Dec '04

11 Dec '04

As I mentioned in some earlier post.. I set up file vault are in the Boost-Sandbox web space: http://boost-sandbox.sourceforge.net/vault/ It works much like the Yahoo files area used to work. It's read only for everyone, and read-write if you "register". Registration is not closed or anything and is only there to verify that it's a real person, or as close as email verification can get, uploading files. NOTE: It seems a bit sluggish. Don't know if it's SF or the scripts. But I would suspect the scripts. If you need admin access email me. -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com - 102708583/icq

2 6

logos
by David Abrahams 11 Dec '04

11 Dec '04

For a while there, we were having such fun posting proposed logo designs; there were easily 20 posts a day on the topic. I requested that the local posting stop so we could run a contest "for real," that would include the wider C++ community, and solicited a contest manager, but so far nobody has stepped forward. It would be a real shame if Boost ended up with no new logo or an inferior logo just because of that. Really, for some of you who've been very involved with the previous flurry of posts, this job shouldn't occupy much more time than you were already going to spend on it. Someone just has to: 1. write up a voting system 2. modify the wiki page to reflect recent requirements consensus 3. post an announcement 4. tally the results Rene has already established a great "head start" by setting up the Wiki page. Isn't there anyone out there who's willing to perform this valuable service to the Boost community? Don't make me start emailing individuals to prod them ;-) -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

6 5

[smart cont.] Const semantics in boost::ptr_map vs. std::map
by Eelis van der Weegen 11 Dec '04

11 Dec '04

Two issues: (1.) I stumbled upon a strange inconsistency in boost::ptr_map's iterator interface. I've attached some demonstration code that shows the problem. (2.) Given a (nonempty) const std::map<X, Y*> object, it is possible to retrieve a Y& from it. Given a const boost::ptr_map<X, Y> object, it is not possible (without casting) to retrieve a Y& from it. Thus, it is not possible (in general) to refactor code which uses a std::map<X, Y*> combined with manual ptr_map-like lifetime/ownership management to use a boost::ptr_map<X, Y> without changing const semantics. Was this effect intentional? If so, why was this approach chosen? It seems like ptr_map attempts to "hide" the level of indirection that a standard container of pointers has. While this may be desirable, I think it should be mentioned in the documentation since it can come as a surprise to people (like me) who actually try to perform the refactoring mentioned above. Eelis #include <map> #include <boost/smart_container/ptr_map.hpp> typedef std::map<int, int *> M; typedef boost::ptr_map<int, int> N; void f (M & m) { M::iterator i = m.begin(); M::iterator const ci = i; int & a = *(i->second); // ok int & b = *(ci->second); // ok } void g (N & n) { N::iterator i = n.begin(); N::iterator const ci = i; int & a = *i; // ok int & b = *ci; // error: invalid initialization of reference of type 'int&' from expression of type 'const int' }

2 4

auto-link, DLLS and exported constants
by Robert Ramey 11 Dec '04

11 Dec '04

I'm trying to implement auto-link and build static versions of the serialization libraries. It seems I'm making progress but I'm sort of stuck on one point right now. one my header files now contains: extern BOOST_SERIALIZATION_DECL const char * ARCHIVE_SIGNATURE; extern BOOST_SERIALIZATION_DECL unsigned int ARCHIVE_VERSION; while the corresponding implemenation file contains: /////////////////////////////////////////////////////////////////////// // constants used in archive signature //This should never ever change. note that is not an std::string // string. BOOST_SERIALIZATION_DECL const char * ARCHIVE_SIGNATURE = "serialization::archive"; // this should change if the capabilities are added to the library // such that archives can be created which can't be read by previous // versions of this library // 1 - initial version // 2 - made address tracking optional // 3 - numerous changes - can't guarentee compatibility with previous versions BOOST_SERIALIZATION_DECL unsigned int ARCHIVE_VERSION = 3; When I link an executable with the static library things work fine. When I link with the dll import library I get errors indicating undefined symbols for these const variables. What is recommended here? Robert Ramey

2 1