Data Structures

Small-Buffer Vector

Difficulty

Asked at Hudson River Trading

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.

xxxx xx xxx xxxxxxx xx x xxxxxxx xxxxxx xxxx xxx xx xxxxx xxxxxxxx: xxx xxxxx xx x xxxxx xxxxx, xxx xxxx xx x xxxxxx, xxx xxxxxx x xxxxxx xxxxxxx. xxx::xxxxxx xxxxxxxxx xxx xxx xxxxx xxx xx xxxx, xxx xx x xxx xxxx xxxx xx xxx x xxx xxxxxxxxxxx, xx xx x xxxx xxxxxxx xxx xxxxxxxxx xxxxx xxxxx xxxx xx xxxxx xxxxxxx, xxxx xxx x xxxx xxxxx.

xxx xxx xx xx xxxxxx xxxxxx. xxxx xxx xxxxx xxx xxxxxxxx xxxxxx xxx xxxxxx xxx xxxx xxxxx xxx xxx xxxx xxxx xxxx xxxx xxx. xxxx::xxxxxxxxxxx, xxxxx::xxxxxxxxx::xxxxx_xxxxxx xxx xxxxx xxxxxxx xxxx'x xxxxxxxx xxxxxxxxxx xxx xxxx.

xxxxxxxxx xxxxxxxxxxx<xxxxxx>, xxxxxxx xxxx xxxx.

xxxx_xxxx(x) — xxxxxx, xxxxxxx xx xxxxxxxx xxxx xx xxx xxxxxxx
xxxx(), xxxxxxxx(), xxxxxxxx[] (xxxxx xxx xxxxxxx)
xx_xxxxxx() — xxxx xxxxx xxx xxxx xxxxx xxxxx xxxxxx xxx xxxxxx

xxx xxxxx xxxx xxxxxxxx xx x * xxxxxx, xxx xxxx xxxxxx xxxxx xxxx xxxxxxx. xxx xxxxx xxxx xxxxxxxx xxxxxxxxxx xxxxxxx xxxxxx.

xxx xxxxxx xxxxxxxx xxx xx xxxxxxxxxxxx, xx "xxxx xxx xxxxxxxx" xx xxxxxxxx xxxxxx xxxx xxxxxxx.

xxxxxxxx

xxxxxxxxxxx<x> x;
xxx (xxx x = x; x < x; ++x) x.xxxx_xxxx(x * xx);
// x xxxxxxxxxxx, xx_xxxxxx() xxxx, xxxxxxxx() x

x.xxxx_xxxx(xx);
// x xxxxxxxxxx, xx_xxxxxx() xxxxx, xxxxxxxx() x, xxx x[x] xx xxxxx x

xxxxxxxxxxx

xxxxxxxx xxx xxxx xxxx, xx xxxxx xx xxxxxxx xx xxxxxxxxx xx xxxxxxx. xxxx xx xxx xxxxxxxxx, xxx x xxxx xxxxxxxxx: xxxx xxx xxxxxxxxxx xxx xxxxxxx.
xxxxxxx xxx xxxxxxxxxx xxx xxx xxxxx, xxx xx xxxxxxxxxx xx xxx xxx x xxxxxx xxxx xxxxx xxxxxxx xxxxxx, xxxxxxxxx xxx xxxx xx xxxxxxx-xxxxxxxxxxx xxx xxxxx xxxx.
xxx xxxxxxx xxxx xxxx xx xxxxxxxxx xxxxxxx x xxxxxx xxxxxxxx. xxx xxxxxx xx xxx "xxxxxx xx xxxx?" xxxxxx xx xxx x xxxxx xxxxxx xxxx xx xxxxxxx xxx xxxxxx xxxxxx xxxxx xx xxx xxxxxxx, xxx xxx xxxxx xxxxxx xxxxxxx xxxxxxxx[] xx xxxx xxxxx xx xxx xxxxxxxxxx.

This problem is only available to subscribers.

Language: C++SmallVector

#include <cstddef>
#include <cstdlib>
#include <new>
#include <utility>

// ...
// ...
// ...
// ...
// ...
namespace probe {
inline long long& counter() {
    static long long calls = 0;
    return calls;
}
inline long long allocations() { return counter(); }
inline void reset() { counter() = 0; }
}  // ...

void* operator new(std::size_t bytes) {
    ++probe::counter();
    void* p = std::malloc(bytes ? bytes : 1);
    if (!p) throw std::bad_alloc();
    return p;
}
void* operator new[](std::size_t bytes) { return ::operator new(bytes); }
void operator delete(void* p) noexcept { std::free(p); }
void operator delete[](void* p) noexcept { std::free(p); }
void operator delete(void* p, std::size_t) noexcept { std::free(p); }
void operator delete[](void* p, std::size_t) noexcept { std::free(p); }

// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
template <std::size_t Inline>
class SmallVector {
public:
    SmallVector() = default;

    ~SmallVector() {
        // ...
    }

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

    void push_back(long long value) {
        // ...
        (void)value;
    }

    long long& operator[](std::size_t index) {
        // ...
        (void)index;
        return inline_[0];
    }

    const long long& operator[](std::size_t index) const {
        // ...
        (void)index;
        return inline_[0];
    }

    std::size_t size() const { return size_; }

    std::size_t capacity() const {
        // ...
        return 0;
    }

    bool is_inline() const {
        // ...
        return true;
    }

private:
    long long inline_[Inline]{};
    long long* heap_ = nullptr;
    std::size_t size_ = 0;
    std::size_t heap_capacity_ = 0;
};

Unlock to runUpgrade

Sample tests

Unlock the problem to run it against the tests.