字符串(const char*， size_t)到int?

What's the fastest way to convert a string represented by (const char*, size_t) to an int?

将由(const char*， size_t)表示的字符串转换为int的最快方法是什么?

The string is not null-terminated. Both these ways involve a string copy (and more) which I'd like to avoid.

该字符串不是以null结尾的。这两种方法都包含了我想要避免的字符串拷贝(以及更多)。

And yes, this function is called a few million times a second. :p

是的，这个函数被称为每秒几百万次。:p

int to_int0(const char* c, size_t sz)
{
    return atoi(std::string(c, sz).c_str());
}

int to_int1(const char* c, size_t sz)
{
    return boost::lexical_cast<int>(std::string(c, sz));
}

6 个解决方案

#1

Fastest:

最快:

int to_int(char const *s, size_t count)
{
     int result = 0;
     size_t i = 0 ;
     if ( s[0] == '+' || s[0] == '-' ) 
          ++i;
     while(i < count)
     {
          if ( s[i] >= '0' && s[i] <= '9' )
          {
              //see Jerry's comments for explanation why I do this
              int value = (s[0] == '-') ? ('0' - s[i] ) : (s[i]-'0');
              result = result * 10 + value;
          }
          else
              throw std::invalid_argument("invalid input string");
          i++;
     }
     return result;
}

Since in the above code, the comparison (s[0] == '-') is done in every iteration, we can avoid this by calculating result as negative number in the loop, and then return result if s[0] is indeed '-', otherwise return -result (which makes it a positive number, as it should be):

因为在上面的代码中，比较(s[0] == '-')在每个迭代中都完成，我们可以通过计算循环中的负数来避免这个结果，如果s[0]确实是'-'，则返回结果，否则返回-结果(这使它成为正数，应该是这样):

int to_int(char const *s, size_t count)
{
     size_t i = 0 ;
     if ( s[0] == '+' || s[0] == '-' ) 
          ++i;
     int result = 0;
     while(i < count)
     {
          if ( s[i] >= '0' && s[i] <= '9' )
          {
              result = result * 10  - (s[i] - '0');  //assume negative number
          }
          else
              throw std::invalid_argument("invalid input string");
          i++;
     }
     return s[0] == '-' ? result : -result; //-result is positive!
}

That is an improvement!

这是一个进步!

In C++11, you could however use any function from std::stoi family. There is also std::to_string family.

在c++ 11中，您可以使用std::stoi家族的任何函数。还有std::to_string家族。

#2

Given a counted string like this, you may be able to gain a little speed by doing the conversion yourself. Depending on how robust the code needs to be, this may be fairly difficult though. For the moment, let's assume the easiest case -- that we're sure the string is valid, containing only digits, (no negative numbers for now) and the number it represents is always within the range of an int. For that case:

给定一个像这样的计数字符串，您可以通过自己进行转换获得一些速度。这取决于代码的健壮性，但这可能相当困难。现在，让我们假设最简单的情况——我们确信字符串是有效的，只包含数字，(现在没有负数)，它所表示的数字总是在整数范围内。

int to_int2(char const *c, size_t sz) { 
    int retval = 0;
    for (size_t i=0; i<sz; i++)
        retval *= 10;
        retval += c[i] -'0';
    }
    return retval;
}

From there, you can get about as complex as you want -- handling leading/trailing whitespace, '-' (but doing so correctly for the maximally negative number in 2's complement isn't always trivial [edit: see Nawaz's answer for one solution to this]), digit grouping, etc.

从那里，你可以得到你想要的复杂的东西——处理前导/拖尾空格，'-'(但是在2的补码中正确地处理最大的负数并不总是琐碎的[编辑:看到纳瓦兹的一个解决方案])，数字分组，等等。

#3

Another slow version, for uint32:

另一个缓慢版本，uint32:

void str2uint_aux(unsigned& number, unsigned& overflowCtrl, const char*& ch)
{
    unsigned digit = *ch - '0';
    ++ch;

    number = number * 10 + digit;

    unsigned overflow = (digit + (256 - 10)) >> 8;
    // if digit < 10 then overflow == 0
    overflowCtrl += overflow;
}

unsigned str2uint(const char* s, size_t n)
{
    unsigned number = 0;
    unsigned overflowCtrl = 0;

    // for VC++10 the Duff's device is faster than loop
    switch (n)
    {
    default:
        throw std::invalid_argument(__FUNCTION__ " : `n' too big");

    case 10: str2uint_aux(number, overflowCtrl, s);
    case  9: str2uint_aux(number, overflowCtrl, s);
    case  8: str2uint_aux(number, overflowCtrl, s);
    case  7: str2uint_aux(number, overflowCtrl, s);
    case  6: str2uint_aux(number, overflowCtrl, s);
    case  5: str2uint_aux(number, overflowCtrl, s);
    case  4: str2uint_aux(number, overflowCtrl, s);
    case  3: str2uint_aux(number, overflowCtrl, s);
    case  2: str2uint_aux(number, overflowCtrl, s);
    case  1: str2uint_aux(number, overflowCtrl, s);
    }

    // here we can check that all chars were digits
    if (overflowCtrl != 0)
        throw std::invalid_argument(__FUNCTION__ " : `s' is not a number");

    return number;
}

Why it's slow? Because it processes chars one-by-one. If we'd had a guarantee that we can access bytes upto s+16, we'd can use vectorization for *ch - '0' and digit + 246.
Like in this code:

为什么慢?因为它一个一个地处理chars。如果我们有一个保证，我们可以访问到s+16的字节，那么我们就可以用矢量化来实现*ch - '0'和数字+ 246。像在这段代码中:

    uint32_t digitsPack = *(uint32_t*)s - '0000';
    overflowCtrl |= digitsPack | (digitsPack + 0x06060606); // if one byte is not in range [0;10), high nibble will be non-zero
    number = number * 10 + (digitsPack >> 24) & 0xFF;
    number = number * 10 + (digitsPack >> 16) & 0xFF;
    number = number * 10 + (digitsPack >> 8) & 0xFF;
    number = number * 10 + digitsPack & 0xFF;
    s += 4;

Small update for range checking:
the first snippet has redundant shift (or mov) on every iteration, so it should be

对范围检查的小更新:第一个片段在每次迭代上都有冗余移位(或mov)，所以应该是这样。

unsigned digit = *s - '0';
overflowCtrl |= (digit + 256 - 10);
...
if (overflowCtrl >> 8 != 0) throw ...

#4

llvm::StringRef s(c,sz);
int n;
s.getAsInteger(10,n);
return n;

http://llvm.org/docs/doxygen/html/classllvm_1_1StringRef.html

#5

You'll have to either write custom routine or use 3rd party library if you're dead set on avoiding string copy.

如果你想避免字符串拷贝，那么你必须编写自定义例程或使用第三方库。

You probably don't want to write atoi from scratch (it is still possible to make a bug here), so I'd advise to grab existing atoi from public domain or BSD-licensed code and modify it. For example, you can get existing atoi from FreeBSD cvs tree.

您可能不想从头编写atoi(这里仍然有可能出现bug)，因此我建议从公共域或bsd许可的代码中抓取现有的atoi，并修改它。例如，您可以从FreeBSD cvs树获得现有的atoi。

#6

If you run the function that often, I bet you parse the same number many times. My suggestion is to BCD encode the string into a static char buffer (you know it's not going to be very long, since atoi only can handle +-2G) when there's less than X digits (X=8 for 32 bit lookup, X=16 for 64 bit lookup) then place a cache in a hash map.

如果你经常运行这个函数，我打赌你会多次解析相同的数字。我的建议是BCD编码字符串为一个静态字符缓冲区(你知道它不会很长,因为atoi仅能处理+ 2 g)的数字小于X(X = 8 32位查找,X = 16 64位查找)将在一个散列映射缓存。

When you're done with the first version, you can probably find nice optimizations, such as skipping the BCD encoding entirely and just using X characters in the string (when length of string <= X) for lookup in the hash table. If the string is longer, you fallback to atoi.

当您完成了第一个版本时，您可能会发现一些很好的优化，比如完全跳过BCD编码，并且只使用字符串中的X字符(当string <= X的长度)用于在散列表中查找时。如果字符串比较长，则可以返回atoi。

Edit: ... or fallback instead of atoi to Jerry Coffin's solution, which is as fast as they come.

编辑:…或者是撤退，而不是对杰里·科芬的解决方案，这是最快的。

#1