3
\$\begingroup\$

In C++, currently we have few possibilities to work with strings:

  1. by using plain old C-strings - unfortunately, we have penalty for getting length of string each time, and we should manually control life time of array, which actually contains data...

  2. we can use std::string, but again, unfortunately this is not very efficient class: it's relatively large (32 bytes on 64-bit platform) and it always copies data;

  3. modern C++ gives new opportunity: std::string_view class, which is quite effective, but unfortunately it doesn't own strings, on which it references: again we should control life time of the containers in which strings really stored.

In Java or C# we have more reasonable solution, when class implementing strings divided on two:

  • StringBuilder which behaves like std::string and can be used to construct and edit strings;

  • String which is lightweight and always read-only, and can be used to access previously created strings -- this class can be stored in arrays, passed in functions, etc...

I think, same solution might be perfect for C++, but this requires lot of work...

I want to present solution, which behaves like string in C# (in sense, that it is read-only and only can be created and reassigned). No counterpart, like StringBuffer was created, but my solution has very basic functions to create new strings.

I want to see some comments about my solution and suggestions how can I improve it.

Basic requirements when I design my own string-class implementation was following:

  • it should be very lightweight;

  • copying and passing by value should be almost free;

  • multiple instances of same string should share its representation (and memory);

  • strings cant be created from string literals and shouldn't require memory allocation or copying in that case;

  • strings should be freely convertible to/from std::string_view class.

You can see the code on Coliru.

#include <new>
#include <string_view>
#include <atomic>
#include <stdexcept>
#include <stdarg.h>

// Some implementation of class similar to `string_view' should be available in global namespace
// (CString class requires this)
using std::string_view;


// Class `CString' implements lightweight constant read-only string suitable
// for storing in arrays, for passing by value, etc...
//
// Main essential properties of `CString' class are following:
//
//    * it has extremelly small size (1 pointer);
//
//    * copying (and passing by value) is almost free of cost;
//
//    * multiple instances of CString can share internal representation;
//
//    * if CString created from string literal it doesn't require
//      neither memory allocation, nor data copying (so constant strings
//      are really weightless).
//
// Some negative properties:
//
//    * size of stored string limited to 65536 bytes;
//
//    * nul-symbol can't be stored inside string;
//
//    * program can crash in runtime when constructing CString from string literal,
//      if .rodata segment is larger than 8 MBytes (this is limit for 32-bit platform,
//      for 64-bit platform limit is hardly noticeable);
//
//    * computing string size, when string was created from string literal and size
//      is larger than 128 bytes, isn't performed in constant time: for each next
//      128 bytes small additional penalty added (so computing size of large string
//      created from string literals isn't free).
//
// This class can be modified, it represents only read-only strings, and can be
// created in one of the following ways:
//
//    1) from literal string: CString text("some text...");
//
//    2) from `string_view' and from const char* (implicitly, via string_view);
//
//    3) as result of calling static printf-like functions `printf' and `vprintf';
//
//    4) as result of concatenation of any string-like objects convertible to string_view,
//       via static concat(...) function;
//
//    5) as result of calling constructor with specifying desired string size and
//       initializer function, which then creates string contents.
//
// CString class supports following operations:
//
//    * strings can be reassigned (but not modified);
//
//    * conversion to C-string or string_view (CString always stores zero-terminated
//      representation of the string, nul-symbol can't be stored in the string);
//
//    * size of the string computed in constant time for most practical cases (see note above);
//
//    * characters can be accessed by index (implemented operator[]).
//
class CString
{
public:
    typedef unsigned short size_type;  // first major limit: string sizes

private:
    // This structure contains shared representation of the string, when string 
    // is stored in allocated memory.
    struct Shared
    {
        std::atomic<unsigned short> count;  // second major limit: the number of shared copies
        const size_type  size;              // size of the string (not including terminating zero)
        char             data[1];

        Shared(size_type size) : count{1}, size{size} {}
    };

    // This constant determines how many bits of variable `ptr' used for storing offset
    // from `Base' to string literal, and how many bits used for encoding string literal length.
    // Actually for string length ConstSizeBits-1 bits used (only lower bits of the length are
    // stored, upper bits restored in runtime).
    constexpr static const unsigned ConstSizeBits = 8;

    // Address of this variable used to compute offset in .rodata segment, for storing string literals.
    static const char Base[1];

    // this variable might contain one of the three variants:
    //     1) nullptr -- when CString contains empty string;
    //     2) pointer to struct Shared -- when CString holds string in allocated memory;
    //     3) offset between `Base' and string literal (offset in .rodata segment)
    //        combined with lowest 7 bits of string length.
    intptr_t ptr;

    // returns `true' if current instance of CString stores string literal.
    bool is_const() const noexcept        { return ptr & 1; }

    Shared *get_shared() const noexcept   { return reinterpret_cast<Shared*>(ptr); }

    // returns string literal address from offset stored in `ptr'
    const char* const_data() const noexcept
    {
        intptr_t offset = ptr >> ConstSizeBits;
        return reinterpret_cast<const char*>(offset + Base);
    }

    // function called in case, when offset can't be encoded in `ptr' (when offset is too large)
    __attribute__((noreturn, noinline))
    void runtime_error(const char *msg) const
    {
        throw std::runtime_error(msg);
    }

public:
    // create empty string (no memory allocation)
    CString() noexcept : ptr{0} {}

    // create string with specified size and initialize it by given functior (memory allocated)
    template <typename Initializer> CString(size_t size, Initializer init)
    {
        if (!size) new (this) CString;
        else {
            if (size > size_type(-1))
                runtime_error("CString overflow");

            Shared *shared = static_cast<Shared*>(operator new(size + sizeof(Shared)));
            new (shared) Shared(size_type(size));
            init(shared->data);
            shared->data[size] = 0;
            ptr = intptr_t(shared);
        }
    }

    // create string from string_view class (memory allocated and string copy created)
    explicit CString(string_view str)
    {
        new (this) CString(str.size(), [&str](char *data){ str.copy(data, str.size()); });
    }

    // Note: constructor like CString(const char *str) and operator= with same argument
    // not implemented intentionally -- string should be created or assigned via intermediate
    // string_view class. Existence of constructor or assigne operator with "const char *"
    // argument prevents implementation of constructor or assign operators wich works with
    // string literals (see below).

    // create constant string from string literal (i.e. CString const_string("text")...)
    // memory will not be allocated, instead size and pointer  will be saved (as offset from Base symbol)
    template <size_t Size>
    constexpr explicit CString(const char (&literal)[Size])
    {
        if (!Size) new (this) CString;
        else {         
            // compute offset from `Base'
            const intptr_t offset = literal - Base;
            const intptr_t MaxOffset = uintptr_t(-1) >> (ConstSizeBits + 1);
            const intptr_t MinOffset = uintptr_t(-1) << (sizeof(intptr_t)*8 - ConstSizeBits);
            if (offset > MaxOffset || offset < MinOffset)
                runtime_error("CString offset in too large");

            // compute low bits of size
            constexpr size_t size = Size - 1;  // don't count terminating zero
            constexpr uintptr_t short_size = size & ((1<<(ConstSizeBits - 1)) - 1);

            // combine result
            ptr = offset << ConstSizeBits | (short_size<<1) | 1;
        }
    }

    // create copy of the string (by increasing reference count)
    CString(const CString& other) noexcept : ptr{other.ptr}
    {
        if (ptr) {
            if (! is_const())
                get_shared()->count++;
        }
    }

    // move constructor just makes string empty
    CString(CString&& other) noexcept : ptr{other.ptr} { other.ptr = 0; }


    ~CString()
    {
        if (ptr && !is_const())
        {
            // free memory only in case if CString holds string in allocated memory
            Shared *shared = get_shared();
            if (--shared->count == 0)
                operator delete(shared);
        }
    }

    // These functions used to create CString as result of calling printf-like function...
    static CString vprintf(const char *fmt, va_list args);
    static CString printf(const char *fmt, ...);

    // Create CString as result of concatenation of given arguments
    // (all shold be convertible to string_view).
    template <typename... Args>
    static CString concat(Args&&... args)
    {
            string_view parts[] = { args... };
            size_t len = 0;
            for (const string_view& s : parts)
                len += s.size();

            return CString(len, [&parts](char *data){
                            for(const string_view& s : parts)
                                data += s.copy(data, s.size());
                        });
    }

    // Assign new value.
    CString& operator=(const CString& other)
    {
            this->~CString();
            return *new (this) CString(other);
    }

    // This function also handles case, when assigning "const char*" to CString,
    // see comment in CString(string_view) above.
    CString operator=(string_view str)
    {
        this->~CString();
        return *new (this) CString(str);
    }

    // Assign string literal.
    template <size_t Size> CString& operator=(const char (&literal)[Size])
    {
        this->~CString();
        return *new (this) CString(literal);
    }

    // Get zero-terminated C-string representation.
    const char *c_str() const noexcept
    {
        if (! ptr)  // empty string (returns pointer to nul-symbol)
        {
            return reinterpret_cast<const char*>(&ptr);
        }
        else if (! is_const())  // data in allocated memory
        {
            return get_shared()->data;
        }
        else {
            return const_data(); // return string literal
        }
    }

    // Return size of the stored string.
    size_t size() const noexcept
    {
        if (! ptr)  // empty string
        {
            return 0;
        }
        else if (! is_const())  // data in allocated memory
        {
            return get_shared()->size;
        }
        else {
            // decode `ptr' to lowest bits of string size and offset
            const uintptr_t short_size = (ptr & ((1<<ConstSizeBits) - 1)) >> 1;
            const char *start = const_data();
            // start searching end of string
            const char *end = &start[short_size];
            while (*end) end += 1<<(ConstSizeBits - 1);
            // compute length
            return end - start;
        }
    }

    // return `true' if CString is empty
    bool empty() const noexcept { return !ptr; }

    // access particular character by index
    const char& operator[](int i) const noexcept { return c_str()[i]; }

    // conversion to string_view
    operator string_view() const noexcept { return string_view(c_str(), size()); }
};

// these functions allow CString comparison with string_view or string literals
template <typename T> bool operator==(const CString& s, T other) { return static_cast<string_view>(s) == static_cast<string_view>(other); }
template <typename T> bool operator!=(const CString& s, T other) { return static_cast<string_view>(s) != static_cast<string_view>(other); }
template <typename T> bool operator<(const CString& s, T other)  { return static_cast<string_view>(s) < static_cast<string_view>(other); }
template <typename T> bool operator>(const CString& s, T other)  { return static_cast<string_view>(s) > static_cast<string_view>(other); }
template <typename T> bool operator<=(const CString& s, T other) { return static_cast<string_view>(s) <= static_cast<string_view>(other); }
template <typename T> bool operator>=(const CString& s, T other) { return static_cast<string_view>(s) >= static_cast<string_view>(other); }

template <typename T> bool operator==(T other, const CString& s) { return static_cast<string_view>(other) == static_cast<string_view>(s); }
template <typename T> bool operator!=(T other, const CString& s) { return static_cast<string_view>(other) != static_cast<string_view>(s); }
template <typename T> bool operator<(T other, const CString& s)  { return static_cast<string_view>(other) < static_cast<string_view>(s); }
template <typename T> bool operator>(T other, const CString& s)  { return static_cast<string_view>(other) > static_cast<string_view>(s); }
template <typename T> bool operator<=(T other, const CString& s) { return static_cast<string_view>(other) <= static_cast<string_view>(s); }
template <typename T> bool operator>=(T other, const CString& s) { return static_cast<string_view>(other) >= static_cast<string_view>(s); }

bool operator==(const CString& s, const CString& other) { return static_cast<string_view>(s) == static_cast<string_view>(other); }
bool operator!=(const CString& s, const CString& other) { return static_cast<string_view>(s) != static_cast<string_view>(other); }
bool operator<(const CString& s, const CString& other)  { return static_cast<string_view>(s) < static_cast<string_view>(other); }
bool operator>(const CString& s, const CString& other)  { return static_cast<string_view>(s) > static_cast<string_view>(other); }
bool operator<=(const CString& s, const CString& other) { return static_cast<string_view>(s) <= static_cast<string_view>(other); }
bool operator>=(const CString& s, const CString& other) { return static_cast<string_view>(s) >= static_cast<string_view>(other); }


////////////////////////////// CString.cpp file //////////////////////////////////////

#include <stdio.h>

const char CString::Base[1] = "";

CString CString::vprintf(const char *fmt, va_list args)
{
    int len = vsnprintf(NULL, 0, fmt, args);
    if (len <= 0) return CString(string_view());
    return CString(len, [&](char *data){ vsnprintf(data, len + 1, fmt, args); });
}

CString CString::printf(const char *fmt, ...)
{
    va_list args;
    va_start(args, fmt);
    CString result = CString::vprintf(fmt, args);
    va_end(args);
    return result;
}


/////////////////////// Usage examples ////////////////////////////////////////////////

int main()
{
    // create CString from literal
    CString lit("1234");

    // create CString by contatenating multiple strings
    string_view sv = "ccc";
    CString a = CString::concat("a", "bb", sv, lit);

    // create CString by using printf-function
    CString b = CString::printf("%d %s %d %s\n", int(lit.size()), lit.c_str(), a.size(), a.c_str());

    // comparing CStrings
    a == b;
    a < b;
    b >= a;
    a == "xxx";
    "yyy" != b;
    a == sv;
    sv != b;

    string_view(a).data();

    return 0;
}

\$\endgroup\$
  • 1
    \$\begingroup\$ What's wrong with simply using const std::string& or const std::string_view&, if you want to have read only characteristics? \$\endgroup\$ – πάντα ῥεῖ Aug 2 at 16:20
  • \$\begingroup\$ std::string_view not own the string itself, so I should manually control ownership in some way. Obvious problem, I can't create string and return string_view from function: because nobody owns resulting string. With passing/returning reference (to any object) same problem. Owning reference doesn't guarantee owning the data. Of course, I can use const std::string as "constant string". No problems with ownership, but in better case (short string or using std::move) compiler will copy 32 bytes (4-8 pointers) every time. In worst case new memory will be allocated and data copied. Not good. \$\endgroup\$ – fk0 Aug 2 at 17:06
  • 1
    \$\begingroup\$ If you pass a std::string const& you are affectively passing a read only version of the string. Also the assertion and it always copyes data is not strictly true. It has to have the same affect as if copying the data but the compiler is allowed to optimize that out which C++03 compilers did very effectively. Now with move semantics built into the language this becomes even more redundant. Can you provide a unit test (one we can tempatize with std::string const& and your CString that would show a significant difference). \$\endgroup\$ – Martin York Aug 2 at 20:16
  • \$\begingroup\$ If I understand correct, you are trying to mix const std::string& and std::string_view together, thus obfuscating the ownership. I guess I am missing something. \$\endgroup\$ – L. F. Aug 3 at 4:12
1
\$\begingroup\$

All assignment operators contain the same bug - not checking for self assignment. This bug will lead to undefined behavior, or a SEGFAULT.

\$\endgroup\$
  • 3
    \$\begingroup\$ Not checking for self-assignment is generally the right thing. Of course, self-assignment should still work (self-move-assignment may change the value, self-copy-assignment may be inefficient, but both must be safe). \$\endgroup\$ – Deduplicator Aug 16 at 18:20
  • \$\begingroup\$ Thanks, I also have found another bug: when CString constructed from array of (non-const) chars, the length of contained string computed incorrectly. For example, we can have same buffer char buffer[256] and some short string, which was constructed in this buffer. Currently CString class not distinguish between const and non-const arrays, and always assumes, that string length is same, as array size. This is right for const string literals, but for case with buffer this is wrong. \$\endgroup\$ – fk0 Sep 17 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.