5
\$\begingroup\$

I know, there are a few implementations of immutable strings out there, but my focus seems to be a little different.

My goal was to have a type that provided value semantics, but didn't incur the cost of dynamic memory allocation when constructed from a string literal which is already guaranteed to exist during the whole program runtime.

After refactoring, I ended up with two classes:

  • one str_ref class similar to string_view (maybe I can switch to gsl::string_span once I have a c++14 compiler) primarily used as a parameter for functions that don't intend to copy / take ownership of the string.
  • The actual const_string class which is derived from it but also stores the a dynamically allocated character array if necessary (via a shared pointer)

str_ref

#include <algorithm>
#include <iterator>
#include <string>
#include <ostream>

class str_ref {
public:
    //type defs
    using value_type = char;
    using traits_type = std::char_traits<value_type>;
    using size_type = size_t;
    using difference_type = std::ptrdiff_t;
    using reference = value_type&;
    using const_reference = const value_type&;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using iterator = pointer;
    using const_iterator = const_pointer;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

public:
    /* #### CTORS #### */
    constexpr str_ref() = default;

    str_ref(const std::string& other) noexcept:
    _start(other.data()),
        _size(other.size())
    {}

    constexpr str_ref(const char* other, size_t size) noexcept :
        _start(other),
        _size(size)
    {}

    //NOTE: Use only for string literals!!!
    template<size_t N>
    constexpr str_ref(const char(&other)[N]) noexcept :
    _start(other),
        _size(N - 1)
    {}

    template<class T>
    str_ref(const T * const& other) = delete;

    /* #### Special member functions #### */
    str_ref(const str_ref& other) = default;
    str_ref& operator=(const str_ref& other) = default;

    /* #### container functions #### */
    constexpr const_reference first()   const { return *begin(); }
    constexpr const_reference last()    const { return *(cend() - 1); }

    constexpr const_iterator cbegin()   const noexcept { return _start; }
    constexpr const_iterator cend()     const noexcept { return _start + _size; }
    constexpr const_iterator begin()    const noexcept { return cbegin(); }
    constexpr const_iterator end()      const noexcept { return cend(); }

    const_reverse_iterator crbegin()    const { return const_reverse_iterator(cend()); }
    const_reverse_iterator crend()      const { return const_reverse_iterator(cbegin()); }
    const_reverse_iterator rbegin()     const { return const_reverse_iterator(cend()); }
    const_reverse_iterator rend()       const { return const_reverse_iterator(cbegin()); }

    constexpr size_type size()          const noexcept { return _size; }
    constexpr bool empty()              const noexcept { return size() == 0; }

    constexpr const_reference operator[](size_t idx) const {
        return _start[idx];
    }


    /*#### string functions ####*/
    std::string to_string() {
        return std::string(begin(), end());
    }

    constexpr str_ref sub_string(size_t offset, size_t count) const {
        return str_ref{ this->_start + offset, count };
    }

    int compare(const str_ref& other) const {
        if ((begin() == other.begin()) && (size() == other.size())) {
            return 0;
        }
        return std::lexicographical_compare(cbegin(), cend(), other.cbegin(), other.cend());
    }

protected:
    const char* _start = nullptr;
    size_type _size = 0;
};

/* operator overloads */
bool operator==(const str_ref& l, const str_ref& r) { return l.compare(r) == 0; }
bool operator!=(const str_ref& l, const str_ref& r) { return !(l == r); }
bool operator< (const str_ref& l, const str_ref& r) { return l.compare(r) < 0; }
bool operator> (const str_ref& l, const str_ref& r) { return r<l; }
bool operator<=(const str_ref& l, const str_ref& r) { return !(l>r); }
bool operator>=(const str_ref& l, const str_ref& r) { return !(l<r); }

std::ostream& operator<<(std::ostream& out, const str_ref& string) {
    out.write(&*(string.begin()), string.size());       
    return out;
}

const_string

#include <memory>
#include "StrRef.h"

class const_string;

namespace _impl_helper {
    template<class ...ARGS>
    const_string concat_impl(const ARGS&...args);
}

class const_string : public str_ref {
public:
    /* #### CTORS #### */
    const_string() = default;

             const_string(const char* other, size_t size)   { _copyFrom(other,          size        ); }
    explicit const_string(const std::string& other)         { _copyFrom(other.c_str(),  other.size()); }
    explicit const_string(const str_ref& other)             { _copyFrom(other.cbegin(), other.size()); }

    // don't accept c-strings
    template<class T>
    const_string(const T * const& other) = delete;

    //NOTE: Use only for string literals (arrays with static storage duration)!!!
    template<size_t N>
    explicit constexpr const_string(const char(&other)[N]) noexcept :
        str_ref(other, N - 1)
    {}

    /* #### Special member functions #### */
    const_string(const const_string& other) = default;
    const_string(const_string&& other) = default;
    const_string& operator=(const const_string& other) = default;
    const_string& operator=(const_string&& other) = default;

    /* #### String functions  #### */
    const_string sub_string(size_t offset, size_t count) const {
        const_string retval;
        retval._start = this->_start + offset;
        retval._size = count;
        retval._data = this->_data;
        return retval;
    }

    template<class ...ARGS>
    friend const_string _impl_helper::concat_impl(const ARGS&...args);

private:
    std::shared_ptr<char> _data = nullptr;

    void _copyFrom(const char* other, size_t size) {
        _data = std::shared_ptr<char>(new char[size], std::default_delete<char[]>());
        std::copy_n(other, size, _data.get());
        _size = size;
        _start = _data.get();
    }
};


namespace _impl_helper {
    void addTo(char*& buffer, const str_ref& str) {
        std::copy_n(str.begin(), str.size(), buffer);
        buffer += str.size();       
    }

    template<class ...ARGS>
    const_string concat_impl(const ARGS& ...args) {
        //determine total size
        size_t newSize = 0;
        int ignore[] = { (newSize += args.size(),0)... };

        //create chonst_string object
        const_string retval;
        retval._data = std::shared_ptr<char>(new char[newSize], std::default_delete<char[]>());
        retval._start = retval._data.get();
        retval._size = newSize;

        //place copy arguments to buffer
        char * bufferStart = retval._data.get();
        int ignore2[] = { (addTo(bufferStart,args),0)... };
        return retval;
    }
}

template<class ...ARGS>
const_string concat(ARGS&&...args) {
    return _impl_helper::concat_impl(str_ref(args)...);
}

Aside from general advice of how to improve my class (I bet, there is a lot), I'd especially like to know if

  • The creation of a new string can be made cheaper (currently it incurs two dynamic memory allocations - one for the string and one for the shared_ptr control block)
  • You see a way to implement concat, that doesn't require the forward declaration of the _impl_helper namespace (I'd like to keep it stashed away at the end of the file, not in front of the actual class)
  • You think that it is a problem, that the internal representation of the string is not zero-terminated. In my current project, there are very few 3rd party functions that require zero terminated strings (and I try to avoid them myself where ever possible - hence this class), but what is your experience?

I also made the deliberate design choice, to not provide a virtual destructor due to the overhead it would incur and the fact that I don't see any use case, where I would want to destruct const_string via a pointer to str_ref. Still this goes against best practices and might be suprising for other people using that code - would you accept such a code in your codebase?

I haven't finished documentation and the unit tests yet (I hope the code is readable enough), but here is some sample code to play around with:

#include <iostream>

#include "const_string.h"

using namespace std;

namespace {
void print_str_ref(str_ref s) {
    std::cout << s << std::endl;
}
}

int main() {
    //constexpr const char* tmp{ "Hello World" };
    //const const_string ccs(tmp); //<-should produce compiler error

    const_string cs0;
    const_string cs1("Hello World");
    const_string cs2("Hello World"s);
    const char* t = "Hello World";
    const_string cs3(t, std::strlen(t));
    const_string cs4(cs1);
    const_string cs5("tmp");
    cs5 = cs1;
    const_string cs6;
    cs6 = cs2;

    const_string cs71("Hello 12"s);
    const_string cs72("World"s);
    const_string cs7(concat(cs71.sub_string(0, 6), cs72));

    std::string cppStr(cs7.to_string());

    std::cout << cs1 << ":" << (cs1 == cs1) << std::endl;
    std::cout << cs2 << ":" << (cs1 == cs2) << std::endl;
    std::cout << cs3 << ":" << (cs1 == cs3) << std::endl;
    std::cout << cs4 << ":" << (cs1 == cs4) << std::endl;
    std::cout << cs5 << ":" << (cs1 == cs5) << std::endl;
    std::cout << cs6 << ":" << (cs1 == cs6) << std::endl << std::endl;

    std::cout << cppStr << ":" << (cppStr == "Hello World"s) << std::endl << std::endl;

    print_str_ref("Hello World");
    print_str_ref("Hello World"s);
    print_str_ref(cs1);
    print_str_ref({ t,std::strlen(t) });

    std::cout << std::endl;
    const str_ref tstr("ld");
    print_str_ref(concat("Hel", "lo"s, const_string(" W"), str_ref("or"), tstr));

}

/*#### static / Constexpr stuff ####*/
constexpr str_ref str("Hello");
constexpr auto it = str.begin() + 4;
static_assert(*it == 'o', "");

template<class T>
struct CheckNothrowDefaults {
    static_assert(std::is_nothrow_copy_assignable<T>::value, "");
    static_assert(std::is_nothrow_move_assignable<T>::value, "");

    static_assert(std::is_nothrow_copy_constructible<T>::value, "");
    static_assert(std::is_nothrow_move_constructible<T>::value, "");
};

CheckNothrowDefaults<str_ref> _1{};
CheckNothrowDefaults<const_string> _2{};

Note: So far I can't use c++14 features, as the compiler for my embedded system is based on gcc4.8

\$\endgroup\$
  • 1
    \$\begingroup\$ Owww. Fancy. Mentioning gsl::<anything>. +1 just for being up on the latest C++ stuff. github.com/Microsoft/GSL \$\endgroup\$ – Martin York Jan 6 '16 at 16:52
1
\$\begingroup\$

The creation of a new string can be made cheaper (currently it incurs two dynamic memory allocations - one for the string and one for the shared_ptr control block)

Is there a reason that your control block is a shared_ptr? It doesn't look like you're going to be sharing that data with any other object since it seems like each instance of the class will own its own copy of a string literal. (Remember, shared_ptr and unique_ptr are for describing ownership). I would switch to a unique_ptr since unique_ptr has far less overhead and is more lightweight than a shared_ptr. Also, by switching to a unique_ptr, you make your ownership semantics clear to the code reviewer; when I read your code and saw "shared_ptr", I assumed you'd be sharing data when you weren't. You could then switch to a more concise initialization function for it:

_data = std::make_unique<char[]>(new char[size]);

You see a way to implement concat, that doesn't require the forward declaration of the _impl_helper namespace (I'd like to keep it stashed away at the end of the file, not in front of the actual class).

Yes, it seems that namespace is pretty unnecessary as you could just implement those functions as private member functions of the const_string class. This also achieves the goal of keeping them at the end of the file as you have your private declarations at the end of the file. ;)

You think that it is a problem, that the internal representation of the string is not zero-terminated. In my current project, there are very few 3rd party functions that require zero terminated strings (and I try to avoid them myself where ever possible - hence this class), but what is your experience?

It shouldn't be a problem as long as you don't pass your string's internal data representation to an API that works with or expects NULL-terminated strings. If the only thing operating on your data is the class itself, you should be fine. Remember, NULL-terminated strings are an implementation detail that should only be exposed if necessary. It doesn't look like that's necessary here.

Also, a few general remarks:

constexpr const_iterator begin()    const noexcept { return cbegin(); }
constexpr const_iterator end()      const noexcept { return cend(); }

 const_reverse_iterator rbegin()     const { return const_reverse_iterator(cend()); }
    const_reverse_iterator rend()       const { return const_reverse_iterator(cbegin()); }

I don't see a need for these to exist; they are identical to their cbegin and cend variations and they also communicate the wrong thing to the user - that they point to mutable data (which they don't). Since you're creating an immutable string class, keep your interface const-only.

/* #### CTORS #### */
    constexpr str_ref() = default;
 /* #### Special member functions #### */
    str_ref(const str_ref& other) = default;
    str_ref& operator=(const str_ref& other) = default;

No need to define these as the compiler essentially does this for you for "free". This just clutters the code.

\$\endgroup\$
  • \$\begingroup\$ "It doesn't look like you're going to be sharing that data with any other object" Actually, any copy of a const_string will reference the same storage. Thanks for the other tipps though \$\endgroup\$ – MikeMB Jan 6 '16 at 16:16
  • \$\begingroup\$ The whole point of std::make_unique<>() is that you don't explicitly call new. \$\endgroup\$ – Martin York Jan 6 '16 at 16:55
  • \$\begingroup\$ The point of the cbegin(), begin(), rbegin() etc is that they are part of the interface for a container. See 23 Containers library [containers] of n4567 \$\endgroup\$ – Martin York Jan 6 '16 at 17:00
  • \$\begingroup\$ @LokiAstari: Actually, I'm not sure if providing only the const version of begin() and end() helps much. According to the table in the linked document, there also should be a non-const version that returns an instance of iterator (as opposed to const_iterator). But basically, I was just sticking to what std::experimental::string_view provided. \$\endgroup\$ – MikeMB Jan 6 '16 at 19:22
  • \$\begingroup\$ @LokiAstari: comming back to this, I think the main reason to implement begin() and end() is for compatibility with range based for loops \$\endgroup\$ – MikeMB Jan 6 '16 at 22:28

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.