[CPP] String, Vector and Iterator

Library string type

A string is a variable-length sequence of characters. To use the string type, we must include the string header. Because it is part of the library, string is defined in the std namespace:

#include <string>
using std::string;

Defining and initializing strings

examples:

string s1; //default initialization; s1 is the empty string
string s2 = s1; //s2 is a copy of s1, but it is copy initialization
string s2(s1); //also the same as above. s2 is a copy of s1, but it is direct initialization
string s3 = "hiya" //s3 is a copy of the string literal
string s3("hiya"); //same as above
string s4(10, 'c'); //s4 is cccccccccc

operations on strings

read and write strings

int main(){
    string s;
    cin >> s;
    cout << s << endl;
    return 0;
}

The string input operator reads and discards any leading whitespace(e.g. spaces, newlines, tabs). It then reads characters until the next whitespace character is encountered.

So, if the input to this program is Hello World! (note leading and trailing spaces), then the output will be Hello with no extra spaces

Here, we want to get two strings, so we cin two strings. But the output does not contain any extra spaces, so “Hello World” became “HelloWorld”

using getline to read an entire line

Sometimes we do not want to ignore the whitespace in our input. In such cases, we can use the getline function instead of the >> operator. The getline function takes an input stream and a string. This function reads the give stream up to and string argument. After getline sees a newline, even if it is the first character in the input, it stops reading and returns.

string - empty and size operations

The empty function does what one would expect: It returns a bool indicating whether the string is empty.
The size member returns the length of a string.

The string::size_type type

It might be logical to expect that size returns an int. However, size returns a string::size_type value. This type requires a bit of explanation.
The string class-and most other library types-defines several companion types. These companion types make it possible to use the library types in a machine-independent manner. The type size_type is one of these companion types. To use the size_type defined by string, we use the scope operator to say that the name size_type is defined in the string class.
Admittedly, it can be tedious to type string::size_type. Under C++ 11 standard, we can ask the compiler to provide the appropriate type by using auto or decltype:

auto len = string.size(); //len has type string::size_type

Because size returns an unsigned type, it is essential to remember that
expressions that mix signed and unsigned data can have surprising results.
For example, if n is an int that holds a negative value, then s.size() < n will almost surely evaluate as true. It yields true because the negative value in n will convert to a large unsigned value.

If there is already size() in the expression, do not use int!!!(avoid conversion problem)

Comparing strings

The string class defines several operators that compare strings. These operators work by comparing the characters of the strings. The comparisons are case sensitive—upper- and lowercase versions of a letter are different characters.

If two strings have different lengths and if every character in the shorter string is equal to the corresponding character of the longer string, then the shorter string is less than the longer one
If any characters at corresponding positions in the two strings differ, then the result of the string comparison is the result of comparing the first character at which the strings differ

Dealing with the characters in a string

Often we need to deal with the individual characters in a string. We might want to check to see whether a string contains any whitespace, or to change the characters to lowercase, or to see whether a given character is present, etc.
This part of jobs is handled by a set of library functions called cctype header.

example: (take care the decltype and auto keywords used)

Why shouldn’t we use “+” between two string literals

Because C++ string literal is not the same as string in standard library. When you use “+”, either the left part or the right part of “+” should be a string(not literal)

Using a Range for to Change the Characters in a string

As we learned in java, range for (or for each loop) is read-only, which means it can not change value.
But using reference, we can change the value in for each loop

Library type vector

header file for using vector:

#include <vector>
using std::vector;

For class template like vector, we need to provide some extra information to show which class it will be instantiated to. For example:

vector<int> ivec; //ivec stores int object
vector<Sales_item> Sales_vec; //store Sales_item object
vector<vector<string>> file; //store a vector type

Defining and initializing vector

list initializing a vector

vector<string> articles = {"a", "an", "the"};

Creating a specified number of elements

vector<int> ivec(10, -1); //ten int element, each initialized to -1
vector<string> svec(10,"hi"); //ten strings; each element is "hi"

value initialization

We can usually omit the value and supply only a size. In this case the library creates a value-initialized element initializer for us. This library-generated value is used to initialize each element in the container. The value of the element initializer depends on the type of the elements stored in the vector.
If the vector holds elements of a built-in type, such as int, then the element initializer has a value of 0. If the elements are of a class type, such as string, then the element initializer is itself default initialized:

vector<int> ivec(10); // ten elements, each initialized to 0

List Initializer or Element Count?

vector<int> v1(10); //v1 has ten elements with value 0
vector<int> v2{10}; //v2 has one element with value 10
vector<int> v3(10,1); //v3 has ten elements with value 1
vector<int> v4{10,1}; //v4 has two elements 10 and 1

When we use parentheses( ), we are saying that the values we supply are to be used to construct the object.
When we use curly braces, {…}, we’re saying that, if possible, we want to list initialize the object.

add element to vector–push_back()

vector<int> v2;//we don't specify the element number here
for(int i = 0; i<100; i++){
    v2.push_back(i);
}

Starting with an empty vector and adding elements at run time is
distinctly different from how we use built-in arrays in C and in most other languages. In particular, if you are accustomed to using C or Java, you might expect that it would be best to define the vector at its expected size. In fact, the contrary is usually the case.

other operation on vector

• v.empty(); //check whether vector is empty
• v.size(); //return the number of elements in vector
• v[n]; //return a reference to the element at position n in vector

size_type

To use size_type, we must name the type in which it is defined. A vector type always includes its element type:

vector<int>::size_type; //ok
vector::size_type; //error

subscript operator

The subscript operator on vector (and string) fetches an existing
element; it does not add an element.

Iterator

Although we can use subscripts to access the characters of a string or the elements in a vector, there is a more general mechanism—known as iterators—that we can use for the same purpose.

Using iterators

Unlike pointers, we don’t use the address-of operator to obtain an iterator. Instead, types that have members that return iterators.

begin and end

The begin member returns an iterator that denotes the first element (or first character), if there is one:

auto b = v.begin(), e = v.end();
//b denotes the first element and e denotes one past the last element in v

The iterator returned by end is an iterator positioned “one past the end” of the associated container (or string). This iterator denotes a nonexistent element “off the end” of the container. It is used as a marker indicating when we have processed all the elements.

Iterator Operations

• *iter: returns a reference to the element denoted by the iterator iter;
• iter->mem: Dereference iter and fetches the memeber mem of iterator, same as (*iter).mem
• ++iter : the next element in iterator
• –iter

Iterator types

Just as we do not know the precise type of a vector or string size_type, we don’t know the precise type of iterator. Instead, as with size_type, the library types that have iterators define types named iterator and const_iterator that represent actual iterator types:

vector<int>::iterator it; //it can read and write vector<int> elements
string::iterator it2; //it2 can read and write characters in a string
vector<int>::const_iterator it3; //it3 can read but not write elements
string::const_iterator it4; //it4 can read but not write characters

If the object only need to read but not write, it is best to use const_iterator. To let us ask specifically for the const_iterator type, the new standard introduced two new functions named cbegin and cend:

auto it3 = v.cbegin(); //the type of it3 is vector<int>::const_iterator

now we can rewrite our for loop, the for loop now can read(iterate) through the string

Arithmetic Operations on Iterators

As an example, we can compute an iterator to the element nearest the
middle of a vector:

auto mid = v.begin()+v.end()/2;

Using Iterator Arithmetic

A classic algorithm that uses iterator arithmetic is binary search. A binary search looks for a particular value in a sorted sequence. It operates by looking at the element closest to the middle of the sequence. If that element is the one we want, we’re done. Otherwise, if that element is smaller than the one we want, we continue our search by looking only at elements after the rejected one. If the middle element is larger than the one we want, we continue by looking only in the first half. We compute a new middle element in the reduced range and continue looking until we either find the element or run out of elements.

Question?

In the binary search program, why did we write mid = beg + (end - beg) / 2; instead of mid = (beg + end) /2;?
Because the iterator of vector don’t define the + operator between the two iterators. beg + end is illegal.
We can only use the subtraction between the two iterators.