C/C++ Grammar Note

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

1. 复制和别名有什么区别？

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

   如果要复制一个数组，应当使用已经过时的 memmove

2. 如何在 C 中返回多个数据项？

   A：可以使用随用随弃的结构体。示例代码

3. 数组可否在运行时动态分配内存空间？

   可以，参考问题 5。

4. 如何理解函数堆栈？

   • 使用 malloc 分配的内存并不位于栈中，而是在系统中称为堆的空间中

   • 函数帧：函数在内存中占据的空间，用于保存与这个函数有关的信息

5. 如何区分自动、静态和手工内存的区别？

   • 自动：很常见；如果不使用 static 关键字，在函数内部声明的所有变量都是自动变量；离开自己的作用域之后被销毁；可以在初始化时设置非常量值；

   • 在函数外部和函数内部使用 static 关键字初始化的变量都是静态变量；注意静态变量数据是在 main 函数启动之前被初始化的，因此所有初始化值都必须是常量，并且不需要计算；在启动时设置为 0;

   • 手工内存：涉及到 malloc 和 free 函数；程序员痛苦的根源；可以在运行时设置数组长度，可以改变长度，不能使用 sizeof 计算数组长度。

Pointer and Array

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

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

Question

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

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

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

但是当程序在代码中遇到 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 = π // wrong!
const double *cptr = π // 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

#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

非类型参数

1. 可以在模板中定义非类型参数，一个非类型参数表示一个值而非一个类型。

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

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

• 使用非类型模板

• 参数为 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

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 需要验证一个字符串是否为回文串，给出的字符串中存在空格和下划线等非字母字符，也存在大小写，但是不区分大小写，空字符串也是回文串。

我们的解决思路是，使用双指针分别从字符的开头和结尾处开始遍历整个字符串，相同则继续寻找，不相同直接返回 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, 给定一个字符串，要求分割该字符串，使得分割出来的子串都是回文串，返回所有可能的分割方案。

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

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

1. 递归实现

2. 前后双指针交换，该方法速度较快

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--]);
    }
}

代码详情可以参考这里

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并编译：

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