Sorts using icu collation

sort.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <memory>
#include <initializer_list>

#include <unicode/ucol.h>

template <typename T>
struct comparator
{
  virtual bool compare(T const& first, T const& last) = 0;
};

struct u16string_comparator : comparator<std::u16string>
{
  explicit u16string_comparator(std::string const& language = "en_US")
  {
    UErrorCode status = U_ZERO_ERROR;
    _coll = ucol_open(language.c_str(), &status);

    if (U_FAILURE(status)) {
      throw std::runtime_error("Failed to initialize UCollator");
    }
  }

  u16string_comparator(u16string_comparator const& other) = delete;
  u16string_comparator(u16string_comparator && other) noexcept
  {
    *this = std::move(other);
  }
  u16string_comparator& operator=(u16string_comparator && other)
  {
    if (this != &other) {
      if (other._coll != nullptr) {
        _coll = other._coll;
        other._coll = nullptr;
      }
    }
    return *this;
  }

  ~u16string_comparator()
  {
    if (_coll) {
      ucol_close(_coll);
      _coll = nullptr;
    }
  }

  virtual bool compare(std::u16string const& first, std::u16string const& last) noexcept override
  {
    auto result = ucol_strcoll(_coll, reinterpret_cast<const UChar *>(&first[0]),
                               static_cast<uint32_t>(first.length()),
                               reinterpret_cast<const UChar *>(&last[0]),
                               static_cast<uint32_t>(last.length()));
    return (result == UCOL_LESS);
  }

private:
  UCollator *_coll = nullptr;
};

template <typename T, typename C>
struct sorted_vector
{
  explicit sorted_vector(C && comparator = C()) noexcept :
  _comp(std::move(comparator))
  {
  }

  void append(std::initializer_list<T> l) noexcept
  {
    _items.insert(_items.end(), l.begin(), l.end());
    std::sort(_items.begin(), _items.end(), [&](T const& first, T const& last) {
      return _comp.compare(first, last);
    });
  }

  void push_back(T const& item) noexcept
  {
    _items.push_back(item);
    std::sort(_items.begin(), _items.end(), [&](T const& first, T const& last) {
      return _comp.compare(first, last);
    });
  }

  bool contains(T const& item) noexcept
  {
    auto lower = std::lower_bound(_items.cbegin(), _items.cend(), item, [&](T const& first, T const& last) {
      return _comp.compare(first, last);
    });
    auto which = lower != _items.cend() && !_comp.compare(item, *lower) ? lower : _items.cend();
    return which != _items.cend();
  }

  std::size_t size() noexcept
  {
    return _items.size();
  }

  T &operator[](const std::size_t i) noexcept
  {
    return _items[i];
  }

  auto begin()
  {
    return _items.begin();
  }

  auto end()
  {
    return _items.end();
  }

private:
  C _comp = nullptr;
  std::vector<T> _items = {};
};