ROSE  0.10.7.0
Public Types | Public Member Functions | List of all members
Sawyer::Container::Tracker< T, K, Traits > Class Template Reference

Description

template<class T, class K = T, class Traits = TrackerTraits<K>>
class Sawyer::Container::Tracker< T, K, Traits >

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:

// C++03
std::set<Thing> seen;
bool done = false;
while (!done) {
std::vector<Thing> things = findSomeThings(); // unsorted
done = true; // unless we process something
BOOST_FOREACH (const Thing &thing, things) {
if (seen.insert(thing).second) {
process(thing);
done = false;
}
}
}

There are two problems with the above code:

So a more realistic implementation looks like this:

// C++03
std::set<Identifier> seen;
bool done = false;
while (!done) {
std::vector<Thing> things = findSomeThings(); // unsorted
size_t nSaved = 0;
for (size_t i = 0; i < things.size(); ++i) {
if (seen.insert(Identifier(things[i])).second)
things[nSaved++] = things[i];
}
things.resize(nSaved);
done = things.empty();
process(things);
}

The main problem with the above implementation is there's a lot going on that isn't the main point of the algorithm:

The purpose of the Tracker class is to reduce all this clutter:

// C++03
Tracker<Thing, Identifier> tracker;
bool done = false;
while (!done) {
std::vector<Thing> things = findSomeThings(); // unsorted
tracker.removeIfSeen(things);
done = things.empty();
process(things);
}

Definition at line 165 of file Tracker.h.

#include <Tracker.h>

Inheritance diagram for Sawyer::Container::Tracker< T, K, Traits >:
Inheritance graph
[legend]

Public Types

typedef T Value
 Type of values represented by the tracker. More...
 
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. More...
 
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...
 

Member Typedef Documentation

template<class T, class K = T, class Traits = TrackerTraits<K>>
typedef T Sawyer::Container::Tracker< T, K, Traits >::Value

Type of values represented by the tracker.

Definition at line 168 of file Tracker.h.

template<class T, class K = T, class Traits = TrackerTraits<K>>
typedef K Sawyer::Container::Tracker< T, K, Traits >::Key

Key type for the values represented by the tracker.

The tracker stores keys, not values. A key should be able to be constructed from a value.

Definition at line 173 of file Tracker.h.

Member Function Documentation

template<class T, class K = T, class Traits = TrackerTraits<K>>
void Sawyer::Container::Tracker< T, K, Traits >::clear ( )
inline

Make this tracker forget everything it has seen.

Thread safety: This method is thread safe.

Definition at line 183 of file Tracker.h.

template<class T, class K = T, class Traits = TrackerTraits<K>>
bool Sawyer::Container::Tracker< T, K, Traits >::testAndSet ( const Value value)
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< size_t >::insert(), and Sawyer::Container::Tracker< size_t >::operator()().

template<class T, class K = T, class Traits = TrackerTraits<K>>
bool Sawyer::Container::Tracker< T, K, Traits >::operator() ( const Value value)
inline

Unary operator is the same as testAndSet.

Definition at line 200 of file Tracker.h.

template<class T, class K = T, class Traits = TrackerTraits<K>>
bool Sawyer::Container::Tracker< T, K, Traits >::wasSeen ( const Value value) const
inline

Test whether a value has been encountered previously.

Returns true if the value has been seen before, false if not. Does not cause the value to be added to the tracker.

Thread safety: This method is thread safe.

Definition at line 209 of file Tracker.h.

template<class T, class K = T, class Traits = TrackerTraits<K>>
bool Sawyer::Container::Tracker< T, K, Traits >::insert ( const Value value)
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.

Referenced by Sawyer::Container::Tracker< size_t >::removeIfSeen().

template<class T, class K = T, class Traits = TrackerTraits<K>>
void Sawyer::Container::Tracker< T, K, Traits >::removeIfSeen ( std::vector< Value > &  vector)
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:

std::vector<int> va{1, 2, 1, 8, 2, 3};
std::vector<int> vb{4, 3, 2, 5, 8, 6};
Tracker<int> tracker;
tracker.removeIfSeen(va); // va = {1, 2, 8, 3} tracker = {1, 2, 3, 8}
tracker.removeIfSeen(vb); // vb = {4, 5, 6} tracker = {1, 2, 3, 4, 5, 6, 8}

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.


The documentation for this class was generated from the following file: