C/C++ Grammar Note

weigaochen 6/11/2019 c/c++

The goal of new cpp aims at:

Make cpp a better language for systems programming and library building
Make cpp easier to teach and learn

# Pointer

overview

本章节启发自《C 程序设计新思维》中的指针章节

# Questions

复制和别名有什么区别？

示例代码 (opens new window) 可以看出，对于数组结构的赋值其实是创建了数组的一个别名，当复制被修改时，原数据也别修改。

如果要复制一个数组，应当使用已经过时的 memmove
如何在 C 中返回多个数据项？

A：可以使用随用随弃的结构体。示例代码 (opens new window)
数组可否在运行时动态分配内存空间？

可以，参考问题 5。
如何理解函数堆栈？
- 使用 malloc 分配的内存并不位于栈中，而是在系统中称为堆的空间中
- 函数帧：函数在内存中占据的空间，用于保存与这个函数有关的信息
如何区分自动、静态和手工内存的区别？
- 自动：很常见；如果不使用 static 关键字，在函数内部声明的所有变量都是自动变量；离开自己的作用域之后被销毁；可以在初始化时设置非常量值；
- 在函数外部和函数内部使用 static 关键字初始化的变量都是静态变量；注意静态变量数据是在 main 函数启动之前被初始化的，因此所有初始化值都必须是常量，并且不需要计算；在启动时设置为 0;
- 手工内存：涉及到 malloc 和 free 函数；程序员痛苦的根源；可以在运行时设置数组长度，可以改变长度，不能使用 sizeof 计算数组长度。

# Pointer and Array

意识到数组和指针其密不可分的关系，参考示例代码 2 (opens new window).

第 6 行体现了将成员 1 的地址取得，而后赋值给新指针，新数组可以包含 {2, 4, 6, 8} , 并通过下标访问。

Question

What is difference between int an_array[] and int *a_pointer ?

对于此问题，先研究 int an_array[32] 执行后会发生什么：

在栈上分配空间，足够容纳 32 个整数；
把 an_array 看做一个指针；
把这个指针和新分配的地址绑定。

但是当程序在代码中遇到 int *a_pointer 的时候，只会做一件事：

把 a_pointer 声明为指针。

a_pointer = malloc(32*sizeof(int));
a_pointer = an_array;

都是被允许的。

# Pointer and Const

与引用一样，也可以令指针指向常量或非常量；指向常量的指针 pointer to const 不能用于改变其所指对象的值。

想要存放常量对象的地址，只能使用指向常量的指针：

const double pi = 3.14;
double *ptr = &pi; // wrong!
const double *cptr = &pi; // right!

# main()

main () 函数的原型为：

int main(int argc, char** argv) or int main(int argc, char* argv[]) .

其中 argc 表示参数的数量， argv 数组为从下标 0 开始的数组，第 0 个参数一般为可运行的文件。

# Define Struct

There are many ways to define struct, what we should do is that chose a best way to solve problem.

Example 1

struct Point { double x, y; };
double dist(struct Point a, struct Point b){
    return hypot(a.x-b.x, a.y-b.y);
}

Example2

typedef struct { double x, y; } Point;
double dist(Point a, Point b){
    return hypot(a.x-b.x, a.y-b.y);
}

As you can see from the comparison, Example 2 is better, which use typedef struct { define; }struct name; to define.

# Lvalue and Rvalue

int x = 0;  //x is lvalue
int* p = &++x;  //++x is lvalue, can use &
++x = 10;
p = &x++;   //x++ returns a temperate value,, error!

lvalue can be assigned a value or use '&', rvalue can't.

more information about rvalue reference (opens new window)

#include <iostream>
#include <utility>

int i = 101, j = 101;

int foo(){ return i; }
int&& bar(){ return std::move(i); }
void set(int&& k){ k = 102; }
int main()
{
    foo();
    std::cout << i << std::endl;
    set(bar());
    std::cout << i << std::endl;
}
/*output:
101
102*/

# OOP

Q: What is different between difination and declaration?

# Usage

# member initializer list

class Point {
private:
    const float x,y;
    Point(float xa = 0.0, float ya =0.0) : y(ya), x(xa) {}
};

# Templates

# Defination

函数模板的例子：

// 方便阅读，其实可以写成一行
// template <typename T> int compare(const T &v1, const T &v2)
template <typename T>
int compare(const T &v1, const T &v2)
{
    // 使用 less<T> 似的类型无关和可移植
    if (less<T> (v1, v2)) return -1;
    if (less<T> (v2, v1)) return -1;
    return 0;
}

// compare(0, 1)

当我们调用一个函数模板时，编译器通常用函数实参来为我们推断模板实参。

在模板参数列表中， typename 和 class 含义相同，可以互换使用。

the format for declaring function template with type parameters is:

template <class identifier> function_declaration;

template <typename identifier> function_declaration;

its use is indistinct, so both expressions have exactly the same meaning.

# Nontype Parameter

非类型参数

可以在模板中定义非类型参数，一个非类型参数表示一个值而非一个类型。
非类型参数必须是常量表达式，从而允许编译器在编译时实例化模板；当一个模板被实例化时，非类型参数被一个用户提供的或编译器推断出的值所代替。

一个最典型的应用是处理任意大小数组的 print 函数 (opens new window):

使用非类型模板
参数为 Arr const &arr (Arr 类型的 arr 引用)

# String

# memset()

memset() is used to fill a block of memory with a particular value, in <string.h> .

Example 1: 将数组中每个元素设置为 0

// C program to demonstrate working of memset()
#include <stdio.h>
#include <string.h>

int main()
{
    int n = 10;
    int arr[n];

    // Fill whole array with 0
    memset(arr, 0, n*sizeof(arr[0]));
}

bug avoiding

注意可以将 memset 的第二个参数设置为 0 或 -1 其他的可能不 work

Example 2: 字符串替换

// C program to demonstrate working of memset()
#include <stdio.h>
#include <string.h>

int main()
{
    char str[50] = "GeeksForGeeks is for programming geeks.";
    printf("\nBefore memset(): %s\n", str);

    // Fill 8 characters starting from str[13] with '.'
    memset(str + 13, '.', 8 * sizeof(char));  

    printf("After memset(): %s", str);
    return 0;

    //Before memset(): GeeksForGeeks is for programming geeks.
    //After memset(): GeeksForGeeks........programming geeks.
}

# strchr()

Prototype: const char * strchr ( const char * str, int character );

Functions: It looks for the first occurrence of a character in a string, and returns a pointer to the matching character in the string. If the string doesn’t contain the character, strchr() returns NULL .

int is_separator(int c) {
  return isspace(c) || c == '\0' || strchr(",.()+-/*=~%<>[];", c) != NULL;
}

官方示例：

/* strchr example */
#include <stdio.h>
#include <string.h>

int main()
{
    char str[] = "This is a sample string";
    char *pch;
    pch = strchr(str, 's');
    while (pch != NULL)
    {
        printf("found at %d\n", pch - str + 1);
        pch = strchr(pch + 1, 's');
    }
    return 0;
}
//Looking for the 's' character in "This is a sample string"...
//found at 4
//found at 7
//found at 11
//found at 18

# strrchr()

Prototype: const char * strrchr ( const char * str, int character );

Locate last occurrence of character in string, Returns a pointer to the last occurrence of character in the C string str. The terminating null-character is considered part of the C string. Therefore, it can also be located to retrieve a pointer to the end of a string.

官方示例：

/* strrchr example */
#include <stdio.h>
#include <string.h>

int main()
{
    char str[] = "This is a sample string";
    char *pch;
    pch = strrchr(str, 's');
    printf("Last occurence of 's' found at %d \n", pch - str + 1);
    return 0;
}
//Last occurrence of 's' found at 18

Example : 检测文件类型

char *ext = strrchr(E.filename, '.');

# strncmp and strcmp

int strncmp(const char *str1, const char *str2, size_t n) 把 str1 和 str2 进行比较，最多比较前 n 个字节
int strcmp(const char *str1, const char *str2) 把 str1 所指向的字符串和 str2 所指向的字符串进行比较

# Library string Type

Also could be see in Books - C++ Prime - String

# getline(input stream, string)

int main() {
    string line;
    while (getline(cin, line))
        cout << line << endl;
    return 0;
}

# string::size_type

s.back : (c++ 11) access last character.
s.begin()
s.end()
s.size()

A s.size() example:

string line;
while (getline(cin, line))
    if (line.size() >80)
        cout << line << endl;

In this case, function getline() returns string::size_type type(not int or unsigned) which defined in the string class.

bug avoiding

A example that s.size() < n will return true if n is an int that holds a negative value, it yields true because the negative value in n will convert to a large unsigned value.

# string for

This is an example use a range for and the ispunct function to count the number of punctuation characters in a string:

#include <iostream>
#include <string>
#include <cctype>
using namespace std;
int main(int argc, char const *argv[])
{
    string str("some string!!!@#!");
    decltype(str.size()) punct_cnt = 0;
    for (auto c : str)
        if (ispunct(c))
            ++punct_cnt;
    cout << punct_cnt << " punctuation characters in" << str << endl;
    return 0;
}
//6 punctuation characters insome string!!!@#!

# Charater Type

Sometimes we need to process only a specific character, theses functions helps us change the characteristics of a character. These functions are defined in the cctype headers.

isalnum(c) : true if c is a letter or digit
isalpha(c) : letter
isdigital(c) : digit
islower(c)/isupper(c) , tolower(c)/toupper(c)
isspace(c) : true if c is whitespace(a space, tab, vertical tab, return, newline or formfeed)

This is Python String functions (opens new window)

# toupper()

This is an example to use function toupper() . Note that If we want to change the value of the characters in a string, we must define the loop variable as a reference type.

int main(int argc, char const *argv[])
{
    string str("This is a string!");
    for(auto &c: str){
        c = toupper(c);
    }
    cout << str << endl;
    return 0;
}

# Using Subscript for Iteration

The string subscript oprator ([ ]) takes a string::size_type value, that denotes the position of the character we want to access, the operator returns a reference to the character at the given position.

for (decltype(s.size() ) index = 0;
    index != s.size() && !isspace(s[index]); ++index)
        s[index] = toupper(s[index]);
//some time -> SOME time

# Additional string Operations

# Other ways to construct strings

const char *cp = "Hello World!"; //null-terminated array
string s1(cp); // s1 == "Hello World!"
string s2(cp, 6, 20); //ok, copy only to end of s1
string s3(cp, 18); //exception: out_of_range

Note that when we create a string from a const char* , the array to which the pointer points must be null terminated.

# substr

We can pass substr an optional starting position and couont:

s.substr(pos, n)
//default pos is 0
string s("Hello World!");
string s1 = s.substring(6);
string s2 = s.substring(7, 12);

# insert and replace

Example: Write a function that takes three strings, s, oldVal, and newVal. Using iterators, and the insert and erase functions replace all instances of oldVal that appear in s by newVal.Test your function by using it to replace common abbreviations, such as “tho” by “though” and “thru” by “through”.

auto replace_with(string &s, string const &oldVal, string const &newVal)
{

    for (auto cur = s.begin(); cur <= s.end() - oldVal.size();)
    {
        if (oldVal == string{cur, cur + oldVal.size()})
        {
            cur = s.erase(cur, cur + oldVal.size());
            cur = s.insert(cur, newVal.begin(), newVal.end());
            cur += newVal.size();
        }
        else
        {
            ++cur;
        }
    }
}

# Array and string

copy an array:

#include<string.h>
memcpy(b, a, sizeof(int)*k)
memcpy(b, a, sizeof(a))

reset an array:

#include<string.h>
memset(a, 0, sizeof(a))

# String in Leetcode

# Get All Substring

对于字符串运算中，获得所有的子串并进行操作是很常见的问题，故将代码总结如下：

def getAllSubstring(s):
    n = len(s)
    return [s[i:j + 1] for i in range(n) for j in range(i, n)]

generator 版本：

def getAllSubstring(s):
    length = len(s)
    for i in range(length):
        for j in range(i + 1, length + 1):
            yield(s[i:j])

print([_ for _ in getAllSubstring('aaab')])

# Longest Palindrome

判断一个字符串是否为回文串，比较常用的方法为动态规划判定法：

def longestPalindrome(s):
    dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            dp[i][j] = s[i] == s[j] and (j - i < 3 or dp[i + 1][j - 1])

            if dp[i][j] and (res == '' or j - i + 1 > len(res)):
                res = s[i:j+1]

    return res

上述代码为求最长回文子串的代码，核心状态转移公式为第 5 行重点部分，如果是回文子串的话，则对应的 dp[i][j] 的值为 1.

考虑这个示例：如果我们已经知道是回文，那么很明显，一定是回文，因为它的左首字母和右尾字母是相同的。

formula

, if 是回文串。

, otherwise.

=> = { and }

so,

= ( == )

经过优化后，有一种简单的 Python 解法：

class Solution:
    def longestPalindrome(self, s):
        res = ''
        for i in range(len(s)):
            res = max(self.helper(s, i, i), self.helper(
                s, i, i + 1), res, key=len)
        return res

    def helper(self, s, l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return s[l + 1:r]

print(Solution().longestPalindrome('cbbd'))

# Is Palindrome

又比如 LC125 (opens new window) 需要验证一个字符串是否为回文串，给出的字符串中存在空格和下划线等非字母字符，也存在大小写，但是不区分大小写，空字符串也是回文串。

我们的解决思路是，使用双指针分别从字符的开头和结尾处开始遍历整个字符串，相同则继续寻找，不相同直接返回 false .

注意到使用的内置 Python String 函数有：

lower() : 转化字符串中的所有大写为小写，对应的为 upper()
isalnum() : 判断是否字符或数字
replace(old, new, [,max]) : 替换字符串，如果 max 指定，则最多不超过 max 次

我们也可以使用 Python 中自带的 translate() 方法构造一个字典，该方法速度较快，具体的解析可以参考 POST Python: str.maketrans()

def isPalindrome(self, s: str) -> bool:
    s = s.translate(str.maketrans('', '', string.punctuation))
    s = s.lower()
    s = s.replace(' ', '')
    return (s == s[::-1])

也可以使用正则表达式：

import re
s = re.sub(r'[^0-9a-z]','', s.lower())

或者使用 filter() :

s = filter(s.isalnum(), s.lower())
# return a filter object, we could convert it to list

# Palindrome Partitioning

这道题目是 LC 131 (opens new window), 给定一个字符串，要求分割该字符串，使得分割出来的子串都是回文串，返回所有可能的分割方案。

# Reverse Numebr

逆序一个数，一般的 C++ 操作为：

int sum = 0;
while(x) {
    sum = sum  * 10 + x % 10;
    x /= 10;
}
// sum is reversed x

而 Python 只需要使用 str(x)[::-1] .

# Reverse String

将一个字符串翻转，可以实现的方法有：

递归实现
前后双指针交换，该方法速度较快

void helper(int index, string str)
{
    if (index >= str.length())
    {
        return;
    }
    helper(index + 1, str);
    putchar(str[index]);
}
void printReverse(string str)
{
    helper(0, str);
}

void reverseStringInplace(vector<char> &s)
{
    int start = 0, end = s.size() - 1;
    while (start < end)
    {
        swap(s[start++], s[end--]);
    }
}

代码详情可以参考这里 (opens new window)

# Vector

# library vector type

The push_back() operation takes a value and "pushes" and values as a new last element onto the "back" of the vector.

Example: Read a sequence of words from cin and store the values a vector. After you've read all the words, process the vector and change each word to uppercase. Print the transformed elements, eight words to a line.

int main(int argc, char const *argv[])
{
    vector<string> vec;
    for (string word; cin >> word; vec.push_back(word))
        ;
    //standard store operation
    for (auto &str : vec)
        for (auto &c : str)
            c = toupper(c);

    for (string::size_type i = 0; i != vec.size(); ++i)
    {
        if (i != 0 && i % 8 == 0)
            cout << endl;
        cout << vec[i] << " ";
    }
    cout << endl;
    return 0;
}

# Iterators

# toupper example

Example: capitalize the first character of a string using an iterator of a subscript:

string s("some string");
if (s.begin() != s.end()) //make sure s is empty
{
    auto it = s.begin();
    *it = toupper(*it);
}
//Some string

As with pointers, we can dereference an iterator to obtain the element denoted by an element.

string s("some string");
for( auto it = s.begin(); it != s.end() && !isspace(*it); ++it)
    *it = toupper(*it);
//SOME string

# twice iterator value

Example: write a program to create a vector with ten int elements. Using an iterator, assign each element a value that is twice its current value. Test your program by printing the vector.

#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

int main(int argc, char const *argv[])
{
    // vector<int> v{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    vector<int> v;
    for (int i = 0; i < 10; i++)
        v.push_back(i);
    //2 ways to init a vector with ten int element
    for (auto it = v.begin(); it != v.end(); ++it)
        *it *= 2;
    for (auto i : v)
        cout << i << " ";
    cout << endl;
    return 0;
}

# Find in iterator

Example(9.4): write a function that takes a pair of iterators to a vector and an int value. Look for the value in the range and return an iterator to the requested element:

#include <iostream>
#include <vector>
using namespace std;

auto contains(vector<int>::const_iterator first, vector<int>::const_iterator last, int value)
{
    for (; first != last; ++first)
    {
        if (*first == value)
            return first;
    }
    return last;
}

int main(int argc, char const *argv[])
{
    vector<int> v{1, 2, 3, 4, 5, 7, 8, 9};
    auto find_result = contains(v.begin(), v.end(), 9);
    cout << *find_result << endl;
    return 0;
}

# Makefile

# Example

My Text editor MAKEFILE :

kilo: kilo.c
        $(CC) kilo.c -o kilo -Wall -Wextra -pedantic -std=c99

# CMake

A CMakeLists.txt file example:

# CMake 最低版本号要求
cmake_minimum_required (VERSION 2.8)

# 项目信息
project (Demo1)

# 指定生成目标
add_executable(Demo main.cc)

在 Linux 平台下使用 CMake 生成 Makefile 并编译：

编写 CMake 配置文件 CMakeLists.txt
执行命令 cmake PATH 或者 ccmake PATH 生成 Makefile 。其中， PATH 是 CMakeLists.txt 所在的目录
使用 make 命令进行编译

Chener丶

C/C++ Grammar Note

C/C++ Grammar Note

# Pointer

# Questions

# Pointer and Array

# Pointer and Const

# main()

# Define Struct

# Lvalue and Rvalue

# OOP

# Usage

# member initializer list

# Templates

# Defination

# Nontype Parameter

# String

# memset()

# strchr()

# strrchr()

# strncmp and strcmp

# Library string Type

# getline(input stream, string)

# string::size_type

# string for

# Charater Type

# toupper()

# Using Subscript for Iteration

# Additional string Operations

# Other ways to construct strings

# substr

# insert and replace

# Array and string

# String in Leetcode

# Get All Substring

# Longest Palindrome

# Is Palindrome

# Palindrome Partitioning

# Reverse Numebr

# Reverse String

# Vector

# library vector type

# Iterators

# toupper example

# twice iterator value

# Find in iterator

# Makefile

# Example

# CMake