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:

• If 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.
• The 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:

// 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 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.
• There's a whole six lines (almost half the implementation) to remove things that have already been processed in a previous iteration. It would be nice to be able to use std::vector::erase together with std::remove_if, but in C++03 that takes no fewer lines and they're moved farther away in their own class.

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 167 of file Tracker.h.

#include <Sawyer/Tracker.h>

Inheritance diagram for Sawyer::Container::Tracker< T, K, Traits >:

Public Types
typedef T	Value
	Type of values represented by the tracker.
typedef K	Key
	Key type for the values represented by the tracker.

Public Member Functions
void	clear ()
	Make this tracker forget everything it has seen.
bool	testAndSet (const Value &value)
	Test and then insert the value.
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.
bool	insert (const Value &value)
	Cause this tracker to see a value.
void	removeIfSeen (std::vector< Value > &vector)
	Remove and track items from a vector.

Member Typedef Documentation

Value

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 170 of file Tracker.h.

Key

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 175 of file Tracker.h.

Member Function Documentation

clear()

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 185 of file Tracker.h.

testAndSet()

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 195 of file Tracker.h.

Referenced by Sawyer::Container::Tracker< T, K, Traits >::insert(), and Sawyer::Container::Tracker< T, K, Traits >::operator()().

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 202 of file Tracker.h.

References Sawyer::Container::Tracker< T, K, Traits >::testAndSet().

wasSeen()

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 211 of file Tracker.h.

insert()

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 223 of file Tracker.h.

References Sawyer::Container::Tracker< T, K, Traits >::testAndSet().

Referenced by Sawyer::Container::Tracker< T, K, Traits >::removeIfSeen().

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 247 of file Tracker.h.

References Sawyer::Container::Tracker< T, K, Traits >::insert().

---

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

• Tracker.h