In C++, currently we have few possibilities to work with strings:
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...
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;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 likestd::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;
}
const std::string&
orconst std::string_view&
, if you want to have read only characteristics? \$\endgroup\$std::string const&
you are affectively passing a read only version of the string. Also the assertionand 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 yourCString
that would show a significant difference). \$\endgroup\$const std::string&
andstd::string_view
together, thus obfuscating the ownership. I guess I am missing something. \$\endgroup\$