Re: [boost] [regex] regex_replace with format string replaced asitis

From: Lorenzo Bettini (bettini_at_[hidden])
Date: 2005-07-03 07:05:40

John Maddock wrote:
>> well, since what[] is already an array of n subexpressions, during 
>> finding of matches, I suppose, you set all the fields of what[i], if 
>> the i-th subexpression matched.  While you're doing this, you could 
>> also store the index i into another structure of what.
>>
>> I hope I explained this correctly...
> 
> 
> Yes, but it's not that simple...
> 
> 1) As well as adding matches to the list, matches can become "unmatched" 
> during backtracking.
> 2) The time taken for a match is completely dominated by the time taken 
> for calls to new and delete, especially for simple expressions a call to 
> new is about 10x as long as the time to find a match, so if you reuse 
> your match_results structures (so the matcher doesn't have to allocate 
> any memory), then matching is extremely fast.  Using a dynamic memory 
> structure (like std::set or std::map) to store just those 
> sub-expressions that matched would completely blow this out of the 
> water.  And yes, for some folks this is very important....
> 
> An alternative would be to extend the existing structure to hold the 
> extra information, the trouble is, almost any way I can think of 
> arranging this will have rather a negative speed impact (don't forget 
> you have to remove as well as add entries).  Probably the fastest method 

OK, I see: I wasn't thinking about backtracking and removing entries 
from a dynamic structure.  I was thinking about a list, but I see that 
if you need to remove an entry this may waste lot of time.

> 
> There is one option I can think of that might work: add a linked list to 
> the existing submatches, so that each links forward to the next matched 
> subexpression and back to the previous matched subexpression.  However, 
> this means that only bi-directional (not random access ) would be 
> possible to "just the matched" sub-expressions.  It would also double 

but again you may need to modify this structure during backtracking, right?

Lorenzo

-- 
+-----------------------------------------------------+
|  Lorenzo Bettini          ICQ# lbetto, 16080134     |
|  PhD in Computer Science                            |
|  Dip. Sistemi e Informatica, Univ. di Firenze       |
|  Florence - Italy        (GNU/Linux User # 158233)  |
|  Home Page        : http://www.lorenzobettini.it    |
|  http://music.dsi.unifi.it         XKlaim language  |
|  http://www.lorenzobettini.it/purple    Cover Band  |
|  http://www.gnu.org/software/src-highlite           |
|  http://www.gnu.org/software/gengetopt              |
|  http://www.lorenzobettini.it/software/gengen       |
|  http://www.lorenzobettini.it/software/doublecpp    |
+-----------------------------------------------------+