Data Structures

Visit a Tagged Union

Difficulty

Asked at Squarepoint Capital, XTX Markets

Theory: Data Structures You Implement, Not Import

Read the problem, hints and solution here. The editor needs a bigger screen: open this page on a laptop to write and run your code.

xxxxxxxxx xxxxxxx, x xxxxxx xxxxx xxxx xxxxx xxxxxxx xxx xx xxxxx, xxxxx xx xxxxxx . x xxxxxx xxxx xxxxxxx xxxxxxxx x xxxxx, x xxxxx xx x xxxxxx, xxx xx x xxxx, xxx xxxxx xxxxxxxxx xx xxx xxxxxxxxx xxxxxxx. xxxxxxxxxxx xxxxx x xxxx xxxxxxxxxx xxx x xxxxxxx xxxx. x xxxxxx xxxx xxx xxxxx xxxxxxx xxxxxx xxxxx xxxxxxx xx xxxx xxx xxx xx xx xxxxx xx xxxxx xxx. x xxxxxx xxxxx xxx xxxxxxx xxx xxx xxxxxxx xxxxxxxxxxx xxxx x xxxxx xxxxxxx xxxxxx xxxxx xxx xx xx xx. xxx xxxxxxxxx: xxxxxxxxx xxxx xxx xx xxx xxxxx, xxxxxxx x xxxx xxxxx() : x, x xx x xxxxx(x) : xxxx x xxxx xxx xxxxxxxxxxx xxxxxxxxx xxxx, xxx xxxxxx xxxx x xxxxxxx xxx xxxxxxxxxx, xxxxx xxxx xxxxxxx xxxxxxxx xx xxxx x xxxxxxxx xxxxxxx xx xxxxxxxx xx xxx xxxxx xxx xxx xxxxxxx xxxx xxxxx xxxxxx xxxx xxxxxxxxxxxx xxx xxxxxxxxxxx. xxxxxxxx xxxxxx xxxxxxxx { xxxx xxxx xxxxxxxx()(xxxxx xxxxx& x) xxxxx { xxxxxx x.xxx - x.xxx; } xxxx xxxx xxxxxxxx()(xxxxx xxxxx& x) xxxxx { xxxxxx x.xxxxx * x.xxx; } xxxx xxxx xxxxxxxx()(xxxxx xxxxxx&) xxxxx { xxxxxx x; } }; xxxxxxx x{xxxxx(xxx, x)}; x.xxxxx(); // x x.xxxxx(xxxxxxxx{}); // xxx xxxxxxxxxxx xxx xxxxxxx xxxx xx xxx xxxxx, xxxxx xxx xxxxxxx xxx xxx xxxxxxx xxxxxxxxxxx. xxxxxx(xxxxxxx) xx xx xxxx, xxx xxx xx xxxx xxxxx xxxxxxx xxxxx xxxx. xxx xxxxxxxxxx xxxx xxxxxxx xxxxxxx xxx xxxxxxx xxxxxxxxxxx. xxxxxxxxxx xxxxxxx xxx xxxxx xxx xxxx xxx xxxxx xxxxxxxxxx, xxxxx xx xxxxxxxxx xxxxxxxxx xxx, xxx xxxxx xxxx xxx xxxxxxxx, x xxxx xx x xxxxxx xxxx. xxxxx xxx xx xxxx x xxxx x xxxxxxxxx xxxxxx xxxx xxxxxxxxx xx x xxx-xxxx xxxxx, xxx xxxxx xxxxxx xxx xx xxxxxxx xxxx xxxxxx xxxx xxx xxxx. xxx xxxxxxxx xxxx xxxxxxxxx xxxxxx xxx xxxx xxxx. xxxx xxx xxxxxxxxxx xxx xxxxxxx. xxxx xx xxx xxxxxxxxx, xxx xxx::xxxxxxx .

This problem is only available to subscribers.

Language: C++23Message

#include <cstddef>
#include <new>
#include <string>
#include <type_traits>
#include <utility>

// ...
// ...
// ...
// ...
struct Lifetime {
    static inline long long constructed = 0;
    static inline long long destroyed = 0;
    static void reset() { constructed = 0; destroyed = 0; }
    static long long live() { return constructed - destroyed; }
};

struct Quote : Lifetime {
    long long bid = 0;
    long long ask = 0;
    Quote(long long b, long long a) : bid(b), ask(a) { ++constructed; }
    Quote(const Quote& other) : bid(other.bid), ask(other.ask) { ++constructed; }
    ~Quote() { ++destroyed; }
};

struct Trade : Lifetime {
    long long price = 0;
    long long qty = 0;
    Trade(long long p, long long q) : price(p), qty(q) { ++constructed; }
    Trade(const Trade& other) : price(other.price), qty(other.qty) { ++constructed; }
    ~Trade() { ++destroyed; }
};

struct Cancel : Lifetime {
    long long order_id = 0;
    explicit Cancel(long long id) : order_id(id) { ++constructed; }
    Cancel(const Cancel& other) : order_id(other.order_id) { ++constructed; }
    ~Cancel() { ++destroyed; }
};

// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
class Message {
public:
    explicit Message(const Quote& value) {
        // ...
        (void)value;
    }

    explicit Message(const Trade& value) {
        // ...
        (void)value;
    }

    explicit Message(const Cancel& value) {
        // ...
        (void)value;
    }

    ~Message() {
        // ...
    }

    Message(const Message&) = delete;
    Message& operator=(const Message&) = delete;

    long long index() const { return tag_; }

    template <typename F>
    auto visit(F&& f) const {
        // ...
        (void)f;
        return decltype(f(std::declval<const Cancel&>())){};
    }

private:
    static constexpr std::size_t kSize =
        sizeof(Quote) > sizeof(Trade)
            ? (sizeof(Quote) > sizeof(Cancel) ? sizeof(Quote) : sizeof(Cancel))
            : (sizeof(Trade) > sizeof(Cancel) ? sizeof(Trade) : sizeof(Cancel));

    alignas(Quote) alignas(Trade) alignas(Cancel) std::byte storage_[kSize];
    long long tag_ = -1;
};

Unlock to runUpgrade

Unlock the problem to run it against the tests.

Next in STL From Scratchstd::function InternalsC++ Internals