1. Standard library type string

1. Definition and initialization

    string s1;              // Default initialization, s1 is an empty string
    string s2 = s1;         // s2 is a copy of s1, note that s2 only has the same value as S1 and does not point to the same address
    string s3 = "hiya";     // s3 is a copy of the literal value of the string
    string s4(10, 'c');     // The content of s4 is "cccccccccc"

2. Operation on string

(1) getline reads a whole line

    string s;    
    getline(cin,s);

(2) string comparison

Support >, <, >=, <=, ==, ==,!= For all comparison operations, compare in dictionary order.

(3) Addition of two string objects

string s1 = "hello,  "", s2 = "world\n";
string s3 = s1 + s2; * The // s3 content is hello, world\n
s1 += s2;                               // s1 = s1 + s2

(4) Add literal values to string objects:

In addition, literal values and characters are converted to string objects, so direct addition is to concatenate these literal values:

string s1 = "hello", s2 = "world";      // There are no punctuation symbols in s1 and s2
string s3 = s1 + ", " + s2 + '\n';

When using string objects with literal values of characters and string literals in a single statement, you must ensure that at least one object on either side of each addition operator is a string:

string s4 = s1 + ", ";  // Correct: Add a string object to a literal value
string s5 = "hello" + ", "; // Error: Neither operand is a string

string s6 = s1 + ", " + "world";  // Yes, one operator for each addition operation is string
string s7 = "hello" + ", " + s2;  // Error: Literal values cannot be added directly. Operations are left to right

3. Processing characters in string objects

string objects can be treated as character arrays:

    string s = "hello world";

    for (int i = 0; i < s.size(); i ++ )
        cout << s[i] << endl;
    
    for (char c: s) cout << c << endl;

4. Common functions for manipulating string s

(1)find function

Basic Usage

string's find() function is used to find letters in Character string Position in.

find(str,position)

• str: the element to find

• Position: A position in the string that indicates that the specified element is found in the string starting at that position (no second parameter is filled in, default is found at the beginning of the string)

Returns the position of the target character (the first character is 0) and npos if no target character is found

Give an example

//Find the location of the target character
string s = "hello world!";
cout << s.find("e") << endl;
Output result: 1

//Target character not found
string s = "hello world!";
if (s.find("a") == s.npos) {
    cout << "not found" << endl;
}
Output results: not found

//Specify Find Location
string s = "hello world!";
cout << s.find("l",5) << endl;
Output result: 9

Extension Usage

Find the first and last occurrences of the target character

string s = "hello world!";
cout <<s.find_first_of("l") << endl;//Position of first occurrence
cout << s.find_last_of("l") << endl;//Last occurrence
 Output:
2
9

Reverse Lookup

string s = "hello world!";
cout << s.rfind("l") << endl;//That is, the first occurrence of "l" from back to front
 Output:
9

Usually, we can use this to indicate that substrings are not unique when a forward lookup does not have the same location as a reverse lookup.

Find where all substrings appear in the parent string

//Find all locations where flag appears in s.
	string s("hello world!");
    string flag="l";
    int position=0;
    int i=1;
    while((position=s.find(flag,position))!=string::npos)
    {
        cout<<"position  "<<i<<" : "<<position<<endl;
        position++;
        i++;
    }

Run result:
  position  1 : 2
  position  2 : 3
  position  3 : 9

2. STL

1. #include <vector>

Vectors are variable-length arrays that support random access and do not support O(1) insertion anywhere. In order to ensure efficiency, elements should generally be added or deleted at the end.

(1) Declaration

#Include <vector> //header file
vector<int> a;      // Equivalent to an int array with a long dynamic change
vector<int> b[233]; // An int array equivalent to the first dimension length 233 and the second dimension length dynamic change
vector<string>c     // Equivalent to a two-dimensional string array
struct rec{...};
vector<rec> d;      // Custom structure types can also be saved in vector s

(2) Iterators

Iterators are like "pointers" to STL containers and can be dereferenced with asterisk * operators.

An iterator declaration method for a vector s holding int s is:

vector<int>::iterator it;

vector's iterator is a Random Access Iterator, which adds and subtracts vectors from an integer and behaves like pointer movement. You can subtract the two iterators of the vectors, and the result is similar to pointer subtraction to get the distance between the corresponding subscripts of the two iterators.

(3) begin/end

The begin function returns an iterator that points to the first element in the vectors. For example, if a is a non-empty vector, *a.begin() works the same as a[0].

All containers can be thought of as a "front-closed-back-open" structure, and the end function returns the end of the vector s, which is the "boundary" that follows the nth element. a.end() and a[n] are both cross-border visits, where n = a.size().

The next two codes iterate through vector <int> A and output all its elements.

for (int i = 0; i < a.size(); i ++)
    cout << a[i] << endl;

for (vector<int>::iterator it = a.begin(); it != a.end(); it ++)
    cout << *it << endl;

(4) push_back() and pop_back()

a.push_back(x)  //Insert element x at the end of vector a.
a.pop_back()    //Delete the last element of vector a.

2. #include <set>

The header file set mainly consists of set and multiset containers, which are "ordered set" and "ordered multiple set". That is, the elements of the former cannot be duplicated, while the latter can contain several equal elements. The internal implementation of set and multiset is a red-black tree, and they support essentially the same functions.

(1) Declaration

set<int> s;
struct rec{...}; set<rec> s;  // Less than sign must be defined in structure rec
multiset<double> s;

(2) Iterators

The iterators for set and multiset are called "two-way access iterators". They do not support "random access". They support asterisk* dereferencing and only support ++ and--two arithmetic-related operations.

Set it as an iterator, for example set <int>:: iterator it;

If it ++, it points to the next element. Here, the "next" element refers to the element that ranks next to it in the result of sorting elements from small to large. Similarly, if it --, it will point to the element in the "previous" row.

(3) insert

s.insert(x)  //Inserts an element x into the set s with a time complexity of O(logn)O(logn).

In set, if an element already exists, it is not inserted repeatedly and has no effect on the state of the collection.

(4) find

s.find(x)   //Finds an element equal to x in the set s and returns an iterator pointing to that element.
//If it does not exist, s.end() is returned.
if(s.find(x)!=s.end())   //Determine if x is in s

(5) erase

If it is an iterator, s.erase(it) deletes from s the elements pointed to by iterator it with a time complexity of O(logn)O(logn).

Set x to be an element, s.erase(x) deletes all elements equal to x from s with a time complexity of O(k+logn)O(k+logn), where k k is the number of elements deleted.

s.erase(it)   //Delete the element pointed to by iterator it
s.erase(x)    //Delete x from s

(6) count

s.count(x) returns the number of elements in the set s equal to x, with a time complexity of O(k+logn)O(k+logn), where k k is the number of elements X.

s.count(x)    //Returns the number of x in s

(7) lower_bound/upper_bound

The usage of these two functions is similar to that of find, but the search conditions are slightly different and the time complexity is O(logn)O(logn).

s.lower_bound(x)    //Finds the smallest element greater than or equal to x and returns an iterator pointing to that element.
s.upper_bound(x)    //Finds the smallest element larger than x and returns an iterator pointing to that element.

3. #include <map>

The map container is a key-value mapping, and its internal implementation is a red-black tree with key as the key. Map keys and values can be of any type, where keys must define less than sign operators.

(1) Declaration

map<key_type, value_type> name;

//For example:
map<long, long, bool> vis;
map<string, int> hash;
map<pair<int, int>, vector<int>> test;

(2) size/empty/clear/begin/end

Similar to vector,set

(3) insert/erase

Similar to set, but with all parameters

pair<key_type, value_type>. 

(4) find

h.find(x)    //Find a tuple with key x in a map named h.

(5) Operator []

h[key]    //Returns a reference to the value of the key map

The time complexity is O(logn)O(logn).

The [] operator is the most attractive aspect of a map.

We can easily get the value of the key by h[key], or assign it to change the value of the key.

4. #include <queue>

Header file queue mainly includes circular queue and priority_priority Queue two containers.

(1) Declaration

queue<int> q;
struct rec{...}; queue<rec> q;                        //Less than sign must be defined in structure rec
priority_queue<int> q;                              // Big Root Heap
priority_queue<int, vector<int>, greater<int>> q;   // Small root heap
priority_queue<pair<int, int>>q;

(2) Circular queue

q.push(x)    // Insert from End of Queue
q.pop()     // Eject from Team Head
q.front()   // Return Queue Head Element
q.back()    // Return trailing elements

(3) Priority queue priority_queue

q.push()    // Insert elements into the heap
q.pop()     // Remove heap top elements
q.top()     // Query heap top elements (maximum)

5. #include <stack>

The header file stack contains a stack. Declare similar to previous containers

s.push(x)    // Insert to top of stack
s.pop()     // Pop-up top element

6. #include <deque>

A double-ended queue dequeue is a continuous linear storage space that supports efficient insertion or deletion of elements at both ends. It's like a combination of vectors and queues. Compared with vectors, it only takes O(1)O(1) time for deques to add or delete elements in the header; Compared to queue, dequeue supports random access like arrays.

a[i]                // Random Access
a.begin()/a.end()   // Return the deque head/tail iterator
a.front()/back()    // Queue Head/End Elements
a.push_back(x)      // Enter from the end of the team
a.push_front(x)     // Enter from the team leader
a.pop_back()        // Exit from the end of the team
a.pop_front()       // Get out of the team
a.clear()           // ClearQueue