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 | +-----------------------------------------------------+