Data Structures

Short String Optimization

Difficulty

Asked at IMC 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.

This problem is only available to subscribers.

Language: C++23SsoString

#include <cstddef>
#include <cstdlib>
#include <cstring>
#include <new>
#include <string_view>

// ...
// ...
// ...
// ...
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); }

// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
class SsoString {
public:
    static constexpr std::size_t kInline = 22;

    SsoString() { /* ... */ }

    explicit SsoString(std::string_view text) {
        // ...
        (void)text;
    }

    ~SsoString() {
        // ...
    }

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

    void append(std::string_view text) {
        // ...
        (void)text;
    }

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

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

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

    const char* c_str() const {
        // ...
        return small_;
    }

    std::string_view view() const { return std::string_view(c_str(), size_); }

private:
    char small_[kInline + 1] = {};
    char* heap_ = nullptr;
    std::size_t size_ = 0;
    std::size_t heap_capacity_ = 0;
};

Unlock to runUpgrade

Unlock the problem to run it against the tests.

Next in STL From ScratchVisit a Tagged UnionData Structures

Short String Optimization

xxxxxxxx

xxxxxxxxxxx