Boost logo

Boost :

From: Angus Leeming (angus.leeming_at_[hidden])
Date: 2004-10-05 03:18:18

Earlier, Gennadiy Rozental wrote:
AL>> No doubt there's lots of implementation details left, (like
AL>> using input_iterator_adaptor), but I think that this
AL>> using idea.
GR> You may use iterator_facade also. I just found that
GR> implementing Input iterators using input_iterator_adaptor
GR> is easier. It's located in Boost.Test details derectory
GR> along with some usage examples.
AL>> Am I on the right track?
GR> Definitely. Looking forward to see it implemented.

Later, Rob Stewart wrote:
AL>>>> It works, but is considerably slower than the function
AL>>>> returning a list. No doubt profiling will help track
AL>>>> down what I'm doing inefficiently.
RS>>> No doubt.
GR>> I do not see anything in iterator implementation that
GR>> suggest inherent inefficiency.
RS> What he described sounded like he populated a container with the
RS> results and then iterated that. Using the resulting iterator to
RS> populate another container would, thus, reduce efficiency.

Ahhhh. Now I understand you.

Actually, the glob_iterator I've implemented and have just posted
(Docs can be viewed on line at:

doesn't store anything but remains two to three times slower than the
glob function that stores its results in a std::list.

$ cd libs/glob/example
$ time ./glob_function '*/*/*.hpp' '/home/angus/boost/cvs/' > /dev/null
count_operator 1997 count_regex_match 1997
real 0m0.095s
user 0m0.080s
sys 0m0.020s

$ time ./glob_iterator '*/*/*.hpp' '/home/angus/boost/cvs/' > /dev/null
count_operator 1997 count_regex_match 1997
real 0m0.241s
user 0m0.220s
sys 0m0.010s

I'm pretty sure I'm not doing anything daft. The 'count' data shows
how many times I call the glob_predicate::operator() that decides
whether a given file matches the globbing pattern. As you can see,
this function is called the same number of times in each case. The
algorithm to iterate over the files '*/*/*.hpp' is basically the same
in the two cases, but the iterator version obviously has more 'if'
statements in the inner loop. I guess that this is the killer and I
don't think that there's anything we can do about it.

Soooooooooo... do we flag that one up as a valient effort and move on
or can the iterator be as efficient as the function and I just
haven't found the right algorithm?


Boost list run by bdawes at, gregod at, cpdaniel at, john at