basic_string.hpp

Go to the documentation of this file.

/*
 * Copyright 2019-2020, Intel Corporation
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in
 *       the documentation and/or other materials provided with the
 *       distribution.
 *
 *     * Neither the name of the copyright holder nor the names of its
 *       contributors may be used to endorse or promote products derived
 *       from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
#ifndef LIBPMEMOBJ_CPP_BASIC_STRING_HPP
#define LIBPMEMOBJ_CPP_BASIC_STRING_HPP
 
#include <algorithm>
#include <iterator>
#include <limits>
#include <string>
 
#include <libpmemobj++/container/array.hpp>
#include <libpmemobj++/container/detail/contiguous_iterator.hpp>
#include <libpmemobj++/container/vector.hpp>
#include <libpmemobj++/detail/common.hpp>
#include <libpmemobj++/detail/iterator_traits.hpp>
#include <libpmemobj++/detail/life.hpp>
#include <libpmemobj++/persistent_ptr.hpp>
#include <libpmemobj++/pext.hpp>
#include <libpmemobj++/slice.hpp>
#include <libpmemobj++/transaction.hpp>
 
namespace pmem
{
 
namespace obj
{
 
template <typename CharT, typename Traits = std::char_traits<CharT>>
class basic_string {
public:
    /* Member types */
    using traits_type = Traits;
    using value_type = CharT;
    using size_type = std::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 = pmem::detail::basic_contiguous_iterator<CharT>;
    using const_iterator = const_pointer;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
    using for_each_ptr_function =
        std::function<void(persistent_ptr_base &)>;
 
    /* Number of characters which can be stored using sso */
    static constexpr size_type sso_capacity = (32 - 8) / sizeof(CharT) - 1;
 
    /* Constructors */
    basic_string();
    basic_string(size_type count, CharT ch);
    basic_string(const basic_string &other, size_type pos,
             size_type count = npos);
    basic_string(const std::basic_string<CharT> &other, size_type pos,
             size_type count = npos);
    basic_string(const CharT *s, size_type count);
    basic_string(const CharT *s);
    template <
        typename InputIt,
        typename Enable = typename std::enable_if<
            pmem::detail::is_input_iterator<InputIt>::value>::type>
    basic_string(InputIt first, InputIt last);
    basic_string(const basic_string &other);
    basic_string(const std::basic_string<CharT> &other);
    basic_string(basic_string &&other);
    basic_string(std::initializer_list<CharT> ilist);
 
    /* Destructor */
    ~basic_string();
 
    /* Assignment operators */
    basic_string &operator=(const basic_string &other);
    basic_string &operator=(const std::basic_string<CharT> &other);
    basic_string &operator=(basic_string &&other);
    basic_string &operator=(const CharT *s);
    basic_string &operator=(CharT ch);
    basic_string &operator=(std::initializer_list<CharT> ilist);
 
    /* Assignment methods */
    basic_string &assign(size_type count, CharT ch);
    basic_string &assign(const basic_string &other);
    basic_string &assign(const std::basic_string<CharT> &other);
    basic_string &assign(const basic_string &other, size_type pos,
                 size_type count = npos);
    basic_string &assign(const std::basic_string<CharT> &other,
                 size_type pos, size_type count = npos);
    basic_string &assign(const CharT *s, size_type count);
    basic_string &assign(const CharT *s);
    template <typename InputIt,
          typename Enable = typename pmem::detail::is_input_iterator<
              InputIt>::type>
    basic_string &assign(InputIt first, InputIt last);
    basic_string &assign(basic_string &&other);
    basic_string &assign(std::initializer_list<CharT> ilist);
 
    /* Element access */
    reference at(size_type n);
    const_reference at(size_type n) const;
    const_reference const_at(size_type n) const;
    reference operator[](size_type n);
    const_reference operator[](size_type n) const;
    CharT &front();
    const CharT &front() const;
    const CharT &cfront() const;
    CharT &back();
    const CharT &back() const;
    const CharT &cback() const;
    CharT *data();
    const CharT *data() const noexcept;
    const CharT *cdata() const noexcept;
    const CharT *c_str() const noexcept;
    void for_each_ptr(for_each_ptr_function func);
 
    /* Iterators */
    iterator begin();
    const_iterator begin() const noexcept;
    const_iterator cbegin() const noexcept;
    iterator end();
    const_iterator end() const noexcept;
    const_iterator cend() const noexcept;
    reverse_iterator rbegin();
    const_reverse_iterator rbegin() const noexcept;
    const_reverse_iterator crbegin() const noexcept;
    reverse_iterator rend();
    const_reverse_iterator rend() const noexcept;
    const_reverse_iterator crend() const noexcept;
 
    /* Capacity */
    bool empty() const noexcept;
    size_type size() const noexcept;
    size_type length() const noexcept;
    size_type max_size() const noexcept;
    size_type capacity() const noexcept;
    void resize(size_type count, CharT ch);
    void resize(size_type n);
    void reserve(size_type new_cap = 0);
    void shrink_to_fit();
    void clear();
 
    /* Modifiers */
    basic_string &erase(size_type index = 0, size_type count = npos);
    iterator erase(const_iterator pos);
    iterator erase(const_iterator first, const_iterator last);
    /* We add following overloads to resolve erase(0) ambiguity */
    template <typename T,
          typename Enable = typename std::enable_if<
              std::is_convertible<T, size_type>::value>::type>
    basic_string &erase(T param);
    template <typename T,
          typename Enable = typename std::enable_if<
              !std::is_convertible<T, size_type>::value>::type>
    iterator erase(T param);
    void pop_back();
 
    basic_string &append(size_type count, CharT ch);
    basic_string &append(const basic_string &str);
    basic_string &append(const basic_string &str, size_type pos,
                 size_type count = npos);
    basic_string &append(const CharT *s, size_type count);
    basic_string &append(const CharT *s);
    template <typename InputIt,
          typename Enable = typename pmem::detail::is_input_iterator<
              InputIt>::type>
    basic_string &append(InputIt first, InputIt last);
    basic_string &append(std::initializer_list<CharT> ilist);
    void push_back(CharT ch);
    basic_string &operator+=(const basic_string &str);
    basic_string &operator+=(const CharT *s);
    basic_string &operator+=(CharT c);
    basic_string &operator+=(std::initializer_list<CharT> ilist);
 
    basic_string &insert(size_type index, size_type count, CharT ch);
    basic_string &insert(size_type index, const CharT *s);
    basic_string &insert(size_type index, const CharT *s, size_type count);
    basic_string &insert(size_type index, const basic_string &str);
    basic_string &insert(size_type index1, const basic_string &str,
                 size_type index2, size_type count = npos);
    iterator insert(const_iterator pos, CharT ch);
    iterator insert(const_iterator pos, size_type count, CharT ch);
    template <typename InputIt,
          typename Enable = typename pmem::detail::is_input_iterator<
              InputIt>::type>
    iterator insert(const_iterator pos, InputIt first, InputIt last);
    iterator insert(const_iterator pos, std::initializer_list<CharT> ilist);
    template <typename T,
          typename Enable = typename std::enable_if<
              std::is_convertible<T, size_type>::value>::type>
    basic_string &insert(T param, size_type count, CharT ch);
    template <typename T,
          typename Enable = typename std::enable_if<
              !std::is_convertible<T, size_type>::value>::type>
    iterator insert(T param, size_type count, CharT ch);
 
    basic_string &replace(size_type index, size_type count,
                  const basic_string &str);
    basic_string &replace(const_iterator first, const_iterator last,
                  const basic_string &str);
    basic_string &replace(size_type index, size_type count,
                  const basic_string &str, size_type index2,
                  size_type count2 = npos);
    template <typename InputIt,
          typename Enable = typename pmem::detail::is_input_iterator<
              InputIt>::type>
    basic_string &replace(const_iterator first, const_iterator last,
                  InputIt first2, InputIt last2);
    basic_string &replace(const_iterator first, const_iterator last,
                  const CharT *s, size_type count2);
    basic_string &replace(const_iterator first, const_iterator last,
                  const CharT *s);
    basic_string &replace(size_type index, size_type count,
                  size_type count2, CharT ch);
    basic_string &replace(const_iterator first, const_iterator last,
                  size_type count2, CharT ch);
    basic_string &replace(size_type index, size_type count, const CharT *s,
                  size_type count2);
    basic_string &replace(size_type index, size_type count, const CharT *s);
    basic_string &replace(const_iterator first, const_iterator last,
                  std::initializer_list<CharT> ilist);
 
    size_type copy(CharT *s, size_type count, size_type index = 0) const;
 
    int compare(const basic_string &other) const;
    int compare(const std::basic_string<CharT> &other) const;
    int compare(size_type pos, size_type count,
            const basic_string &other) const;
    int compare(size_type pos, size_type count,
            const std::basic_string<CharT> &other) const;
    int compare(size_type pos1, size_type count1, const basic_string &other,
            size_type pos2, size_type count2 = npos) const;
    int compare(size_type pos1, size_type count1,
            const std::basic_string<CharT> &other, size_type pos2,
            size_type count2 = npos) const;
    int compare(const CharT *s) const;
    int compare(size_type pos, size_type count, const CharT *s) const;
    int compare(size_type pos, size_type count1, const CharT *s,
            size_type count2) const;
 
    /* Search */
    size_type find(const basic_string &str, size_type pos = 0) const
        noexcept;
    size_type find(const CharT *s, size_type pos, size_type count) const;
    size_type find(const CharT *s, size_type pos = 0) const;
    size_type find(CharT ch, size_type pos = 0) const noexcept;
    size_type rfind(const basic_string &str, size_type pos = npos) const
        noexcept;
    size_type rfind(const CharT *s, size_type pos, size_type count) const;
    size_type rfind(const CharT *s, size_type pos = npos) const;
    size_type rfind(CharT ch, size_type pos = npos) const noexcept;
    size_type find_first_of(const basic_string &str,
                size_type pos = 0) const noexcept;
    size_type find_first_of(const CharT *s, size_type pos,
                size_type count) const;
    size_type find_first_of(const CharT *s, size_type pos = 0) const;
    size_type find_first_of(CharT ch, size_type pos = 0) const noexcept;
    size_type find_first_not_of(const basic_string &str,
                    size_type pos = 0) const noexcept;
    size_type find_first_not_of(const CharT *s, size_type pos,
                    size_type count) const;
    size_type find_first_not_of(const CharT *s, size_type pos = 0) const;
    size_type find_first_not_of(CharT ch, size_type pos = 0) const noexcept;
    size_type find_last_of(const basic_string &str,
                   size_type pos = npos) const noexcept;
    size_type find_last_of(const CharT *s, size_type pos,
                   size_type count) const;
    size_type find_last_of(const CharT *s, size_type pos = npos) const;
    size_type find_last_of(CharT ch, size_type pos = npos) const noexcept;
    size_type find_last_not_of(const basic_string &str,
                   size_type pos = npos) const noexcept;
    size_type find_last_not_of(const CharT *s, size_type pos,
                   size_type count) const;
    size_type find_last_not_of(const CharT *s, size_type pos = npos) const;
    size_type find_last_not_of(CharT ch, size_type pos = npos) const
        noexcept;
 
    /* Special value. The exact meaning depends on the context. */
    static const size_type npos = static_cast<size_type>(-1);
 
private:
    using sso_type = array<value_type, sso_capacity + 1>;
    using non_sso_type = vector<value_type>;
 
    union {
        struct {
            /*
             * EXACTLY the same type as first member in vector
             * Holds size for sso string, bit specified by _sso_mask
             * indicates if sso is used.
             */
            p<size_type> _size;
 
            sso_type _data;
        } sso;
 
        struct {
            non_sso_type _data;
        } non_sso;
    };
 
    /*
     * MSB is used because vector is known not to use entire range of
     * size_type.
     */
    static constexpr size_type _sso_mask = 1ULL
        << (std::numeric_limits<size_type>::digits - 1);
 
    /* helper functions */
    bool is_sso_used() const;
    void destroy_data();
    template <
        typename InputIt,
        typename Enable = typename std::enable_if<
            pmem::detail::is_input_iterator<InputIt>::value>::type>
    size_type get_size(InputIt first, InputIt last) const;
    size_type get_size(size_type count, value_type ch) const;
    size_type get_size(const basic_string &other) const;
    template <typename... Args>
    pointer replace_content(Args &&... args);
    template <typename... Args>
    pointer initialize(Args &&... args);
    void allocate(size_type capacity);
    template <
        typename InputIt,
        typename Enable = typename std::enable_if<
            pmem::detail::is_input_iterator<InputIt>::value>::type>
    pointer assign_sso_data(InputIt first, InputIt last);
    pointer assign_sso_data(size_type count, value_type ch);
    pointer assign_sso_data(basic_string &&other);
    template <
        typename InputIt,
        typename Enable = typename std::enable_if<
            pmem::detail::is_input_iterator<InputIt>::value>::type>
    pointer assign_large_data(InputIt first, InputIt last);
    pointer assign_large_data(size_type count, value_type ch);
    pointer assign_large_data(basic_string &&other);
    pool_base get_pool() const;
    void check_pmem() const;
    void check_tx_stage_work() const;
    void check_pmem_tx() const;
    void add_sso_to_tx(size_type first, size_type num) const;
    size_type get_sso_size() const;
    void enable_sso();
    void disable_sso();
    void set_sso_size(size_type new_size);
    void sso_to_large(size_t new_capacity);
    void large_to_sso();
    typename basic_string<CharT, Traits>::non_sso_type &non_sso_data();
    typename basic_string<CharT, Traits>::sso_type &sso_data();
    const typename basic_string<CharT, Traits>::non_sso_type &
    non_sso_data() const;
    const typename basic_string<CharT, Traits>::sso_type &sso_data() const;
};
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string()
{
    check_pmem_tx();
    sso._size = 0;
 
    allocate(0);
    initialize(0U, value_type('\0'));
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(size_type count, CharT ch)
{
    check_pmem_tx();
    sso._size = 0;
 
    allocate(count);
    initialize(count, ch);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(const basic_string &other,
                      size_type pos, size_type count)
{
    check_pmem_tx();
    sso._size = 0;
 
    if (pos > other.size())
        throw std::out_of_range("Index out of range.");
 
    if (count == npos || pos + count > other.size())
        count = other.size() - pos;
 
    auto first = static_cast<difference_type>(pos);
    auto last = first + static_cast<difference_type>(count);
 
    allocate(count);
    initialize(other.cbegin() + first, other.cbegin() + last);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(const std::basic_string<CharT> &other,
                      size_type pos, size_type count)
{
    check_pmem_tx();
    sso._size = 0;
 
    if (pos > other.size())
        throw std::out_of_range("Index out of range.");
 
    if (count == npos || pos + count > other.size())
        count = other.size() - pos;
 
    auto first = static_cast<difference_type>(pos);
    auto last = first + static_cast<difference_type>(count);
 
    allocate(count);
    initialize(other.cbegin() + first, other.cbegin() + last);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(const CharT *s, size_type count)
{
    check_pmem_tx();
    sso._size = 0;
 
    allocate(count);
    initialize(s, s + count);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(const CharT *s)
{
    check_pmem_tx();
    sso._size = 0;
 
    auto length = traits_type::length(s);
 
    allocate(length);
    initialize(s, s + length);
}
 
template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
basic_string<CharT, Traits>::basic_string(InputIt first, InputIt last)
{
    auto len = std::distance(first, last);
    assert(len >= 0);
 
    check_pmem_tx();
    sso._size = 0;
 
    allocate(static_cast<size_type>(len));
    initialize(first, last);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(const basic_string &other)
{
    check_pmem_tx();
    sso._size = 0;
 
    allocate(other.size());
    initialize(other.cbegin(), other.cend());
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(const std::basic_string<CharT> &other)
    : basic_string(other.cbegin(), other.cend())
{
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(basic_string &&other)
{
    check_pmem_tx();
    sso._size = 0;
 
    allocate(other.size());
    initialize(std::move(other));
 
    if (other.is_sso_used())
        other.initialize(0U, value_type('\0'));
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(std::initializer_list<CharT> ilist)
{
    check_pmem_tx();
    sso._size = 0;
 
    allocate(ilist.size());
    initialize(ilist.begin(), ilist.end());
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits>::~basic_string()
{
    if (!is_sso_used())
        detail::destroy<non_sso_type>(non_sso_data());
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator=(const basic_string &other)
{
    return assign(other);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator=(const std::basic_string<CharT> &other)
{
    return assign(other);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator=(basic_string &&other)
{
    return assign(std::move(other));
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator=(const CharT *s)
{
    return assign(s);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator=(CharT ch)
{
    return assign(1, ch);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator=(std::initializer_list<CharT> ilist)
{
    return assign(ilist);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(size_type count, CharT ch)
{
    auto pop = get_pool();
 
    transaction::run(pop, [&] { replace_content(count, ch); });
 
    return *this;
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(const basic_string &other)
{
    if (&other == this)
        return *this;
 
    auto pop = get_pool();
 
    transaction::run(
        pop, [&] { replace_content(other.cbegin(), other.cend()); });
 
    return *this;
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(const std::basic_string<CharT> &other)
{
    return assign(other.cbegin(), other.cend());
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(const basic_string &other, size_type pos,
                    size_type count)
{
    if (pos > other.size())
        throw std::out_of_range("Index out of range.");
 
    if (count == npos || pos + count > other.size())
        count = other.size() - pos;
 
    auto pop = get_pool();
    auto first = static_cast<difference_type>(pos);
    auto last = first + static_cast<difference_type>(count);
 
    transaction::run(pop, [&] {
        replace_content(other.cbegin() + first, other.cbegin() + last);
    });
 
    return *this;
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(const std::basic_string<CharT> &other,
                    size_type pos, size_type count)
{
    if (pos > other.size())
        throw std::out_of_range("Index out of range.");
 
    if (count == npos || pos + count > other.size())
        count = other.size() - pos;
 
    return assign(other.c_str() + pos, count);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(const CharT *s, size_type count)
{
    auto pop = get_pool();
 
    transaction::run(pop, [&] { replace_content(s, s + count); });
 
    return *this;
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(const CharT *s)
{
    auto pop = get_pool();
 
    auto length = traits_type::length(s);
 
    transaction::run(pop, [&] { replace_content(s, s + length); });
 
    return *this;
}
 
template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(InputIt first, InputIt last)
{
    auto pop = get_pool();
 
    transaction::run(pop, [&] { replace_content(first, last); });
 
    return *this;
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(basic_string &&other)
{
    if (&other == this)
        return *this;
 
    auto pop = get_pool();
 
    transaction::run(pop, [&] {
        replace_content(std::move(other));
 
        if (other.is_sso_used())
            other.initialize(0U, value_type('\0'));
    });
 
    return *this;
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(std::initializer_list<CharT> ilist)
{
    return assign(ilist.begin(), ilist.end());
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::for_each_ptr(for_each_ptr_function func)
{
    if (!is_sso_used()) {
        non_sso._data.for_each_ptr(func);
    }
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::begin()
{
    return is_sso_used() ? iterator(&*sso_data().begin())
                 : iterator(&*non_sso_data().begin());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_iterator
basic_string<CharT, Traits>::begin() const noexcept
{
    return cbegin();
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_iterator
basic_string<CharT, Traits>::cbegin() const noexcept
{
    return is_sso_used() ? const_iterator(&*sso_data().cbegin())
                 : const_iterator(&*non_sso_data().cbegin());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::end()
{
    return begin() + static_cast<difference_type>(size());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_iterator
basic_string<CharT, Traits>::end() const noexcept
{
    return cbegin() + static_cast<difference_type>(size());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_iterator
basic_string<CharT, Traits>::cend() const noexcept
{
    return cbegin() + static_cast<difference_type>(size());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::reverse_iterator
basic_string<CharT, Traits>::rbegin()
{
    return reverse_iterator(end());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_reverse_iterator
basic_string<CharT, Traits>::rbegin() const noexcept
{
    return crbegin();
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_reverse_iterator
basic_string<CharT, Traits>::crbegin() const noexcept
{
    return const_reverse_iterator(cend());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::reverse_iterator
basic_string<CharT, Traits>::rend()
{
    return reverse_iterator(begin());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_reverse_iterator
basic_string<CharT, Traits>::rend() const noexcept
{
    return crend();
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_reverse_iterator
basic_string<CharT, Traits>::crend() const noexcept
{
    return const_reverse_iterator(cbegin());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::reference
basic_string<CharT, Traits>::at(size_type n)
{
    if (n >= size())
        throw std::out_of_range("string::at");
 
    return is_sso_used() ? sso_data()[n] : non_sso_data()[n];
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_reference
basic_string<CharT, Traits>::at(size_type n) const
{
    return const_at(n);
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_reference
basic_string<CharT, Traits>::const_at(size_type n) const
{
    if (n >= size())
        throw std::out_of_range("string::const_at");
 
    return is_sso_used()
        ? static_cast<const sso_type &>(sso_data())[n]
        : static_cast<const non_sso_type &>(non_sso_data())[n];
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::reference
    basic_string<CharT, Traits>::operator[](size_type n)
{
    return is_sso_used() ? sso_data()[n] : non_sso_data()[n];
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_reference
    basic_string<CharT, Traits>::operator[](size_type n) const
{
    return is_sso_used() ? sso_data()[n] : non_sso_data()[n];
}
 
template <typename CharT, typename Traits>
CharT &
basic_string<CharT, Traits>::front()
{
    return (*this)[0];
}
 
template <typename CharT, typename Traits>
const CharT &
basic_string<CharT, Traits>::front() const
{
    return cfront();
}
 
template <typename CharT, typename Traits>
const CharT &
basic_string<CharT, Traits>::cfront() const
{
    return static_cast<const basic_string &>(*this)[0];
}
 
template <typename CharT, typename Traits>
CharT &
basic_string<CharT, Traits>::back()
{
    return (*this)[size() - 1];
}
 
template <typename CharT, typename Traits>
const CharT &
basic_string<CharT, Traits>::back() const
{
    return cback();
}
 
template <typename CharT, typename Traits>
const CharT &
basic_string<CharT, Traits>::cback() const
{
    return static_cast<const basic_string &>(*this)[size() - 1];
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::size() const noexcept
{
    if (is_sso_used())
        return get_sso_size();
    else if (non_sso_data().size() == 0)
        return 0;
    else
        return non_sso_data().size() - 1;
}
 
template <typename CharT, typename Traits>
CharT *
basic_string<CharT, Traits>::data()
{
    return is_sso_used() ? sso_data().range(0, get_sso_size() + 1).begin()
                 : non_sso_data().data();
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::erase(size_type index, size_type count)
{
    auto sz = size();
 
    if (index > sz)
        throw std::out_of_range("Index exceeds size.");
 
    count = (std::min)(count, sz - index);
 
    auto pop = get_pool();
 
    auto first = begin() + static_cast<difference_type>(index);
    auto last = first + static_cast<difference_type>(count);
 
    if (is_sso_used()) {
        transaction::run(pop, [&] {
            auto move_len = sz - index - count;
            auto new_size = sz - count;
 
            auto range = sso_data().range(index, move_len + 1);
 
            traits_type::move(range.begin(), &*last, move_len);
 
            set_sso_size(new_size);
 
            assert(range.end() - 1 ==
                   &sso_data()._data[index + move_len]);
            *(range.end() - 1) = value_type('\0');
        });
    } else {
        non_sso_data().erase(first, last);
    }
 
    return *this;
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::erase(const_iterator pos)
{
    return erase(pos, pos + 1);
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::erase(const_iterator first, const_iterator last)
{
    size_type index =
        static_cast<size_type>(std::distance(cbegin(), first));
    size_type len = static_cast<size_type>(std::distance(first, last));
 
    erase(index, len);
 
    return begin() + static_cast<difference_type>(index);
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::pop_back()
{
    erase(size() - 1, 1);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::append(size_type count, CharT ch)
{
    auto sz = size();
    auto new_size = sz + count;
 
    if (new_size > max_size())
        throw std::length_error("Size exceeds max size.");
 
    if (is_sso_used()) {
        auto pop = get_pool();
 
        transaction::run(pop, [&] {
            if (new_size > sso_capacity) {
                sso_to_large(new_size);
 
                non_sso_data().insert(
                    non_sso_data().cbegin() +
                        static_cast<difference_type>(
                            sz),
                    count, ch);
            } else {
                add_sso_to_tx(sz, count + 1);
                traits_type::assign(&sso_data()._data[sz],
                            count, ch);
 
                assert(new_size == sz + count);
                set_sso_size(new_size);
                sso_data()._data[new_size] = value_type('\0');
            }
        });
    } else {
        non_sso_data().insert(non_sso_data().cbegin() +
                          static_cast<difference_type>(sz),
                      count, ch);
    }
 
    return *this;
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::append(const basic_string &str)
{
    return append(str.data(), str.size());
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::append(const basic_string &str, size_type pos,
                    size_type count)
{
    auto sz = str.size();
 
    if (pos > sz)
        throw std::out_of_range("Index out of range.");
 
    count = (std::min)(count, sz - pos);
 
    append(str.data() + pos, count);
 
    return *this;
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::append(const CharT *s, size_type count)
{
    return append(s, s + count);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::append(const CharT *s)
{
    return append(s, traits_type::length(s));
}
 
template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::append(InputIt first, InputIt last)
{
    auto sz = size();
    auto count = static_cast<size_type>(std::distance(first, last));
    auto new_size = sz + count;
 
    if (new_size > max_size())
        throw std::length_error("Size exceeds max size.");
 
    if (is_sso_used()) {
        auto pop = get_pool();
 
        transaction::run(pop, [&] {
            if (new_size > sso_capacity) {
                /* 1) Cache C-style string in case of
                 * self-append, because it will be destroyed
                 * when switching from sso to large string.
                 *
                 * 2) We cache in std::vector instead of
                 * std::string because of overload deduction
                 * ambiguity on Windows
                 */
                std::vector<value_type> str(first, last);
 
                sso_to_large(new_size);
                non_sso_data().insert(
                    non_sso_data().cbegin() +
                        static_cast<difference_type>(
                            sz),
                    str.begin(), str.end());
            } else {
                add_sso_to_tx(sz, count + 1);
                std::copy(first, last, &sso_data()._data[sz]);
 
                assert(new_size == sz + count);
                set_sso_size(new_size);
                sso_data()._data[new_size] = value_type('\0');
            }
        });
    } else {
        non_sso_data().insert(non_sso_data().cbegin() +
                          static_cast<difference_type>(sz),
                      first, last);
    }
 
    return *this;
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::append(std::initializer_list<CharT> ilist)
{
    return append(ilist.begin(), ilist.end());
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::push_back(CharT ch)
{
    append(static_cast<size_type>(1), ch);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator+=(const basic_string &str)
{
    return append(str);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator+=(const CharT *s)
{
    return append(s);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator+=(CharT ch)
{
    push_back(ch);
 
    return *this;
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator+=(std::initializer_list<CharT> ilist)
{
    return append(ilist);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::insert(size_type index, size_type count, CharT ch)
{
    if (index > size())
        throw std::out_of_range("Index out of range.");
 
    auto pos = cbegin() + static_cast<difference_type>(index);
 
    insert(pos, count, ch);
 
    return *this;
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::insert(size_type index, const CharT *s)
{
    return insert(index, s, traits_type::length(s));
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::insert(size_type index, const CharT *s,
                    size_type count)
{
    if (index > size())
        throw std::out_of_range("Index out of range.");
 
    auto pos = cbegin() + static_cast<difference_type>(index);
 
    insert(pos, s, s + count);
 
    return *this;
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::insert(size_type index, const basic_string &str)
{
    return insert(index, str.data(), str.size());
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::insert(size_type index1, const basic_string &str,
                    size_type index2, size_type count)
{
    auto sz = str.size();
 
    if (index1 > size() || index2 > sz)
        throw std::out_of_range("Index out of range.");
 
    count = (std::min)(count, sz - index2);
 
    return insert(index1, str.data() + index2, count);
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::insert(const_iterator pos, CharT ch)
{
    return insert(pos, 1, ch);
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::insert(const_iterator pos, size_type count,
                    CharT ch)
{
    auto sz = size();
 
    if (sz + count > max_size())
        throw std::length_error("Count exceeds max size.");
 
    auto new_size = sz + count;
 
    auto pop = get_pool();
 
    auto index = static_cast<size_type>(std::distance(cbegin(), pos));
 
    transaction::run(pop, [&] {
        if (is_sso_used() && new_size <= sso_capacity) {
            auto len = sz - index;
 
            add_sso_to_tx(index, len + count + 1);
 
            traits_type::move(&sso_data()._data[index + count],
                      &sso_data()._data[index], len);
            traits_type::assign(&sso_data()._data[index], count,
                        ch);
 
            assert(new_size == index + len + count);
            set_sso_size(new_size);
            sso_data()._data[new_size] = value_type('\0');
        } else {
            if (is_sso_used())
                sso_to_large(new_size);
 
            non_sso_data().insert(
                non_sso_data().begin() +
                    static_cast<difference_type>(index),
                count, ch);
        }
    });
 
    return iterator(&data()[static_cast<difference_type>(index)]);
}
 
template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::insert(const_iterator pos, InputIt first,
                    InputIt last)
{
    auto sz = size();
 
    auto count = static_cast<size_type>(std::distance(first, last));
 
    if (sz + count > max_size())
        throw std::length_error("Count exceeds max size.");
 
    auto pop = get_pool();
 
    auto new_size = sz + count;
 
    auto index = static_cast<size_type>(std::distance(cbegin(), pos));
 
    transaction::run(pop, [&] {
        if (is_sso_used() && new_size <= sso_capacity) {
            auto len = sz - index;
 
            add_sso_to_tx(index, len + count + 1);
 
            traits_type::move(&sso_data()._data[index + count],
                      &sso_data()._data[index], len);
            std::copy(first, last, &sso_data()._data[index]);
 
            assert(new_size == index + len + count);
            set_sso_size(new_size);
            sso_data()._data[new_size] = value_type('\0');
        } else {
            if (is_sso_used()) {
                /* 1) Cache C-style string in case of
                 * self-insert, because it will be destroyed
                 * when switching from sso to large string.
                 *
                 * 2) We cache in std::vector instead of
                 * std::string because of overload deduction
                 * ambiguity on Windows
                 */
                std::vector<value_type> str(first, last);
 
                sso_to_large(new_size);
                non_sso_data().insert(
                    non_sso_data().begin() +
                        static_cast<difference_type>(
                            index),
                    str.begin(), str.end());
            } else {
                non_sso_data().insert(
                    non_sso_data().begin() +
                        static_cast<difference_type>(
                            index),
                    first, last);
            }
        }
    });
 
    return iterator(&data()[static_cast<difference_type>(index)]);
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::insert(const_iterator pos,
                    std::initializer_list<CharT> ilist)
{
    return insert(pos, ilist.begin(), ilist.end());
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(size_type index, size_type count,
                     const basic_string &str)
{
    return replace(index, count, str.data(), str.size());
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(const_iterator first, const_iterator last,
                     const basic_string &str)
{
    return replace(first, last, str.data(), str.data() + str.size());
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(size_type index, size_type count,
                     const basic_string &str, size_type index2,
                     size_type count2)
{
    auto sz = str.size();
 
    if (index2 > sz)
        throw std::out_of_range("Index out of range.");
 
    count2 = (std::min)(count2, sz - index2);
 
    return replace(index, count, str.data() + index2, count2);
}
 
template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(const_iterator first, const_iterator last,
                     InputIt first2, InputIt last2)
{
    auto sz = size();
    auto index = static_cast<size_type>(std::distance(cbegin(), first));
    auto count = static_cast<size_type>(std::distance(first, last));
    auto count2 = static_cast<size_type>(std::distance(first2, last2));
 
    count = (std::min)(count, sz - index);
 
    if (sz - count + count2 > max_size())
        throw std::length_error("Count exceeds max size.");
 
    auto new_size = sz - count + count2;
 
    auto pop = get_pool();
 
    transaction::run(pop, [&] {
        if (is_sso_used() && new_size <= sso_capacity) {
            add_sso_to_tx(index, new_size - index + 1);
 
            assert(count2 < new_size + 1);
            traits_type::move(&sso_data()._data[index + count2],
                      &sso_data()._data[index + count],
                      sz - index - count);
            std::copy(first2, last2, &sso_data()._data[index]);
 
            set_sso_size(new_size);
            sso_data()._data[new_size] = value_type('\0');
        } else {
            /* 1) Cache C-style string in case of
             * self-replace, because it will be destroyed
             * when switching from sso to large string.
             *
             * 2) We cache in std::vector instead of
             * std::string because of overload deduction
             * ambiguity on Windows
             */
            std::vector<value_type> str(first2, last2);
 
            if (is_sso_used()) {
                sso_to_large(new_size);
            }
 
            auto beg =
                begin() + static_cast<difference_type>(index);
            auto end = beg + static_cast<difference_type>(count);
            non_sso_data().erase(beg, end);
            non_sso_data().insert(beg, str.begin(), str.end());
        }
 
        if (!is_sso_used() && new_size <= sso_capacity)
            large_to_sso();
    });
 
    return *this;
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(const_iterator first, const_iterator last,
                     const CharT *s, size_type count2)
{
    return replace(first, last, s, s + count2);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(size_type index, size_type count,
                     const CharT *s, size_type count2)
{
    if (index > size())
        throw std::out_of_range("Index out of range.");
 
    auto first = cbegin() + static_cast<difference_type>(index);
    auto last = first + static_cast<difference_type>(count);
 
    return replace(first, last, s, s + count2);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(size_type index, size_type count,
                     const CharT *s)
{
    return replace(index, count, s, traits_type::length(s));
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(size_type index, size_type count,
                     size_type count2, CharT ch)
{
    if (index > size())
        throw std::out_of_range("Index out of range.");
 
    auto first = cbegin() + static_cast<difference_type>(index);
    auto last = first + static_cast<difference_type>(count);
 
    return replace(first, last, count2, ch);
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(const_iterator first, const_iterator last,
                     size_type count2, CharT ch)
{
    auto sz = size();
    auto index = static_cast<size_type>(std::distance(cbegin(), first));
    auto count = static_cast<size_type>(std::distance(first, last));
 
    count = (std::min)(count, sz - index);
 
    if (sz - count + count2 > max_size())
        throw std::length_error("Count exceeds max size.");
 
    auto new_size = sz - count + count2;
 
    auto pop = get_pool();
 
    transaction::run(pop, [&] {
        if (is_sso_used() && new_size <= sso_capacity) {
            add_sso_to_tx(index, new_size - index + 1);
 
            assert(count2 < new_size + 1);
            traits_type::move(&sso_data()._data[index + count2],
                      &sso_data()._data[index + count],
                      sz - index - count);
            traits_type::assign(&sso_data()._data[index], count2,
                        ch);
 
            set_sso_size(new_size);
            sso_data()._data[new_size] = value_type('\0');
        } else {
            if (is_sso_used()) {
                sso_to_large(new_size);
            }
 
            auto beg =
                begin() + static_cast<difference_type>(index);
            auto end = beg + static_cast<difference_type>(count);
            non_sso_data().erase(beg, end);
            non_sso_data().insert(beg, count2, ch);
        }
 
        if (!is_sso_used() && new_size <= sso_capacity)
            large_to_sso();
    });
 
    return *this;
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(const_iterator first, const_iterator last,
                     const CharT *s)
{
    return replace(first, last, s, traits_type::length(s));
}
 
template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(const_iterator first, const_iterator last,
                     std::initializer_list<CharT> ilist)
{
    return replace(first, last, ilist.begin(), ilist.end());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::copy(CharT *s, size_type count,
                  size_type index) const
{
    auto sz = size();
 
    if (index > sz)
        throw std::out_of_range("Index out of range.");
 
    auto len = (std::min)(count, sz - index);
 
    traits_type::copy(s, data() + index, len);
 
    return len;
}
 
template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(size_type pos, size_type count1,
                     const CharT *s, size_type count2) const
{
    if (pos > size())
        throw std::out_of_range("Index out of range.");
 
    if (count1 > size() - pos)
        count1 = size() - pos;
 
    auto ret = traits_type::compare(cdata() + pos, s,
                    std::min<size_type>(count1, count2));
 
    if (ret != 0)
        return ret;
 
    if (count1 < count2)
        return -1;
    else if (count1 == count2)
        return 0;
    else
        return 1;
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find(const basic_string &str, size_type pos) const
    noexcept
{
    return find(str.data(), pos, str.size());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find(const CharT *s, size_type pos,
                  size_type count) const
{
    auto sz = size();
 
    if (pos > sz)
        return npos;
 
    if (count == 0)
        return pos;
 
    while (pos + count <= sz) {
        auto found = traits_type::find(cdata() + pos, sz - pos, s[0]);
        if (!found)
            return npos;
        pos = static_cast<size_type>(std::distance(cdata(), found));
        if (traits_type::compare(found, s, count) == 0) {
            return pos;
        }
        ++pos;
    }
    return npos;
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find(const CharT *s, size_type pos) const
{
    return find(s, pos, traits_type::length(s));
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find(CharT ch, size_type pos) const noexcept
{
    return find(&ch, pos, 1);
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::rfind(const basic_string &str, size_type pos) const
    noexcept
{
    return rfind(str.cdata(), pos, str.size());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::rfind(const CharT *s, size_type pos,
                   size_type count) const
{
    if (count <= size()) {
        pos = (std::min)(size() - count, pos);
        do {
            if (traits_type::compare(cdata() + pos, s, count) == 0)
                return pos;
        } while (pos-- > 0);
    }
    return npos;
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::rfind(const CharT *s, size_type pos) const
{
    return rfind(s, pos, traits_type::length(s));
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::rfind(CharT ch, size_type pos) const noexcept
{
    return rfind(&ch, pos, 1);
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_first_of(const basic_string &str,
                       size_type pos) const noexcept
{
    return find_first_of(str.cdata(), pos, str.size());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_first_of(const CharT *s, size_type pos,
                       size_type count) const
{
    size_type first_of = npos;
    for (const CharT *c = s; c != s + count; ++c) {
        size_type found = find(*c, pos);
        if (found != npos && found < first_of)
            first_of = found;
    }
    return first_of;
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_first_of(const CharT *s, size_type pos) const
{
    return find_first_of(s, pos, traits_type::length(s));
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_first_of(CharT ch, size_type pos) const
    noexcept
{
    return find(ch, pos);
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_first_not_of(const basic_string &str,
                           size_type pos) const noexcept
{
    return find_first_not_of(str.cdata(), pos, str.size());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_first_not_of(const CharT *s, size_type pos,
                           size_type count) const
{
    if (pos >= size())
        return npos;
 
    for (auto it = cbegin() + pos; it != cend(); ++it)
        if (!traits_type::find(s, count, *it))
            return static_cast<size_type>(
                std::distance(cbegin(), it));
    return npos;
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_first_not_of(const CharT *s,
                           size_type pos) const
{
    return find_first_not_of(s, pos, traits_type::length(s));
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_first_not_of(CharT ch, size_type pos) const
    noexcept
{
    return find_first_not_of(&ch, pos, 1);
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_last_of(const basic_string &str,
                      size_type pos) const noexcept
{
    return find_last_of(str.cdata(), pos, str.size());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_last_of(const CharT *s, size_type pos,
                      size_type count) const
{
    if (size() == 0 || count == 0)
        return npos;
 
    bool found = false;
    size_type last_of = 0;
    for (const CharT *c = s; c != s + count; ++c) {
        size_type position = rfind(*c, pos);
        if (position != npos) {
            found = true;
            if (position > last_of)
                last_of = position;
        }
    }
    if (!found)
        return npos;
    return last_of;
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_last_of(const CharT *s, size_type pos) const
{
    return find_last_of(s, pos, traits_type::length(s));
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_last_of(CharT ch, size_type pos) const
    noexcept
{
    return rfind(ch, pos);
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_last_not_of(const basic_string &str,
                          size_type pos) const noexcept
{
    return find_last_not_of(str.cdata(), pos, str.size());
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_last_not_of(const CharT *s, size_type pos,
                          size_type count) const
{
    if (size() > 0) {
        pos = (std::min)(pos, size() - 1);
        do {
            if (!traits_type::find(s, count, *(cdata() + pos)))
                return pos;
 
        } while (pos-- > 0);
    }
    return npos;
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_last_not_of(const CharT *s,
                          size_type pos) const
{
    return find_last_not_of(s, pos, traits_type::length(s));
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::find_last_not_of(CharT ch, size_type pos) const
    noexcept
{
    return find_last_not_of(&ch, pos, 1);
}
 
template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(const basic_string &other) const
{
    return compare(0, size(), other.cdata(), other.size());
}
 
template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(
    const std::basic_string<CharT> &other) const
{
    return compare(0, size(), other.data(), other.size());
}
 
template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(size_type pos, size_type count,
                     const basic_string &other) const
{
    return compare(pos, count, other.cdata(), other.size());
}
 
template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(
    size_type pos, size_type count,
    const std::basic_string<CharT> &other) const
{
    return compare(pos, count, other.data(), other.size());
}
 
template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(size_type pos1, size_type count1,
                     const basic_string &other, size_type pos2,
                     size_type count2) const
{
    if (pos2 > other.size())
        throw std::out_of_range("Index out of range.");
 
    if (count2 > other.size() - pos2)
        count2 = other.size() - pos2;
 
    return compare(pos1, count1, other.cdata() + pos2, count2);
}
 
template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(size_type pos1, size_type count1,
                     const std::basic_string<CharT> &other,
                     size_type pos2, size_type count2) const
{
    if (pos2 > other.size())
        throw std::out_of_range("Index out of range.");
 
    if (count2 > other.size() - pos2)
        count2 = other.size() - pos2;
 
    return compare(pos1, count1, other.data() + pos2, count2);
}
 
template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(const CharT *s) const
{
    return compare(0, size(), s, traits_type::length(s));
}
 
template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(size_type pos, size_type count,
                     const CharT *s) const
{
    return compare(pos, count, s, traits_type::length(s));
}
 
template <typename CharT, typename Traits>
const CharT *
basic_string<CharT, Traits>::cdata() const noexcept
{
    return is_sso_used() ? sso_data().cdata() : non_sso_data().cdata();
}
 
template <typename CharT, typename Traits>
const CharT *
basic_string<CharT, Traits>::data() const noexcept
{
    return cdata();
}
 
template <typename CharT, typename Traits>
const CharT *
basic_string<CharT, Traits>::c_str() const noexcept
{
    return cdata();
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::length() const noexcept
{
    return size();
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::max_size() const noexcept
{
    return PMEMOBJ_MAX_ALLOC_SIZE / sizeof(CharT) - 1;
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::capacity() const noexcept
{
    return is_sso_used() ? sso_capacity : non_sso_data().capacity() - 1;
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::resize(size_type count, CharT ch)
{
    if (count > max_size())
        throw std::length_error("Count exceeds max size.");
 
    auto sz = size();
 
    auto pop = get_pool();
 
    transaction::run(pop, [&] {
        if (count > sz) {
            append(count - sz, ch);
        } else if (is_sso_used()) {
            set_sso_size(count);
            sso_data()[count] = value_type('\0');
        } else {
            non_sso_data().resize(count + 1, ch);
            non_sso_data().back() = value_type('\0');
        }
    });
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::resize(size_type count)
{
    resize(count, CharT());
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::reserve(size_type new_cap)
{
    if (new_cap > max_size())
        throw std::length_error("New capacity exceeds max size.");
 
    if (new_cap < capacity() || new_cap <= sso_capacity)
        return;
 
    if (is_sso_used()) {
        auto pop = get_pool();
 
        transaction::run(pop, [&] { sso_to_large(new_cap); });
    } else {
        non_sso_data().reserve(new_cap + 1);
    }
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::shrink_to_fit()
{
    if (is_sso_used())
        return;
 
    if (size() <= sso_capacity) {
        auto pop = get_pool();
 
        transaction::run(pop, [&] { large_to_sso(); });
    } else {
        non_sso_data().shrink_to_fit();
    }
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::clear()
{
    erase(begin(), end());
}
 
template <typename CharT, typename Traits>
bool
basic_string<CharT, Traits>::empty() const noexcept
{
    return size() == 0;
}
 
template <typename CharT, typename Traits>
bool
basic_string<CharT, Traits>::is_sso_used() const
{
    return (sso._size & _sso_mask) != 0;
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::destroy_data()
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
 
    if (is_sso_used()) {
        add_sso_to_tx(0, get_sso_size() + 1);
        /* sso.data destructor does not have to be called */
    } else {
        non_sso_data().free_data();
        detail::destroy<non_sso_type>(non_sso_data());
    }
}
 
template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::get_size(InputIt first, InputIt last) const
{
    return static_cast<size_type>(std::distance(first, last));
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::get_size(size_type count, value_type ch) const
{
    return count;
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::get_size(const basic_string &other) const
{
    return other.size();
}
 
template <typename CharT, typename Traits>
template <typename... Args>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::replace_content(Args &&... args)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
 
    auto new_size = get_size(std::forward<Args>(args)...);
 
    /* If non_sso.data is used and there is enough capacity */
    if (!is_sso_used() && new_size <= capacity())
        return assign_large_data(std::forward<Args>(args)...);
 
    destroy_data();
 
    allocate(new_size);
    return initialize(std::forward<Args>(args)...);
}
 
template <typename CharT, typename Traits>
template <typename... Args>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::initialize(Args &&... args)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
 
    auto size = get_size(std::forward<Args>(args)...);
 
    if (is_sso_used()) {
        auto ptr = assign_sso_data(std::forward<Args>(args)...);
        set_sso_size(size);
 
        return ptr;
    } else {
        return assign_large_data(std::forward<Args>(args)...);
    }
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::allocate(size_type capacity)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
 
    if (capacity <= sso_capacity) {
        enable_sso();
    } else {
        disable_sso();
    }
 
    /*
     * array is aggregate type so it's not required to call
     * a constructor.
     */
    if (!is_sso_used()) {
        detail::conditional_add_to_tx(&non_sso_data(), 1,
                          POBJ_XADD_NO_SNAPSHOT);
        detail::create<non_sso_type>(&non_sso_data());
        non_sso_data().reserve(capacity + 1);
    }
}
 
template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::assign_sso_data(InputIt first, InputIt last)
{
    auto size = static_cast<size_type>(std::distance(first, last));
 
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    assert(size <= sso_capacity);
 
    add_sso_to_tx(0, size + 1);
    std::copy(first, last, &sso_data()._data[0]);
 
    sso_data()._data[size] = value_type('\0');
 
    return &sso_data()[0];
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::assign_sso_data(size_type count, value_type ch)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    assert(count <= sso_capacity);
 
    add_sso_to_tx(0, count + 1);
    traits_type::assign(&sso_data()._data[0], count, ch);
 
    sso_data()._data[count] = value_type('\0');
 
    return &sso_data()[0];
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::assign_sso_data(basic_string &&other)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
 
    return assign_sso_data(other.cbegin(), other.cend());
}
 
template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::assign_large_data(InputIt first, InputIt last)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
 
    auto size = static_cast<size_type>(std::distance(first, last));
 
    non_sso_data().reserve(size + 1);
    non_sso_data().assign(first, last);
    non_sso_data().push_back(value_type('\0'));
 
    return non_sso_data().data();
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::assign_large_data(size_type count, value_type ch)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
 
    non_sso_data().reserve(count + 1);
    non_sso_data().assign(count, ch);
    non_sso_data().push_back(value_type('\0'));
 
    return non_sso_data().data();
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::assign_large_data(basic_string &&other)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
 
    if (other.is_sso_used())
        return assign_large_data(other.cbegin(), other.cend());
 
    non_sso_data() = std::move(other.non_sso_data());
 
    return non_sso_data().data();
}
 
template <typename CharT, typename Traits>
pool_base
basic_string<CharT, Traits>::get_pool() const
{
    auto pop = pmemobj_pool_by_ptr(this);
    assert(pop != nullptr);
 
    return pool_base(pop);
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::check_pmem() const
{
    if (pmemobj_pool_by_ptr(this) == nullptr)
        throw pmem::pool_error("Object is not on pmem.");
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::check_tx_stage_work() const
{
    if (pmemobj_tx_stage() != TX_STAGE_WORK)
        throw pmem::transaction_scope_error(
            "Call made out of transaction scope.");
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::check_pmem_tx() const
{
    check_pmem();
    check_tx_stage_work();
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::add_sso_to_tx(size_type idx_first,
                       size_type num) const
{
    assert(idx_first + num <= sso_capacity + 1);
    assert(is_sso_used());
 
    auto initialized_num = get_sso_size() + 1 - idx_first;
 
    /* Snapshot elements in range [idx_first, sso_size + 1 (null)) */
    detail::conditional_add_to_tx(&sso_data()._data[0] + idx_first,
                      (std::min)(initialized_num, num));
 
    if (num > initialized_num) {
        /* Elements after sso_size + 1 do not have to be snapshotted */
        detail::conditional_add_to_tx(
            &sso_data()._data[0] + get_sso_size() + 1,
            num - initialized_num, POBJ_XADD_NO_SNAPSHOT);
    }
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::get_sso_size() const
{
    return sso._size & ~_sso_mask;
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::enable_sso()
{
    /* temporary size_type must be created to avoid undefined reference
     * linker error */
    sso._size |= (size_type)(_sso_mask);
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::disable_sso()
{
    sso._size &= ~_sso_mask;
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::set_sso_size(size_type new_size)
{
    sso._size = new_size | _sso_mask;
}
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::sso_to_large(size_t new_capacity)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    assert(new_capacity > sso_capacity);
    assert(is_sso_used());
 
    auto sz = size();
 
    sso_type tmp;
    std::copy(cbegin(), cend(), tmp.data());
    tmp[sz] = value_type('\0');
 
    destroy_data();
    allocate(new_capacity);
 
    auto begin = tmp.cbegin();
    auto end = begin + sz;
 
    initialize(begin, end);
 
    assert(!is_sso_used());
};
 
template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::large_to_sso()
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    assert(!is_sso_used());
 
    auto sz = size();
 
    assert(sz <= sso_capacity);
 
    sso_type tmp;
    std::copy(cbegin(), cbegin() + sz, tmp.data());
    tmp[sz] = value_type('\0');
 
    destroy_data();
    allocate(sz);
 
    auto begin = tmp.cbegin();
    auto end = begin + sz;
 
    initialize(begin, end);
 
    assert(is_sso_used());
};
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::non_sso_type &
basic_string<CharT, Traits>::non_sso_data()
{
    assert(!is_sso_used());
    return non_sso._data;
}
 
template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::sso_type &
basic_string<CharT, Traits>::sso_data()
{
    assert(is_sso_used());
    return sso._data;
}
 
template <typename CharT, typename Traits>
const typename basic_string<CharT, Traits>::non_sso_type &
basic_string<CharT, Traits>::non_sso_data() const
{
    assert(!is_sso_used());
    return non_sso._data;
}
 
template <typename CharT, typename Traits>
const typename basic_string<CharT, Traits>::sso_type &
basic_string<CharT, Traits>::sso_data() const
{
    assert(is_sso_used());
    return sso._data;
}
 
template <typename CharT, typename Traits>
template <typename T, typename Enable>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::erase(T param)
{
    return erase(static_cast<size_type>(param));
}
 
template <typename CharT, typename Traits>
template <typename T, typename Enable>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::erase(T param)
{
    return erase(static_cast<const_iterator>(param));
}
 
template <typename CharT, typename Traits>
template <typename T, typename Enable>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::insert(T param, size_type count, CharT ch)
{
    return insert(static_cast<size_type>(param), count, ch);
}
 
template <typename CharT, typename Traits>
template <typename T, typename Enable>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::insert(T param, size_type count, CharT ch)
{
    return insert(static_cast<const_iterator>(param), count, ch);
}
 
template <class CharT, class Traits>
bool
operator==(const basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) == 0;
}
 
template <class CharT, class Traits>
bool
operator!=(const basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) != 0;
}
 
template <class CharT, class Traits>
bool
operator<(const basic_string<CharT, Traits> &lhs,
      const basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) < 0;
}
 
template <class CharT, class Traits>
bool
operator<=(const basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) <= 0;
}
 
template <class CharT, class Traits>
bool
operator>(const basic_string<CharT, Traits> &lhs,
      const basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) > 0;
}
 
template <class CharT, class Traits>
bool
operator>=(const basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) >= 0;
}
 
template <class CharT, class Traits>
bool
operator==(const CharT *lhs, const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) == 0;
}
 
template <class CharT, class Traits>
bool
operator!=(const CharT *lhs, const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) != 0;
}
 
template <class CharT, class Traits>
bool
operator<(const CharT *lhs, const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) > 0;
}
 
template <class CharT, class Traits>
bool
operator<=(const CharT *lhs, const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) >= 0;
}
 
template <class CharT, class Traits>
bool
operator>(const CharT *lhs, const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) < 0;
}
 
template <class CharT, class Traits>
bool
operator>=(const CharT *lhs, const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) <= 0;
}
 
template <class CharT, class Traits>
bool
operator==(const basic_string<CharT, Traits> &lhs, const CharT *rhs)
{
    return lhs.compare(rhs) == 0;
}
 
template <class CharT, class Traits>
bool
operator!=(const basic_string<CharT, Traits> &lhs, const CharT *rhs)
{
    return lhs.compare(rhs) != 0;
}
 
template <class CharT, class Traits>
bool
operator<(const basic_string<CharT, Traits> &lhs, const CharT *rhs)
{
    return lhs.compare(rhs) < 0;
}
 
template <class CharT, class Traits>
bool
operator<=(const basic_string<CharT, Traits> &lhs, const CharT *rhs)
{
    return lhs.compare(rhs) <= 0;
}
 
template <class CharT, class Traits>
bool
operator>(const basic_string<CharT, Traits> &lhs, const CharT *rhs)
{
    return lhs.compare(rhs) > 0;
}
 
template <class CharT, class Traits>
bool
operator>=(const basic_string<CharT, Traits> &lhs, const CharT *rhs)
{
    return lhs.compare(rhs) >= 0;
}
 
template <class CharT, class Traits>
bool
operator==(const std::basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) == 0;
}
 
template <class CharT, class Traits>
bool
operator!=(const std::basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) != 0;
}
 
template <class CharT, class Traits>
bool
operator<(const std::basic_string<CharT, Traits> &lhs,
      const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) > 0;
}
 
template <class CharT, class Traits>
bool
operator<=(const std::basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) >= 0;
}
 
template <class CharT, class Traits>
bool
operator>(const std::basic_string<CharT, Traits> &lhs,
      const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) < 0;
}
 
template <class CharT, class Traits>
bool
operator>=(const std::basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) <= 0;
}
 
template <class CharT, class Traits>
bool
operator==(const basic_string<CharT, Traits> &lhs,
       const std::basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) == 0;
}
 
template <class CharT, class Traits>
bool
operator!=(const basic_string<CharT, Traits> &lhs,
       const std::basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) != 0;
}
 
template <class CharT, class Traits>
bool
operator<(const basic_string<CharT, Traits> &lhs,
      const std::basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) < 0;
}
 
template <class CharT, class Traits>
bool
operator<=(const basic_string<CharT, Traits> &lhs,
       const std::basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) <= 0;
}
 
template <class CharT, class Traits>
bool
operator>(const basic_string<CharT, Traits> &lhs,
      const std::basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) > 0;
}
 
template <class CharT, class Traits>
bool
operator>=(const basic_string<CharT, Traits> &lhs,
       const std::basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) >= 0;
}
 
} /* namespace obj */
 
} /* namespace pmem */
 
#endif /* LIBPMEMOBJ_CPP_BASIC_STRING_HPP */