flex_string和SlimStringStorage

68 阅读 0 评论 45 点赞

我是靠谱客的博主迅速糖豆，最近开发中收集的这篇文章主要介绍flex_string和SlimStringStorage，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在2001年就拜读了C++巨匠Andrei Alexandrescu的著作：《A Policy-Based basic_string Implementation》。flex_string的精巧令人叹服。其后阅读《Modern C++ Design》，更是令人震撼，正如候捷译序中所说：“让我瞠目结舌，陷入沉思……与……呃……恍惚。”Loki库更是如获至宝……
可惜在当时在下载了flex_string的源码以后，一经测试，竟然几个显而易见大大的bug就放在那里……高手也是有偶然犯错的时候……

今年之所以无意中想起这件事，原因是同事问起：他有一个数据结构需要用大量定长的字符串作Key，但std::string比较浪费空间，const char *既不安全也不好用，除了自己写一个class还有没有其他的好方法？这一下子让我想起了flex_string的SmallStringOpt，简直就是度身订做的解决方案，于是再找到 Code Snippets的地址，发现flex_string今年初换了新版本，简直欣喜若狂。特别是作者的这句话：“Harmut Kaizer reported that simply dropping in flex_string in the Wave Boost Preprocessor improved its speed by 5-10%, depending on input.” 有人做过白老鼠，这次应该不会有什么bug了吧。于是下载编译测试……

看到各种的Storage，让我又想起另外一件事：有个程序员跟我说他的工程需要很多不定长的字符串作为Key，仅仅作为一种只读的字符串，不需要任何的变更，因此std::string的几个指针变得“多余”，换句话说，他只想要一个“节省”而又“安全”的const char *。其实个人觉得SmallStringOpt<SimpleStringStorage<char, std::allocator<char>, 3>之类的已经足够了，但别人坚持“我就喜欢”，那有什么办法呢。于是简单做一个SlimStringStorage给flex_string用用吧：

#include <utility>

template <typename E, class A = std::allocator<E> >
class SlimStringStorage
{
// The "public" below exists because MSVC can't do template typedefs
public:
static const E emptyString_;
typedef typename A::size_type size_type;

private:
E * pData_;

void Init(size_type size)
{
  if (pData_ != &emptyString_)
   free(pData_);
  if (size == 0)
   pData_ = const_cast<E*>(&emptyString_);
  else
  {
   pData_ = static_cast<E*>(malloc(sizeof(E) + size * sizeof(E)));
   if (!pData_) throw std::bad_alloc();
   pData_[size] = E();
  }
}

public:
typedef E value_type;
typedef E* iterator;
typedef const E* const_iterator;
typedef A allocator_type;

SlimStringStorage(const SlimStringStorage& rhs)
{
  pData_ = const_cast<E*>(&emptyString_);
  const size_type sz = rhs.size();
  Init(sz);
  if (sz) flex_string_details::pod_copy(rhs.begin(), rhs.begin() + sz, begin());
}

SlimStringStorage(const SlimStringStorage& s,flex_string_details::Shallow)
: pData_(s.pData_)
{}

SlimStringStorage(const A&)
{ pData_ = const_cast<E*>(&emptyString_); }

SlimStringStorage(const E* s, size_type len, const A&)
{
  pData_ = const_cast<E*>(&emptyString_);
  Init(len);
  flex_string_details::pod_copy(s, s + len, begin());
}

SlimStringStorage(size_type len, E c, const A&)
{
  pData_ = const_cast<E*>(&emptyString_);
  Init(len);
  flex_string_details::pod_fill(begin(), begin() + len, c);
}

SlimStringStorage& operator=(const SlimStringStorage& rhs)
{
  const size_type sz = rhs.size();
  reserve(sz);
  if (sz)
  {
   flex_string_details::pod_copy(&*rhs.begin(), &*(rhs.begin() + sz), begin());
   pData_[sz] = E();
  }

  return *this;
}

~SlimStringStorage()
{
if (pData_ != &emptyString_) free(pData_);
}

iterator begin()
{ return pData_; }

const_iterator begin() const
{ return pData_; }

iterator end()
{ return pData_ + size(); }

const_iterator end() const
{ return pData_ + size(); }

size_type size() const;

size_type max_size() const
{ return size_t(-1) / sizeof(E) - sizeof(E *) - 1; }

size_type capacity() const
{ return size(); }

void reserve(size_type res_arg)
{
  if (pData_ == &emptyString_ || res_arg == 0)
  {
   Init(res_arg);
   if (res_arg)
    *pData_ = E();
  }
  else
  {
   const size_type sz = size();

   if (res_arg > sz)
   {
    void* p = realloc(pData_, sizeof(E) + res_arg * sizeof(E));
    if (!p) throw std::bad_alloc();

    if (p != pData_)
    {
     pData_ = static_cast<E*>(p);
     pData_[sz] = E();
    } // if (p != pData_)
    pData_[res_arg] = E();
   }
  }
}

void append(const E* s, size_type sz)
{
const size_type szOrg = size();
const size_type neededCapacity = szOrg + sz;

  const iterator b = begin();
  static std::less_equal<const E*> le;
  if (le(b, s) && le(s, pData_ + szOrg))
  {
   // aliased
   const size_type offset = s - b;
   reserve(neededCapacity);
   s = begin() + offset;
  } // if (le(b, s) && le(s, pData_ + szOrg))
  else
   reserve(neededCapacity);

  flex_string_details::pod_copy(s, s + sz, pData_ + szOrg);
}

template <class InputIterator>
  void append(InputIterator b, InputIterator e)
  {
   const size_type szOrg = size();
   const size_type neededCapacity = szOrg + std::distance(b,e);
   reserve(neededCapacity);

   for (E * p = pData_ + szOrg; b != e; ++b, ++p)
    *p = *b;
  }

void resize(size_type newSize, E fill)
{
  const size_type szOrg = size();
  const int delta = int(newSize - szOrg);
  if (delta == 0) return;

  reserve(newSize);
  if (delta > 0)
  {
   E* e = pData_ + szOrg;
   flex_string_details::pod_fill(e, e + delta, fill);
  } // if (delta > 0)
  else if (newSize)
   pData_[newSize] = E();
}

void swap(SlimStringStorage& rhs)
{
std::swap(pData_, rhs.pData_);
}

const E* c_str() const
{
return pData_;
}

const E* data() const
{ return pData_; }

A get_allocator() const
{ return A(); }
};

template <typename E, class A>
typename SlimStringStorage<E,A>::size_type SlimStringStorage<E,A>::size() const
{
register const E * p = pData_;
for (; *p; ++p);
return static_cast<size_type>(p - pData_);
}

template <typename E, class A>
const E SlimStringStorage<E,A>::emptyString_ = E();

其实原理也很简单，Copy SimpleStringStorage的代码改一下，只用一个指针就是了。

最后用flex_string的测试程序测试，不通过……后来才发现String result(random(0, maxSize), '/0');然后获得result.size()的时候变成0。哦，那当然了，少了一个指针指向字符串结尾，只能通过寻找'/0'，当然size不正确了，于是测试程序的几处：
    String result(random(0, maxSize), '/0');
    int i = 0;
    for (; i != result.size(); ++i)

改为：

size_t nSize = random(0, maxSize);
String result(nSize, '/0');
int i = 0;
for (; i != nSize; ++i)
测试通过了。不过用的时候就要注意了，用了SlimStringStorage的flex_string的resize的含义和普通的string不一样了，不过也没关系的。

另外一点想不通的就是flex_string为什么不加上：

template<class T2,class A2,class S2>

flex_string(const flex_string<E,T2,A2,S2> & str, size_type pos,size_type n = npos, const A& a = A());

template<class T2,class A2,class S2>

flex_string(const std::basic_string<E,T2,A2> & str, size_type pos,size_type n = npos, const A& a = A());

template<class T2,class A2,class S2>

flex_string& operator=(const flex_string<E,T2,A2,S2> & str);
template<class T2,class A2,class S2>

flex_string& operator=(const std::basic_string<E,T2,A2> & str);

之类的函数，使得std::string和不同的Storage的flex_string之间可以相互通用呢？高手可能自有高手的看法，有空的话自己慢慢加吧。