STL Map Use

What’s wrong with the following code?

template<typename T1, typename T2>
struct my_pair
{
    typedef T1 first_type;
    typedef T2 second_type;

    my_pair() : first(T1()), second(T2()) {}
    my_pair(const T1& v1, const T2& v2) : first(v1), second(v2) {}

    T1 first;
    T2 second;
};

template<typename T1, typename T2>
inline bool operator<
    (
    const my_pair<T1, T2>& x,
    const my_pair<T1, T2>& y
    )
{
    return (x.first < y.first || x.second < y.second);
}

void f()
{
    typedef my_pair<..., ...> key_type;
    typedef ... value_type;
    typedef std::map<key_type, value_type> map_type;

    map_type map;
    // Use map
}

Answer: my_pair cannot be used as a key for a STL map because the operator< violates the rule of strict weak ordering. More specifically, the operator is not antisymmetric. Consider the following:

typedef my_pair<int, int> P;
P p1(3, 5);
P p2(2, 6);

Both p1 < p2 and p2 < p1 evaluate to true.

If you use my_pair as a key into a map you will not get any compiler errors or warnings but you will likely see some bizarre runtime behavior. For example, keys which were successfully insert()ed may not be able to be found using find().

A correct version of operator< (which places minimal burden on T1 and T2 — they are only required to implement operator<) is:

template<typename T1, typename T2>
inline bool operator<
    (
    const my_pair<T1, T2>& x,
    const my_pair<T1, T2>& y
    )
{
    return
        (
        x.first < y.first ||
        (!(y.first < x.first) && x.second < y.second)
        );
}
Advertisements

STL Vector Use

I recently wrote a piece of code that looked something like the following:

static const int NUM_TOTAL_VALUES = ...;
typedef ... T;

// Create vec and reserve NUM_TOTAL_VALUES spaces for later insertion
std::vector<T> vec(NUM_TOTAL_VALUES);

// Insert values into vec
for (int i = 0; i != NUM_TOTAL_VALUES; ++i)
    vec.push_back(...);

// vec should now have NUM_TOTAL_VALUES values in it (but doesn't!)

What’s wrong with this code?

The constructor vector(size_type _Count); does more than just allocate enough space to store _Count items — it also inserts _Count (default constructed) items into the vector. To reserve space without actually inserting values, use reserve():

static const int NUM_TOTAL_VALUES = ...;
typedef ... T;

std::vector<T> vec;
vec.reserve(NUM_TOTAL_VALUES);

for (int i = 0; i != NUM_TOTAL_VALUES; ++i)
    vec.push_back(...);

// vec now has NUM_TOTAL_VALUES values in it, as intended.

Managed Wrappers and Hidden Interdependencies

Let’s say you have the following unmanaged code:

#pragma unmanaged

class Stream { ... }; // Conceptual stream class

class StreamWriter
{
public:
    StreamWriter(Stream* pStream) : m_pStream(pStream) {}
    ~StreamWriter() { /* Use m_pStream in some way */ }

    ...
private:
    Stream* m_pStream;
};

void f()
{
    Stream stream;
    StreamWriter streamWriter(&stream);

    // Use streamWriter

    // streamWriter is destroyed
    // stream is destroyed
}

Note that StreamWriter’s destructor uses m_pStream (perhaps by flushing the stream). This means that the order of destruction is important — StreamWriter must be destroyed before its underlying Stream is.

Now let’s try to write and use some simple managed C++ wrappers for these classes:

#pragma managed

public __gc class ManagedStream
{
public:
    ManagedStream() : m_pStream(new Stream) {}

    // NOTE: This is a finalizer, not a determinstic destructor
    ~ManagedStream() { delete m_pStream; }

public private: // Make accessible by ManagedStreamWriter
    Stream __nogc* m_pStream;
};

public __gc class ManagedStreamWriter
{
public:
    ManagedStreamWriter(ManagedStream* pStream) :
        m_pStreamWriter(new StreamWriter(pStream->m_pStream)) {}

    // NOTE: This is a finalizer, not a determinstic destructor
    ~ManagedStreamWriter() { delete m_pStreamWriter; }

private:
    StreamWriter __nogc* m_pStreamWriter;
};

void f()
{
    ManagedStream stream = __gc new ManagedStream();
    ManagedStreamWriter streamWriter = __gc new ManagedStreamWriter(stream);

    // Use streamWriter

    // GC will clean up stream and streamWriter
}

See the problem?

As I (gratituously) hinted above, we have a problem due to nondeterminstic destruction. Since the GC does not define the order in which it will destroy managed objects, we cannot guarantee that the ManagedStreamWriter will be destroyed before the ManagedStream. If the ManagedStream is destroyed first, then its Stream will be deleted before the ManagedStreamWriter’s StreamWriter destructor is called. This means that StreamWriter will be using a deleted pointer — a sure recipe for disaster.

I can think of a few possible solutions to this problem:

  1. Have the managed classes implement IDisposable, and require developers to use it to achieve determinstic destruction. The main downside to this approach is “what if developers forget?”
  2. Recapture the interdependencies among unmanaged classes in the managed wrappers. For example, add a reference in ManagedStreamWriter to the ManagedStream object. This will force the GC to properly order their destruction, and is probably the right way to go.