ROSE
0.11.96.11
|
Tracks whether something has been seen before.
Template parameter T
are the things that are being tracked, but the tracker doesn't necessarily store them. Instead, it stores a key, type K
, that can be derived from T
and which might be a lot smaller.
Many iterative algorithms need to operate on an object just once. They use an std::set
to remember which objects they've encountered already. For example:
There are two problems with the above code:
Thing
is large, then storing it in an std::set
is expensive. In fact, Thing
might not even be copyable in which case storing it in the set is impossible. Authors work around this by storing a proxy for the Thing
, such as an identification number. for
loop serializes the processing of the objects, but it might be more efficient to process all the things
at once. Authors do this by filtering out from the vector those things that have already been processed in a previous pass.So a more realistic implementation looks like this:
The main problem with the above implementation is there's a lot going on that isn't the main point of the algorithm:
seen
set stores values of type Identifier
and there's nothing really obvious that says that Identifier
is related somehow to Thing
. You'd have to go find the definition of Identifier
to see that it can be implicitly constructed from Thing
. The purpose of the Tracker
class is to reduce all this clutter:
#include <Tracker.h>
Public Types | |
typedef T | Value |
Type of values represented by the tracker. | |
typedef K | Key |
Key type for the values represented by the tracker. More... | |
Public Member Functions | |
void | clear () |
Make this tracker forget everything it has seen. More... | |
bool | testAndSet (const Value &value) |
Test and then insert the value. More... | |
bool | operator() (const Value &value) |
Unary operator is the same as testAndSet. | |
bool | wasSeen (const Value &value) const |
Test whether a value has been encountered previously. More... | |
bool | insert (const Value &value) |
Cause this tracker to see a value. More... | |
void | removeIfSeen (std::vector< Value > &vector) |
Remove and track items from a vector. More... | |
typedef K Sawyer::Container::Tracker< T, K, Traits >::Key |
|
inline |
|
inline |
Test and then insert the value.
Causes the specified value to be seen by this tracker and then returns whether it had been seen already.
Thread safety: This method is thread safe.
Definition at line 193 of file Tracker.h.
Referenced by Sawyer::Container::Tracker< T, K, Traits >::insert(), and Sawyer::Container::Tracker< T, K, Traits >::operator()().
|
inline |
|
inline |
Cause this tracker to see a value.
Insert the value into the tracker and return true only if it was not already present. This function is identical to testAndSet and the unary function operator except it returns the opposite Boolean.
Thread safety: This method is thread safe.
Definition at line 221 of file Tracker.h.
References Sawyer::Container::Tracker< T, K, Traits >::testAndSet().
Referenced by Sawyer::Container::Tracker< T, K, Traits >::removeIfSeen().
|
inline |
Remove and track items from a vector.
Modifies vector
by removing those items that are present in the tracker
, and adds the other items to the tracker
. The relative order of the items in the vector is unchanged. The vector is processed from low to high indexes as the tracker is updated.
One use of this is similar to std::unique
in that it can remove duplicates from a vector. However, unlike std::unique
, this function can operate on unsorted vectors. For example:
Thread safety: Althrough the operations on the tracker are thread-safe, the operations on the vector are not. Therefore it's permissible to be using the specified tracker in two different threads as long as this thread is the only one accessing the vector.
Definition at line 245 of file Tracker.h.
References Sawyer::Container::Tracker< T, K, Traits >::insert().