CODEWITHSUNDEEP
c++
najm
najm

Reputation: 894

How is std::stoi implemented?

Most everyday use cases have already been converted into a function available within the standard library. However, I'd like to know how some of them work behind the scenes. Like what is the actual code behind std::stoi ?

Upvotes: 2

Views: 6002

Answers (4)

ericssonl07
ericssonl07

Reputation: 11

To convert a string (assuming all of its characters are integers from 0 to 9):

  1. You must get the length of the string.
  2. Iterate through the string (your choice for forwards or backwards) and add each power to a result variable.

I would start with a multiplier variable and a result variable: int multiplier = 1, result = 0, then I would get the string length using std::string::length function. Looping backward through the string, I would multiply each element by the multiplier and add it to the result. Be sure that when you're accessing the char you should subtract the ASCII value for the char 0. This can be done either by subtracting 48, or if you don't want to look up the ASCII value you can just enclose 0 in single brackets. For example, if you don't perform this conversion from char to int, then accessing the character '1' will cause the program to read 49, which is no good. As for the multiplier, multiply it by 10 at the end of each iteration of the loop.

The reason I iterate from the back is to avoid using the pow() function which uses double/float. I find it simpler, but it's your choice. Of course, you could also avoid pow() by manually making a loop multiplying by 10 for the same amount of times as the length of the string, but then it's a little less efficient.

Here is a simple implementation that could be used:

#include <string>
#include <iostream>

int stoi(std::string s) {
  int multiplier = 1, result = 0;
  for (int i = s.length() - 1; i >= 0; i--) {
    result += multiplier * (s[i] - '0');
    multiplier *= 10;
  }
  return result;
}

int main() {
  std::cout << stoi("1235") + 1;
  return 0;
}

If you run this program, it should output 1236, as the string "1235" has been converted into an integer.

Of course, this is just my own implementation; if you want the official one, then this article contains some information about that.

Upvotes: 0

Peter Johnson
Peter Johnson

Reputation: 1

It's a reference to strtoi, but I assume you want an actual explanation as to how it works. It's actually quite simple. Steps:

  1. Find maximum multiplier (exp(base, strlen(number)-1)
  2. Run a for loop over the string and multiply it by the multiplier
  3. Divide the multiplier by the base each iteration

Implementation of strtoi in C:

#include <string.h>

int ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

int charToDigit(char ch) {
    switch (ch) {
        case '0':
            return 0;
            break;
       case '1':
            return 1;
            break;
        case '2':
            return 2;
            break;
        case '3':
            return 3;
            break;
        case '4':
            return 4;
            break;
        case '5':
            return 5;
            break;
        case '6':
            return 6;
            break;
        case '7':
            return 7;
            break;
        case '8':
            return 8;
            break;
        case '9':
            return 9;
            break;
        default:
            throw "0-9";
            break;
    }
};

int stoi(const char* string) {
    int basenum = 0;
    int pos = ipow(10, strlen(string)-1);
    const int len = strlen(string);

    // first is biggest, pos
    for (int i = 0; i<len; i++) {
        basenum += charToDigit(string[i])*pos;
        pos /= 10;
    };
    return basenum;
};

Upvotes: 0

2785528
2785528

Reputation: 5566

I'd like to know how some of them work behind the scenes. Like what is the actual code behind std::stoi ?

I think you can find the 'actual' code by doing a search similar to:

  • On Ubuntu, my makefile creates a .depends file with:

    g++-5 -m64 -O3 -ggdb -std=c++14 -Wall -Wextra -Wshadow -Wnon- virtual-dtor -pedantic -Wcast-align -Wcast-qual -Wconversion -Wpointer-arith -Wunused -Woverloaded-virtual -O0 -M *.cc > .depends

    (I try to keep the compiler options for this command matching my normal compile.)

  • In a browser, I look at

    http://en.cppreference.com/w/cpp/string/basic_string/stol

    to identify that

    std::stoi is included from std::basic_string (at top of page)

  • In my editor, (or) using grep, I search through the .depends file for "basic_string"

    grep --color -nH -e "basic_string" .depends

    grep reports the string 214 times in my current depends file, which changes size when I change code.

    Example of one report:

    .depends:14105: /usr/include/c++/5/bits/basic_string.h \

  • In my editor, I open the indicated file

    "/usr/include/c++/5/bits/basic_string.h",

    then search for "stoi", which appears to exist only twice.

    This indicates v5 of the compiler.

I think you should be able to do a similar search on your system.

Good luck.

Upvotes: 1

Pete Becker
Pete Becker

Reputation: 76315

The most straightforward way to do it is to call the appropriate C function, in this case strtol, check what happened and throw appropriate exceptions if it failed, and then return the result.

Upvotes: 3

Related Questions