new features in c++14

From : wiki

New language features[edit]

These are the features added to the core language of C++14.

Function return type deduction[edit]

C++11 allowed lambda functions to deduce the return type based on the type of the expression given to the return statement. C++14 provides this ability to all functions. It also extends these facilities to lambda functions, allowing return type deduction for functions that are not of the form return expression;.[3]

c++允许 lambda 表达式根据返回值表达式推测返回值类型, c++14将其范围提升到了所有函数.

(后面这句我不明白它是什么意思)

In order to induce return type deduction, the function must be declared with auto as the return type, but without the trailing return type specifier in C++11:

为了引进返回值推测, 需要在声明时在返回值类型上带上 auto 关键字. 而不需要尾随返回值说明符.

1

auto DeduceReturnType();   // Return type to be determined.

If multiple return expressions are used in the function’s implementation, then they must all deduce the same type.[4]

如果函数实现中存在多个返回值表达式, 它们必须被能被推测为一种类型.

Functions that deduce their return types can be forward declared, but they cannot be used until they have been defined. Their definitions must be available to the translation unit that uses them.

返回值类型推导可以前向声明. 但是直到被定义时才能使用. 定义必须能被翻译单元使用.

Recursion can be used with a function of this type, but the recursive call must happen after at least one return statement in the definition of the function:[4]

递归函数也可以使用返回值推导, 但是必须在至少一个返回语句之后使用.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

auto Correct(int i)
{
  if (i == 1)
    return i;             // return type deduced as int

  return Correct(i-1)+i;  // ok to call it now
}

auto Wrong(int i)
{
  if (i != 1)
    return Wrong(i-1)+i;  // Too soon to call this. No prior return statement.

  return i;               // return type deduced as int
}

Alternate type deduction on declaration[5]

In C++11, two methods of type deduction were added. auto was a way to create a variable of the appropriate type, based on a given expression. decltype was a way to compute the type of a given expression. However, decltype and auto deduce types in different ways. In particular, auto always deduces a non-reference type, as though by using std::decay, while auto&& always deduces a reference type. However, decltype can be prodded into deducing a reference or non-reference type, based on the value category of the expression and the nature of the expression it is deducing:[3]

在 c++11, 引进了两种类型推导. auto 和 decltype auto 总是推导出非引用类型, decltype 则推导出完整的类型.

1
2
3
4
5
6
7
8

int   i;
int&& f();
auto          x3a = i;     // decltype(x3a) is int
decltype(i)   x3d = i;     // decltype(x3d) is int
auto          x4a = (i);   // decltype(x4a) is int
decltype((i)) x4d = (i);   // decltype(x4d) is int&
auto          x5a = f();   // decltype(x5a) is int
decltype(f()) x5d = f();   // decltype(x5d) is int&&

C++14 adds the decltype(auto) syntax. This allows auto declarations to use the decltype rules on the given expression.

c++ 增加了 decltype(auto) 语法, 这使 auto 声明可以在指定表达式上使用 decltype 规则.

The decltype(auto) syntax can also be used with return type deduction, by using decltype(auto) syntax instead of auto for the function’s return type deduction.[4]

decltype(auto) 语法还可以在返回值类型推导上使用.

Relaxed constexpr restrictions[edit]

C++11 introduced the concept of a constexpr-declared function; a function which could be executed at compile time. Their return values could be consumed by operations that require constant expressions, such as an integer template argument. However, C++11 constexpr functions could only contain a single expression that is returned (as well as static_asserts and a small number of other declarations).

c++引进了常量声明函数(一个可以在编译期执行的函数). 他么的返回值可以被常量表达式使用. 然而, c++11 常量表达式函数只能包含单个返回的表达式

C++14 relaxes these restrictions. Constexpr-declared functions may now contain the following:[3]

c++14 取消了这些限制, 常量表达式函数可以包含以下:

• Any declarations except:

  • static or thread_local variables.

    staic 或 thread_local 变量.

  • Variable declarations without initializers.

    没有初始化的变量声明(???)

• The conditional branching statements if and switch.

  if 和 switch 条件语句

• Any looping statement, including range-based for.

  任何循环语句, 包括基于循环的 for

• Expressions which change the value of an object if the lifetime of that object began within the constant expression function. This includes calls to any non-const constexpr-declared non-static member functions.

  可更改开始于常量表达式函数的对象的值. 这包括任何对非常属性, 常量表达式定义, 非静态成员函数的调用.

goto statements are forbidden in C++14 relaxed constexpr-declared functions.

Also, C++11 stated that all non-static member functions that were declared constexpr were also implicitly declared const, with respect to this. That has since been removed; non-static member functions may be non-const.[6] However, per the restrictions above, a non-const constexpr member function can only modify a class member if that object’s lifetime began within the constant expression evaluation.

C++11规定所有非静态, 被 constexpr 声明的成员函数是隐式声明为 const 的. 这同样也被移除了, 非静态成员函数可以是 non-const 的. 然而, 根据上面的限制, 一个 non-const constexpr 的成员函数只能更改对象生命周期随常量表达式求值开始的对象的成员(???)

(我在其他文档中并未看到具体的关于更改值的介绍, 我简单理解的话, constexpr 现已可以支持循环和分支语句, 并且可以包含 static 和 thread_local 变量)

Variable templates[edit]

In prior versions of C++, only functions, classes or type aliases could be templated. C++14 now allows the creation of variables that are templated. An example given in the proposal is a variable pi that can be read to get the value of pi for various types (e.g., 3 when read as an integral type; the closest value possible with float, double or long double precision when read as float, double or long double, respectively; etc.).

在之前版本的 C++ 中, 类/类型别名可以模板化, C++14 允许创建变量模板.

The usual rules of templates apply to such declarations and definitions, including specialization.[7][8]

1
2
3
4
5
6

template<typename T>
constexpr T pi = T(3.141592653589793238462643383);

// Usual specialization rules apply:
template<>
constexpr const char* pi<const char*> = "pi";

Aggregate member initialization[edit]

C++11 added member initializers, expressions to be applied to members at class scope if a constructor did not initialize the member itself. The definition of aggregates was changed to explicitly exclude any class with member initializers; therefore, they are not allowed to use aggregate initialization.

C++14 relaxes this restriction,[3] allowing aggregate initialization on such types. If the braced init list does not provide a value for that argument, the member initializer takes care of it.[9]

(我不明白说的什么, 成员初始化不是 C++11 就有的么?)

Binary literals[edit]

Numeric literals in C++14 can be specified in binary form.[3] The syntax uses the prefixes 0b or 0B. The syntax is also used in other languages e.g. Java, C#, Swift, Go, Scala, Ruby, Python, OCaml, and as an unofficial extension in some C compilers since at least 2007.[10]

Digit separators[edit]

In C++14, the single-quote character may be used arbitrarily as a digit separator in numeric literals, both integer literals and floating point literals.[11] This can make it easier for human readers to parse large numbers through subitizing.

auto integer_literal = 1’000’000;
auto floating_point_literal = 0.000’015’3;
auto binary_literal = 0b0100’1100’0110;
auto silly_example = 1’0’0’000’00;

C++14中, 单引号专用于整数/浮点数表示, 使人看起来可以更加清晰(woo, 真是个人性化的功能)

Generic lambdas[edit]

In C++11, lambda function parameters need to be declared with concrete types. C++14 relaxes this requirement, allowing lambda function parameters to be declared with the auto type specifier.[7]

在 C++11 中, lambda 函数参数声明必须具有具体的类型, C++14 放松了这个要求, 允许 lambda 函数参数使用 auto 关键字声明, 如下:

1

auto lambda = [](auto x, auto y) {return x + y;};

Concerning auto type deduction, generic lambdas follow the rules of template argument deduction (which are similar, but not identical in all respects[*clarification needed*]). The code above is equivalent to this:[12]

关于 auto 类型推导, 泛型 lambdas 遵循模板参数推导原则. 上述代码等同于以下:

(其实也证实了, 与其说是匿名函数, 不如说是带 () 重载的匿名类)

1
2
3
4
5

struct
{
  template<typename T, typename U>
    auto operator()(T x, U y) const {return x + y;}
} lambda{};

Generic lambdas are essentially templated functor lambdas.

泛型 lambdas 是更高效的函数模板

Lambda capture expressions[edit]

C++11 lambda functions capture variables declared in their outer scope by value-copy or by reference. This means that value members of a lambda cannot be move-only types.[13] C++14 allows captured members to be initialized with arbitrary expressions. This allows both capture by value-move and declaring arbitrary members of the lambda, without having a correspondingly named variable in an outer scope.[7]

C++11 在其所在作用域中按值/引用捕获变量, 这意味着 lambda 成员的值不能是 move-only 类型. C++14 循序被捕获变量以任意形式初始化. 这使所有捕获可以值/移动, 以及声明任意的 lambda 成员, 而不需要在外层作用域中有对应的已命名成员.

This is done via the use of an initializer expression:

1

auto lambda = [value = 1] {return value;};

The lambda function lambda returns 1, which is what value was initialized with. The declared capture deduces the type from the initializer expression as if by auto.

声明捕获像 auto 一样推导初始化表达式.

This can be used to capture by move, via the use of the standard std::move function:

还可以用于捕获移动语义(赞啊 -v- )

1
2

std::unique_ptr<int> ptr(new int(10));
auto lambda = [value = std::move(ptr)] {return *value;};

The attribute [[deprecated]][edit]

The deprecated attribute allows marking an entity deprecated, which makes it still legal to use but puts users on notice that use is discouraged and may cause a warning message to be printed during compilation. An optional string literal can appear as the argument of deprecated, to explain the rationale for deprecation and/or to suggest a replacement.

deprecated 属性可以标记一个整体为’废弃的’, 继续使用这个整体是合法的, 但是用户会在编译时收到一个警告.

deprecated 可以增加字符串文本, 用作警示语.

1
2
3
4
5
6
7
8
9
10
11
12

[[deprecated]] int f();

[[deprecated("g() is thread-unsafe. Use h() instead")]]
void g( int& x );

void h( int& x );

void test()
{
  int a = f(); // warning: 'f' is deprecated
  g(a); // warning: 'g' is deprecated: g() is thread-unsafe. Use h() instead
}

(在 gcc (Debian 6.3.0-18+deb9u1) 6.3.0 20170516 版本下, 对于类的支持有所不足)

New standard library features[edit]

Shared mutexes and locking[edit]

C++14 adds a shared timed mutex and a companion shared lock type.[14][15]

C++14 增加了共享互斥锁, 以及他的’伴侣’共享锁类型.

(这里有点不好说, mutex 本身是一把锁, 而 lock 也是锁的意思, 不过是加锁, lock(mutex), emm, 应该是这意思)

Heterogeneous lookup in associative containers[edit]

The C++ Standard Library defines four associative container classes. These classes allow the user to look up a value based on a value of that type. The map containers allow the user to specify a key and a value, where lookup is done by key and returns a value. However, the lookup is always done by the specific key type, whether it is the key as in maps or the value itself as in sets.

C++ 标准库定义了四种关联的容器类, 这些类型使用户可以检查基于该值类型的值. 然而, 检查总是需要指定类型来完成 (??? 卧槽 你想干嘛???)

C++14 allows the lookup to be done via an arbitrary type, so long as the comparison operator can compare that type with the actual key type.[16] This would allow a map from std::string to some value to compare against a const char* or any other type for which an operator<overload is available. It is also useful for indexing composite objects in a std::set by the value of a single member without forcing the user of find to create a dummy object (for example creating an entire struct Person to find a person by name).

C++14 允许检查可以经由任意类型完成, 只要对比操作可以和正确的键类型对比. 这使 map<std::string>可以和 const char* 类型的值或其他有有效 < 重载的操作符的类型(为什么一定是 < ? > 它不香么?)

当要检查一个集合中的复合类型时, 不需要创建一个复杂的复合类型也可以检索 (比如: 检索 struct person, 可以使用他的名字, 而并不需要创建一个 person 对象)

To preserve backwards compatibility, heterogeneous lookup is only allowed when the comparator given to the associative container allows it. The standard library classes std::less<> and std::greater<> are augmented to allow heterogeneous lookup.[17]

为了保持向后兼容性, heterogeneous 检查只在关联的容器允许对比器时才适用. 标准库 std::less<>, std::greater<> 被 heterogeneous 检查接纳 (诶, 我不知道这该怎么写…)

(这是我在网上找到的代码, 其中两个包含 thread::id 的重载缺一不可, 也就是说编译器都会用到)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

struct ThreadCmp {
  using is_transparent = void;
  // Regular overload.
  bool operator()(const std::thread& a, const std::thread& b) const {
    return a.get_id() < b.get_id();
  }
  // Transparent overloads
  bool operator()(const std::thread& a, std::thread::id b) const {
    return a.get_id() < b;
  }
  bool operator()(std::thread::id a, const std::thread& b) const {
    return a < b.get_id();
  }
  //bool operator()(std::thread::id a, std::thread::id b) const {
  //  return a < b;
  //}
};

int main() {
    std::set<std::thread, ThreadCmp> threads;
    // Can't construct an instance of `std::thread` with the same id, just to do the lookup.
    // But we can look up by id instead.
    std::thread::id id = this_thread::get_id();;
    auto it = threads.find(id);
}

Standard user-defined literals[edit]

C++11 defined the syntax for user-defined literal suffixes, but the standard library did not use any of them. C++14 adds the following standard literals:[16]

C++14 增加了以下标准字面量

• “s”, for creating the various std::basic_string types.

  “s”, 创建各种 std::basic_string 类型

• “h”, “min”, “s”, “ms”, “us”, “ns”, for creating the corresponding std::chrono::duration time intervals.

  “h”, “min”, “s”, “ms”, “us”, “ns”, 创建对应的 std::chrono::duration 时间间隔

• “if”, “i”, “il”, for creating the corresponding std::complex, std::complex and std::complex imaginary numbers.

1
2
3

auto str = "hello world"s; // auto deduces string
auto dur = 60s;            // auto deduces chrono::seconds
auto z   = 1i;             // auto deduces complex<double>

The two “s” literals do not interact, as the string one only operates on string literals, and the one for seconds operates only on numbers.[18]

Tuple addressing via type[edit]

The std::tuple type introduced in C++11 allows an aggregate of typed values to be indexed by a compile-time constant integer. C++14 extends this to allow fetching from a tuple by type instead of by index.[16] If the tuple has more than one element of the type, a compile-time error results:[19]

C++14 扩展了 std::tuple , 可以通过类型来获取元素, 如果 tuple 有多个相同类型, 则会出错.

1
2
3
4

tuple<string, string, int> t("foo", "bar", 7);
int i = get<int>(t);        // i == 7
int j = get<2>(t);          // Same as before: j == 7
string s = get<string>(t);  // Compile-time error due to ambiguity

Smaller library features[edit]

std::make_unique can be used like std::make_shared for std::unique_ptr objects.[7]

std::integral_constant gained an operator() overload to return the constant value.[16]

The class template std::integer_sequence and related alias templates were added for representing compile-time integer sequences, such as the indices of elements in a parameter pack.[20]

The global std::begin/std::end functions were augmented with std::cbegin/std::cend functions, which return constant iterators, and std::rbegin/std::rend and std::crbegin/std::crend which return reverse iterators.

The std::exchange function template assigns a new value to a variable and returns the old value.[21]

New overloads of std::equal, std::mismatch, and std::is_permutation take a pair of iterators for the second range, so that the caller does not need to separately check that the two ranges are of the same length.[22]

The std::is_final type trait detects if a class is marked final.

The std::quoted stream I/O manipulator allows inserting and extracting strings with embedded spaces, by placing delimiters (defaulting to double-quotes) on output and stripping them on input, and escaping any embedded delimiters.[23]

summary

1. 类型推导, type deduce

   以 auto 为主, 可以推导返回值而不需返回值后置语法. 同时 decltype 可以用于推导 auto 的原类型

2. 常量表达式加强 constexpr

   constexpr 中可以有静态变量, thread_local 变量, 可以有分支和循环语句

3. 值模板 variable template

   不仅类, 现在值也可以模板化

4. 数字分隔符 digit separators

   使数字更加易读

5. 加强 lambda

   lambda 的参数可以是 auto 推导的了, 同时 lambda 的捕获增加了移动语义, 还可以不是外部成员(也就是自建变量)

6. 关键字 [[deprecated]]

   用于警示用户

7. 新的字面量, “s”, “h”, “min” …

   新的字面量, 用于快捷创建变量, 而不需显式转换类型

8. 新的 tuple 元素索引方式

   可以用类型来检索了呢 :)

以上是我从 C++14 中印象比较深刻的新特性

these are my impressive new features in c++14

#内层对齐补齐与分支目标缓冲器
出自《C++反汇编技术分析与揭秘》
此书我并没有读完，收获是对于底层更加了解，有2个点更加清楚了

内存对齐与补齐，为什么是4字节

• CPU运算的第二梯队是cache（高速缓冲区），它的访问速度仅次于寄存器

• cache中有虚拟地址映射，当运算时会从中拿到地址进行寻址操作

• 同时32位机的寄存器位数为32位，我们常用的数据整形int和指针的大小也为4字节

• 思考2个问题：

  • 一般常用的数据类型基本是4字节以上（除单个的char和short）

  • cache的内存十分宝贵，里面保存的地址是否有必要精确到1位

    对于cache进行了优化，其中保存的内存地址会丢弃后两位，丢弃之后，寻址操作只能基于4字节的倍数
    所以对齐补齐是以4字节为基础的

对于循环的优化

• 先考虑流水线优化，其原理很简单：
  A B C D四个工人，当一个任务来的时候，顺序是A->B->C->D
  当A做完了，继续来了第2个任务，在此时，B在做第一个任务的第二步，参考如图：

  1. A B C D

  2.  A B C D

  3.    A B C D

  4. ……

     其核心是，如果只有一个任务，那么就需要花费一整段工作时间
     而如果是多个任务，例如2个任务，那么就是5/4的时间，以此类推

• 分支目标缓冲器，考虑下面的循环：

  /**
  *@brief 外层循环做10次
  */
  for (int i = 0; i < 10; ++i)
  {
      /**
      *@brief 内层做1000次循环，第一次不预测，预测成功999次，第1001次预测失败
      */
      for (int j = 0; j < 1000; ++j)
      {
          //...
      }
  }

  分支目标缓冲器要结合流水线优化来理解
  当第一个分支启动时，分支目标缓冲器不进行预测，当第二次循环进行时，进行预测，预测成功，直到失败
  分支目标缓冲器是经验主义，预测越多，优化更好，如果多次失败，则会刷新
  （intel的CPU是这样的，当进行一个分支时，下一个分支已经在进行预测了，它对true/false的情况进行预测
  ，也就是在这次分支执行时，下一次分支已经准备好了（其中的同步这些则是更底层的知识了）如果预测失败则会回流，
  如果预测成功，将会节省时间以达到提升性能的目的）

  如果外层分支进行10次，内层分支进行1000次，那么1次不预测，999次成功，最后一次失败，这样的操作重复10次
  则 10 x 999 = 9990 次
  如果外层分支进行1000次，内层分支进行10次，那么1次不预测，9次成功，最后一次失败，这样的操作重复1000次
  则 9 x 1000 = 9000 次
  分支预测是经验主义，预测越多，优化也就更好，所以：
  多重循环，内层循环次数应大于外层循环次数
  PS：这需要结合CPU来考虑，intel的CPU是这样的，AMD就不知道了

至于switch，if，等等，都有优化，具体以后再补，分支的结构类似于函数调用，都会发生跳转（inline例外）
PS：强推程序应当了解底层知识，编译器优化和汇编，如果了解了底层，很多知识点都能迎刃而解
当然，前提是有那耐心，一个简单的除法编译器都可能会优化成一堆计算机处理比较简单，而人理解起来就很头疼的代码
那涉及到数学方面的知识，并且不简单…

#为什么是-128127?
我们常说char类型数据占1个字节,范围是-128127
OK,1字节八位,1位为符号为,7位存储数据,但是为什么负数要比正数多一个呢?

这涉及到补码和反码的概念,8位能表示2^8+1种变化(我更偏向于称它为变化,因为计算机中的二进制是我们赋予他的意义,这里+1指的是0)
也就是0255,256个数字,所以-128127是正确的
考虑一下0会如何被表示:

在符号位为正的情况下为 0000 0000  
在符号位为负的情况下为 1000 0000  

同样的数,他们表示方式重叠了,这显然不好
所以CPU采用了正数和负数表示方式不同的方法来解决这个问题
负数的表现方式为 补码: 反码 + 1

##反码
就和它的名字一样,它的意义是除符号位外,其他所有位取反
例如 0000 0000 取反为 0111 1111

##补码
补码即为反码 + 1

有了以上知识,那么可以得知以下二进制表示多少(假设为1 byte):

1111 1111 反码:1000 0000 补码:1000 0001 表示 -1
1000 0000 反码:1111 1111 补码:(这里不好表示o(*￣▽￣*)ブ) 表示:-128

所以,为什么负数比正数多了一个呢?
因为计算机内部结构(补码)造成了负数比正数能多表达一个(这一个是来自于-0这个概念,因为我们更加偏向于+0而不是-0,
所以就让正数吃亏了,也不仅仅是这样,在很多我无法举例但的确存在的某些”骚操作”里面,这种方式给予了很大的支持)

这里也映射了很多概念,比如一个数已经表示最大了(比如char的127)我将它+1 为什么他表示了-128?

127二进制 0111 1111
+1之后 1000 0000(很熟悉吧,就在上面,这表示了负最大)

PS:底层的东西很有趣,不然为什么编译原理和操作系统凭什么被认为是程序三大浪漫(还有一个是图形学,
emmm 三大浪漫有很多争议,有些认为应当包含数据库和算法,新的三大浪漫还有人工智能和机器视觉等等)

PS:关于符号位扩展

思考下面代码
(x << 1) >> 1
x左移一位后又右移一位, 乍一看并没有什么改变, 这涉及到符号位的扩展问题

对于移位操作, 左移都补0, 而右移因为反码的关系:正数移位补0, 而负数移位补1, 所以当x左移改变了符号位时,再右移,它的值将会发生改变
具体改变的规律是符号位发生改变, 而数值上的体现涉及到负数会补码, 所以改变前后可能是两个看起来完全不同但其实有规律的值

##对于溢出和越界的理解(overflow/outside range)

x86汇编flag寄存器有两个表示位, 分别位OF/CF, 溢出标志位/进位标志位
其中OF只对有符号数有效, 例如:
当两个1字节大小的数字相加时, A: 0111 1111 (127), B: 0000 0001 (1)
A + B = 128, 对应二进制位是 1000 0000, 但是对于有符号数来说, 这是负数, 计算结果是错误的
这里错误的原因是计算结果占用了一个不该它占有的有效位
不该它占有: 它占有了符号位, 这个位错误地被计算结果改变
有效: 这个符号位是被合理分配的, 并不是未定义的

CF只对无符号数有效, 例如:
当两个1字节大小的数字相加时, A: 1111 1111 (255), B: 0000 0001 (1)
A + B = 256, 对应二进制位是 1 0000 0000, 1字节大小存不下9bit, 计算结果无法保存, 产生错误
错误原因是: 计算结果超出了合理的范围, 这个位未被定义
同样不该它占有, 但是同时这是个未被定义的空间

那么就可以简单看出, 从寄存器角度, 溢出/越界的区分了, 那个位是否有效
(但是也不一定…)

vector<int> veci{1, 2, 3};
vector<int>::iterator it1 = veci.begin();
vector<int>::iterator it2 = veci.begin() + 1; 

veci.erase(it1);
// @note 这里的erase会报错, 因为在上一句代码中, begin迭代器所指向的数据被删除了, 
//     删除之后, begin迭代器之后的元素重新排序(往前移), 此时的it2已经不指向它原先希望指向的位置了  
//     可能它指向了新的begin迭代器之后的位置, 也可能指向begin了, 直接的结果是: 它失效了  
veci.erase(it2);

在上段代码中, it2实际可能还是指向一个元素的, (实际VS debug中, it2指向了第三个元素, 也就是3)
it2并未失效, 它依旧指向一块内存,(至少在VS debug中这样) 但是这是块不该它占有的内存
按照上述我们对溢出/越界的定义, 这种问题属于溢出

但是很可惜, 报错信息是:
“vector erase iterator outside range”
emmmmmmmmmm, 也就是说, 它认为这是越界…
所以我的理解可能是错的, 但是我还是认为这样子理解没有什么问题(大概… :) )

或许这样说更好, 有符号数, 只有7位数值, 两个7位数值无论如何计算也不会超过8位
而无符号数, 8位数值, 计算是可能超过8位的

Step

1. 编写动态库源文件
2. 将动态库源文件编译链接生成动态库文件
3. 在执行源文件中添加头文件声明
4. 使用动态库文件

Step1:

…

Step2:

gcc/g++ -fPIC -shared -o [libname].so [sourcefile]

example:

gcc -fPIC -shared -o tlib.so tlib.c

这样就会生成一个tlib.so的动态库文件
其中-fPIC的含义是: Position Independent Code (位置无关代码)

Step3:

添加声明可以在单独的头文件中添加, 也可以直接在使用的源文件内添加

Step4:

gcc t.c -L. tlib.so  

会生成一个默认的a.out可执行文件

此时还有一个问题就是直接运行的话会报错:
应用程序找不到.so文件
解决方法有两种, 一种是改系统文件, 另外一种是临时告诉shell动态库的路径
因为这个是测试用例, 介绍第二种

LD_LIBRARY_PATH=. ./a.out  

执行此命令可以解决报错问题, 其中LD_LIBRARY_PATH=.的含义是:
告诉shell, 库的路径在当前路径下(如果库放在别的路径, 将.替换即可)

以上经验来自博客园

顺便: 第一次写了makefile, 用作上述的动态库管理

make build: 生成动态库, 可执行文件
make doit: 执行程序(如果文件并不存在, 先生成文件)
make clean: 清除生成的文件

 1 build: tlib.so a.out
 2 
 3 tlib.so: tlib.c
 4           gcc -fPIC -shared -o $@ $<
 5 
 6 a.out: t1.c
 7           gcc $< -L. tlib.so
 8 
 9 doit: build 
10           LD_LIBRARY_PATH=. ./a.out
11 
12 file = tlib.so a.out
13 clean: 
14           rm $(file)

书写makedile和核心就是搞清楚依赖关系
其中build为创建动态库和可执行文件, 所以依赖于tlib.so和a.out
而tlib.so依赖于tlib.c, a.out依赖于t1.c
…

有一份make教程

上述所用到的基础makefile规则并不难理解, 这里不做赘述

234 Palindrome Linked List

判断链表是否是回文链表, 可以的话, O(n)时间复杂度, O(1)空间复杂度.

Determine whether the given single-linked list is a palindrome linked list.

Flow up: O(n) time and O(1) space.

my solution

单链表, 时间O(n), 空间O(1), 同时满足有点难啊 = = …

It’s a little difficult to solve this question with both O(n) time and O(1) space.

我能相出的办法仅在知道链表长度/链表尾节点的情况下适用.

I can solve this if I know the length of the linked list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            int n = 0;
            ListNode* cursor = head;
            if (cursor) {
                ++n;
                cursor = cursor->next;
            }

            if (n == 1) return true;

            ListNode *prev = head;
            LisTNode *next = prev->next;
            for (int i = 1; i < n / 2; ++i) {
                ListNode *tmp = next->next;
                next->next = prev;

                prev = next;
                next = tmp;
            }
            // // this methond redirect two nodes in one cycle
            // cursor = head;
            // ListNode *prev = nullptr;
            // LisTNode *next = cursor->next;
            // for (int i = 1; i < n / 2; ++i) {
            //     cursor->next = prev;
            //     ListNode *tmp = next->next;
            //     next->next = cursor;
            //     
            //     prev = next;
            //     cursor = tmp;
            //     next = cursor->next;
            // }

            if (n & 1)
                next = next->next;

            while (next) {
                if (next->val != prev->val)
                    return false;
                next = next->next;
                prev = prev->next;
            }

            return true;
        }
};

知道了节点长度的话, 不断反向节点, 直到到达中间节点, 然后从中间节点向两端对比就好了, 两次循环各遍历一半的节点. 所以还算 O(1), 空间只需要必须的用于遍历的节点, O(1)也满足. 但问题就是这是节点长度的情况下. 所以很好奇什么算法可以满足这两个需求. (其实看了之后感觉 = = , emmm… 没有很惊艳)

If know the length of the linked list, reverse nodes until the center of the linked list, then compare elements between the center node.

best solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        slow->next = reverseList(slow->next);
        slow = slow->next;
        while (slow) {
            if (head->val != slow->val) return false;
            head = head->next;
            slow = slow->next;
        }
        return true;
    }

    ListNode* reverseList(ListNode* head) {
        if (head == NULL) {
            return head;
        }
        ListNode* currentHead = head;
        while (head->next) {
            ListNode* p = head->next;
            head->next = p->next;
            p->next = currentHead;
            currentHead = p;
        }
        return currentHead;
    }
};

办法几乎和我相同, 核心就是那个中间节点, 结果是用这种方法来解决的… 怎么没想到呢 = =, 学到了学到了…

还有就是, 我在奇偶长度上花了些心思, 所以从 1 开始循环, 并且对两种情况做了处理.

但是这种方法的话, 因为并不是由内向外, 所以奇偶不重要, 也不需要额外的代码来处理了.

gdb

gdb是一个 c/c++ debug 工具

没有一个教程和文档比 gdb 官方手册更加详细和准确

这个文件只是简单地介绍其中一小部分频繁使用的功能, 具体需要结合 gdb
的官方文档使用

(gdb非常强大, 其文档有400多页, 完全是一本参考书的规格)

( 同时gdb也做到了透明, 大多数时候你使用它只需掌握极少的几条指令(基础功能中的指令) )

基础功能

n : next

用于跳转到下一条语句, 同时会先执行当前语句, 可配合 number 跳转多行

s : step

进入函数调用

b : break

断点

c : continue

继续执行

p : print

打印变量信息, ptype 可以打印类型信息(用于类, 它会将类的所有成员都打印出来)

l ：list

查看当前行附近的代码信息, 可以指定行号和函数, 可以用于跳转到指定文件

bt : backtrace

调用回溯, 查看当前调用栈

f : frame

与 bt 的信息配合, 使用 number 指定跳转到某条函数调用之前

info

这条指令用于观察gdb指令的当前信息

例如: info breakpoints, info frame, info watchpoints, info record…

u : until

跳出当前循环, 或者配合 number 指定执行到何处

finish

完成当前函数调用, 跳转到函数调用的最后一条语句

中级功能

watch

观察点, 可以用来观察一个变量或者表达式的变化

checkpoint

检查点用来保存当前进度, 可以在执行若干语句之后回到当前检查点

record

记录命令的使用信息, 实用之处在于: 使用其中的 full 模式, 可以实现 reverse 操作

比如 reverse-next, 这将会反向执行到上一个语句

forward-search/search

前向搜索/搜索

inferior

gdb支持debug多个进程

thread

gdb支持debug多线程程序

catch

捕获一个事件

singal

捕获一个信号

win : winheight

进入可视化模式, 简单来说就是代码界面拥有了窗口, 同时一系列信息也会显示在上面

(不过这个模式实际上会出现会显示错误, 比如会显示删除符号, 显示tab键之类的问题, 我不知道这算不算bug…)

(或许我使用方式不对? )

e : edit

你可以在 gdb 中直接更改源文件, 不过这好像有点鸡肋…

disassemble

反编译代码, 显示 machine code

diaplay

自动显示变量

set (convenience variable)

使用该指令可以保存变量, 之后你可以用在任何命令的表达式里面, 记得前面加美元($)前缀

(gdb) set {int}0x604010 = 4
(gdb) p v[0]
$16 = (__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type &) @0x604010: 4
(gdb) set {int}0x604010 = 5
(gdb) p v[0]
$17 = (__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type &) @0x604010: 5

它可以用于对内存赋值!!!

(gdb) p $rbx
$18 = 1
(gdb) set $rbx = 200
(gdb) p $rbx
$19 = 200

也可以用于对寄存器赋值!!!

convenience function (10.12)

gdb提供了一系列的函数以供使用, 例如:

$_strlen(str)     $_streq(str1, str2)      $_regex(str, regex) 

前面依旧要加 ‘$’ 符号

register (这个我超喜欢的) (10.13)

这个指令支持你查看寄存器的内容, 使用方法是

p $register

(这个或许应该放在 p 中, 不过我觉得这应该放在高级内容中)

我依稀记得之前我曾经因为无法在运行时看内存内容而苦恼

现在这个问题随着gdb的深入学习而解决了, 以后我分析汇编的时候, 可以更加深入了

并且支持使用 set 来改变内容!!

info os [args]

查看系统相关信息, 比如:

info os files

将会查看系统使用文件描述符的信息

trace (13)

按照 gdb 官方文档的描述, 这个指令是用来调试那些对于实时性有要求的程序

但是我也没能理解这个指令是如何使用的, 同时有这么一句话

The tracepoint facility is currently available only for remote targets
追溯点当前只对远程目标有效

这个指令的内容占了整个 13 章节, 应该相当重要. 所以这里仅仅记录一下, 或许以后会用到

14 Debugging Programs That Use Overlays

=========

后续内容(从 13 章往后)是一些高级内容(以置于我不得不将这段主题的标题改成中级功能…)

比如大型程序, 远程调试 …

暂不研究

other

源自http://www.waider.ie/music/lyrics/gdb.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

GDB!
based on _Tragedy_ by Barry, Robin and Maurice Gibb

Here's vi
In a lost and lonely part of code
Held in time
In a world of bugs my head explodes
Goin' home
I just can't make it all alone
I really should be coding you, coding you
running you, running you

CHORUS:
GDB when the program's wrong and the debug's on
It's GDB when the system dies and you don't know why
It's hard to bear
With no one to help you
You're going nowhere
GDB when you press control and the box just rolls
It's GDB when the system dies and you don't know why
It's hard to bear
With no one beside you
You're going nowhere

Night and Day
There's a burning down inside of me
Burning code
And a kernel that won't let me be
Down it goes
and I just can't take it all alone
I really should be coding you, coding you
Running you, running you

REPEAT CHORUS

REPEAT CHORUS(fade)

源自https://www.gnu.org/music/gdb-song.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Let's start at the very beginning, a very good place to start,
When you're learning to sing, its Do, Re, Mi; 
When you're learning to code, its G, D, B. 
(background) G, D, B.

The first three letters just happen to be, G, D, B.

(background) G, D, B.

(Chorus)

G!,
GNU!, it's Stallman's hope,
D,
a break I set myself.
B,
debug that rotten code,
Run,
a far, far way to go.
Print,
to see what you have done,
Set,
a patch that follows print.
Quit,
and recompile your code - - -
That will bring it back to G,
                              D,
                                 B,
                                    <link>
(Resume from the Chorus)

感觉, 嗯, 很有气势

Rotate Image

顺时针90度旋转矩阵
要求就地更改(不能创建另外一个矩阵)

我的做法

思路:

使用下标来获取元素更方便
从外层到内层, 一层层旋转, 每次旋转n个, 每层旋转4次
不可避免需要保存一组数值

具体代码:

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();

        for (int i = 0; i < n / 2; ++i){
            // backup first stream
            vector<int> backup ((matrix.begin() + i)->begin() + i + 1, 
                (matrix.begin() + i)->end() - i);

                for (int col = i + 1, row = n - i - 2; col < n - i; ++col, --row)
                    matrix[i][col] = matrix[row][i];

                for (int row = i, col = i; row < n - i - 1; ++row, ++col)
                    matrix[row][i] = matrix[n - 1 - i][col];

                for (int col = i, row = n - i - 1; col < n - i - 1; ++col, --row)
                    matrix[n - 1 - i][col] = matrix[row][n - i - 1];

                for (int row = n - 1 - i, t = backup.size() - 1; t >= 0; --row, --t)
                    matrix[row][n - i - 1] = backup[t];
        }
    }
};

最后结果:

dalao的做法

class Solution {
public:
    void swapLR(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; i++) {
            int l = 0;
            int r = n-1;
            while(l<r) {
                int temp = matrix[i][l];
                matrix[i][l++] = matrix[i][r];
                matrix[i][r--] = temp;
            }
        }
    }

    void swapdig(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-1-i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][n-1-i];
                matrix[n-1-j][n-1-i] = temp;
            }
        }
    }

    void rotate(vector<vector<int>>& matrix) {
        swapLR(matrix);
        swapdig(matrix);
    }
};

首先分析 swapLR 函数:

emmmm, 它好像将左右的数据对换了

emmm, 还是看不懂有什么规律,

6啊…, 更改后的行就是最终结果的列, 只要遍历倒叙一遍就可以了
这种思路是如何得出的? 需要哪方面的知识么?
思路这种东西好难弥补, 我自认为不出意外的话, 是无法想到这一点的

Trapping Rain Water

原地址

大致描述: 给出一个数组, 按如上所述, 求出蓝色方块的数量
(就像一个山脉一样, 看这样的山脉降雨后能留下多少水)

我的思路:

排错:

1. 必须有3个以上的山脉才有可能有积水, 所以数组长度必定大于3
2. 左右为平地的数组下标截断, 直到有山脉为止

做法:

1. 从左到右依次拿到符合条件的格子下标(比如第一次是(1, 3) )
2. 计算改区域的雨水
3. 重复第一步, 直到结束

// 具体代码在42_.txt中

dalao的思路

// 具体代码在42_2.txt中

分析:
一个格子中能不能存水取决于左右格子的高度
算法从左到右一次, 从有到左一次.
每次假设该格子以左/右单方面最大能放多少水
将同一格的两次数据求最小, 这就是该下标实际能存多少水
最后减去本身的实体格子, 也就得到了空下的格子

算法复杂度为O(n)

排序两个链表

思路:

每次对比两条链表的当前节点, 按适当顺序插入的同时需要注意一点

如果小的节点的接下来的值依旧小于大的节点, 那么需要继续往下遍历, 知道遇到一个节点大于大的节点

这样的话一次循环中就可以排序多个节点, 循环的次数就可以变少

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		if (!l1 && l2) return l2;
		if (!l2 && l1) return l1;

        ListNode *smaller = l1->val > l2->val ?
            l2 : l1;
        ListNode *bigger = l1->val > l2->val ?
            l1 : l2;
        ListNode *result = smaller;
        while (smaller && bigger) {
            while (smaller->next && smaller->next->val < bigger->val)
                smaller = smaller->next;

            ListNode *tmps = smaller->next;
            smaller->next = bigger;

            smaller = bigger;
            bigger = tmps;
        }

        return result;
    }
};

采用了一次循环对比多个的算法, 每次循环之后不必再计算谁大谁小, 身份像开关一样会互换

但是代码复杂度增加了

结果:

emmmmm…, 预差有点大…

按理来说我觉得算法很好啊, 一次循环中排序了多个节点

每次循环后还不需要计算谁大谁小

分析一下4ms的算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* pre=new ListNode(0);
        ListNode* crt=pre;
        while(l1!=NULL && l2!=NULL){
            if(l1->val<l2->val) {
                crt->next=l1;
                l1=l1->next;
            }
            else {
                crt->next=l2;
                l2=l2->next;
            }
            crt=crt->next;   
        }
        crt->next=(l1==NULL)?l2:l1;
        return pre->next;
    }
};

emmmm…

他的思路很简单, 每次对比两个节点, 筛选出一个最小的

将筛选出节点的那条链接往下循环, 另外一条不变

但是时间比我少了很多, 我仔细思考了的算法反倒没有这种单纯的算法好

有点出乎意料和不服气…

@exprience:

我以后或许需要考虑 以循环次数换取减少循环复杂度 的做法了

这样的话我的每次循环尽量简单, 虽然次数变多了, 但是总体的效率可能还会有提升, 比如这次 = =