- Boost - lists.boost.org

Re: [boost] Help on 2 key search
by Vicente Botet 18 May '11

18 May '11

Renee wrote: > > HiAll > Being a newbie i request your help. > > I have a emp database. I store them based on emp id as well as ssn and > need to store their extended details. What datatype is best used to store > this info. I need to search through millions of emp recs that can be > searched by either ssn or by emp id. do suggest. > some fields are as below: > emp id > ssn > emp first name > emp last name > emp sal > emp age > if we use map can have just one key value so it can be either ssn or emp > id. using 2 maps one for ssn and emp record and another for emp id and emp > record is not efficient as there are millions of records. > ur help is appreciated. will multi index help in this case. do suggest. > > -Renee > Hi, If you need to realize search based on these two fields MultiIndex seems the appropriated structure. If emp_id is an integer (unique) the use of a non-ordered index could give you better performances. The major problem is how to ensure this id is unique. I guess that ssn stands for Social Security Number, which is too big to fall on a builtin, so a string will be need. Again the use of a good hash could improve the performances. HTH, Vicente P.S. This kind of questions are better answered on the Boost User ML or even on Stack Overflow. -- View this message in context: http://boost.2283326.n4.nabble.com/Help-on-2-key-search-tp3530830p3531660.h… Sent from the Boost - Dev mailing list archive at Nabble.com.

1 0

[variant] static_visitor deadlock
by Andrew Hundt 17 May '11

17 May '11

I believe I may have found a way to create a deadlock in static_visitor, but it may be my own mistake. It seems if I apply one static visitor within another with an extra call to operator() that I use for shared_ptr objects, the program deadlocks in apply_visitor_binary_invoke::internal_visit(). The template in my class below is another static visitor object, so in essence I am creating an effect similar to a java decorator using visitors. Here is a stripped down version of the class with which the deadlock occurs: /** * @class VisitorDecorator * * @brief decorates (wraps) a normal visitor */ template <typename T> class VisitorDecorator : public boost::static_visitor<typename T::result_type> { typedef typename T::result_type t_result_type; public: VisitorDecorator(boost::shared_ptr<T> deviceCommandVisitor, std::string filename): m_visitor(deviceCommandVisitor), m_filename(filename) {} /** * @brief strip shared pointers and handle the object itself */ template <typename U, typename V> inline t_result_type operator()( boost::shared_ptr<U>& deviceP, boost::shared_ptr<V>& commandP){ return operator()(*deviceP,*commandP); } /** * @brief Connect the specified struct types to the log file */ template<typename U, typename V> t_result_type operator()(U& device, V& command){ return (*m_visitor)(device,command); } private: boost::shared_ptr<T> m_visitor; std::string m_filename; }; Does anyone have thoughts or suggestions, be it my fault or a bug in the library? Cheers! Andrew Hundt

1 1

[introductions]
by Gregory Crosswhite 17 May '11

17 May '11

Hey everyone! I don't know what the protocol is for this, but since I have been posting occasionally for a while and have offered to be a Review Manager but am relatively unknown to the community (which, again, means that I will completely understand and won't be offended in the slightest if you politely decline my offer to be a Review Manager :-) ) and have never introduced myself I figured that now might be as good a time as any: I am a graduate student who will be finishing up my PhD in Physics in the next month. My field is roughly quantum computing/quantum simulation, and my specialty is writing software that solves problems in the field of quantum error correction. My web page, which gives an overview of my background, is here: http://students.washington.edu/gcross/index.html Cheers, Greg

6 7

[multi_index] Extending multi_index_container hash tables
by Vladimir Voznesensky 17 May '11

17 May '11

Hello there. Another question. Why nodes with similar values are grouped sequentially in non-unique hash table? It's rather a strong restriction leading to extra iterations during insertions and modifications (please, see link_point and in_place methods in hashed_index.hpp). -vv

1 0

[review] Formal review of AutoIndex starts 5th May
by Daniel James 17 May '11

17 May '11

Hello everyone, The formal review of John Maddock's AutoIndex starts tomorrow, 5th May and finishes on Saturday 14th May. It's a little different to normal as it's a review of a documentation tool, rather than a library. We'll follow the normal procedure. Hopefully the review will also provide some experience for deciding how to deal with other tools in the future. About AutoIndex =============== The documentation describes it as "a tool for taking the grunt work out of indexing a Boostbook/Docbook document that describes C/C++ code". The documentation is online at: http://svn.boost.org/svn/boost/sandbox/tools/auto_index/doc/html/index.html AutoIndex can be downloaded from the vault: http://www.boostpro.com/vault/index.php?action=downloadfile&filename=auto_i… The download also contains a pdf of the documentation at 'doc/auto_index.pdf', and a copy of the html documentation at 'doc/html/index.html'. You can also see some examples of the indexes it generates, in a few libraries' documentation: http://www.boost.org/libs/spirit/ http://www.boost.org/libs/type_traits/ http://www.boost.org/libs/math/doc/sf_and_dist/html/ Review guidelines ================= Reviews should be submitted to the developer list (boost(a)lists.boost.org) with '[autoindex]' in the subject. Or if you don't wish to for some reason, you can send them privately to me. If so, please let me know whether or not you'd like your review to be forwarded to the list. All reviews are appreciated, even if you don't have time for an in-depth study. It's worth a look even if you don't use docbook or the boost documentation tools yourself. As someone who uses boost, the generated indexes are intended for your use so your views do matter. Even though this isn't a library, I think the (slightly modified) general guidelines still apply: - 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 AutoIndex? - Did you try to use it? 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? And finally, every review should answer this question: - Do you think that AutoIndex should be accepted into Boost? Be sure to say this explicitly so that your other comments don't obscure your overall opinion. More detail on the review process is available at: http://www.boost.org/community/reviews.html I think it should be made clear that if accepted, there won't be any requirement to use AutoIndex it. Thanks in advance, Daniel James AutoIndex Review Manager

6 11

[review][autoindex] AutoIndex review extended
by Daniel James 17 May '11

17 May '11

Hello all, The AutoIndex review is extended for another week, it's now running until Saturday 21st May. This will hopefully give people who have been busy preparing for boostcon a chance to review it in a quiet moment. I'm also interested in hearing from people who won't be using the tool directly, but might be using the indexes it generates. Or perhaps already are, since it's already been used for Boost.Spirit, Boost.Type Traits and Boost.Math: http://www.boost.org/libs/spirit/ http://www.boost.org/libs/type_traits/ http://www.boost.org/libs/math/doc/sf_and_dist/html/ It doesn't need to be a long or in depth review to be useful. The documentation is online at: http://svn.boost.org/svn/boost/sandbox/tools/auto_index/doc/html/index.html AutoIndex can be downloaded from the vault: http://www.boostpro.com/vault/index.php?action=downloadfile&filename=auto_i… thanks, Daniel James AutoIndex review manager

3 12

Boost talk / Funding / Your input is needed
by Ruediger Berlich 17 May '11

17 May '11

Dear all, at BoostCon 2011, I will give a presentation with the title and abstract: //---------------------------------------- Funding Boost development through national and international research programs and funds This presentation wants to start a discussion about possible ways of leveraging national and international research programs and funds to support Boost development. The goals are threefold: - To start and organize a joint effort in many countries to leverage national and international research funding schemes (e.g. NSF, European Union, …) for the benefit of Boost development - To make Boost a standard topic in the curricula of computer science education at universities and polytechnicals around the world - To involve new protagonists from the science community in Boost development //---------------------------------------- I think that this pretty much sums up what the presentation is about. I will, however, necessarily have to assume a (European and particularly German) view on this topic, as I have no experience with e.g. US academic funding schemes. The session is meant to be a brainstorming session and reality check; and without your input it will hardly be possible to fill 90 minutes for this topic. If you have first-hand experience with research grants and national or international funding schemes or if you have any related idea you would like to share, I particularly invite you to come along and contribute to the overall picture. I am sending this mail to the development list, as this is hardly a user- level issue. Thanks and maybe see you at the session, Ruediger Berlich

2 1

[Block Pointer] now thread safe!
by Phil Bouchard 17 May '11

17 May '11

Ok, Block Pointer is now thread safe! The following file was its test: https://svn.boost.org/svn/boost/sandbox/block_ptr/libs/smart_ptr/example/th… It is now ready for a review. Thanks! -Phil

3 6

[siprit] Can't compile the following code with vs 2008
by 罗勇刚(Yonggang Luo) 16 May '11

16 May '11

/***************************************************************************** * * This file is part of Mapnik (c++ mapping toolkit) * * Copyright (C) 2009 Artem Pavlenko * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA * *****************************************************************************/ //$Id$ #ifndef MAPNIK_EXPRESSIONS_GRAMMAR_HPP #define MAPNIK_EXPRESSIONS_GRAMMAR_HPP // mapnik #include <mapnik/value.hpp> #include <mapnik/expression_node.hpp> // boost #include <boost/version.hpp> #include <boost/variant.hpp> #include <boost/shared_ptr.hpp> #include <boost/concept_check.hpp> //spirit2 #include <boost/spirit/include/qi.hpp> #include <boost/spirit/include/qi_action.hpp> //fusion #include <boost/fusion/include/adapt_struct.hpp> //phoenix #include <boost/spirit/include/phoenix_core.hpp> #include <boost/spirit/include/phoenix_object.hpp> #include <boost/spirit/include/phoenix_operator.hpp> #include <boost/spirit/include/phoenix_function.hpp> #include <boost/spirit/include/phoenix_stl.hpp> #include <boost/spirit/home/phoenix/object/construct.hpp> namespace mapnik { namespace qi = boost::spirit::qi; namespace standard_wide = boost::spirit::standard_wide; using standard_wide::space_type; struct unicode_impl { template <typename T> struct result { typedef UnicodeString type; }; explicit unicode_impl(mapnik::transcoder const& tr) : tr_(tr) {} UnicodeString operator()(std::string const& str) const { return tr_.transcode(str.c_str()); } mapnik::transcoder const& tr_; }; struct regex_match_impl { template <typename T0, typename T1> struct result { typedef expr_node type; }; explicit regex_match_impl(mapnik::transcoder const& tr) : tr_(tr) {} template <typename T0,typename T1> expr_node operator() (T0 & node, T1 const& pattern) const { #if defined(BOOST_REGEX_HAS_ICU) return regex_match_node(node,tr_.transcode(pattern.c_str())); #else return regex_match_node(node,pattern); #endif } mapnik::transcoder const& tr_; }; struct regex_replace_impl { template <typename T0, typename T1, typename T2> struct result { typedef expr_node type; }; explicit regex_replace_impl(mapnik::transcoder const& tr) : tr_(tr) {} template <typename T0,typename T1,typename T2> expr_node operator() (T0 & node, T1 const& pattern, T2 const& format) const { #if defined(BOOST_REGEX_HAS_ICU) return regex_replace_node(node,tr_.transcode(pattern.c_str()),tr_.transcode(format.c_str())); #else return regex_replace_node(node,pattern,format); #endif } mapnik::transcoder const& tr_; }; template <typename Iterator> struct expression_grammar : qi::grammar<Iterator, expr_node(), space_type> { typedef qi::rule<Iterator, expr_node(), space_type> rule_type; explicit expression_grammar(mapnik::transcoder const& tr) : expression_grammar::base_type(expr), unicode_(unicode_impl(tr)), regex_match_(regex_match_impl(tr)), regex_replace_(regex_replace_impl(tr)) { using boost::phoenix::construct; using qi::_1; using qi::_a; using qi::_b; using qi::_r1; #if BOOST_VERSION > 104200 using qi::no_skip; #else using qi::lexeme; #endif using qi::_val; using qi::lit; using qi::int_; using qi::double_; using standard_wide::char_; expr = logical_expr.alias(); logical_expr = not_expr [_val = _1] >> *( ( ( lit("and") | lit("&&")) >> not_expr [_val && _1] ) | (( lit("or") | lit("||")) >> not_expr [_val || _1]) ) ; not_expr = cond_expr [_val = _1 ] | ((lit("not") | lit('!')) >> cond_expr [ _val = !_1 ]) ; cond_expr = equality_expr [_val = _1] | additive_expr [_val = _1] ; equality_expr = relational_expr [_val = _1] >> *( ( (lit("=") | lit("eq") | lit("is")) >> relational_expr [_val == _1]) | (( lit("!=") | lit("<>") | lit("neq") ) >> relational_expr [_val != _1]) ) ; regex_match_expr = lit(".match") >> lit('(') >> ustring [_val = _1] >> lit(')') ; regex_replace_expr = lit(".replace") >> lit('(') >> ustring [_a = _1] >> lit(',') >> ustring [_b = _1] >> lit(')') [_val = regex_replace_(_r1,_a,_b)] ; relational_expr = additive_expr[_val = _1] >> *( ( (lit("<=") | lit("le") ) >> additive_expr [ _val <= _1 ]) | ( (lit('<') | lit("lt") ) >> additive_expr [ _val < _1 ]) | ( (lit(">=") | lit("ge") ) >> additive_expr [ _val >= _1 ]) | ( (lit('>') | lit("gt") ) >> additive_expr [ _val > _1 ]) ) ; additive_expr = multiplicative_expr [_val = _1] >> * ( '+' >> multiplicative_expr[_val += _1] | '-' >> multiplicative_expr[_val -= _1] ) ; multiplicative_expr = primary_expr [_val = _1] >> *( '*' >> primary_expr [_val *= _1] | '/' >> primary_expr [_val /= _1] | '%' >> primary_expr [_val %= _1] | regex_match_expr[_val = regex_match_(_val, _1)] | regex_replace_expr(_val) [_val = _1] ) ; primary_expr = strict_double [_val = _1] | int_ [_val = _1] | lit("true") [_val = true] | lit("false") [_val = false] | lit("null") [_val = value_null() ] | ustring [_val = unicode_(_1) ] * | attr [_val = construct<attribute>( _1 ) ]* * | '(' >> expr [_val = _1 ] >> ')'* *//These lines got errors!, The first line can be resolved by replace with * * attr [_val = ( _1 ) ], And I can't deal with the second line!* *//Even though, the first line I can't to be sure if the resolve is correct! * ; attr %= '[' >> +(char_ - ']') >> ']'; #if BOOST_VERSION > 104200 ustring %= '\'' >> no_skip[*~char_('\'')] >> '\''; #else ustring %= '\'' >> lexeme[*(char_-'\'')] >> '\''; #endif } qi::real_parser<double, qi::strict_real_policies<double> > strict_double; boost::phoenix::function<unicode_impl> unicode_; boost::phoenix::function<regex_match_impl> regex_match_; boost::phoenix::function<regex_replace_impl> regex_replace_; // rule_type expr; rule_type equality_expr; rule_type cond_expr; rule_type relational_expr; rule_type logical_expr; rule_type additive_expr; rule_type multiplicative_expr; rule_type not_expr; rule_type primary_expr; qi::rule<Iterator, std::string() > regex_match_expr; qi::rule<Iterator, expr_node(expr_node), qi::locals<std::string,std::string>, space_type> regex_replace_expr; qi::rule<Iterator, std::string() , space_type> attr; qi::rule<Iterator, std::string() > ustring; }; } // namespace #endif // MAPNIK_EXPRESSIONS_GRAMMAR_HPP -- 此致礼罗勇刚 Yours sincerely, Yonggang Luo

2 1

[multi_index] Extending multi_index_container hash tables
by Vladimir Voznesensky 16 May '11

16 May '11

Dear Joaquin, Dear all, Please, find the comments below. Joaquin M Lopez Munoz writes: > Vladimir Voznesensky<vvoznesensky<at> gmail.com> writes: > > >> > >> > Hello there. >> > >> > Current implementation of hashed index has, at least, two issues, preventing >> > me from re-using it in some places. >> > >> > First, the time for unlink operation in >> > multi_index/detail/hash_index_node.hpp is O(m) where m is a occupancy of the >> > given bucket. I'ts usually ok for unique index, but seems to hit performance >> > of removing item in a non-unique index. It's all because of using >> > single-linked list instead of double-linked one. >> > The question here is whether non-unique indices will be populated > with many equivalent elements or not: if the former, a singly-linked > list implementation such as that of Boost.MultiIndex certainly > degrades at erasure, but going to a doubly-linked list unncessarily > imposes a non-negligible penalty (one pointer per element) in the > latter case. Having to decide I chose to favor the former case. > I think it should be up to a user to choose: the usage pattern could be very specific (for instance, a LIFO pattern seems to work OK with the single linked machinery). > If you can contribute a Boost-quality modification of the implementation > that lets the user decide between singly-linked and doubly-linked > implementation (say with an extra template paramater in > the hashed<...> index specifier I can certainly add it to the > library. > I have some questions to discuss here. 1. The 1st obvious step is to realize a double- linked list near a single-linked one. I plan not to subclass any stuff from the current detail/hash_index_node.hpp, but use it as a near sample. Should I copy detail/hash_index_node.hpp to, say, detail/hash_index_dbl_node.hpp or use the same file for realization? It seems not to be a problem to add a concrete NodeImpl second template argument to a class bucket_array. 2. hashed_index.hpp arise some gentle problems. I could put another template argument into detail::hashed_index, hashed_unique and hashed_non_unique, but what kind should it be? It's seems possible to add NodeType template argument to class hashed_index without breaking up BOOST_MULTI_INDEX_ENABLE_SAFE_MODE stuff, but how should we pass such sophisticatedly formed type from the final API? detail::hashed_index_args looks like a template hell. So, maybe it would be wiser to just introduce struct hashed_dbl_unique and struct hashed_dbl_non_unique extra variants? > Hahsed indices have the following bucket-handling interface: > > // bucket interface: > > size_type bucket_count()const; > size_type max_bucket_count()const; > size_type bucket_size(size_type n)const; > size_type bucket(const key_type& k)const; > > local_iterator begin(size_type n); > const_local_iterator begin(size_type n)const; > local_iterator end(size_type n); > const_local_iterator end(size_type n)const; > const_local_iterator cbegin(size_type n)const; > const_local_iterator cend(size_type n)const; > > local_iterator local_iterator_to(const value_type& x); > const_local_iterator local_iterator_to(const value_type& x)const; > > (See > http://www.boost.org/libs/multi_index/doc/reference/hash_indices.html#hash_…) > Is this not what you're looking for? > It's not clear from the docs and the sources, how to, say, insert a new element before or after a given one. Thank you.

1 0