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
复制和别名有什么区别?
示例代码 (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 = π // 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 (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 digitisalpha(c)
: letterisdigital(c)
: digitislower(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
=>
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
命令进行编译