阅读视图

发现新文章,点击刷新页面。
☑️ ☆

Inversion of Control Containers and the Dependency Injection Pattern (控制反转和依赖注入模式译文)

引言

北京中鼎项目用到了 .NET 的依赖注入框架,借此机会了解了控制反转等设计理念,追溯到 Martin Fowler 的这篇 Inversion of Control Containers and the Dependency Injection pattern,特作此博文研读。

One of the entertaining things about the enterprise Java world is the huge amount of activity in building alternatives to the mainstream J2EE technologies, much of it happening in open source. A lot of this is a reaction to the heavyweight complexity in the mainstream J2EE world, but much of it is also exploring alternatives and coming up with creative ideas. A common issue to deal with is how to wire together different elements: how do you fit together this web controller architecture with that database interface backing when they were built by different teams with little knowledge of each other. A number of frameworks have taken a stab at this problem, and several are branching out to provide a general capability to assemble components from different layers. These are often referred to as lightweight containers, examples include PicoContainer, and Spring.

Java 社群近来掀起了一阵轻量级容器的热潮,这些容器能够帮助开发者将来自不同项目的组件组装成为一个内聚的应用程序。在它们的背后有着同一个模式,这个模式决定了这些容器进行组件装配的方式。人们用一个大而化之的名字来称呼这个模式:“控制反转”(Inversion of Control,IoC)。在本文中,我将深入探索这个模式的工作原理,给它一个更能描述其特点的名字——“依赖注入”(Dependency Injection),并将其与“服务定位器”(Service Locator)模式作一个比较。不过,这两者之间的差异并不太重要,更重要的是:应该将组件的配置与使用分离开——两个模式的目标都是这个。

在企业级 Java 的世界里存在一个有趣的现象:有很多人投入很多精力来研究主流 J2EE 技术的替代品——自然,这大多发生在开源社群。在很大程度上,这可以看作是开发者对主流 J2EE 技术的笨重和复杂作出的回应,但其中的确有很多极富创意的想法,的确提供了一些可供选择的方案。J2EE 开发者常遇到的一个问题就是如何组装不同的程序元素:如果 web 控制器体系结构和数据库接口是由不同的团队所开发的,彼此几乎一无所知,你应该如何让它们配合工作?很多框架尝试过解决这个问题,有几个框架索性朝这个方向发展,提供了更通用的“组装各层组件”的方案。这样的框架通常被称为“轻量级容器”,PicoContainerSpring 都在此列中。

Underlying these containers are a number of interesting design principles, things that go beyond both these specific containers and indeed the Java platform. Here I want to start exploring some of these principles. The examples I use are in Java, but like most of my writing the principles are equally applicable to other OO environments, particularly .NET.

在这些容器背后,一些有趣的设计原则发挥着作用。这些原则已经超越了特定容器的范畴,甚至已经超越了 Java 平台的范畴。在本文中,我就要初步揭示这些原则。我使用的范例是 Java 代码,但正如我的大多数文章一样,这些原则也同样适用于别的 OO 环境,特别是.NET。

组件服务 Components and Services

The topic of wiring elements together drags me almost immediately into the knotty terminology problems that surround the terms service and component. You find long and contradictory articles on the definition of these things with ease. For my purposes here are my current uses of these overloaded terms.

“装配程序元素”,这样的话题立即将我拖进了一个棘手的术语问题:如何区分“服务”(service)和“组件”(component)?你可以毫不费力地找出关于这两个词定义的长篇大论,各种彼此矛盾的定义会让你感受到我所处的窘境。有鉴于此,对于这两个遭到了严重滥用的词汇,我将首先说明它们在本文中的用法。

I use component to mean a glob of software that’s intended to be used, without change, by an application that is out of the control of the writers of the component. By ‘without change’ I mean that the using application doesn’t change the source code of the components, although they may alter the component’s behavior by extending it in ways allowed by the component writers.

所谓“组件”是指这样一个软件单元:它将被作者无法控制的其他应用程序使用,但后者不能对组件进行修改。也就是说,使用一个组件的应用程序不能修改组件的源代码,但可以通过作者预留的某种途径对其进行扩展,以改变组件的行为。

A service is similar to a component in that it’s used by foreign applications. The main difference is that I expect a component to be used locally (think jar file, assembly, dll, or a source import). A service will be used remotely through some remote interface, either synchronous or asynchronous (eg web service, messaging system, RPC, or socket.)

服务和组件有某种相似之处:它们都将被外部的应用程序使用。在我看来,两者之间最大的差异在于:组件是在本地使用的(例如 JAR 文件、程序集、DLL、或者源码导入);而服务是要通过——同步或异步的——远程接口来远程使用的(例如 web service、消息系统、RPC,或者 socket)。

I mostly use service in this article, but much of the same logic can be applied to local components too. Indeed often you need some kind of local component framework to easily access a remote service. But writing “component or service” is tiring to read and write, and services are much more fashionable at the moment.

在本文中,我将主要使用“服务”这个词,但文中的大多数逻辑也同样适用于本地组件。实际上,为了方便地访问远程服务,你往往需要某种本地组件框架。不过,“组件或者服务”这样一个词组实在太麻烦了,而且“服务”这个词当下也很流行,所以本文将用“服务”指代这两者。

一个简单的例子 A Naive Example

To help make all of this more concrete I’ll use a running example to talk about all of this. Like all of my examples it’s one of those super-simple examples; small enough to be unreal, but hopefully enough for you to visualize what’s going on without falling into the bog of a real example.

In this example I’m writing a component that provides a list of movies directed by a particular director. This stunningly useful function is implemented by a single method.

为了更好地说明问题,我要引入一个例子。和我以前用的所有例子一样,这是一个超级简单的例子:它非常小,小得有点不够真实,但足以帮助你看清其中的道理,而不至于陷入真实例子的泥潭中无法自拔。

在这个例子中,我编写了一个组件,用于提供一份电影清单,清单上列出的影片都是由一位特定的导演执导的。实现这个伟大的功能只需要一个方法:

class MovieLister...

public Movie[] moviesDirectedBy(String arg) {
List allMovies = finder.findAll();
for (Iterator it = allMovies.iterator(); it.hasNext();) {
Movie movie = (Movie) it.next();
if (!movie.getDirector().equals(arg)) it.remove();
}
return (Movie[]) allMovies.toArray(new Movie[allMovies.size()]);
}

The implementation of this function is naive in the extreme, it asks a finder object (which we’ll get to in a moment) to return every film it knows about. Then it just hunts through this list to return those directed by a particular director. This particular piece of naivety I’m not going to fix, since it’s just the scaffolding for the real point of this article.

你可以看到,这个功能的实现极其简单:moviesDirectedBy 方法首先请求 finder(影片搜寻者)对象(我们稍后会谈到这个对象)返回后者所知道的所有影片,然后遍历 finder 对象返回的清单,并返回其中由特定的某个导演执导的影片。非常简单,不过不必担心,这只是整个例子的脚手架罢了。

The real point of this article is this finder object, or particularly how we connect the lister object with a particular finder object. The reason why this is interesting is that I want my wonderful moviesDirectedBy method to be completely independent of how all the movies are being stored. So all the method does is refer to a finder, and all that finder does is know how to respond to the findAll method. I can bring this out by defining an interface for the finder.

我们真正想要考察的是 finder 对象,或者说,如何将 MovieLister 对象与特定的 finder 对象连接起来。为什么我们对这个问题特别感兴趣?因为我希望上面这个漂亮的 moviesDirectedBy 方法完全不依赖于影片的实际存储方式。所以,这个方法只能引用一个 finder 对象,而 finder 对象则必须知道如何对 findAll 方法作出回应。为了帮助读者更清楚地理解,我给 finder 定义了一个接口:

public interface MovieFinder {
List findAll();
}

Now all of this is very well decoupled, but at some point I have to come up with a concrete class to actually come up with the movies. In this case I put the code for this in the constructor of my lister class.

现在,两个对象之间没有什么耦合关系。但是,当我要实际寻找影片时,就必须涉及到 MovieFinder 的某个具体子类。在这里,我把“涉及具体子类”的代码放在 MovieLister 类的构造子中。

class MovieLister...

private MovieFinder finder;
public MovieLister() {
finder = new ColonDelimitedMovieFinder("movies1.txt");
}

The name of the implementation class comes from the fact that I’m getting my list from a colon delimited text file. I’ll spare you the details, after all the point is just that there’s some implementation.

这个实现类的名字就说明:我将要从一个逗号分隔的文本文件中获得影片列表。你不必操心具体的实现细节,只要设想这样一个实现类就可以了。

Now if I’m using this class for just myself, this is all fine and dandy. But what happens when my friends are overwhelmed by a desire for this wonderful functionality and would like a copy of my program? If they also store their movie listings in a colon delimited text file called “movies1.txt” then everything is wonderful. If they have a different name for their movies file, then it’s easy to put the name of the file in a properties file. But what if they have a completely different form of storing their movie listing: a SQL database, an XML file, a web service, or just another format of text file? In this case we need a different class to grab that data. Now because I’ve defined a MovieFinder interface, this won’t alter my moviesDirectedBy method. But I still need to have some way to get an instance of the right finder implementation into place.

如果这个类只由我自己使用,一切都没问题。但是,如果我的朋友叹服于这个精彩的功能,也想使用我的程序,那又会怎么样呢?如果他们也把影片清单保存在一个逗号分隔的文本文件中,并且也把这个文件命名为“ movie1.txt”,那么一切还是没问题。如果他们只是给这个文件改改名,我也可以从一个配置文件获得文件名,这也很容易。但是,如果他们用完全不同的方式——例如 SQL 数据库、XML 文件、web service,或者另一种格式的文本文件——来存储影片清单呢?在这种情况下,我们需要用另一个类来获取数据。由于已经定义了 MovieFinder 接口,我可以不用修改 moviesDirectedBy 方法。但是,我仍然需要通过某种途径获得合适的 MovieFinder 实现类的实例。

Figure 1: The dependencies using a simple creation in the lister class

Figure 1 shows the dependencies for this situation. The MovieLister class is dependent on both the MovieFinder interface and upon the implementation. We would prefer it if it were only dependent on the interface, but then how do we make an instance to work with?

图 1 展现了这种情况下的依赖关系:MovieLister 类既依赖于 MovieFinder 接口,也依赖于具体的实现类。我们当然希望 MovieLister 类只依赖于接口,但我们要如何获得一个 MovieFinder 子类的实例呢?

In my book P of EAA, we described this situation as a Plugin. The implementation class for the finder isn’t linked into the program at compile time, since I don’t know what my friends are going to use. Instead we want my lister to work with any implementation, and for that implementation to be plugged in at some later point, out of my hands. The problem is how can I make that link so that my lister class is ignorant of the implementation class, but can still talk to an instance to do its work.

Patterns of Enterprise Application Architecture 一书中,我们把这种情况称为“插件”(plugin):MovieFinder的实现类不是在编译期连入程序之中的,因为我并不知道我的朋友会使用哪个实现类。我们希望 MovieLister 类能够与 MovieFinder 的任何实现类配合工作,并且允许在运行期插入具体的实现类,插入动作完全脱离我(原作者)的控制。这里的问题就是:如何设计这个连接过程,使 MovieLister 类在不知道实现类细节的前提下与其实例协同工作。

Expanding this into a real system, we might have dozens of such services and components. In each case we can abstract our use of these components by talking to them through an interface (and using an adapter if the component isn’t designed with an interface in mind). But if we wish to deploy this system in different ways, we need to use plugins to handle the interaction with these services so we can use different implementations in different deployments.

将这个例子推而广之,在一个真实的系统中,我们可能有数十个服务和组件。在任何时候,我们总可以对使用组件的情形加以抽象,通过接口与具体的组件交流(如果组件并没有设计一个接口,也可以通过适配器与之交流)。但是,如果我们希望以不同的方式部署这个系统,就需要用插件机制来处理服务之间的交互过程,这样我们才可能在不同的部署方案中使用不同的实现。

So the core problem is how do we assemble these plugins into an application? This is one of the main problems that this new breed of lightweight containers face, and universally they all do it using Inversion of Control.

所以,现在的核心问题就是:如何将这些插件组合成一个应用程序?这正是新生的轻量级容器所面临的主要问题,而它们解决这个问题的手段无一例外地是控制反转(Inversion of Control)模式。

控制反转 Inversion of Control

When these containers talk about how they are so useful because they implement “Inversion of Control” I end up very puzzled. Inversion of control is a common characteristic of frameworks, so saying that these lightweight containers are special because they use inversion of control is like saying my car is special because it has wheels.

几位轻量级容器的作者曾骄傲地对我说:这些容器非常有用,因为它们实现了“控制反转”。这样的说辞让我深感迷惑:控制反转是框架所共有的特征,如果仅仅因为使用了控制反转就认为这些轻量级容器与众不同,就好象在说“我的轿车是与众不同的,因为它有四个轮子”。

The question is: “what aspect of control are they inverting?” When I first ran into inversion of control, it was in the main control of a user interface. Early user interfaces were controlled by the application program. You would have a sequence of commands like “Enter name”, “enter address”; your program would drive the prompts and pick up a response to each one. With graphical (or even screen based) UIs the UI framework would contain this main loop and your program instead provided event handlers for the various fields on the screen. The main control of the program was inverted, moved away from you to the framework.

问题的关键在于:它们反转了哪方面的控制?我第一次接触到的控制反转针对的是用户界面的主控权。早期的用户界面是完全由应用程序来控制的,你预先设计一系列命令,例如“输入姓名”、“输入地址”等,应用程序逐条输出提示信息,并取回用户的响应。而在图形用户界面环境下,UI 框架将负责执行一个主循环,你的应用程序只需为屏幕的各个区域提供事件处理函数即可。在这里,程序的主控权发生了反转:从应用程序移到了框架。

For this new breed of containers the inversion is about how they lookup a plugin implementation. In my naive example the lister looked up the finder implementation by directly instantiating it. This stops the finder from being a plugin. The approach that these containers use is to ensure that any user of a plugin follows some convention that allows a separate assembler module to inject the implementation into the lister.

对于这些新生的容器,它们反转的是“如何定位插件的具体实现”。在前面那个简单的例子中,MovieLister 类负责定位 MovieFinder 的具体实现——它直接实例化后者的一个子类。这样一来,MovieFinder 也就不成其为一个插件了,因为它并不是在运行期插入应用程序中的。而这些轻量级容器则使用了更为灵活的办法,只要插件遵循一定的规则,一个独立的组装模块就能够将插件的具体实现“注射”到应用程序中。

As a result I think we need a more specific name for this pattern. Inversion of Control is too generic a term, and thus people find it confusing. As a result with a lot of discussion with various IoC advocates we settled on the name Dependency Injection.

因此,我想我们需要给这个模式起一个更能说明其特点的名字——“控制反转”这个名字太泛了,常常让人有些迷惑。与多位 IoC 爱好者讨论之后,我们决定将这个模式叫做“依赖注入” (Dependency Injection)。

I’m going to start by talking about the various forms of dependency injection, but I’ll point out now that that’s not the only way of removing the dependency from the application class to the plugin implementation. The other pattern you can use to do this is Service Locator, and I’ll discuss that after I’m done with explaining Dependency Injection.

下面,我将开始介绍 Dependency Injection 模式的几种不同形式。不过,在此之前,我要首先指出:要消除应用程序对插件实现的依赖,依赖注入并不是唯一的选择,你也可以用 Service Locator 模式获得同样的效果。介绍完 Dependency Injection 模式之后,我也会谈到 Service Locator 模式。

依赖注入的几种形式 Forms of Dependency Injection

The basic idea of the Dependency Injection is to have a separate object, an assembler, that populates a field in the lister class with an appropriate implementation for the finder interface, resulting in a dependency diagram along the lines of Figure 2

Dependency Injection 模式的基本思想是:用一个单独的对象(装配器)来获得 MovieFinder 的一个合适的实现,并将其实例赋给 MovieLister 类的一个字段。这样一来,我们就得到了图2所示的依赖图:

Figure 2: The dependencies for a Dependency Injector

依赖注入的形式主要有三种,我分别将它们叫做构造子注入(Constructor Injection)、设值方法注入(Setter Injection)和接口注入(Interface Injection)。如果读过最近关于 IoC 的一些讨论材料,你不难看出:这三种注入形式分别就是 type 1 IoC(接口注入)、type 2 IoC(设值方法注入)和 type 3 IoC(构造子注入)。我发现数字编号往往比较难记,所以我使用了这里的命名方式。

使用 PicoContainer 进行构造子注入

I’ll start with showing how this injection is done using a lightweight container called PicoContainer. I’m starting here primarily because several of my colleagues at Thoughtworks are very active in the development of PicoContainer (yes, it’s a sort of corporate nepotism.)

首先,我要向读者展示如何用一个名为 PicoContainer 的轻量级容器完成依赖注入。之所以从这里开始,主要是因为我在 ThoughtWorks 公司的几个同事在 PicoContainer 的开发社群中非常活跃——没错,也可以说是某种偏袒吧。

PicoContainer uses a constructor to decide how to inject a finder implementation into the lister class. For this to work, the movie lister class needs to declare a constructor that includes everything it needs injected.

PicoContainer 通过构造子来判断“如何将 MovieFinder 实例注入 MovieLister 类”。因此,MovieLister 类必须声明一个构造子,并在其中包含所有需要注入的元素:

class MovieLister...

public MovieLister(MovieFinder finder) {
this.finder = finder;
}

The finder itself will also be managed by the pico container, and as such will have the filename of the text file injected into it by the container.

MovieFinder 实例本身也将由 PicoContainer 来管理,因此文本文件的名字也可以由容器注入:

class ColonMovieFinder...

public ColonMovieFinder(String filename) {
this.filename = filename;
}

The pico container then needs to be told which implementation class to associate with each interface, and which string to inject into the finder.

随后,需要告诉 PicoContainer:各个接口分别与哪个实现类关联、将哪个字符串注入 MovieFinder 组件。

private MutablePicoContainer configureContainer() {
MutablePicoContainer pico = new DefaultPicoContainer();
Parameter[] finderParams = {new ConstantParameter("movies1.txt")};
pico.registerComponentImplementation(MovieFinder.class, ColonMovieFinder.class, finderParams);
pico.registerComponentImplementation(MovieLister.class);
return pico;
}

This configuration code is typically set up in a different class. For our example, each friend who uses my lister might write the appropriate configuration code in some setup class of their own. Of course it’s common to hold this kind of configuration information in separate config files. You can write a class to read a config file and set up the container appropriately. Although PicoContainer doesn’t contain this functionality itself, there is a closely related project called NanoContainer that provides the appropriate wrappers to allow you to have XML configuration files. Such a nano container will parse the XML and then configure an underlying pico container. The philosophy of the project is to separate the config file format from the underlying mechanism.

这段配置代码通常位于另一个类。对于我们这个例子,使用我的 MovieLister 类的朋友需要在自己的设置类中编写合适的配置代码。当然,还可以将这些配置信息放在一个单独的配置文件中,这也是一种常见的做法。你可以编写一个类来读取配置文件,然后对容器进行合适的设置。尽管 PicoContainer 本身并不包含这项功能,但另一个与它关系紧密的项目 NanoContainer 提供了一些包装,允许开发者使用 XML 配置文件保存配置信息。NanoContainer 能够解析 XML 文件,并对底下的 PicoContainer 进行配置。这个项目的哲学观念就是:将配置文件的格式与底下的配置机制分离开。

To use the container you write code something like this.

使用这个容器,你写出的代码大概会是这样:

public void testWithPico() {
MutablePicoContainer pico = configureContainer();
MovieLister lister = (MovieLister) pico.getComponentInstance(MovieLister.class);
Movie[] movies = lister.moviesDirectedBy("Sergio Leone");
assertEquals("Once Upon a Time in the West", movies[0].getTitle());
}

Although in this example I’ve used constructor injection, PicoContainer also supports setter injection, although its developers do prefer constructor injection.

尽管在这里我使用了构造子注入,实际上 PicoContainer 也支持设值方法注入,不过该项目的开发者更推荐使用构造子注入。

使用 Spring 进行设值方法注入

The Spring framework is a wide ranging framework for enterprise Java development. It includes abstraction layers for transactions, persistence frameworks, web application development and JDBC. Like PicoContainer it supports both constructor and setter injection, but its developers tend to prefer setter injection - which makes it an appropriate choice for this example.

Spring 框架是一个用途广泛的企业级 Java 开发框架,其中包括了针对事务、持久化框架、web 应用开发和 JDBC 等常用功能的抽象。和 PicoContainer 一样,它也同时支持构造子注入和设值方法注入,但该项目的开发者更推荐使用设值方法注入——恰好适合这个例子。

To get my movie lister to accept the injection I define a setting method for that service

为了让 MovieLister 类接受注入,我需要为它定义一个设值方法,该方法接受类型为 MovieFinder 的参数:

class MovieLister...

private MovieFinder finder;
public void setFinder(MovieFinder finder) {
this.finder = finder;
}

Similarly I define a setter for the filename.

类似地,在 MovieFinder 的实现类中,我也定义了一个设值方法,接受类型为 String 的参数:

class ColonMovieFinder...

public void setFilename(String filename) {
this.filename = filename;
}

The third step is to set up the configuration for the files. Spring supports configuration through XML files and also through code, but XML is the expected way to do it.

第三步是设定配置文件。Spring 支持多种配置方式,你可以通过 XML 文件进行配置,也可以直接在代码中配置。不过,XML 文件是比较理想的配置方式。

<beans>
<bean id="MovieLister" class="spring.MovieLister">
<property name="finder">
<ref local="MovieFinder"/>
</property>
</bean>
<bean id="MovieFinder" class="spring.ColonMovieFinder">
<property name="filename">
<value>movies1.txt</value>
</property>
</bean>
</beans>

The test then looks like this.

于是,测试代码大概就像下面这样:

public void testWithSpring() throws Exception {
ApplicationContext ctx = new FileSystemXmlApplicationContext("spring.xml");
MovieLister lister = (MovieLister) ctx.getBean("MovieLister");
Movie[] movies = lister.moviesDirectedBy("Sergio Leone");
assertEquals("Once Upon a Time in the West", movies[0].getTitle());
}

接口注入

The third injection technique is to define and use interfaces for the injection. Avalon is an example of a framework that uses this technique in places. I’ll talk a bit more about that later, but in this case I’m going to use it with some simple sample code.

除了前面两种注入技术,还可以在接口中定义需要注入的信息,并通过接口完成注入。Avalon 框架就使用了类似的技术。在这里,我首先用简单的范例代码说明它的用法,后面还会有更深入的讨论。

With this technique I begin by defining an interface that I’ll use to perform the injection through. Here’s the interface for injecting a movie finder into an object.

首先,我需要定义一个接口,组件的注入将通过这个接口进行。在本例中,这个接口的用途是将一个 MovieFinder 实例注入继承了该接口的对象。

public interface InjectFinder {
void injectFinder(MovieFinder finder);
}

This interface would be defined by whoever provides the MovieFinder interface. It needs to be implemented by any class that wants to use a finder, such as the lister.

这个接口应该由提供 MovieFinder 接口的人一并提供。任何想要使用 MovieFinder 实例的类(例如 MovieLister 类)都必须实现这个接口。

class MovieLister implements InjectFinder

public void injectFinder(MovieFinder finder) {
this.finder = finder;
}

I use a similar approach to inject the filename into the finder implementation.

然后,我使用类似的方法将文件名注入 MovieFinder 的实现类:

public interface InjectFinderFilename {
void injectFilename (String filename);
}
class ColonMovieFinder implements MovieFinder, InjectFinderFilename...

public void injectFilename(String filename) {
this.filename = filename;
}

Then, as usual, I need some configuration code to wire up the implementations. For simplicity’s sake I’ll do it in code.

class Tester...

private Container container;

private void configureContainer() {
container = new Container();
registerComponents();
registerInjectors();
container.start();
}

When the dependent is a class written for this container, it makes sense for the component to implement the injector interface itself, as I do here with the movie finder. For generic classes, such as the string, I use an inner class within the configuration code.

class ColonMovieFinder implements Injector...

public void inject(Object target) {
((InjectFinder) target).injectFinder(this);
}
class Tester...

public static class FinderFilenameInjector implements Injector {
public void inject(Object target) {
((InjectFinderFilename)target).injectFilename("movies1.txt");
}
}

The tests then use the container.

测试代码则可以直接使用这个字段:

class Tester

public void testIface() {
configureContainer();
MovieLister lister = (MovieLister)container.lookup("MovieLister");
Movie[] movies = lister.moviesDirectedBy("Sergio Leone");
assertEquals("Once Upon a Time in the West", movies[0].getTitle());
}

The container uses the declared injection interfaces to figure out the dependencies and the injectors to inject the correct dependents. (The specific container implementation I did here isn’t important to the technique, and I won’t show it because you’d only laugh.)

使用 Service Locator Using a Service Locator

The key benefit of a Dependency Injector is that it removes the dependency that the MovieLister class has on the concrete MovieFinder implementation. This allows me to give listers to friends and for them to plug in a suitable implementation for their own environment. Injection isn’t the only way to break this dependency, another is to use a service locator.

依赖注入的最大好处在于:它消除了 MovieLister 类对具体 MovieFinder 实现类的依赖。这样一来,我就可以把 MovieLister 类交给朋友,让他们根据自己的环境插入一个合适的 MovieFinder 实现即可。不过,Dependency Injection 模式并不是打破这层依赖关系的唯一手段,另一种方法是使用 Service Locator 模式。

The basic idea behind a service locator is to have an object that knows how to get hold of all of the services that an application might need. So a service locator for this application would have a method that returns a movie finder when one is needed. Of course this just shifts the burden a tad, we still have to get the locator into the lister, resulting in the dependencies of Figure 3

Service Locator 模式背后的基本思想是:有一个对象(即服务定位器)知道如何获得一个应用程序所需的所有服务。也就是说,在我们的例子中,服务定位器应该有一个方法,用于获得一个 MovieFinder 实例。当然,这不过是把麻烦换了一个样子,我们仍然必须在 MovieLister 中获得服务定位器,最终得到的依赖关系如图 3 所示:

Figure 3: The dependencies for a Service Locator

In this case I’ll use the ServiceLocator as a singleton Registry. The lister can then use that to get the finder when it’s instantiated.

在这里,我把 ServiceLocator 类实现为一个 Singleton 的注册表,于是 MovieLister 就可以在实例化时通过 ServiceLocator 获得一个 MovieFinder 实例。

class MovieLister...

MovieFinder finder = ServiceLocator.movieFinder();
class ServiceLocator...

public static MovieFinder movieFinder() {
return soleInstance.movieFinder;
}
private static ServiceLocator soleInstance;
private MovieFinder movieFinder;

As with the injection approach, we have to configure the service locator. Here I’m doing it in code, but it’s not hard to use a mechanism that would read the appropriate data from a configuration file.

和注入的方式一样,我们也必须对服务定位器加以配置。在这里,我直接在代码中进行配置,但设计一种通过配置文件获得数据的机制也并非难事。

class Tester...

private void configure() {
ServiceLocator.load(new ServiceLocator(new ColonMovieFinder("movies1.txt")));
}
class ServiceLocator...

public static void load(ServiceLocator arg) {
soleInstance = arg;
}

public ServiceLocator(MovieFinder movieFinder) {
this.movieFinder = movieFinder;
}

Here’s the test code.

下面是测试代码:

class Tester...

public void testSimple() {
configure();
MovieLister lister = new MovieLister();
Movie[] movies = lister.moviesDirectedBy("Sergio Leone");
assertEquals("Once Upon a Time in the West", movies[0].getTitle());
}

I’ve often heard the complaint that these kinds of service locators are a bad thing because they aren’t testable because you can’t substitute implementations for them. Certainly you can design them badly to get into this kind of trouble, but you don’t have to. In this case the service locator instance is just a simple data holder. I can easily create the locator with test implementations of my services.

我时常听到这样的论调:这样的服务定位器不是什么好东西,因为你无法替换它返回的服务实现,从而导致无法对它们进行测试。当然,如果你的设计很糟糕,你的确会遇到这样的麻烦;但你也可以选择良好的设计。在这个例子中,ServiceLocator 实例仅仅是一个简单的数据容器,只需要对它做一些简单的修改,就可以让它返回用于测试的服务实现。

For a more sophisticated locator I can subclass service locator and pass that subclass into the registry’s class variable. I can change the static methods to call a method on the instance rather than accessing instance variables directly. I can provide thread–specific locators by using thread–specific storage. All of this can be done without changing clients of service locator.

对于更复杂的情况,我可以从 ServiceLocator 派生出多个子类,并将子类型的实例传递给注册表的类变量。另外,我可以修改 ServiceLocator 的静态方法,使其调用 ServiceLocator 实例的方法,而不是直接访问实例变量。我还可以使用特定于线程的存储机制,从而提供特定于线程的服务定位器。所有这一切改进都无须修改 ServiceLocator 的使用者。

A way to think of this is that service locator is a registry not a singleton. A singleton provides a simple way of implementing a registry, but that implementation decision is easily changed.

一种改进的思路是:服务定位器仍然是一个注册表,但不是 Singleton。Singleton 的确是实现注册表的一种简单途径,但这只是一个实现时的决定,可以很轻松地改变它。

为定位器提供分离的接口

One of the issues with the simple approach above, is that the MovieLister is dependent on the full service locator class, even though it only uses one service. We can reduce this by using a role interface. That way, instead of using the full service locator interface, the lister can declare just the bit of interface it needs.

上面这种简单的实现方式有一个问题:MovieLister 类将依赖于整个 ServiceLocator 类,但它需要使用的却只是后者所提供的一项服务。我们可以针对这项服务提供一个单独的接口,减少 MovieListerServiceLocator 的依赖程度。这样一来,MovieLister 就不必使用整个的 ServiceLocator 接口,只需声明它想要使用的那部分接口。

In this situation the provider of the lister would also provide a locator interface which it needs to get hold of the finder.

此时,MovieLister 类的提供者也应该一并提供一个定位器接口,使用者可以通过这个接口获得 MovieFinder 实例。

public interface MovieFinderLocator {
public MovieFinder movieFinder();

The locator then needs to implement this interface to provide access to a finder.

真实的服务定位器需要实现上述接口,提供访问 MovieFinder 实例的能力:

MovieFinderLocator locator = ServiceLocator.locator();
MovieFinder finder = locator.movieFinder();
public static ServiceLocator locator() {
return soleInstance;
}
public MovieFinder movieFinder() {
return movieFinder;
}
private static ServiceLocator soleInstance;
private MovieFinder movieFinder;

You’ll notice that since we want to use an interface, we can’t just access the services through static methods any more. We have to use the class to get a locator instance and then use that to get what we need.

你应该已经注意到了:由于想要使用接口,我们不能再通过静态方法直接访问服务——我们必须首先通过 ServiceLocator 类获得定位器实例,然后使用定位器实例得到我们想要的服务。

动态服务定位器

The above example was static, in that the service locator class has methods for each of the services that you need. This isn’t the only way of doing it, you can also make a dynamic service locator that allows you to stash any service you need into it and make your choices at runtime.

上面是一个静态定位器的例子——对于你所需要的每项服务,ServiceLocator 类都有对应的方法。这并不是实现服务定位器的唯一方式,你也可以创建一个动态服务定位器,你可以在其中注册需要的任何服务,并在运行期决定获得哪一项服务。

In this case, the service locator uses a map instead of fields for each of the services, and provides generic methods to get and load services.

在本例中,ServiceLocator 使用一个 map 来保存服务信息,而不再是将这些信息保存在字段中。此外,ServiceLocator 还提供了一个通用的方法,用于获取和加载服务对象。

class ServiceLocator...

private static ServiceLocator soleInstance;
public static void load(ServiceLocator arg) {
soleInstance = arg;
}
private Map services = new HashMap();
public static Object getService(String key){
return soleInstance.services.get(key);
}
public void loadService (String key, Object service) {
services.put(key, service);
}

Configuring involves loading a service with an appropriate key.

同样需要对服务定位器进行配置,将服务对象与适当的关键字加载到定位器中:

class Tester...

private void configure() {
ServiceLocator locator = new ServiceLocator();
locator.loadService("MovieFinder", new ColonMovieFinder("movies1.txt"));
ServiceLocator.load(locator);
}

I use the service by using the same key string.

我使用与服务对象类名称相同的字符串作为服务对象的关键字:

class MovieLister...

MovieFinder finder = (MovieFinder) ServiceLocator.getService("MovieFinder");

On the whole I dislike this approach. Although it’s certainly flexible, it’s not very explicit. The only way I can find out how to reach a service is through textual keys. I prefer explicit methods because it’s easier to find where they are by looking at the interface definitions.

总体而言,我不喜欢这种方式。无疑,这样实现的服务定位器具有更强的灵活性,但它的使用方式不够直观明朗。我只有通过文本形式的关键字才能找到一个服务对象。相比之下,我更欣赏“通过一个方法明确获得服务对象”的方式,因为这让使用者能够从接口定义中清楚地知道如何获得某项服务。

用 Avalon 兼顾服务定位器和依赖注入

Dependency injection and a service locator aren’t necessarily mutually exclusive concepts. A good example of using both together is the Avalon framework. Avalon uses a service locator, but uses injection to tell components where to find the locator.

Dependency Injection 和 Service Locator 两个模式并不是互斥的,你可以同时使用它们,Avalon 框架就是这样的一个例子。Avalon 使用了服务定位器,但“如何获得定位器”的信息则是通过注入的方式告知组件的。

Berin Loritsch sent me this simple version of my running example using Avalon.

对于前面一直使用的例子,Berin Loritsch 发送给了我一个简单的 Avalon 实现版本:

public class MyMovieLister implements MovieLister, Serviceable {
private MovieFinder finder;

public void service( ServiceManager manager ) throws ServiceException {
finder = (MovieFinder)manager.lookup(“finder”);
}

The service method is an example of interface injection, allowing the container to inject a service manager into MyMovieLister. The service manager is an example of a service locator. In this example the lister doesn’t store the manager in a field, instead it immediately uses it to lookup the finder, which it does store.

service 方法就是接口注入的例子,它使容器可以将一个 ServiceManager 对象注入 MyMovieLister 对象。ServiceManager 则是一个服务定位器。在这个例子中,MyMovieLister 并不把 ServiceManager 对象保存在字段中,而是马上借助它找到 MovieFinder 实例,并将后者保存起来。

作出一个选择 Deciding which option to use

So far I’ve concentrated on explaining how I see these patterns and their variations. Now I can start talking about their pros and cons to help figure out which ones to use and when.

到现在为止,我一直在阐述自己对这两个模式(Dependency Injection 模式和 Service Locator 模式)以及它们的变化形式的看法。现在,我要开始讨论他们的优点和缺点,以便指出它们各自适用的场景。

Service Locator vs. Dependency Injection

The fundamental choice is between Service Locator and Dependency Injection. The first point is that both implementations provide the fundamental decoupling that’s missing in the naive example - in both cases application code is independent of the concrete implementation of the service interface. The important difference between the two patterns is about how that implementation is provided to the application class. With service locator the application class asks for it explicitly by a message to the locator. With injection there is no explicit request, the service appears in the application class - hence the inversion of control.

首先,我们面临 Service Locator 和 Dependency Injection 之间的选择。应该注意,尽管我们前面那个简单的例子不足以表现出来,实际上这两个模式都提供了基本的解耦合能力——无论使用哪个模式,应用程序代码都不依赖于服务接口的具体实现。两者之间最重要的区别在于:这个“具体实现”以什么方式提供给应用程序代码。使用 Service Locator 模式时,应用程序代码直接向服务定位器发送一个消息,明确要求服务的实现;使用 Dependency Injection 模式时,应用程序代码不发出显式的请求,服务的实现自然会出现在应用程序代码中,这也就是所谓 “控制反转”

Inversion of control is a common feature of frameworks, but it’s something that comes at a price. It tends to be hard to understand and leads to problems when you are trying to debug. So on the whole I prefer to avoid it unless I need it. This isn’t to say it’s a bad thing, just that I think it needs to justify itself over the more straightforward alternative.

控制反转是框架的共同特征,但它也要求你付出一定的代价:它会增加理解的难度,并且给调试带来一定的困难。所以,整体来说,除非必要,否则我会尽量避免使用它。这并不意味着控制反转不好,只是我认为在很多时候使用一个更为直观的方案(例如 Service Locator 模式)会比较合适。

The key difference is that with a Service Locator every user of a service has a dependency to the locator. The locator can hide dependencies to other implementations, but you do need to see the locator. So the decision between locator and injector depends on whether that dependency is a problem.

一个关键的区别在于:使用 Service Locator 模式时,服务的使用者必须依赖于服务定位器。定位器可以隐藏使用者对服务具体实现的依赖,但你必须首先看到定位器本身。所以,问题的答案就很明朗了:选择 Service Locator 还是 Dependency Injection,取决于“对定位器的依赖”是否会给你带来麻烦。

Using dependency injection can help make it easier to see what the component dependencies are. With dependency injector you can just look at the injection mechanism, such as the constructor, and see the dependencies. With the service locator you have to search the source code for calls to the locator. Modern IDEs with a find references feature make this easier, but it’s still not as easy as looking at the constructor or setting methods.

Dependency Injection 模式可以帮助你看清组件之间的依赖关系:你只需观察依赖注入的机制(例如构造子),就可以掌握整个依赖关系。而使用 Service Locator 模式时,你就必须在源代码中到处搜索对服务定位器的调用。具备全文检索能力的 IDE 可以略微简化这一工作,但还是不如直接观察构造子或者设值方法来得轻松。

A lot of this depends on the nature of the user of the service. If you are building an application with various classes that use a service, then a dependency from the application classes to the locator isn’t a big deal. In my example of giving a Movie Lister to my friends, then using a service locator works quite well. All they need to do is to configure the locator to hook in the right service implementations, either through some configuration code or through a configuration file. In this kind of scenario I don’t see the injector’s inversion as providing anything compelling.

这个选择主要取决于服务使用者的性质。如果你的应用程序中有很多不同的类要使用一个服务,那么应用程序代码对服务定位器的依赖就不是什么大问题。在前面的例子中,我要把 MovieLister 类交给朋友去用,这种情况下使用服务定位器就很好:我的朋友们只需要对定位器做一点配置(通过配置文件或者某些配置性的代码),使其提供合适的服务实现就可以了。在这种情况下,我看不出 Dependency Injection 模式提供的控制反转有什么吸引人的地方。

The difference comes if the lister is a component that I’m providing to an application that other people are writing. In this case I don’t know much about the APIs of the service locators that my customers are going to use. Each customer might have their own incompatible service locators. I can get around some of this by using the segregated interface. Each customer can write an adapter that matches my interface to their locator, but in any case I still need to see the first locator to lookup my specific interface. And once the adapter appears then the simplicity of the direct connection to a locator is beginning to slip.

但是,如果把 MovieLister 看作一个组件,要将它提供给别人写的应用程序去使用,情况就不同了。在这种时候,我无法预测使用者会使用什么样的服务定位器 API,每个使用者都可能有自己的服务定位器,而且彼此之间无法兼容。一种解决办法是为每项服务提供单独的接口,使用者可以编写一个适配器,让我的接口与他们的服务定位器相配合。但即便如此,我仍然需要到第一个服务定位器中寻找我规定的接口。而且一旦用上了适配器,服务定位器所提供的简单性就被大大削弱了。

Since with an injector you don’t have a dependency from a component to the injector, the component cannot obtain further services from the injector once it’s been configured.

另一方面,如果使用 Dependency Injection 模式,组件与注入器之间不会有依赖关系,因此组件无法从注入器那里获得更多的服务,只能获得配置信息中所提供的那些。这也是 Dependency Injection 模式的局限性之一。

A common reason people give for preferring dependency injection is that it makes testing easier. The point here is that to do testing, you need to easily replace real service implementations with stubs or mocks. However there is really no difference here between dependency injection and service locator: both are very amenable to stubbing. I suspect this observation comes from projects where people don’t make the effort to ensure that their service locator can be easily substituted. This is where continual testing helps, if you can’t easily stub services for testing, then this implies a serious problem with your design.

人们倾向于使用 Dependency Injection 模式的一个常见理由是:它简化了测试工作。这里的关键是:出于测试的需要,你必须能够轻松地在“真实的服务实现”与“供测试用的‘伪’组件” 之间切换。但是,如果单从这个角度来考虑,Dependency Injection 模式和 Service Locator 模式其实并没有太大区别:两者都能够很好地支持“伪”组件的插入。之所以很多人有 “Dependency Injection 模式更利于测试”的印象,我猜是因为他们并没有努力保证服务定位器的可替换性。这正是持续测试起作用的地方:如果你不能轻松地用一些“伪”组件将一个服务架起来以便测试,这就意味着你的设计出现了严重的问题。

Of course the testing problem is exacerbated by component environments that are very intrusive, such as Java’s EJB framework. My view is that these kinds of frameworks should minimize their impact upon application code, and particularly should not do things that slow down the edit-execute cycle. Using plugins to substitute heavyweight components does a lot to help this process, which is vital for practices such as Test Driven Development.

当然,如果组件环境具有非常强的侵略性(就像 EJB 框架那样),测试的问题会更加严重。我的观点是:应该尽量减少这类框架对应用程序代码的影响,特别是不要做任何可能使“编辑-执行” 的循环变慢的事情。用插件(plugin)机制取代重量级组件会对测试过程有很大帮助,这正是测试驱动开发(Test Driven Development,TDD)之类实践的关键所在。

So the primary issue is for people who are writing code that expects to be used in applications outside of the control of the writer. In these cases even a minimal assumption about a Service Locator is a problem.

所以,主要的问题在于:代码的作者是否希望自己编写的组件能够脱离自己的控制、被使用在另一个应用程序中。如果答案是肯定的,那么他就不能对服务定位器做任何假设——哪怕最小的假设也会给使用者带来麻烦。

构造子注入 vs. 设值方法注入

For service combination, you always have to have some convention in order to wire things together. The advantage of injection is primarily that it requires very simple conventions - at least for the constructor and setter injections. You don’t have to do anything odd in your component and it’s fairly straightforward for an injector to get everything configured.

在组合服务时,你总得遵循一定的约定,才可能将所有东西拼装起来。依赖注入的优点主要在于:它只需要非常简单的约定——至少对于构造子注入和设值方法注入来说是这样。相比于这两者,接口注入的侵略性要强得多,比起 Service Locator 模式的优势也不那么明显。

Interface injection is more invasive since you have to write a lot of interfaces to get things all sorted out. For a small set of interfaces required by the container, such as in Avalon’s approach, this isn’t too bad. But it’s a lot of work for assembling components and dependencies, which is why the current crop of lightweight containers go with setter and constructor injection.

所以,如果你想要提供一个组件给多个使用者,构造子注入和设值方法注入看起来很有吸引力:你不必在组件中加入什么希奇古怪的东西,注入器可以相当轻松地把所有东西配置起来。

The choice between setter and constructor injection is interesting as it mirrors a more general issue with object-oriented programming - should you fill fields in a constructor or with setters.

设值函数注入和构造子注入之间的选择相当有趣,因为它折射出面向对象编程的一些更普遍的问题:应该在哪里填充对象的字段,构造子还是设值方法?

My long running default with objects is as much as possible, to create valid objects at construction time. This advice goes back to Kent Beck’s Smalltalk Best Practice Patterns: Constructor Method and Constructor Parameter Method. Constructors with parameters give you a clear statement of what it means to create a valid object in an obvious place. If there’s more than one way to do it, create multiple constructors that show the different combinations.

一直以来,我首选的做法是尽量在构造阶段就创建完整、合法的对象——也就是说,在构造子中填充对象字段。这样做的好处可以追溯到 Kent Beck 在 Smalltalk Best Practice Patterns 一书中介绍的两个模式:Constructor Method 和 Constructor Parameter Method。带有参数的构造子可以明确地告诉你如何创建一个合法的对象。如果创建合法对象的方式不止一种,你还可以提供多个构造子,以说明不同的组合方式。

Another advantage with constructor initialization is that it allows you to clearly hide any fields that are immutable by simply not providing a setter. I think this is important - if something shouldn’t change then the lack of a setter communicates this very well. If you use setters for initialization, then this can become a pain. (Indeed in these situations I prefer to avoid the usual setting convention, I’d prefer a method like initFoo, to stress that it’s something you should only do at birth.)

构造子初始化的另一个好处是:你可以隐藏任何不可变的字段——只要不为它提供设值方法就行了。我认为这很重要:如果某个字段是不应该被改变的,“没有针对该字段的设值方法”就很清楚地说明了这一点。如果你通过设值方法完成初始化,暴露出来的设值方法很可能成为你心头永远的痛。(实际上,在这种时候我更愿意回避通常的设值方法约定,而是使用诸如 initFoo 之类的方法名,以表明该方法只应该在对象创建之初调用。)

But with any situation there are exceptions. If you have a lot of constructor parameters things can look messy, particularly in languages without keyword parameters. It’s true that a long constructor is often a sign of an over-busy object that should be split, but there are cases when that’s what you need.

不过,世事总有例外。如果参数太多,构造子会显得凌乱不堪,特别是对于不支持关键字参数的语言更是如此。的确,如果构造子参数列表太长,通常标志着对象太过繁忙,理应将其拆分成几个对象,但有些时候也确实需要那么多的参数。

If you have multiple ways to construct a valid object, it can be hard to show this through constructors, since constructors can only vary on the number and type of parameters. This is when Factory Methods come into play, these can use a combination of private constructors and setters to implement their work. The problem with classic Factory Methods for components assembly is that they are usually seen as static methods, and you can’t have those on interfaces. You can make a factory class, but then that just becomes another service instance. A factory service is often a good tactic, but you still have to instantiate the factory using one of the techniques here.

如果有不止一种的方式可以构造一个合法的对象,也很难通过构造子描述这一信息,因为构造子之间只能通过参数的个数和类型加以区分。这就是 Factory Method 模式适用的场合了,工厂方法可以借助多个私有构造子和设值方法的组合来完成自己的任务。经典 Factory Method 模式的问题在于:它们往往以静态方法的形式出现,你无法在接口中声明它们。你可以创建一个工厂类,但那又变成另一个服务实体了。“工厂服务”是一种不错的技巧,但你仍然需要以某种方式实例化这个工厂对象,问题仍然没有解决。

Constructors also suffer if you have simple parameters such as strings. With setter injection you can give each setter a name to indicate what the string is supposed to do. With constructors you are just relying on the position, which is harder to follow.

如果要传入的参数是像字符串这样的简单类型,构造子注入也会带来一些麻烦。使用设值方法注入时,你可以在每个设值方法的名字中说明参数的用途;而使用构造子注入时,你只能靠参数的位置来决定每个参数的作用,而记住参数的正确位置显然要困难得多。

If you have multiple constructors and inheritance, then things can get particularly awkward. In order to initialize everything you have to provide constructors to forward to each superclass constructor, while also adding you own arguments. This can lead to an even bigger explosion of constructors.

如果对象有多个构造子,对象之间又存在继承关系,事情就会变得特别讨厌。为了让所有东西都正确地初始化,你必须将对子类构造子的调用转发给超类的构造子,然后处理自己的参数。这可能造成构造子规模的进一步膨胀。

Despite the disadvantages my preference is to start with constructor injection, but be ready to switch to setter injection as soon as the problems I’ve outlined above start to become a problem.

尽管有这些缺陷,但我仍然建议你首先考虑构造子注入。不过,一旦前面提到的问题真的成了问题,你就应该准备转为使用设值方法注入。

This issue has led to a lot of debate between the various teams who provide dependency injectors as part of their frameworks. However it seems that most people who build these frameworks have realized that it’s important to support both mechanisms, even if there’s a preference for one of them.

在将 Dependecy Injection 模式作为框架的核心部分的几支团队之间,“构造子注入还是设值方法注入”引发了很多的争论。不过,现在看来,开发这些框架的大多数人都已经意识到:不管更喜欢哪种注入机制,同时为两者提供支持都是有必要的。

代码配置 vs. 配置文件

A separate but often conflated issue is whether to use configuration files or code on an API to wire up services. For most applications that are likely to be deployed in many places, a separate configuration file usually makes most sense. Almost all the time this will be an XML file, and this makes sense. However there are cases where it’s easier to use program code to do the assembly. One case is where you have a simple application that’s not got a lot of deployment variation. In this case a bit of code can be clearer than a separate XML file.

另一个问题相对独立,但也经常与其他问题牵涉在一起:如何配置服务的组装,通过配置文件还是直接编码组装?对于大多数需要在多处部署的应用程序来说,一个单独的配置文件会更合适。配置文件几乎都是 XML 文件,XML 也的确很适合这一用途。不过,有些时候直接在程序代码中实现装配会更简单。譬如一个简单的应用程序,也没有很多部署上的变化,这时用几句代码来配置就比 XML 文件要清晰得多。

A contrasting case is where the assembly is quite complex, involving conditional steps. Once you start getting close to programming language then XML starts breaking down and it’s better to use a real language that has all the syntax to write a clear program. You then write a builder class that does the assembly. If you have distinct builder scenarios you can provide several builder classes and use a simple configuration file to select between them.

与之相对的,有时应用程序的组装非常复杂,涉及大量的条件步骤。一旦编程语言中的配置逻辑开始变得复杂,你就应该用一种合适的语言来描述配置信息,使程序逻辑变得更清晰。然后,你可以编写一个构造器(builder)类来完成装配工作。如果使用构造器的情景不止一种,你可以提供多个构造器类,然后通过一个简单的配置文件在它们之间选择。

I often think that people are over-eager to define configuration files. Often a programming language makes a straightforward and powerful configuration mechanism. Modern languages can easily compile small assemblers that can be used to assemble plugins for larger systems. If compilation is a pain, then there are scripting languages that can work well also.

我常常发现,人们太急于定义配置文件。编程语言通常会提供简捷而强大的配置管理机制,现代编程语言也可以将程序编译成小的模块,并将其插入大型系统中。如果编译过程会很费力,脚本语言也可以在这方面提供帮助。

It’s often said that configuration files shouldn’t use a programing language because they need to be edited by non-programmers. But how often is this the case? Do people really expect non-programmers to alter the transaction isolation levels of a complex server-side application? Non-language configuration files work well only to the extent they are simple. If they become complex then it’s time to think about using a proper programming language.

通常认为,配置文件不应该用编程语言来编写,因为它们需要能够被不懂编程的系统管理人员编辑。但是,这种情况出现的几率有多大呢?我们真的希望不懂编程的系统管理人员来改变一个复杂的服务器端应用程序的事务隔离等级吗?只有在非常简单的时候,非编程语言的配置文件才有最好的效果。如果配置信息开始变得复杂,就应该考虑选择一种合适的编程语言来编写配置文件。

One thing we’re seeing in the Java world at the moment is a cacophony of configuration files, where every component has its own configuration files which are different to everyone else’s. If you use a dozen of these components, you can easily end up with a dozen configuration files to keep in sync.

在 Java 世界里,我们听到了来自配置文件的不和谐音——每个组件都有它自己的配置文件,而且格式还各各不同。如果你要使用一打这样的组件,你就得维护一打的配置文件,那会很快让你烦死。

My advice here is to always provide a way to do all configuration easily with a programmatic interface, and then treat a separate configuration file as an optional feature. You can easily build configuration file handling to use the programmatic interface. If you are writing a component you then leave it up to your user whether to use the programmatic interface, your configuration file format, or to write their own custom configuration file format and tie it into the programmatic interface

在这里,我的建议是:始终提供一种标准的配置方式,使程序员能够通过同一个编程接口轻松地完成配置工作。至于其他的配置文件,仅仅把它们当作一种可选的功能。借助这个编程接口,开发者可以轻松地管理配置文件。如果你编写了一个组件,则可以由组件的使用者来选择如何管理配置信息:使用你的编程接口、直接操作配置文件格式,或者定义他们自己的配置文件格式,并将其与你的编程接口相结合。

分离配置与使用

The important issue in all of this is to ensure that the configuration of services is separated from their use. Indeed this is a fundamental design principle that sits with the separation of interfaces from implementation. It’s something we see within an object-oriented program when conditional logic decides which class to instantiate, and then future evaluations of that conditional are done through polymorphism rather than through duplicated conditional code.

所有这一切的关键在于:服务的配置应该与使用分开。实际上,这是一个基本的设计原则——分离接口与实现。在面向对象程序里,我们在一个地方用条件逻辑来决定具体实例化哪一个类,以后的条件分支都由多态来实现,而不是继续重复前面的条件逻辑,这就是“分离接口与实现”的原则。

If this separation is useful within a single code base, it’s especially vital when you’re using foreign elements such as components and services. The first question is whether you wish to defer the choice of implementation class to particular deployments. If so you need to use some implementation of plugin. Once you are using plugins then it’s essential that the assembly of the plugins is done separately from the rest of the application so that you can substitute different configurations easily for different deployments. How you achieve this is secondary. This configuration mechanism can either configure a service locator, or use injection to configure objects directly.

如果对于一段代码而言,接口与实现的分离还只是“有用”的话,那么当你需要使用外部元素(例如组件和服务)时,它就是生死攸关的大事。这里的第一个问题是:你是否希望将“选择具体实现类”的决策推迟到部署阶段。如果是,那么你需要使用插入技术。使用了插入技术之后,插件的装配原则上是与应用程序的其余部分分开的,这样你就可以轻松地针对不同的部署替换不同的配置。这种配置机制可以通过服务定位器来实现(Service Locator 模式),也可以借助依赖注入直接完成(Dependency Injection 模式)。

更多的问题 Some further issues

In this article, I’ve concentrated on the basic issues of service configuration using Dependency Injection and Service Locator. There are some more topics that play into this which also deserve attention, but I haven’t had time yet to dig into. In particular there is the issue of life-cycle behavior. Some components have distinct life-cycle events: stop and starts for instance. Another issue is the growing interest in using aspect oriented ideas with these containers. Although I haven’t considered this material in the article at the moment, I do hope to write more about this either by extending this article or by writing another.

在本文中,我关注的焦点是使用 Dependency Injection 模式和 Service Locator 模式进行服务配置的基本问题。还有一些与之相关的话题值得关注,但我已经没有时间继续申发下去了。特别值得注意的是生命周期行为的问题:某些组件具有特定的生命周期事件,例如“停止”、“开始”等等。另一个值得注意的问题是:越来越多的人对“如何在这些容器中运用面向方面(aspect oriented)的思想”产生了兴趣。尽管目前还没有认真准备过这方面的材料,但我也很希望以后能在这个话题上写一些东西。

You can find out a lot more about these ideas by looking at the web sites devoted to the lightweight containers. Surfing from the picocontainer and spring web sites will lead to you into much more discussion of these issues and a start on some of the further issues.

关于这些问题,你在专注于轻量级容器的网站上可以找到很多资料。浏览 PicoContainer(http://www.picocontainer.org)或者Spring(http://www.springframework.org)的网站,你可以找到大量相关的讨论,并由此引申出更多的话题。

结论和思考 Concluding Thoughts

The current rush of lightweight containers all have a common underlying pattern to how they do service assembly - the dependency injector pattern. Dependency Injection is a useful alternative to Service Locator. When building application classes the two are roughly equivalent, but I think Service Locator has a slight edge due to its more straightforward behavior. However if you are building classes to be used in multiple applications then Dependency Injection is a better choice.

在时下流行的轻量级容器都使用了一个共同的模式来组装应用程序所需的服务,我把这个模式称为 Dependency Injection,它可以有效地替代 Service Locator 模式。在开发应用程序时,两者不相上下,但我认为 Service Locator 模式略有优势,因为它的行为方式更为直观。但是,如果你开发的组件要交给多个应用程序去使用,那么 Dependency Injection 模式会是更好的选择。

If you use Dependency Injection there are a number of styles to choose between. I would suggest you follow constructor injection unless you run into one of the specific problems with that approach, in which case switch to setter injection. If you are choosing to build or obtain a container, look for one that supports both constructor and setter injection.

如果你决定使用 Dependency Injection 模式,这里还有几种不同的风格可供选择。我建议你首先考虑构造子注入;如果遇到了某些特定的问题,再改用设值方法注入。如果你要选择一个容器,在其之上进行开发,我建议你选择同时支持这两种注入方式的容器。

The choice between Service Locator and Dependency Injection is less important than the principle of separating service configuration from the use of services within an application.

Service Locator 模式和 Dependency Injection 模式之间的选择并是最重要的,更重要的是:应该将服务的配置和应用程序内部对服务的使用分离开。

致谢 Acknowledgments

My sincere thanks to the many people who’ve helped me with this article. Rod Johnson, Paul Hammant, Joe Walnes, Aslak Hellesøy, Jon Tirsén and Bill Caputo helped me get to grips with these concepts and commented on the early drafts of this article. Berin Loritsch and Hamilton Verissimo de Oliveira provided some very helpful advice on how Avalon fits in. Dave W Smith persisted in asking questions about my initial interface injection configuration code and thus made me confront the fact that it was stupid. Gerry Lowry sent me lots of typo fixes - enough to cross the thanks threshold.

在此,我要向帮助我理解本文中所提到的问题、并对本文提出宝贵意见的几个人表示感谢,他们是 Rod Johnson、Paul Hammant、Joe Walnes、Aslak Hellesoy、Jon Tirsen 和 Bill Caputo。另外,Berin Loritsch 和 Hamilton Verissimo de Oliveira 在 Avalon 方面给了我非常有用的建议,一并向他们表示感谢。

☑️ ☆

League Director Tutorial -- Install and Run

引言

League Director is a tool for staging and recording videos from League of Legends replays.

Install

Github 下载

最正统的官方下载渠道,下载链接:https://github.com/RiotGames/leaguedirector/releases/tag/v0.1.4

服务器下载

我自己的云存储服务器上也做了一个备份方便大家下载,下载链接:

汉化版的版本比较低,但原版在国服会有一些莫名奇妙的问题,所以还是推荐下载第二个链接。

Feature

  • Control replay playback and speed
  • First person camera controls
  • Attach camera to champion or minion
  • Toggle interface elements including HUD, health bars and notifications
  • Graphical Options
    • Field of view
      Near and far clipping
      Custom skyboxes
      Shadow direction
      Depth and height fog
      Depth of field
  • Sequencer
    • Record and playback keyframed camera position + graphical options
    • Timeline for viewing and editing keyframe values
    • Undo / Redo
    • Save and load pre saved sequences
    • Adjustable keyframe blending
  • Video capture in webm or png format
  • Customizable key bindings

How To Use

Note: Windows Only

  1. Download League Director from the releases page and install.
  2. Start League Director and make sure the checkbox next to your install is checked.
  3. Start League of Legends and launch a replay. League Director will automatically connect.
  4. Open the options menu (ESC key) in game and ensure your Video Graphics settings are set to Very High. If you did need to change your Video Graphics settings, you’ll need to restart the replay to enable the additional rendering features like the skybox.
  5. Select FPS Camera from the Camera Modes drop down in game.
  6. Using the numpad keys (4, 5, 6, 8) and the mouse you can free camera move around. Key bindings for free camera can also be changed inside the game options.

安装一下 SetUp.exe,一路点确定即可。打开程序首先会弹出游戏的安装路径确认窗口:

选择好之后启动游戏并打开录像,就会有如下界面:

☑️ ☆

奇瑞万达端子线号查询定制项目总结

引言

奇瑞万达需要实现快速选择、对比、修改端子功能端子查询功能,做一下项目的总结。

为实体添加扩展数据

删除端子实体时需要一个识别标记,我选择加入扩展数据作为标识符:

  1. 注册一个不会重名的 appName
  2. 创建你所需要的 xData 缓冲区链表
  3. 把这个数据放到实体中
const CString appName = L"SelectXDataApp";

acdbRegApp(appName);
struct resbuf* rb = acutBuildList(AcDb::kDxfRegAppName, appName,
AcDb::kDxfXdAsciiString, TEXT("xxxxxxx"),
RTNONE);

pPline->setXData(rb);
acutRelRb(rb);

acutBuildList() 创建链表时前两个默认为 APP 类型和 APP 名称,后面也是以 type-value 的形式两两创建链表数据。

模态对话框中实现用户和 CAD 的交互操作

问题描述

现在的业务场景需要在弹出模态对话框之后再返回 CAD 选择实体(也就是端子),再重新显示对话框。

最开始我的处理办法是将模态对话框改为非模态对话框,但在对话框的生命周期控制上很难把控,问题比较多,所以目光又重新回到如何使用模态对话框处理这类场景。

文档查阅

在模态对话框中实现用户和AutoCAD 的交互操作 这篇文章提到使用 BeginEditorCommand() 这个方法去从模态对话框切换到 CAD 应用程序,下面是 官方文档 的描述:

Call this method to indicate an AutoCAd interactive command is starting.

还贴心的给了一个使用示例:

BeginEditorCommand();
if (DoMyInteractiveCommand())
CompleteEditorCommand();
else
CancelEditorCommand();
  • BeginEditorCommand 函数用于将控制权(焦点)交给 CAD,一般用于开始一个交
    互操作
  • CompleteEditorCommand 函数用于从一个在 CAD 中完成的交互命令返回到应用
    程序
  • CancelEditorCommand 函数用于从一个在 CAD 中被取消的交互命令返回到应用程

这三个函数组合使用,能够在模态对话框中实现用户和 CAD 的交互操作。

解决方案

ads_point point{ 0 };
ads_name selectUnit { 0, 0 };

BeginEditorCommand();
auto res = acedEntSel(L"\n请选择需要提取的端子:\n", selectUnit, point);
CompleteEditorCommand();

实体高亮显示

问题描述

奇瑞万达方面需要在选择所有端子后所有都高亮显示,并且能够显示出各自的夹点。

一开始不知道高显这个效果该如何实现,尝试直接调用实体的 highlight() 方法高亮。这种方式没有夹点,在缩放后也没有虚化边框那样明显的视觉效果,客户方面不接受这样的高显只能另寻他法。后面在网上查阅到 ARX亮显问题,里面提到了使用 acedSSSetFirst 这个方法。

文档查阅

由于之前从来没用过这个方法,本着严谨的态度去 官方文档 上又查了一下如何使用。

int acedSSSetFirst(
const ads_name pset,
const ads_name unused
);
  • pset:Set of entities to be added to the pickfirst selection set and on which grips will be displayed
  • unused:Ignored

This function sets which objects are selected and gripped.

The parameters have the following data type definition:

typedef long ads_name[2];

The selection set of objects specified by the gset argument are gripped, and the selection set of objects specified by pset are both gripped and selected. If any objects are common to both selection sets, acedSSSetFirst() grips and selects the selection set specified by pset only (it does not grip the gset set).

If gset is NULL and pset is specified, acedSSSetFirst() grips and selects pset. If gset and pset are NULL, acedSSSetFirst() turns off any existing grips and selections.

You are responsible for creating a valid selection set. For example, you may need to verify that a background paper space viewport (DXF group code 69) is not included in the selection set. You may also need to ensure that selected objects belong to the current layout.

Note The addCommand() optional flags ACRX_CMD_USEPICKSET and ACRX_CMD_REDRAW must be used in order for acedSSSetFirst() to work.

Do not call acedSSSetFirst() when AutoCAD is in the middle of executing a command.

解决方案

照着人家给的示例代码照猫画虎,也算达到效果了:

ads_name ssName, ssTemp;
acedSSAdd(NULL, NULL, ssTemp);

acedSSGet(NULL, NULL, NULL, NULL, ssName);
Adesk::Int32 len = 0;
acedSSLength(ssName, &len);

for (auto i = 0; i < len; i++)
{
ads_name ent = {0, 0};
if (acedSSName(ssName, i, ent) != RTNORM) continue;

AcDbObjectId idEnt = AcDbObjectId::kNull;
acdbGetObjectId(idEnt, ent);

AcDbEntity *pEnt = NULL;
if (acdbOpenAcDbEntity(pEnt, idEnt, AcDb::kForRead) != eOk) continue;
acedSSAdd(ent, ssTemp, ssTemp);

pEnt->close();
}
acedSSFree(ssName);
acedSSSetFirst(ssTemp, NULL);

acedSSFree(ssTemp);

注意启动命令要设置为 ACRX_CMD_REDRAW | ACRX_CMD_USEPICKSETacedSSSetFirst 可以控制加点或者选择的显示,但要注意注册命令的参数。

acedRegCmds->addCommand(_T("xxxxxx"), _T("xxx"), _T("xxx"), ACRX_CMD_TRANSPARENT | ACRX_CMD_USEPICKSET | ACRX_CMD_REDRAW, function);

基于LRU的缓存算法实现

奇瑞万达业务上需要下拉框有记忆功能(即下拉框顺序需要以 最近最少使用 的原则去缓存),在 LeetCode 中也有类似的题目(146. LRU 缓存)。

题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类:

  • LRUCache(int capacity)正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

函数 getput 必须以 O(1) 的平均时间复杂度运行。

示例:

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示:

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 10^5
  • 最多调用 2 * 10^5getput
class LRUCache {
public:
LRUCache(int capacity) {

}

int get(int key) {

}

void put(int key, int value) {

}
};

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/

解决方案

思路

  1. 保持把新鲜数据往链表头移动。新鲜的定义:刚被修改(put),或者访问过(get),就算新鲜,就需要 splice 到链表头
  2. 过期键直接 pop_back(),链表节点越往后,越陈旧
class LRUCache {
public:
LRUCache(int capacity) : _capacity(capacity) {

}

int get(int key) {
auto it = _table.find(key);
if (it != _table.end()) {
_lru.splice(_lru.begin(), _lru, it->second);
return it->second->second;
}
return -1;
}

void put(int key, int value) {
auto it = _table.find(key);
if (it != _table.end()) {
_lru.splice(_lru.begin(), _lru, it->second);
it->second->second = value;
return;
}

_lru.emplace_front(key, value);
_table[key] = _lru.begin();

if (_table.size() > _capacity) {
_table.erase(_lru.back().first);
_lru.pop_back();
}
}
private:
unordered_map<int, std::list<std::pair<int, int>>::iterator> _table;
std::list<std::pair<int, int>> _lru;
int _capacity;
};

代码要领

  1. map 中保存的是 <key, 链表节点的指针>,这样查找的时候就不用需要去遍历链表了,使用 unordered_map 就能很快找到链表节点指针
  2. 判断容量的时候,最好不使用 std::list::size() 方法,在 c++ 里,这个方法可能不是 O(1) 的。
☑️ ⭐

东方锅炉图纸清洗项目总结

引言

去东方电气集团旗下的东方锅炉做图纸清洗驻场开发,抽出时间总结一下。

达梦数据库调用

数据库连接

与 MySQL 类似的调用方法,但是似乎 Nuget 上面的包有些问题,我是直接调用本地的 DmProvider.dll 添加引用:

var connection = new DmConnection();
connection.ConnectionString = $"Server={server}; Port={port}; User Id={user}; PWD={password}";
connection.Open();

SQL语句调用

using (var command = new DmCommand("sql语句", connection))
using (var reader = command.ExecuteReader())
{
while (reader.Read())
{
var ret = reader.GetString(0);
......
}
}
☑️ ☆

奇瑞万达端子查询项目总结

引言

奇瑞万达端子查询功能开发的项目总结。

实体高亮显示

问题描述

奇瑞万达方面需要在选择所有端子后所有都高亮显示,并且能够显示出各自的夹点。

一开始不知道高显这个效果该如何实现,尝试直接调用实体的 highlight() 方法高亮。这种方式没有夹点,在缩放后也没有虚化边框那样明显的视觉效果,客户方面不接受这样的高显只能另寻他法。后面在网上查阅到 ARX亮显问题,里面提到了使用 acedSSSetFirst 这个方法。

文档查阅

由于之前从来没用过这个方法,本着严谨的态度去 官方文档 上又查了一下如何使用。

int acedSSSetFirst(
const ads_name pset,
const ads_name unused
);
  • pset:Set of entities to be added to the pickfirst selection set and on which grips will be displayed
  • unused:Ignored

This function sets which objects are selected and gripped.

The parameters have the following data type definition:

typedef long ads_name[2];

The selection set of objects specified by the gset argument are gripped, and the selection set of objects specified by pset are both gripped and selected. If any objects are common to both selection sets, acedSSSetFirst() grips and selects the selection set specified by pset only (it does not grip the gset set).

If gset is NULL and pset is specified, acedSSSetFirst() grips and selects pset. If gset and pset are NULL, acedSSSetFirst() turns off any existing grips and selections.

You are responsible for creating a valid selection set. For example, you may need to verify that a background paper space viewport (DXF group code 69) is not included in the selection set. You may also need to ensure that selected objects belong to the current layout.

Note The addCommand() optional flags ACRX_CMD_USEPICKSET and ACRX_CMD_REDRAW must be used in order for acedSSSetFirst() to work.

Do not call acedSSSetFirst() when AutoCAD is in the middle of executing a command.

解决方案

照着人家给的示例代码照猫画虎,也算达到效果了:

ads_name ssName, ssTemp;
acedSSAdd(NULL, NULL, ssTemp);

acedSSGet(NULL, NULL, NULL, NULL, ssName);
Adesk::Int32 len = 0;
acedSSLength(ssName, &len);

for (auto i = 0; i < len; i++)
{
ads_name ent = {0, 0};
if (acedSSName(ssName, i, ent) != RTNORM) continue;

AcDbObjectId idEnt = AcDbObjectId::kNull;
acdbGetObjectId(idEnt, ent);

AcDbEntity *pEnt = NULL;
if (acdbOpenAcDbEntity(pEnt, idEnt, AcDb::kForRead) != eOk) continue;
acedSSAdd(ent, ssTemp, ssTemp);

pEnt->close();
}
acedSSFree(ssName);
acedSSSetFirst(ssTemp, NULL);

acedSSFree(ssTemp);

注意启动命令要设置为 ACRX_CMD_REDRAW | ACRX_CMD_USEPICKSETacedSSSetFirst 可以控制加点或者选择的显示,但要注意注册命令的参数。

acedRegCmds->addCommand(_T("xxxxxx"), _T("xxx"), _T("xxx"), ACRX_CMD_TRANSPARENT | ACRX_CMD_USEPICKSET | ACRX_CMD_REDRAW, function);

基于LRU的缓存算法实现

奇瑞万达业务上需要下拉框有记忆功能(即下拉框顺序需要以 最近最少使用 的原则去缓存),在 LeetCode 中也有类似的题目(146. LRU 缓存)。

题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类:

  • LRUCache(int capacity)正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

函数 getput 必须以 O(1) 的平均时间复杂度运行。

示例:

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示:

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 10^5getput
class LRUCache {
public:
LRUCache(int capacity) {

}

int get(int key) {

}

void put(int key, int value) {

}
};

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/

实体高亮显示

问题描述

奇瑞万达方面需要在选择所有端子后所有都高亮显示,并且能够显示出各自的夹点。

一开始不知道高显这个效果该如何实现,尝试直接调用实体的 highlight() 方法高亮。这种方式没有夹点,在缩放后也没有虚化边框那样明显的视觉效果,客户方面不接受这样的高显只能另寻他法。后面在网上查阅到 ARX亮显问题,里面提到了使用 acedSSSetFirst 这个方法。

文档查阅

由于之前从来没用过这个方法,本着严谨的态度去 官方文档 上又查了一下如何使用。

int acedSSSetFirst(
const ads_name pset,
const ads_name unused
);
  • pset:Set of entities to be added to the pickfirst selection set and on which grips will be displayed
  • unused:Ignored

This function sets which objects are selected and gripped.

The parameters have the following data type definition:

typedef long ads_name[2];

The selection set of objects specified by the gset argument are gripped, and the selection set of objects specified by pset are both gripped and selected. If any objects are common to both selection sets, acedSSSetFirst() grips and selects the selection set specified by pset only (it does not grip the gset set).

If gset is NULL and pset is specified, acedSSSetFirst() grips and selects pset. If gset and pset are NULL, acedSSSetFirst() turns off any existing grips and selections.

You are responsible for creating a valid selection set. For example, you may need to verify that a background paper space viewport (DXF group code 69) is not included in the selection set. You may also need to ensure that selected objects belong to the current layout.

Note The addCommand() optional flags ACRX_CMD_USEPICKSET and ACRX_CMD_REDRAW must be used in order for acedSSSetFirst() to work.

Do not call acedSSSetFirst() when AutoCAD is in the middle of executing a command.

解决方案

照着人家给的示例代码照猫画虎,也算达到效果了:

ads_name ssName, ssTemp;
acedSSAdd(NULL, NULL, ssTemp);

acedSSGet(NULL, NULL, NULL, NULL, ssName);
Adesk::Int32 len = 0;
acedSSLength(ssName, &len);

for (auto i = 0; i < len; i++)
{
ads_name ent = {0, 0};
if (acedSSName(ssName, i, ent) != RTNORM) continue;

AcDbObjectId idEnt = AcDbObjectId::kNull;
acdbGetObjectId(idEnt, ent);

AcDbEntity *pEnt = NULL;
if (acdbOpenAcDbEntity(pEnt, idEnt, AcDb::kForRead) != eOk) continue;
acedSSAdd(ent, ssTemp, ssTemp);

pEnt->close();
}
acedSSFree(ssName);
acedSSSetFirst(ssTemp, NULL);

acedSSFree(ssTemp);

注意启动命令要设置为 ACRX_CMD_REDRAW | ACRX_CMD_USEPICKSETacedSSSetFirst 可以控制加点或者选择的显示,但要注意注册命令的参数。

acedRegCmds->addCommand(_T("xxxxxx"), _T("xxx"), _T("xxx"), ACRX_CMD_TRANSPARENT | ACRX_CMD_USEPICKSET | ACRX_CMD_REDRAW, function);

基于LRU的缓存算法实现

奇瑞万达业务上需要下拉框有记忆功能(即下拉框顺序需要以 最近最少使用 的原则去缓存),在 LeetCode 中也有类似的题目(146. LRU 缓存)。

题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类:

  • LRUCache(int capacity)正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

函数 getput 必须以 O(1) 的平均时间复杂度运行。

示例:

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示:

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 10^5getput
class LRUCache {
public:
LRUCache(int capacity) {

}

int get(int key) {

}

void put(int key, int value) {

}
};

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
☑️ ☆

送给入门主播的一份 OBS Studio 直播指南

引言

记录博主个人使用 OBS Studio 直播的心得体会。

软件简介

截取一段维基百科的概述:

OBS 是一个用于录制和进行网络直播的自由开源软件包。OBS 使用 C 和 C++ 语言编写,提供实时源和设备捕获、场景组成、编码、录制和广播。数据传输主要通过实时消息协议 RTMP 完成,可以发送到任何支持RTMP的软件,包括 YouTube、Twitch、Instagram 和 Facebook 等流媒体网站。

OBS 相比各大平台自己的直播软件功能更强大,也能在几乎所有平台上直播,很多全职主播的直播画面都是通过 OBS 精心调配的

对于我们使用者来讲,需要着重关注它的 开源 特性:

  • 开源意味着我们可以免费获取该软件,无需额外投入付出(那些让你付费获取的都是骗子和坏蛋!)
  • 这种体量的开源软件通常会有比较稳定的生态,遇到问题可以上论坛提问,也可以根据自己的需求搭配各种第三方插件

基本使用

OBS 下载

万事开头难,OBS 有四种不同的下载途径。

官网下载

从官方网站下载软件虽然很简单,但是我认为这是现代人类上网冲浪的基本修养,请不要在从莫名其妙还带着色情赌博诈骗广告的网站上下载东西了!

进入 OBS官网,选择自己的平台下载即可,这里我也是直接给出下载链接:

Windows MacOS (Intel) macOS (Apple Silicon) Linux
steam 下载

前段时间 OBS 登陆了 steam,没听错,你甚至可以在 steam 上下载 OBS Studio:

在 steam 上直接搜索 OBS Studio ,进入页面点击获取即可:

github 下载

作为开源软件怎么能没有大名鼎鼎的 github 呢?github 搜索 OBS Studio 进入 Release 界面,选择自己需要的平台和版本下载最原汁原味的软件安装包:

需要注意的是如果没有魔法,下载速度应该比较慢,如果只是普通使用者不推荐这种下载方式。

清华镜像源下载(推荐)

既然 OBS 是开源软件,但没有魔法下载又很慢,那为什么不问问神奇的 清华大学开源软件镜像站 呢?

搜索 OBS 选择并下载:

画面推流

直播间优化

第三方插件推荐

模糊/Blur

  • 插件地址:
  • 官方文档:

输入叠加/Input Overlay

简易时钟挂件/Mc-Clock

ダウンロードせずに使える「OBS用デジタル時計」をオンライン上に設置しました。

htmlの書き換えが不要な場合は以下のURLをOBSで読み込んでご利用ください。

ダウンロード版はこちら

  • clock01 : [https://stock.mooncape.net/mc-clock/clock01](https://stock.mooncape.net/mc-clock/clock01)
  • clock02 : [https://stock.mooncape.net/mc-clock/clock02](https://stock.mooncape.net/mc-clock/clock02)
  • clock03 : [https://stock.mooncape.net/mc-clock/clock03](https://stock.mooncape.net/mc-clock/clock03)
  • clock04 : [https://stock.mooncape.net/mc-clock/clock04](https://stock.mooncape.net/mc-clock/clock04)
  • clock05 : [https://stock.mooncape.net/mc-clock/clock05](https://stock.mooncape.net/mc-clock/clock05)

英雄联盟直营服账号数据展示/LoboBot

Creating a League of Legends box

  1. Go to /lol
  2. Add your League Of Legends account. You must change your profile icon with the one provided by LoboBot.
  1. 进入游戏 /lol
  2. 把游戏头像换成这个狼人模样以完成 LoboBot 对你账户拥有权的验证

  1. If all goes well, you will see a message saying that your account has been added successfully.
  2. Click on the account and you will see a both queues (Ranked Solo and Ranked Flex). Select the queue you want to show.
  1. 如果一切顺利,你会看到一条账户添加成功的信息
  2. 点击账户你会看到 单/双排位灵活组排 的战绩,选择你想展示的战绩

  1. Click on the desired box, customize it and finally click on the Create Box button.
  2. Use the link to add the box to your stream.
  1. 选择你喜欢的 box,客制化后点击 Create Box
  2. 通过链接推流到直播间
Adding the box in OBS
  1. Once you have created the box, you will see a link to add the box to your stream.
  2. Copy the link and create a Browser Source in OBS sources.
  3. Paste the link in the URL field. Keep default settings and click on OK.

  1. 当你创建 box 之后,你会得到一个用于推流到直播间的链接
  2. 在 OBS 中创建一个浏览器源
  3. 把刚才 LoboBot 的链接拷贝过来(长度、宽度和位置自己调整)点击确定

后面两种方式我自己没有尝试过,应该都是通过插入浏览器源的方式,故不做翻译了。

Creating a Spotify box
  1. Go to lobobot.com/spotify
  2. Click on the Connect Spotify button.
  3. You will be redirected to Spotify to login and authorize LoboBot to access your account.
  4. Once you have authorized LoboBot, you will be redirected back.
  5. In options, you can customize the box and finally click on the Save Options button.
  6. Use the link to add the box to your stream.
Adding the box in Streamlabs Desktop
  1. Once you have created the box, you will see a link to add the box to your stream.
  2. Copy the link and create a Browser Source in Streamlabs Desktop sources.
  3. Paste the link in the URL field. Keep default settings and click on OK.

自定义 Spotify 音乐播放器

之前在看瓦的pov时候很多主播都用了这个,苦苦查了很久终于在油管上找到了定制教程 The BEST Now Playing Music Widget For Your Stream! (Spotify & YouTube Music)

注册 6klabs

选择 Twitch 或者 Google 账号进行登录:

选择 Accounts & Apps 链接 Soptify。

链接 Soptify
Create Your App

This is a step-by-step tutorial on how to create your Spotify app and link it to 6K Labs.

  1. Visit the Spotify Developer Dashboard
  2. Click on Log in in the top right

这是手把手教你如何创建自己的 Spotify 应用并链接到 6K Labs。

  1. 访问 Spotify 的 Developer Dashboard

  2. 点击右上角的 Log in 登录自己的 Spotify 账号

  1. Once logged in, click on your name. A dropdown appears. Click on Dashboard.
  1. 登陆后点击自己的用户名,选择 Dashboard

  1. Create a new app by clicking on Create app
  1. 点击 Create app 创建一个新的应用程序

  1. Enter this information, then click on Save
  • App Name: Amuse Widget
  • App description: This is an app for the 6K Labs Amuse widget.
  • Redirect URI: https://api.6klabs.com/api/spotify/callback
  1. 输入以下信息并点击保存:
    • App Name:随便填一点
    • App description:随便填一点
    • Redirect URI: https://api.6klabs.com/api/spotify/callback

前面两个可以随便填,第三个 URL 必须填上面 6klabs 的这个链接

  1. Click on Settings
  1. 点击设置 Settings

  1. Click on View client secret
  1. 点击 View client secret

  1. Copy and paste the Client ID and Client Secret into the Amuse Spotify App form
  1. 复制粘贴 Client IDClient Secret 到之前的 6KLabs 链接界面

  1. Click on “Connect” and approve the app.

  2. Enjoy! ✨

  1. 点击 Connect 链接应用程序
  2. ok了 ✨
Troubleshooting
  1. INVALID_CLIENT: Invalid client

    In the event that you click on Connect and receive the INVALID_CLIENT: Invalid client error, this could indicate an incorrect Client ID. Please ensure to verify the correctness of your Client ID.

  2. INVALID_SECRET: Invalid client_secret

    In the event that you click on Connect and receive the INVALID_SECRET: Invalid client_secret error, it suggests that your Client Secret may be incorrect. Please ensure to verify the correctness of your Client Secret.

  3. INVALID_CLIENT: Invalid redirect URI

    In the event that you click on Connect and receive the INVALID_CLIENT: Invalid redirect URI error, it implies that the Redirect URL you entered in step 3 may be incorrect. Please ensure to verify the correctness of your Redirect URL.

自定义 Widgets

心率展示

Garmin

https://www.hyperate.io/#1

心率显示对于佳明设备来说比较简单,在 ConnectIQ 中下载应用程序 HypeRate,之后打开手表就会广播一个你设备心率的网站地址:app.hyperate.io/xxxxx。

把这个网址放到 OBS 的浏览器源自己调整即可。

Xiaomi

小米我没有相应设备,网上搜到一篇文章仅供参考:直播实时显示心率(OBS-HeartRate)

常见问题整理

黑屏无法捕获

部分笔记本使用了混合输出技术,需要把 OBS 设置为核显输出才能正确捕获内容。

☑️ ☆

送给新主播的一份 OBS Studio 直播指南

引言

记录博主个人使用 OBS Studio 直播的心得体会。

软件简介

截取一段维基百科的概述:

OBS 是一个用于录制和进行网络直播的自由开源软件包。OBS 使用 C 和 C++ 语言编写,提供实时源和设备捕获、场景组成、编码、录制和广播。数据传输主要通过实时消息协议 RTMP 完成,可以发送到任何支持RTMP的软件,包括 YouTube、Twitch、Instagram 和 Facebook 等流媒体网站。

对于我们使用者来讲,只需要关注其中三个关键词:开源录制直播

基本使用

OBS 下载

直播间美化

常见问题整理

☑️ ☆

从 R3nzskin 项目窥见中国开源生态的现状及未来

引言

R3nzskin 这个项目我关注了小半年,也算是见证了这个开源项目的兴衰。深夜有感,决定写一篇博文来记录一下我的所见所闻,也希望能给其他开源项目和开发者一些启发和经验。

与 R3 的邂逅

我本人是游戏《英雄联盟》(League of Legends) 的狂热玩家,从大学开始就很喜欢玩这个游戏,也从中收获了很多快乐。

然而秉持着 “差生文具多” 的原则,我在腾讯代理的国服和拳头公司的直营服都为英雄买了很多皮肤,但我并没有足够的经济能力去购买所有我想要和喜欢的皮肤,恰好听闻现在有许多 “换肤” 软件可以使用(老玩家的话可能知道以前的多玩盒子),便踏上了使用换肤软件的道路。

最开始我找到的是大名鼎鼎的 LOLskin

坦诚来说,它的使用并不方便,但是有如此海量的皮肤选择对于我而言已经足够了,更何况这个换肤软件本身就是免费的,我的钱包也终于能松一口气。

然而 LOLSkin 有一个问题:每次游戏版本更新它都必须重新从官网去下载,国服玩家还必须在更新后去等官网的 .1 版本,还是比较繁琐的。作为懒人代表,我把目光放到了淘宝,寄希望于消费获取比较稳定不需要每个游戏版本都要重新折腾的换肤软件。

淘宝网上这类换肤盒子软件眼花缭乱,我尝试了两个买量比较多的店铺,使用上还是比较复杂。共性上两款软件都需要通过远程服务器验证后才可以使用,付费模式就是购买体验卡包月、季、年这样,换肤模式仍是游戏开始前提前手动选择好需要的皮肤。 这种模式我也不是很喜欢,所以还是换回了 LOLskin 使用,同时也逛逛相关的帖子看看有什么比较好的换肤软件。

转机在有一天某位吧友提到了 R3nzskin 换肤效果不错,我就去搜索了一下:

居然还是开源项目,作为程序员那必须上手体验一番了。

从使用者到布道者

C++ 大师侯捷在《Effective C++》中曾经提到,许多新技术得以推广应用,除了发明者的辛劳付出,也离不开许多布道者用通俗易懂的方式去教授讲解。

本着开源共享的精神,我找到了 R3nzskin 的贴吧,发了一篇手把手教如何使用 R3nzskin 的教学帖

截止到写这篇博文为止,这个教学贴拥有 21w 阅读量、658 条回帖以及 227 个点赞,可以肯定的是这个帖子帮助了很多和我一样的人,并且让这个开源项目能够被更多人所熟知。

不仅如此,事实上我也花了一个下午去做了详细的使用教学视频投稿到 bilibili,然而不到半个小时审核就把我的视频下架了,理由是破坏计算机安全:

不过吧主制作了类似的视频用以教学,只是我的视频第一次下架的理由是涉及宣传和广告还是令人啼笑皆非,一个开源软件又哪里有广告呢?

更多的信徒

随着许多朋友的共同努力,R3 在换肤已经小有名气,我有时间也会解答许多朋友遇到的常见问题例如缺失 dll、版本不匹配等等。有人在吧里收集皮肤 bug 提 issue,也有开发直接提交 pr 帮助完善这个项目,我自己也抽时间看了一些项目的源码,但逆向这块技术栈确实不太了解而且工作比较忙,所以后面就没再研究了。

项目中也加入了国人开发者 rainzee 支持国服版本,总之似乎一切都在向好的方向去发展。

与此同时淘宝店家自然不能放过这种赚钱的机会,他们把 R3 免费开源的软件套壳成之前那种需要服务器远程验证付费的样子去倒卖给那些无知的人,吧里也出现了一些倒狗。

大洪水

R3 很快被腾讯盯上了,也可以理解,毕竟断人财路如杀人父母,皮肤可以说占这个游戏 95%+ 的收入都不为过,在国服换肤自然不可能放过(使用 LOLSkin 也有一定概率受到处罚)。 很多人开始抱怨不能在国服使用,但也只是埋怨腾讯,而且恰逢当时拳头直营的台服刚开服,所以许多人跑去外服接着用,也没什么大问题。

大洪水源自 R3 项目原作者需要服兵役,可能未来不会频繁更新项目。

许多朋友感到惋惜,这么好用的软件以后没有人维护,我也给作者发了一封邮件去交流这个项目关于技术上的一些问题,看能不能接手下来继续维护,但是作者一直没有回复我,只好作罢。

一部分开发者开始自救,在 R3 的基础上创建仓库开始自己维护这个项目,其中不乏上面的淘宝店家混入其中推广自己套壳的付费换肤。

最后一根稻草

压死骆驼的最后一根稻草是拳头的一次更新(v13.5),这次更新让之前用旧版本的 R3 玩家在角色死亡后换肤失效:

无数质疑涌向了 R3,倒狗们宣传着 “自己开发 稳定维护” 的套壳 R3,许多人转而投向这些倒狗的怀抱,同时控诉着 R3 不作为。

农夫与蛇

R3 后续还是更新了,但是存在使用时严重掉帧的问题,不能像之前一样正常使用。

R3 的国服开发者 rainzee 加入了 R3 贴吧,决定把自己改过的不掉帧稳定的修改版本分享给大家,但出于对套壳奸商的警惕决定也采用服务器发放许可的方式,虽然许可获取是免费的,但这恰恰成为了许多人攻击的源头。

他们认为 rainzee 就是没赚到钱所以不维护 R3 项目的后续,将开源分享的精神理念和和心怀感恩体谅的情感抛之脑后,对参与 R3 项目的开发者当作倒狗肆意谩骂,更有甚者对着那些主动无偿维护、自愿汉化的贡献者谩骂侮辱,这可能是我自参与开源社区以来见到的最荒谬的事情了。

理想主义之死

他们赢了,他们也输了。

rainzee 发了声明,选择离开了这里,又一位理想主义者离我们而去,也让我想起之前看到的 开源人宣言

开源人宣言 - Open Source Fans Manifesto

我们是一群开源的爱好者与信仰者,我们相信:开源代表着一种向善的力量!作为一场席卷全球的世界性运动,20 多年来的历史证明,开源不仅仅能够孕育最新的技术、创造更好的软件,更能够帮助这个世界变得更好。

开源精神

剖析开源的内涵,理解开源的精神,能够让我们理解,为何开源能够让世界变得更好。在我们看来,开源的精神体现在以下一些方面:

分享(Sharing)

当一个软件工程师写出一个不错的软件,他不会敝帚自珍,不会故步自封。他乐于分享,是因为他相信:这个软件可能会对别人也有帮助,更会有人帮助他,一起做出更好的软件。西谚有云:赠人玫瑰,手留余香。我们都相信:乐于分享是一切善举的开端。

开放(openness)

在很多方面,开放都非常重要。不仅仅是开放源代码,更包括公开透明的社区。这样的社区能够吸引更多的朋友加入。也能够帮助新来者,理解并认同社区规则。还能够促进监督以提升社区运行的程序正义。开放还包括欢迎一切的可能性,开源是世界的,也欢迎来自世界任何一个角落的使用者、参与者和贡献者。中国谚语有云:海纳百川,有容乃大。我们都相信:公开透明是一切良好协作的基石。

平等(Equality)

我们欢迎任何人的任何贡献,我们以统一的标准平等地评审每一次代码或文档提交,我们评审的仅仅是代码或文档本身的质量与价值,而不是以贡献者的学历、年龄、种族、性别或职位等标准来判断。人皆生而平等,所以我们都相信:对于平等的追求是社区健康的保障。

协作(Collaboration)

开源社区的协作,正是从接纳点滴贡献开始的,一个开放的社区,崇尚开放式的协作。这样的协作,不会在整个群体达成所有共识之后再开始,而是欢迎来自每一个人的一点一滴的改进。中国古语有云:不积小流,无以成江海。我们都相信:开放式协作,逐步凝聚共识是社区繁荣的秘诀。

创造美好世界(Build a better world)

每一位投身开源的朋友,都或多或少是理想主义者。我们都相信:这个并不完美的世界,理应变得更好。我们都相信:通过自己掌握的技术,借助开源的方法,能够把这个世界变得更好。我们更加相信:开源的精神内涵,应该被推广到更多的领域。因为:创造更加美好的世界,是开源的终极追求。

行动倡议

开源社区的朋友都相信从我做起的力量,因此,我们发出如下行动倡议:

推而广之(Advocate widely)

我们应该更加努力的向大众传播开源的理念与精神,让更多的人接受开源的理念,成为开源的同道中人。我们还应该在开源软件、开源硬件之外的领域,推广开源的实践,不仅仅是开放源代码,还应该开放数据、开放知识、开放一切可以帮助这个世界变得更好的知识与经验,让更多的行业、更多的群体,都接纳开源,成为开放式协作的受益者。

互帮互助(Help each other)

我们应该帮助更多的开源项目,不断发展成长。帮助各个开源社区,把社区的力量团结起来,共同协作。我们还应该防止开源的含义被滥用或曲解。我们要阻止割裂,反对人为设置的障碍,反对任何附加歧视条款的“伪开源”,确保开源始终是一项惠及全球的事业。

立即行动(Just do it)

每一个人都可以参与开源,而不是只有大咖才能做到。我们可以从翻译或撰写文档,纠正拼写做起,为代码除错,审核代码,提交代码,志愿支持开源活动,我们还可以布道演讲,吸引更多的朋友加入。

我不知道这样的环境之后还会有多少开源项目会因此毁掉,我只知道拥抱开源共享的理念和心怀感恩体谅的情感目前还为时尚早。

☑️ ⭐

精读 Effective C++

引言

深入 C++ 的诸多设计细节,了解实际场景的最佳实践,以面向对象的方式重新认识 C++。

将 C++ 视作一系列的语言

Item 1: View C++ as a federation of languages

最初,C++ 只是 C 语言加上一些面向对象的特性,所以 C++ 的原名是 “C with Classes”。 现在的 C++ 已经逐渐成熟,成为一门 多范式的程序设计语言(multiparadigm programming language)。同时支持过程式、面向对象、函数式、泛型编程,以及元编程。

C++ 的灵活使得它在很多问题上并没有统一的规则,而是取决于具体的程序设计范式和当前架构的设计意图。这样的情况下,我们最好把 C++ 看做是一系列的编程语言,而非一种特定的编程语言。

C++ 有四种主要的子语言:

  • C:C++ 是基于 C 设计的,你可以只使用 C++ 中 C 的那部分语法。此时你会发现你的程序反映的完全是C的特征:没有模板、没有异常、没有重载。
  • Object-Oriented C++:面向对象程序设计也是 C++ 的设计初衷:构造与析构、封装与继承、多态、动态绑定的虚函数。
  • Template C++:这是 C++ 的泛型编程部分,多数程序员很少涉及,但模板在很多情况下仍然很方便。另外 模板元编程(template metaprogramming)也是一个新兴的程序设计范式,虽然有点非主流。
  • STL:这是一个特殊的模板库,它的容器、迭代器和算法优雅地结合在一起,只是在使用时你需要遵循它的程序设计惯例。当然你也可以基于其他想法来构建模板库。

总之 C++ 并非单一的一门语言,它有很多不同的规则集。因而C++可以被视为四种主要子语言的集合,每个子语言都有自己的程序设计惯例。

C++ 程序设计的惯例并非一成不变,而是取决于你使用C++语言的哪一部分。例如, 在基于C语言的程序设计中,基本类型传参时传值比传引用更有效率。 然而当你接触Object-Oriented C++时会发现,传常量指针是更好的选择。 但是你如果又碰到了STL,其中的迭代器和函数对象都是基于C语言的指针而设计的, 这时又回到了原来的规则:传值比传引用更好。

避免使用 define

Item 2: Prefer consts, enums, and inlines to #defines

尽量使用常量、枚举和内联函数,代替 #define。我们知道 #define 定义的宏会在编译时进行替换,属于模块化程序设计的概念。 宏是全局的,面向对象程序设计中破坏了封装。因此在 C++ 中尽量避免它!

接着我们具体来看 #define 造成的问题。

不易理解

众所周知,由于预处理器会直接替换的原因,宏定义最好用括号括起来。#define函数将会产生出乎意料的结果:

#define MAX(a, b) a > b ? a : b
MAX(i++, j)

i 自加次数将取决于 j 的大小,然而调用者并不知情。宏的行为不易理解,本质上是因为宏并非 C++ 语言的一部分,它只是源代码的预处理手段。

不利于调试

宏替换发生在编译时,语法检查之前。因此相关的编译错误中不会出现宏名称,我们不知道是哪个宏出了问题。例如:

#define PERSON alice
PERSON = bob;

如果 alice 未定义,PERSON=bob; 便会出错:use of undeclared identifier ‘alice’。 然而我们可能不知道 alice 是什么东西,PERSON 才是我们定义的“变量”。

宏替换是在预处理过程中进行的,原则上讲编译器不知道宏的概念。然而,在现代的编译器中(例如Apple LLVM version 6.0), 编译器会记录宏替换信息,在编译错误中给出宏的名称:

test.cpp:8:5: error: use of undeclared identifier 'alice'
PERSON = bob;
^
test.cpp:4:16: note: expanded from macro 'PERSON'
#define PERSON alice;
^

于是,Meyers 提到的这个问题已经不存在了。然而作者的本意在于:尽量使用编译器,而不是预处理器。 因为 #define 并不是 C++ 语言的一部分。

enumconst 更好用

既然 #define 不能封装在一个类中,我们可以用 static const 来定义一个常量,并把它的作用于局限在当前类:

class C{
static const int NUM = 3;
int a[NUM];
};

通常 C++ 要求所有的声明都给出定义,然而数值类型(char, int, long)的静态常量可以只给声明。这里的 NUM 就是一个例子。 然而,如果你想取 NUM 的地址,则会得到编译错误:

Undefined symbols for architecture x86_64:
"C::NUM", referenced from:
_main in a-88bbac.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

因此如果你要取地址,那么就给出它的定义:

class C{
static const int NUM = 3;
int a[NUM];
};
const int C::NUM;

因为声明 NUM 时已经给定了初始值,定义时不允许再次给初始值。 如果使用 enum,事情会简单很多:

class C{
enum { NUM = 3 };
int a[NUM];
};

尽量使用常量

Item 3: Use const whenever possible

尽量使用常量。不需多说,这是 防卫型(defensive)程序设计的原则, 尽量使用常量限定符,从而防止客户错误地使用你的代码。

常量的声明

总结一下各种指针的声明方式吧:

char greeting[] = "Hello";

char *p = greeting; // non-const pointer, non-const data
const char *p = greeting; // non-const pointer, const data
char * const p = greeting; // const pointer, non-const data
const char * const p = greeting; // const pointer, const data

const 出现在 * 左边则被指向的对象是常量,出现在 * 右边则指针本身是常量。 然而对于常量对象,有人把 const 放在类型左边,有人把 const 放在 * 左边,都是可以的:

void f1(const Widget *pw);   // f1 takes a pointer to a constant Widget object
void f2(Widget const *pw); // 等效

STL 的 iterator 也是类似的,如果你希望指针本身是常量,可以声明 const iterator; 如果你希望指针指向的对象是常量,请使用 const_iterator

std::vector<int> vec;

// iter acts like a T* const
const std::vector<int>::iterator iter = vec.begin();
*iter = 10; // OK, changes what iter points to
++iter; // error! iter is const

//cIter acts like a const T*
std::vector<int>::const_iterator cIter = vec.begin();
*cIter = 10; // error! *cIter is const
++cIter; // fine, changes cIter

返回值声明为常量可以防止你的代码被错误地使用,例如实数相加的方法:

const Rational operator*(const Rational& lhs, const Rational& rhs);

当用户错误地使用 = 时:

Rational a, b, c;
if (a * b = c){
...
}

编译器便会给出错误:不可赋值给常量。

常量成员方法

声明常量成员函数是为了确定哪些方法可以通过常量对象来访问,另外一方面让接口更加易懂: 很容易知道哪些方法会改变对象,哪些不会。

成员方法添加常量限定符属于函数重载。常量对象只能调用常量方法, 非常量对象优先调用非常量方法,如不存在会调用同名常量方法。 常量成员函数也可以在类声明外定义,但声明和定义都需要指定 const 关键字。 例如:

class TextBlock {
public:
const char& operator[](std::size_t position) const // operator[] for
{ return text[position]; } // const objects

char& operator[](std::size_t position) // operator[] for
{ return text[position]; } // non-const objects

private:
std::string text;
};

TextBlock tb("Hello");
const TextBlock ctb("World");
tb[0] = 'x'; // fine — writing a non-const TextBlock
ctb[0] = 'x'; // error! — writing a const TextBlock

比特常量和逻辑常量

比特常量(bitwise constness):如果一个方法不改变对象的任何非静态变量,那么该方法是常量方法。 比特常量是 C++ 定义常量的方式,然而一个满足比特常量的方法,却不见得表现得像个常量, 尤其是数据成员是指针时:

class TextBlock{
char* text;
public:
char& operator[](int pos) const{
return text[pos];
}
};

const TextBlock tb;
char *p = &tb[1];
*p = 'a';

因为 char* text 并未发生改变,所以编译器认为我们的操作都是合法的。 然而我们定义了一个常量对象 tb,只调用它的常量方法,却能够修改tb的数据。 对数据的操作甚至可以放在 operator[]() 方法里面。

这一点不合理之处引发了 逻辑常量(logical constness)的讨论:常量方法可以修改数据成员, 只要客户检测不到变化就可以。可是常量方法修改数据成员 C++ 编译器不会同意的!这时我们需要 mutable 限定符:

class CTextBlock {
public:
std::size_t length() const;

private:
char *pText;

mutable std::size_t textLength; // these data members may
mutable bool lengthIsValid; // always be modified
};

std::size_t CTextBlock::length() const{
if (!lengthIsValid) {
textLength = std::strlen(pText);
lengthIsValid = true;
}
return textLength;
}

避免常量/非常量方法的重复

通常我们需要定义成对的常量和普通方法,只是返回值的修改权限不同。 当然我们不希望重新编写方法的逻辑。最先想到的方法是常量方法调用普通方法,然而这是 C++ 语法不允许的。 于是我们只能用普通方法调用常量方法,并做相应的类型转换:

const char& operator[](size_t pos) const{
...
}

char& operator[](size_t pos){
return const_cast<char&>(
static_cast<const TextBlock&>(*this)
[pos]
);
}
  1. *this 的类型是 TextBlock,先把它强制隐式转换为 const TextBlock,这样我们才能调用那个常量方法
  2. 调用 operator[](size_t) const,得到的返回值类型为 const char&
  3. 把返回值去掉 const 属性,得到类型为 char& 的返回值
☑️ ⭐

维拓标准接口开发项目总结

引言

维拓标准接口的开发也基本完成了,这也是我首次用 C# 完成定制项目。之前 Unity 学的很多东西都忘掉了,再捡起来用还是有些吃力,所以写了这篇博客总结一下。

C# 编程范式

数组越界

老生常谈的问题了,这里构造 Paper 的时候 item[] 如果没有这些索引又会抛出异常,但自己写的时候经常注意不到:

+if (item.Length < 2)
+ continue;

+try
+{
Paper paper = new Paper(item[0], Double.Parse(item[1]), Double.Parse(item[2]));
result.Add(paper);
+}

文件路径合并

之前对于需要合并的路径我都是这么通过对 string 直接进行加减来操作的:

string FilePath1 = @"C:\Users\MFGYF-WXY\source\repos";
string FilePath2 = @"\PLMInterface\bin\cadext.exe"
string MergeFilePath = FilePath1 + FilePath2;

但这种方式很业余,这种情况正确的处理是用 Path.Combine() 方法将两个路径进行合并:

string FilePath1 = @"C:\Users\MFGYF-WXY\source\repos";
string FilePath2 = @"\PLMInterface\bin\cadext.exe"
string MergeFilePath = Path.Combine(FilePath1, FilePath2);

程序配置与 <bindingRedirect/>

在完成部分接口把程序打包成exe时重新校对了一下 NewtonJson 的版本,之前在 Nuget 上下载的是 13 版本,但是 GStarCAD 目录下的版本是 12。将版本调整之后 exe 无法正常使用:

未经处理的异常:SystemI0.Fi1eLoadException:未能加载文件或程序集“Newtonsoft.Json,Version=13.0.0.0 Culture=neutral Pub1icKeyToken=30ad4fe6b2a6aeed”或它的某一个依赖项。找到的程序集清单定义与程序集引用不匹配。(异常来自 HRESULT:0x80131040)--->SystemIO.Fi1eLoadException:未能加载文件或程序集“Newtonsoft.Ison,Version=12.0.0.0,Culture=neutral, PublicKe yToken=30ad4fe6b2a6aeed”或它的某一个依赖项。找到的程序集清单定义与程序集引用不匹配。(异常来自 HRESULT:0x80131040)

再次检查 Nuget 版本已经调整过来了,但是编译之后的 exe 还是会报错 NewtonJson 版本错误。其实只需要调整一下 app.config 文件:

<?xml version="1.0" encoding="utf-8"?>
<configuration>
<startup>
<supportedRuntime version="v4.0" sku=".NETFramework,Version=v4.8" />
</startup>
<runtime>
<assemblyBinding xmlns="urn:schemas-microsoft-com:asm.v1">
<dependentAssembly>
<assemblyIdentity name="Newtonsoft.Json" publicKeyToken="30ad4fe6b2a6aeed" culture="neutral" />
<bindingRedirect oldVersion="0.0.0.0-13.0.0.0" newVersion="13.0.0.0" />
</dependentAssembly>
</assemblyBinding>
</runtime>
</configuration>

问题在于 <bindingRedirect/> 这个标签,微软官方API文档 这里有比较详细的解释。

将一个程序集版本重定向到另一个版本。

<bindingRedirect
oldVersion="existing assembly version"
newVersion="new assembly version"/>
  • oldVersion:指定最初请求的程序集的版本。 程序集版本号的格式为 major.minor.build.revision。 该版本号的每个部分的有效值介于 0 和 65535 之间。
  • newVersion:指定要用来取代最初请求的版本的程序集版本(格式为:n.n.n.n) ,此值可以指定 oldVersion 之前的版本。

官方还给出了一个示例演示如何将一个程序集版本重定向到另一个版本:

<configuration>  
<runtime>
<assemblyBinding xmlns="urn:schemas-microsoft-com:asm.v1">
<dependentAssembly>
<assemblyIdentity name="myAssembly"
publicKeyToken="32ab4ba45e0a69a1"
culture="neutral" />
<bindingRedirect oldVersion="1.0.0.0"
newVersion="2.0.0.0"/>
</dependentAssembly>
</assemblyBinding>
</runtime>
</configuration>

所以把这个标签删掉,程序就可以正常运行了,这是一个知识盲点记录下来。

读取 .dat 文件数据

所需要读取的 PaperSet.dat 长相如下,包含了国标图幅的各个数据尺寸:

Name   B      L     a     c    e     k    BD     LD
A0 841 1189 25 10 20 1 16 12
A1 594 841 25 10 20 1 12 8
A2 420 594 25 10 10 1 8 6
A3 297 420 25 5 10 1 2 2
A4 210 297 25 5 10 1 2 2
A0X2 1189 1682 25 10 20 3 16 24
A0X3 1189 2523 25 10 20 3 16 36
A1X3 841 1783 25 10 20 3 12 24
A1X4 841 2378 25 10 20 3 12 32
A2X3 594 1261 25 10 20 3 8 18
A2X4 594 1682 25 10 20 3 8 24
A2X5 594 2102 25 10 20 3 8 24
A3X3 420 891 25 10 10 2 6 12
A3X4 420 1189 25 10 10 2 6 16
A3X5 420 1486 25 10 10 2 6 10
A3X6 420 1783 25 10 10 3 6 12
A3X7 420 2080 25 10 10 3 6 14
A4X3 297 630 25 5 10 2 2 8
A4X4 297 841 25 5 10 2 2 12
A4X5 297 1051 25 5 10 2 2 12
A4X6 297 1261 25 5 10 3 2 12
A4X7 297 1471 25 5 10 3 2 14
A4X8 297 1682 25 5 10 3 2 16
A4X9 297 1892 25 5 10 3 2 18

观察数据结构,每行数据均以若干空格分隔图幅名称、长度、宽度等等数据,所以我们需要逐行去读取,先简单声明一个图幅信息类包含图幅名称和长宽:

/// <summary>
/// 国标图幅信息类
/// </summary>
public class Paper
{
public Paper(string Name, double Width, double Length)
{
this.Name = Name;
this.Length = Length;
this.Width = Width;
}

/// <summary>
/// 图幅名称
/// eg. A4
/// </summary>
public string Name { get; }

/// <summary>
/// 图幅长度
/// </summary>
public double Length { get; }

/// <summary>
/// 图幅宽度
/// </summary>
public double Width { get; }
}

之后通过 StreamReader 逐行读取(首行不读取)即可:

List<Paper> result = new List<Paper>();
string path = Path.Combine(installPath, @"MCADSetting\PaperSet.dat");

// 逐行读取 PaperSet.dat 数据
using (StreamReader reader = new StreamReader(path))
{
int index = 0;
string line;
while ((line = reader.ReadLine()) != null)
{
// 首行不作为数据读取,直接跳过
if (index++ == 0) continue;

// 去除字符串中的多余空格
string[] item = line.Split(new[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);

if (item.Length < 2) continue;

Paper paper = new Paper(item[0], Double.Parse(item[1]), Double.Parse(item[2]));
result.Add(paper);
}
}

String.Split 方法可以参考微软的这篇 如何在 C# 中使用 String.Split 分隔字符串StringSplitOptions.RemoveEmptyEntries 参数来排除返回数组中的任何空字符串。要对返回的集合进行更复杂的处理,可使用 LINQ 来处理结果序列。

CADNET & PLM 接口使用

GetCADApplication

获取 CAD 应用程序,首先明确我们的思路:

  1. 若 CAD 程序已经存在,则直接跳转至已打开的 CAD 程序
  2. 否则新建 CAD 应用程序
try
{
// 先尝试是否可以直接捕获打开的CAD应用程序
IGcadApplication app = Marshal.GetActiveObject("GStarCAD.Application") as IGcadApplication;

// 避免出现后台打开的情况
app.Visible = true;
}
catch(Exception exception)
{
// 捕获失败则新建CAD应用程序
app = new GcadApplicationClass();
app.Visible = true;
......
}

这里捕获用到了 System.Runtime.InteropServices 中的 Marshal.GetActiveObject() 方法。

注意 app.Visible 可以让后台的应用程序前置显示,在忘记关闭 Quit() 时会出现多个后台运行程序,在项目的前期测试造成了不少麻烦。

CloseFile

该命令会传入一个图纸路径 filePath,关闭该指定路径的图纸。

关闭图纸的业务场景相对简单,只需要判断两点:

  1. 当前 CAD 是否打开过任何图纸
  2. 在已打开过的图纸中是否有和 filePath 相对应的图纸

最后对找到的图纸进行关闭操作即可。

// 图纸数量小于等于 0 则未打开任何图纸
if (app.Documents.Count <= 0)
return;

// 遍历当前已打开图纸
foreach (GcadDocument doc in app.Documents)
{
if (string.Equals(doc.FullName, filePath, StringComparison.OrdinalIgnoreCase))
{
doc.Close();
return; // 关闭操作成功
}
}

return; // 未找到关闭图纸

需要注意的是这里需要用 doc.FullName 而非 doc.Name,以规避出现诸如 C:\test.dwgD:\test.dwgName 中均为 test.dwg 的末端图纸路径重名的情况。

OpenFile

与前面的关闭命令类似,该命令会传入一个图纸路径 filePath,若已经打开图纸则直接返回,否则打开该指定路径的图纸。

// 若当前已有打开图纸
if (app.Documents.Count > 0)
{
// 遍历当前已打开图纸
foreach (GcadDocument doc in app.Documents)
{
if (string.Equals(doc.FullName, path, StringComparison.OrdinalIgnoreCase))
return; // 图纸已经打开
}
}

// 没找到指定图纸则尝试打开该图纸
app.Documents.Open(path);

SaveFile

保存文件也是类似的,先传入一个图纸路径 filePath,若该图纸还未被打开则直接返回,否则保存该指定路径的图纸。

多的一种情况是 CAD 在图纸为只读模式的前提下逻辑上应禁止保存,这点注意一下即可。

// 图纸数量小于等于 0 则未打开任何图纸
if (appController.CadApp.Documents.Count <= 0)
return Message.SendMessage(false, "没有图纸被打开,保存失败");

// 遍历当前已打开图纸
foreach (GcadDocument doc in appController.CadApp.Documents)
{
if (string.Equals(doc.FullName, path, StringComparison.OrdinalIgnoreCase))
{
// 只读模式下的图纸不保存
if (doc.ReadOnly)
return Message.SendMessage(false, "指定图纸为只读模式,保存失败"); ;

doc.Save();
}
}

return; // 找不到要保存的指定图纸,保存失败;

GetOpeningFile

获取打开文件直接调用 ActiveDocument 即可。

但是当一张图纸新建之后并未保存(诸如 Drawing1.dwg 这样),需要系统变量 DWGTITLED 来判断是否为这种尚未保存的情况:

  • DWGTITLED = 0:Drawing has not been named
  • DWGTITLED = 1:Drawing has been named
if (appController.CadApp.Documents.Count <= 0)
return; // 没有图纸被打开

GcadDocument doc = appController.CadApp.ActiveDocument;
int titled = 0;
string dwgTitled = doc.GetVariable("DWGTITLED").ToString();

if (!int.TryParse(dwgTitled, out titled))
return; // DWGTITLED类型转换失败

return titled == 0 ? null : doc.FullName;

NewtonSoftJson自定义Convertor序列化Json

这个项目一个比较关键的过程就是去解析图纸数据并转换为 Json 格式,前面 PLM 接口负责解析数据,那么该如何将这些数据转换为 Json 呢?

官方样例

查阅官网的 Custom JsonConverter,给出了一个比较完整的示例:

public class KeysJsonConverter : JsonConverter
{
private readonly Type[] _types;

public KeysJsonConverter(params Type[] types)
{
_types = types;
}

public override void WriteJson(JsonWriter writer, object value, JsonSerializer serializer)
{
JToken t = JToken.FromObject(value);

if (t.Type != JTokenType.Object)
{
t.WriteTo(writer);
}
else
{
JObject o = (JObject)t;
IList<string> propertyNames = o.Properties().Select(p => p.Name).ToList();

o.AddFirst(new JProperty("Keys", new JArray(propertyNames)));

o.WriteTo(writer);
}
}

public override object ReadJson(JsonReader reader, Type objectType, object existingValue, JsonSerializer serializer)
{
throw new NotImplementedException("Unnecessary because CanRead is false. The type will skip the converter.");
}

public override bool CanRead
{
get { return false; }
}

public override bool CanConvert(Type objectType)
{
return _types.Any(t => t == objectType);
}
}

public class Employee
{
public string FirstName { get; set; }
public string LastName { get; set; }
public IList<string> Roles { get; set; }
}
Employee employee = new Employee
{
FirstName = "James",
LastName = "Newton-King",
Roles = new List<string>
{
"Admin"
}
};

string json = JsonConvert.SerializeObject(employee, Formatting.Indented, new KeysJsonConverter(typeof(Employee)));

Console.WriteLine(json);
// {
// "Keys": [
// "FirstName",
// "LastName",
// "Roles"
// ],
// "FirstName": "James",
// "LastName": "Newton-King",
// "Roles": [
// "Admin"
// ]
// }

Employee newEmployee = JsonConvert.DeserializeObject<Employee>(json, new KeysJsonConverter(typeof(Employee)));

Console.WriteLine(newEmployee.FirstName);
// James

抽象转换器类

首先继承 JsonConverter 构建抽象类 AbstractJsonConverter。该类主要用于实现 JsonConverter 的方法并留下 RewriteWriter() 作为真正重写转换方法的入口:

abstract public class AbstractJsonConverter : JsonConverter
{
protected readonly Type _type;
public AbstractJsonConverter(Type type)
{
_type = type;
}

public override void WriteJson(JsonWriter writer, object value, JsonSerializer serializer)
{
if (!(value is IDatabase db))
{
writer.WriteNull();
return;
}

RewriteWriter(writer, db, serializer);
}

public override object ReadJson(JsonReader reader, Type objectType, object existingValue, JsonSerializer serializer)
{
throw new NotImplementedException("Unnecessary because CanRead is false. The type will skip the converter.");
}

public override bool CanRead => false;
public override bool CanWrite => true;

public override bool CanConvert(Type objectType)
{
return typeof(IDatabase) == _type;
}

abstract protected void RewriteWriter(JsonWriter writer, IDatabase db, JsonSerializer serializer);
}

在这个过程中 CanConvert 方法的实现遇到了困难,因为该项目以 .exe 可执行程序为载体,所以调用诸如 IDatabase 这样的类型时获取到的 type 是COM组件而非具体的类型。

为了获取真正的类型我尝试过使用原生的类型获取方法、反射获取方法以及 VisualBasic 的内置方法,但均以失败告终,只好以官方示例为准构造时手动传入类型做判断。

维拓转换器类

真正的维拓转换器类我们只需要关心如何实现 RewriteWriter() 即可:

public class WeiTuoDBJsonConverter : AbstractJsonConverter
{
public WeiTuoDBJsonConverter(Type type) : base(type) { }

protected override void RewriteWriter(JsonWriter writer, IDatabase db, JsonSerializer serializer)
{
writer.WriteStartObject();
writer.WritePropertyName(dataText);
WriteDataBaseJson(writer, db, serializer);

writer.WriteEndObject();
}

void WriteDataBaseJson(JsonWriter writer, IDatabase db, JsonSerializer serializer)
{
if (db is null)
{
writer.WriteNull();
return;
}

writer.WriteStartArray();
// 解析图纸
foreach (var paperName in db.PaperNames)
{
IPaper paper = db[paperName];

writer.WriteStartObject();
writer.WritePropertyName(paperName);
writer.WriteStartObject();

WritePaperJson(writer, paper, serializer);

writer.WriteEndObject();
writer.WriteEndObject();
}

writer.WriteEndArray();
}

void WritePaperJson(JsonWriter writer, IPaper paper, JsonSerializer serializer)
{
if (paper is null)
{
writer.WriteNull();
return;
}

var resolver = serializer.ContractResolver as DefaultContractResolver;

ITitle title = paper?.Title;
writer.WritePropertyName(resolver == null
? nameof(title)
: resolver.GetResolvedPropertyName(nameof(title)));
WriteTitleJson(writer, title);

// 解析明细表
IBom bom = paper?.Bom;
writer.WritePropertyName(resolver == null
? nameof(bom)
: resolver.GetResolvedPropertyName(nameof(bom)));
writer.WriteStartArray();
WriteBomJson(writer, bom);
writer.WriteEndArray();

// 解析图框
IFrame frame = paper?.Frame;
writer.WritePropertyName(resolver == null
? nameof(frame)
: resolver.GetResolvedPropertyName(nameof(frame)));
WriteFrameJson(writer, frame, serializer);

......
}

void WriteTitleJson(JsonWriter writer, ITitle title)
{
if (title is null)
{
writer.WriteNull();
return;
}

writer.WriteStartObject();
foreach (string name in title.Names)
{
writer.WritePropertyName(name);
writer.WriteValue(title[name]);
}
writer.WriteEndObject();
}

void WriteBomJson(JsonWriter writer, IBom bom)
{
if (bom is null)
{
writer.WriteNull();
return;
}

foreach (var serialNumber in bom.SerialNumbers)
{
IBomRow bomRow = bom[serialNumber];

writer.WriteStartObject();
foreach (var name in bomRow.Names)
{
writer.WritePropertyName(name);
writer.WriteValue(bomRow[name]);
}
writer.WriteEndObject();
}
}

void WriteFrameJson(JsonWriter writer, IFrame frame, JsonSerializer serializer)
{
if (frame is null)
{
writer.WriteNull();
return;
}

writer.WriteStartObject();
......
writer.WriteEndObject();
}
}

解析命令使用

最后使用上就非常简单了,直接在序列化 SerializeObject() 中传入我们定制的转换器即可:

return JsonConvert.SerializeObject(db, new JsonSerializerSettings {
Formatting = Formatting.Indented,
ContractResolver = new CamelCasePropertyNamesContractResolver(),
Converters = new List<JsonConverter> { new WeiTuoDBJsonConverter(typeof(IDatabase)) }
  • Formatting.Indented 代表换行
  • CamelCasePropertyNamesContractResolver() 代表属性为驼峰命名法

转换器优化

虽然可以看到这种方式能够转换,但其实是手动实现解析的,我们真正希望的是可以自动识别并获取相应的转换器,完全通过成员关系序列化对象。

可能这种说法有些抽象,我还是以刚才的例子来讲。WeiTuoDBJsonConverter 可以解析 IDatabase,但如果后期需要单独解析 ITitle 或者 IBom 则需要重新实现对应的转换器类,现有的代码所有的解析都是作为函数的形式(如 WriteFrameJson())放在转换器类中,不够灵活并且可维护性差。我们希望的是每个类都有对应的转换器类,然后需要的时候将这些转换器进行组合。

具体转换器类

下面就以明细表为例来讲讲如何通过逐级实现转换器来达到目标。首先我们先梳理一下逻辑关系:

IFrame
|__ IBom
|__ IBomRow

如图所示,图框对象 IFrame 包含了 IBom 明细表对象,而 IBom 又包含了若干 IBomRow 明细表行对象。那么首先我们从最底层的 IBomRow 开始实现 BomRowConverter

/// <summary>
/// <see cref="IBomRow"/> data converter for <see cref="Newtonsoft.Json"/>
/// </summary>
public class BomRowConverter : JsonConverter<IBomRow>
{
/// <inheritdoc />
public override bool CanRead => false;

/// <inheritdoc />
public override bool CanWrite => true;

/// <inheritdoc />
public override void WriteJson(JsonWriter writer, IBomRow bomRow, JsonSerializer serializer)
{
if (bomRow is null)
{
writer.WriteNull();
return;
}

writer.WriteStartObject();
foreach (string name in bomRow.Names)
{
writer.WritePropertyName(name);
writer.WriteValue(bomRow[name]);
}

writer.WriteEndObject();
}

/// <inheritdoc />
public override IBomRow ReadJson(JsonReader reader, Type objectType, IBomRow existingValue,
bool hasExistingValue, JsonSerializer serializer)
{
throw new NotImplementedException();
}
}

一个简单的字典结构,遍历就可以序列化完成。BomConverter 的实现则略有不同:

/// <summary>
/// <see cref="IBom"/> data converter for <see cref="Newtonsoft.Json"/>
/// </summary>
public class BomConverter : JsonConverter<IBom>
{
/// <inheritdoc />
public override bool CanRead => false;

/// <inheritdoc />
public override bool CanWrite => true;

/// <inheritdoc />
public override void WriteJson(JsonWriter writer, IBom bom, JsonSerializer serializer)
{
if (bom is null)
{
writer.WriteNull();
return;
}

writer.WriteStartArray();
for (int r = 0; r < bom.RowCount; r++)
serializer.Serialize(writer, bom[r]);
writer.WriteEndArray();
}

/// <inheritdoc />
public override IBom ReadJson(JsonReader reader, Type objectType, IBom existingValue, bool hasExistingValue,
JsonSerializer serializer)
{
throw new NotImplementedException();
}
}

可以看到对于已有转换器的对象我们摒弃了先前的 writer,转而通过 serializer.Serialize() 的方式序列化 IBomRow 对象,FrameConverter 同理:

/// <summary>
/// <see cref="IFrame"/> data converter for <see cref="Newtonsoft.Json"/>
/// </summary>
public class FrameConverter : JsonConverter<IFrame>
{
/// <inheritdoc />
public override bool CanRead => false;

/// <inheritdoc />
public override bool CanWrite => true;

/// <inheritdoc />
public override void WriteJson(JsonWriter writer, IFrame frame, JsonSerializer serializer)
{
if (frame is null)
{
writer.WriteNull();
return;
}

var properties = typeof(IFrame).GetProperties(BindingFlags.Instance | BindingFlags.Public);

var resolver = serializer.ContractResolver as DefaultContractResolver;

writer.WriteStartObject();

foreach (PropertyInfo propertyInfo in properties)
{
writer.WritePropertyName(resolver?.GetResolvedPropertyName(propertyInfo.Name) ?? propertyInfo.Name);
writer.WriteValue(propertyInfo.GetValue(frame));
}

writer.WriteEndObject();
}

/// <inheritdoc />
public override IFrame ReadJson(JsonReader reader, Type objectType, IFrame existingValue, bool hasExistingValue,
JsonSerializer serializer)
{
throw new NotImplementedException();
}
}

通过反射技术获取属性,遍历属性来完成对子属性的定制序列化。

静态方法输出

后面的事情就水到渠成了,只需要将相应的转换器放给对应的打印函数即可:

/// <summary>
/// Structure data based on JSON extension class
/// </summary>
public static class StructureDataExtension
{
/// <summary>
/// Can convert the interface type with one of converter in <see cref="JsonSerializerSettings.Converters"/>
/// </summary>
/// <param name="interfaceType">The interface type of <see cref="AcmSymbb2"/></param>
/// <param name="settings">The <see cref="JsonSerializerSettings"/> object or null</param>
/// <returns>True if can convert, otherwise false</returns>
private static bool CanConvert(Type interfaceType, JsonSerializerSettings settings)
{
return settings != null && settings.Converters.Any(converter => converter.CanConvert(interfaceType));
}

/// <summary>
/// Serialize <see cref="AcmSymbb2"/> interface object
/// </summary>
/// <param name="obj">Interface object</param>
/// <param name="settings"><see cref="JsonSerializerSettings"/> object</param>
/// <param name="types">Interface type and converter type list</param>
/// <returns>JSON string</returns>
private static string SerializeObject(object obj, JsonSerializerSettings settings,
params (Type InterfaceType, Type ConverterType)[] types)
{
// priority: user defined > user default settings > builtin
settings = settings ?? new JsonSerializerSettings();
var defaultSettings = JsonConvert.DefaultSettings?.Invoke();

foreach ((Type interfaceType, Type converterType) in types)
{
if (CanConvert(interfaceType, settings) || CanConvert(interfaceType, defaultSettings))
continue;

settings.Converters.Add((JsonConverter)Activator.CreateInstance(converterType));
}

return JsonConvert.SerializeObject(obj, settings);
}

/// <summary>
/// <see cref="IBomRow"/> object dump to JSON string
/// </summary>
/// <param name="bomRow"><see cref="IBomRow"/> object</param>
/// <param name="settings"><see cref="JsonSerializerSettings"/> object</param>
/// <returns>JSON string</returns>
/// <exception cref="ArgumentNullException"></exception>
public static string Dump(this IBomRow bomRow, JsonSerializerSettings settings = null)
{
if (bomRow == null) throw new ArgumentNullException(nameof(bomRow));

return SerializeObject(bomRow, settings, (typeof(IBomRow), typeof(BomRowConverter)));
}

/// <summary>
/// <see cref="IBom"/> object dump to JSON string
/// </summary>
/// <param name="bom"><see cref="IBom"/> object</param>
/// <param name="settings"><see cref="JsonSerializerSettings"/> object</param>
/// <returns>JSON string</returns>
/// <exception cref="ArgumentNullException"></exception>
public static string Dump(this IBom bom, JsonSerializerSettings settings = null)
{
if (bom == null) throw new ArgumentNullException(nameof(bom));

return SerializeObject(bom, settings, (typeof(IBom), typeof(BomConverter)),
(typeof(IBomRow), typeof(BomRowConverter)));
}

/// <summary>
/// <see cref="IFrame"/> object dump to JSON string
/// </summary>
/// <param name="frame"><see cref="IFrame"/> object</param>
/// <param name="settings"><see cref="JsonSerializerSettings"/> object</param>
/// <returns>JSON string</returns>
/// <exception cref="ArgumentNullException"></exception>
public static string Dump(this IFrame frame, JsonSerializerSettings settings = null)
{
if (frame == null) throw new ArgumentNullException(nameof(frame));

return SerializeObject(frame, settings, (typeof(IFrame), typeof(FrameConverter)));
}
}

这里还需要考虑一下 JsonSerializerSettings 的优先级,用户 > 定制默认 > 系统默认,如果已经包含了可以解析的转换器就没有必要再放入相应的转换器了。

☑️ ⭐

哪些变量会自动初始化?

引言

在 C 语言中的全局变量和静态变量都是会自动初始化为 0,堆和栈中的局部变量不会初始化而拥有不可预测的值。 C++ 保证了所有对象与对象成员都会初始化,但其中基本数据类型的初始化还得依赖于构造函数。 下文来详细探讨 C 风格的”默认初始化”行为,以及 C++ 中成员变量的初始化规则。

初始化的语法

很多人至今不知道 C++ 中如何正确地初始化一个变量,我们首先来解决语法的问题。 C语言中在声明时用 = 即可完成初始化操作。但我们偏向于使用 C++ 风格(本文中均指面向对象程序设计风格)来初始化内置类型:

// C 风格
int i = 3;
int arr[] = {1, 2, 3};

// C++ 风格
int i(3);
int i = int(3);
int *p = new int(3);
int* arr = new int[3] {1, 2, 3};

在 C 语言中 int a; 表示声明了整型 a 但未初始化,而 C++ 中的对象总是会被初始化的,无论是否写了圆括号或者是否写了参数列表,例如:

int basic_var;      // 未初始化:应用"默认初始化"机制
CPerson person; // 初始化:以空的参数列表调用构造函数

默认初始化规则

定义基本数据类型变量(单个值、数组)的同时可以指定初始值,如果未指定 C++ 会去执行默认初始化(default-initialization)。 那么什么是”默认初始化”呢?

栈中的变量(函数体中的自动变量)和堆中的变量(动态内存)会保有不确定的值;
全局变量和静态变量(包括局部静态变量)会初始化为零。
C++11: If no initializer is specified for an object, the object is default-initialized; if no initialization is performed, an object with automatic or dynamic storage duration has indeterminate value. Note: Objects with static or thread storage duration are zero-initialized, see 3.6.2.

所以函数体中的变量定义是这样的规则:

int i;                    // 不确定值
int i = int(); // 0
int *p = new int; // 不确定值
int *p = new int(); // 0

静态和全局变量的初始化

未初始化的和初始化为零的静态/全局变量编译器是同样对待的,把它们存储在进程的BSS段(这是全零的一段内存空间)中。所以它们会被”默认初始化”为零。

来看例子:

int g_var;
int *g_pointer;
static int g_static;

int main(){
int l_var;
int *l_pointer;
static int l_static;

cout<<g_var<<endl<<g_pointer<<endl<<g_static<<endl;
cout<<l_var<<endl<<l_pointer<<endl<<l_static<<endl;
};

输出:

0                   // 全局变量
0x0 // 全局指针
0 // 全局静态变量
32767 // 局部变量
0x7fff510cfa68 // 局部指针
0 // 局部静态变量

动态内存中的变量在上述代码中没有给出,它们和局部变量(自动变量)具有相同的”默认初始化”行为。

成员变量的初始化

成员变量分为成员对象和内置类型成员,其中成员对象总是会被初始化的。而我们要做的就是在构造函数中初始化其中的内置类型成员。 还是先来看看内置类型的成员的”默认初始化”行为:

class A{
public:
int v;
};
A g_var;

int main(){
A l_var;
static A l_static;
cout<<g_var.v<<' '<<l_var.v<<' '<<l_static.v<<endl;
return 0;
}

输出:

0 2407223 0

可见内置类型的成员变量的”默认初始化”行为取决于所在对象的存储类型,而存储类型对应的默认初始化规则是不变的。 所以为了避免不确定的初值,通常会在构造函数中初始化所有内置类型的成员。Effective C++: Item 4一文讨论了如何正确地在构造函数中初始化数据成员。 这里就不展开了,直接给出一个正确的初始化写法:

class A{
public:
int v;
A(): v(0);
};

封闭类嵌套成员的初始化

再来探讨一下当对象聚合发生时成员变量的”默认初始化”行为,同样还是只关注于基本数据类型的成员。

class A{
public:
int v;
};

class B{
public:
int v;
A a;
};

B g_var;
int main(){
B l_var;
cout<<g_var.v<<' '<<g_var.a.v<<endl;
cout<<l_var.v<<' '<<l_var.a.v<<endl;
return 0;
}

输出:

0 0
43224321 -1610612736

规则还是是一样的,默认初始化行为取决于它所属对象的存储类型。 封闭类(Enclosing)中成员对象的内置类型成员变量的”默认初始化”行为取决于当前封闭类对象的存储类型,而存储类型对应的默认初始化规则仍然是不变的。

☑️ ☆

初次体验 Github Copilot

引言

最近一段时间,AI 技术的进步则让代码补全有了更上一层楼的机会。接下来,我们为大家介绍的 Github Copilot 就是这样一款基于 AI 的代码补全工具。

我们编程时写出的代码,在未编译前通常以纯文本格式存在。因此,实际上我们能使用任何文本编辑器来编写代码,包括系统自带的记事本。但是,好的工具能够让我们事半功倍。面对复杂的工作任务,我们需要 IDE(集成开发环境)这样的生产力工具。IDE 本质上就是更高级的文本编辑器,集成了许多人性化功能来提升效率,比如:自动补全变量,提示可能会用到的函数列表,语法高亮,显示语法错误等等。

IDE 本身也在不断进化。我的第一门使用 IDE 的编程语言是 Java,使用的是 Eclipse,当时自动补全功能还比较简陋,局限于符号的提示与选单,我也没有对 IDE 究竟有多强大建立起概念。后来,开始学习开发框架后,我慢慢接触到 JetBrains 出品的 IDEA。IDEA 的提示更智能,例如:可以在数组后输入「.for」自动构成 foreach 循环,也可以使用快捷键自动生成 Getter/Setter、构造函数、重载函数等等。毫无疑问,JetBrains 系列产品为编码工作带来了更高的效率,提供了更加全面、智能的补全功能。

GitHub Copilot 是什么

Github Copilot 是 GitHub 和 OpenAI 合作开发的人工智能工具,可以在编辑代码时帮助你自动生成可能会需要的代码。

GitHub Copilot 能够提取代码上下文,给出整行代码或整个函数的补全建议。它可以帮助我们完成下列任务:

  • 将注释转化为代码;
  • 自动填充重复代码;
  • 编写测试;
  • 快速发现解决问题的替代方法;
  • 无需网络搜索即可快速探索新的 API;
  • 适应用户编写代码的方式,帮助用户更快地完成工作。

原理是什么?

我们先介绍一下 GPT-3。GPT-3(Generative Pre-trained Transformer 3)是一个用于处理自然语言的 AI 模型,由 OpenAI 训练开发。GPT-3 通过阅读几乎一切人类可阅读的内容来进行训练,理论上,它能够完成一切通过语言完成的工作,而且完成效果还非常接近人类。已经有实验证明 GPT-3 可用于撰写文章、回答问题、编写代码生成应用程序、设计表格、开发游戏、将文字描述便携为成型的网页等等。

而 OpenAI Codex 则是基于 GPT-3 开发的一款针对编程所设计的 AI 模型。Codex 从公共代码仓库学习人类编写的代码,其代码来源包括 Github 上的公共代码仓库。官网原文如下:

OpenAI Codex is a descendant of GPT-3; its training data contains both natural language and billions of lines of source code from publicly available sources, including code in public GitHub repositories. (OpenAI Codex 是 GPT-3 的衍生项目;它的训练数据包括自然语言和数以亿计来自公开可用来源的源代码,其中包括 Github 公开仓库的代码。)

最后,GitHub Copilot 则是使用了 Codex 进行研发的一款商业产品。Github 将算法进行包装,做成了插件和网页,进行应用分发。现在 GitHub Copilot 支持在 Visual Studio Code、Visual Studio、JetBrains Rider 上通过插件形式集成进 IDE,以便我们使用。

使用 & 体验

要想使用 GitHub Copilot,首先需要注册一个 Github 账号。有了帐号后,按下面的步骤可以找到并启用 GitHub Copilot:

  1. 找到设置页面:在任何页面的右上角,单击个人资料照片,然后单击“设置”。

  1. 找到 GitHub Copilot 设置页面:在边栏的「代码、规划和自动化」部分,单击「GitHub Copilot」。

  2. 启用 GitHub Copilot:在 GitHub Copilot 设置页面上,单击「启用 GitHub Copilot」。

  1. 选择付费方式(月付/年付):GitHub Copilot 可以免费试用 60 个自然日,随后需要以 $10/月 的价格订阅。如果你是学生的话,可享受教育优惠,免费使用 GitHub Copilot。

在 Rider IDE 进行设置

  1. 在偏好设置里安装 Github Copilot Plugin;
  2. 重启 IDE;
  3. 登陆 Github 完成验证。

设置完成后,IDE 提示可以使用「Tab」来自动补全代码,使用「⌥ + ]」或者「⌥ + [」来选择其他候选的补全选项。

体验如何

在编写代码的过程中,Github Copilot 会自动提示可能的补全方案,此时按下「Tab」即可完成补全。

有时,AI 并不会一次给出完整的提示代码,例如,图示的代码就并非一次性生成的,而是逐行自动补全,最终生成了一个可以实际使用的函数(甚至包括注释)。下图的例子在 Unity3D 中绘制了一条射线用于检测前方是否有物品,只有第一行注释是我写下的。

下面的例子很有趣:当我尝试把乐谱的音高编写成数组时,Github Copilot 也给出了他所理解的音乐:

在这样的例子中,对重复的流行乐片段,Github Copilot 有时可以给出不错的答案。比如预先输入《卡农》的重复性模进片段,Github Copilot 往往可以完全正确地补全乐谱。可见,在面临重复性较高的功能开发,或是使用一些常用的算法时,依靠 AI 补全是一个称得上非常可靠的选择。不过,如果需求非常复杂,大部分情况下,它并不能独立地给出完美的解决方案。GitHub 团队在对一组 Python 函数进行基准性测试后发现尝试十次后,大约 57% 情况下可以给出正确的答案。部分情况下,Github Copilot 也会给出无法通过编译的代码。

Github Copilot 的不足之处

使用 Github Copilot 很久后,Reddit 大佬 Colin Eberhardt 指出了几点不足:

  1. Github Copilot 很多时候响应得不够快。虽然它已经快到秒出答案,但这对快速输出状态的程序员来说仍然是不够的。要么它的提示还没出现你就继续输入了,要么你会因为等它而暂时停下思路。
  2. Github Copilot 总是会自动提示。这种提示和输入存在冲突:有时,当你需要等等看提示怎么说另一些时,会不断有内容弹出,接着消失。或许,自动模式并不是 Github Copilot 的「最佳打开方式」?
  3. Github Copilot 生成代码质量不足。它生成的代码可以满足大部分简单且重复的功能需求,但对于熟练的程序员,可能会额外浪费很多精力来校验它自动生成的代码是否正确。

Github Copilot 版权问题

许多人指出 Github Copilot 会使用有版权的代码作为提示内容(参见 Jacob Crume 的文章“GitHub Copilot is Now Available for All and Not Everyone Likes It”)。少数派作者 100gle 在《GitHub Copilot:革命未竟,未来可期》中更是举出了很多例子。最为出名的莫过于,如果你在编辑器中输入 Fast inverse square root,便会得到一段代码,它和当年《雷神之锤》使用的算法完全一致。

现代开源软件多使用 GPL (GNU General Public License)协议,这个协议要求你也将代码开源,且使用 GPL 协议。而通过 Github Copilot 补全时我们并不确定这段代码的作者为它指定的协议。开源许可证的主要作用是对软件的使用、复制、修改和再发布等进行限制。而显然使用 AI 补全显然会破坏这一点。

可以预见的是,同当今各种 AI 作画工具面对的种种争议一样,Github Copilot 也一定会因为版权问题,难以被大型企业所用,至少短期内如此。

使用建议

  • Github Copilot 能帮助初学者面对不那么熟悉的编程语言或开发框架时,快速学习常用的接口调用方式和简单的实现方案。这意味着我们可以不用为了某些基础问题反复翻找 API 手册,或体验 CSDN 这样的技术博客网站的层层传送门。
  • Github Copilot 可以帮助我们在不熟悉的领域快速上手,只需要一些注释便可快速生成部分业务逻辑,然后进行测试。当然,最终代码的可靠性还是需要开发者人为辨别和控制。
  • Github Copilot 可以在重复性劳动时显著提升效率。比如你需要写一大堆单元测试,它们无法靠复制/粘贴批量生成,同时有一些细微的逻辑变化需要处理。又或是你需要开发一些重复性功能,比如批量声明一些数据类型好几十次。这时 Github Copilot 补全的代码往往很可靠。

总结

Github Copilot 或许并不能承载类似“AI 即将取代程序员”的想象,但在当下,它无疑是程序员的好帮手。作为辅助,它提供的补全并没有智能到让完全不会编程的用户完成开发,但也并不只是简单的提示工具。合理运用 Github Copilot 能够为开发者的学习成长带来很大帮助。

与此同时,它不可避免地存在一些缺陷,代码的版权问题也限制了它商业化的应用前景。不够熟练的程序员可能也会对它失望——就像它名字中的 Copilot 一样,Github Copilot 更接近优秀的副驾驶角色,但工作总归还是需要一位优秀的主驾驶领导。

最好的旅行靴已经送到我们手中,走出什么样的路还需要开发者自己去定夺。

☑️ ☆

Jetbrains IDE 开发环境激活方式记录

引言

Jetbrains 全家桶开发还是比较顺手的,但工作之后学生认证到期了,所以需要重新激活,特此写一篇博文记录自己使用 Jetbrains 产品的各种激活方式。

需要提前声明,Jetbrains 也提供了社区版供学生和初学者使用,本文仅作激活操作记录,使用激活的软件请勿用作商业用途,如有条件请务必支持正版购买许可证。

学生认证

Github 的学生认证可以通过上传学校信息的方式获取正规免费的许可,在 Unity Student Plan 申请指南 这篇文章有详细操作。

如果是在读学生,完全可以用这种方式激活 Jetbrains 相关产品。

注册机激活

不推荐这种激活方式。

之前我使用这种方式激活,因为之前有一些相关文件未删除,会导致整个软件闪退无法使用,在 Mac 上折腾了很长一段时间。

服务器激活

先打开这个网站:https://search.censys.io/

然后搜索框输入:

services.http.response.headers.location: account.jetbrains.com/fls-auth

选择第一个搜索结果,右击进去:

将网址到 Jetbrains,选择许可证服务器 /License server,粘贴刚刚复制的网址 http://134.53.225.196,激活。

大功告成,顺带一提,这个好像是迈阿密大学的服务器……

☑️ ⭐

GStarCAD C++笔试&机试&面试总结

引言

GStarCAD 笔试和机试总结。笔试题主要考核 C++、代码阅读理解、基本几何运算、英文阅读能力,机试题主要考察 VC++、MFC 的实际编程操作能力。

笔试部分

笔试题主要考核 C++、代码阅读理解、基本几何运算、英文阅读能力。

问题1

题目

下列代码有问题、或有可改进之处吗?如有,请直接修改,并写明原因.

class CBase
{
public:
CBase(){m_nVal = 100;}
~CBase(){}

int Get() {return m_nVal;}
int GetDouble() const {m_nVal *= 3; return m_nVal;}
private:
int m_nVal;
};

int main(int argc, char* argv[])
{
CBase base;
std::cout << “val = ”<< base.GetDouble() << std::endl;
return 0;
}
答案

答:int GetDouble() const {m_nVal *= 3; return m_nVal;} 若需要对成员变量进行赋值需删除 const

问题2

题目

请写出 main 函数的输出结果,并写明理由.

class CBase
{
public:
virtual voidSend(){std::cout << "\nSend :"<< m_nVal << std::endl;}
void Output(){Send();}
public:
int m_nVal;
};

class CUser : public CBase
{
public:
CUser(){m_nVal = 101;}
virtual voidSend(){m_nVal++;std::cout << “\nSend :”<<m_nVal<< std::endl;}
void Output(){CBase::Send();}
};

int main(int argc, char* argv[])
{
CUser user;
CBase &base=user;
base.Send();//输出:
CBase *pBase=&base;
pBase->Output();//输出:
user.Output();//输出:
}
答案
Send:102
Send:103
Send:103

问题3

题目

阅读理解类声明代码,并使用之实现功能。

class AcGePoint2d
{
public:
AcGePoint2d();
AcGePoint2d(double x, double y);
AcGePoint2d& set(double x, double y);

double x, y;
};

class AcGeLinearEnt2d
{
public:
boolintersectWith(const AcGeLinearEnt2d& line, AcGePoint2d& intPnt,const AcGeTol& tol = AcGeContext::gTol) const;//求直线交点函数

protected:
AcGeLinearEnt2d ();
AcGeLinearEnt2d (const AcGeLinearEnt2d&);
};

class AcGeLineSeg2d: public AcGeLinearEnt2d
{
public:AcGeLineSeg2d ();
AcGeLineSeg2d (const AcGeLineSeg2d & line);
AcGeLineSeg2d (const AcGePoint2d& pnt1, const AcGePoint2d& pnt2);
AcGeLineSeg2d & set (const AcGePoint2d& pnt1, const AcGePoint2d& pnt2);
};

int main(int argc, char* argv[])
{
//请使用上述类和类成员函数,在本函数中实现两直线段求交点,并输出。
//这两个直线段分别是从点(0,0) 到(500,500); 从点(600,0) 到(200,900)。

return 0;
}
答案
class AcGePoint2d
{
public:
AcGePoint2d();
AcGePoint2d(double x, double y);
AcGePoint2d& set(double x, double y);

double x, y;
};

class AcGeLinearEnt2d
{
public:
boolintersectWith(const AcGeLinearEnt2d& line, AcGePoint2d& intPnt,const AcGeTol& tol = AcGeContext::gTol) const;//求直线交点函数

protected:
AcGeLinearEnt2d ();
AcGeLinearEnt2d (const AcGeLinearEnt2d&);
};

class AcGeLineSeg2d: public AcGeLinearEnt2d
{
public:AcGeLineSeg2d ();
AcGeLineSeg2d (const AcGeLineSeg2d & line);
AcGeLineSeg2d (const AcGePoint2d& pnt1, const AcGePoint2d& pnt2);
AcGeLineSeg2d & set (const AcGePoint2d& pnt1, const AcGePoint2d& pnt2);
};

int main(int argc, char* argv[])
{
//请使用上述类和类成员函数,在本函数中实现两直线段求交点,并输出。
//这两个直线段分别是从点(0,0) 到(500,500); 从点(600,0) 到(200,900)。

+ AcGeLineSeg2dline1(AcGePoint2d(0,0),AcGePoint2d(500,500));
+ AcGeLineSeg2dline2(AcGePoint2d(600,0),AcGePoint2d(200,900));
+ AcGePoint2d pt;Line1.intersectWith(line2,pt);
+ Printf(“x:%.2f,y:%.2f”,pt.x,pt.y);

return 0;
}

问题4

基本几何运算。

  1. 已知两点 pt1,pt2,如何计算从起点 pt1 到终点 pt2 的向量 v
V = pt2 - pt1
  1. 已知向量 v1{1.0,0.0,0.0},v2{0.0,1.0,0.0}v3 = v1 - v2 ,则v3 =?
{1.0,-1.0,0.0}
  1. 已知向量v1{1.0,0.0,0.0},v2{0.0,1.0,0.0},v3=v1×v2 ,则v3=?
{0.0,0.0,1.0}
  1. 两向量的点积 v1·v2 等于 0 ,意味着两向量是什么关系?
垂直

问题5

翻译英文资料。

An ObjectARXapplication is a dynamic link library (DLL) that shares the address space of AutoCAD and makes direct function calls to AutoCAD. You can add new classes to the ObjectARXprogram environment and export them for use by other programs.

一个 ObjectARX 应用是一个的动态链接库(DLL),它共享 AutoCAD 地址空间,并直接调用函数操作 AutoCAD。你可以在 ObjectARX 程序环境中新增新的类,并将其导出给其他程序使用。

CDialog::DoModal() Call this member function to invoke the modal dialog box and return the dialog-box result when done. This member function handles all interaction with the user while the dialog box is active.

CDialog::DoModal(),使用这一成员函数可调出模态对话框,并且当其使用完成后可返回对话框的结果。当对话框激活时,这一成员函数处理所有与用户的交互。

AutoCADstores the values for its operating environment in system variables. Each system variable has an associated type: integer, real, point, or text string. You can examine any system variable and change any writable system variable directly on the command line by entering the system variable name. Many system variables are also accessible through dialog box options.

AutoCAD 保存与操作环境相关的值于系统变量中。每个系统变量有一个相关类型:整形,实型,点或字符串。你可以检测任何系统变量,并通过在命令行输入系统变量名称直接改变系统变量。许多系统变量也可以通过对话框选项设置。

机试部分

机试题主要考察 VC++、MFC 的实际编程操作能力。

控件窗口操作

  • 新建基于对话框的 MFC 工程。
  • 定义 CEdit 的派生类 CMyEdit。在 CMyEdit 类中定义成员函数 void SetIndex(int index),调用本函数后,编辑框内显示 index 数值。
  • 对话框初始创建4个大小不一的控件,分别是:CMyEditCButtonCComboBoxCEdit,分别对齐对话框4个角。
  • 在对话框类内定义一个指针数组成员变量:CArray<CWnd*> m_arrCtrl,并在对话框初始化时将上述4控件的对象指针按逆时针顺序保存到 m_arrCtrl 数组(第1个为左上角控件)。
  • 对话框窗口支持调整大小,对话框窗口大小改变后,4个控件大小不变,但位置自动跟随调整(总是对齐4个角)。
  • 每隔1秒,沿逆时针方向自动旋转切换上述4个控件位置(控件大小不变,只是位置改变,左上角控件跑到左下角,左下角跑到右下角,以此类推),m_arrCtrl 中控件指针也同步切换位置(第1个始终是左上角控件)。每次切换控件位置后,需从指针数组中找到其中唯一的 CMyEdit 控件,并调用它的 SetIndex(index)成员函数,indexCMyEdit 对象在 m_arrCtrl 数组中的新索引(0-3)。
  • 注:对话框内可以定义其它成员变量,但除对话框的构造函数、DoDataExchangeOnInitDialog 函数外,对话框其它函数中只能使用 m_arrCtrl 成员变量,不能使用其它成员变量(也不能使用全局变量和静态变量)。

排序操作

  • 新建基于对话框的 MFC 工程。
  • 在对话框上绘制一个编辑框和一个排序按钮。
  • 编辑框内可输入一系列的数,用空格分开。单击排序按钮,则对这些数由小到大排序,并重新显示在编辑框中。
  • 注:需自写排序算法。

目录浏览

  • 新建基于对话框的 MFC 工程。
  • 对话框左侧显示一个树控件,显示一个两层目录,一级目录为学校,二级为班级。对话框右侧显示一个 LISTBOX
  • 当在左侧选中不同的学校或班级,右侧 LISTBOX 刷新显示为本学校或本班级的所有学生姓名。

面试部分

  • 简单做一个自我介绍
  • 什么时候开始学习 C++ 和开始使用 VC++
  • MFC 方面实际使用过哪些类
  • 描述链表和数组的区别、优缺点,用过链表没,是否用过和了解 STL::map
  • 英语是否过了4级,阅读过MSDN的英文材料有没有问题
  • 目前还掌握了什么开发技能,是否自学的
  • 是否接触过 CAD 软件
  • 简单描述一个最能体现自身技术能力的典型项目或程序的实现
  • 感兴趣、爱好、热爱,对于编程,你属于哪一种?为什么?
  • 是否有哪方面能力特别优秀,在这方面特自信,自认为超过自己周围的人?
  • 评价一下自己有哪些缺点
  • 有什么兴趣爱好
  • 后续有什么职业规划
  • 转正薪资要求?试用期 3 个月是 80%
  • 对于我们公司和这份工作有什么需要了解的
☑️ ⭐

Google开源项目C++风格指南

引言

Google 经常会发布一些开源项目, 意味着会接受来自其他代码贡献者的代码。但是如果代码贡献者的编程风格与 Google 的不一致, 会给代码阅读者和其他代码提交者造成不小的困扰。Google 因此发布了这份自己的编程风格指南, 使所有提交代码的人都能获知 Google 的编程风格。

C++ 是 Google 大部分开源项目的主要编程语言. 正如每个 C++ 程序员都知道的, C++ 有很多强大的特性, 但这种强大不可避免的导致它走向复杂,使代码更容易产生 bug, 难以阅读和维护.

本指南的目的是通过详细阐述 C++ 注意事项来驾驭其复杂性. 这些规则在保证代码易于管理的同时, 也能高效使用 C++ 的语言特性.

风格, 亦被称作可读性, 也就是指导 C++ 编程的约定. 使用术语 “风格” 有些用词不当, 因为这些习惯远不止源代码文件格式化这么简单.

使代码易于管理的方法之一是加强代码一致性. 让任何程序员都可以快速读懂你的代码这点非常重要. 保持统一编程风格并遵守约定意味着可以很容易根据 “模式匹配” 规则来推断各种标识符的含义. 创建通用, 必需的习惯用语和模式可以使代码更容易理解. 在一些情况下可能有充分的理由改变某些编程风格, 但我们还是应该遵循一致性原则,尽量不这么做.

本指南的另一个观点是 C++ 特性的臃肿. C++ 是一门包含大量高级特性的庞大语言. 某些情况下, 我们会限制甚至禁止使用某些特性. 这么做是为了保持代码清爽, 避免这些特性可能导致的各种问题. 指南中列举了这类特性, 并解释为什么这些特性被限制使用.

Google 主导的开源项目均符合本指南的规定.

注意: 本指南并非 C++ 教程, 我们假定读者已经对 C++ 非常熟悉.

头文件

通常每一个 .cc 文件都有一个对应的 .h 文件. 也有一些常见例外, 如单元测试代码和只包含 main() 函数的 .cc 文件.

正确使用头文件可令代码在可读性、文件大小和性能上大为改观.

下面的规则将引导你规避使用头文件时的各种陷阱.

Self-contained 头文件

头文件应该能够自给自足(self-contained,也就是可以作为第一个头文件被引入),以 .h 结尾。至于用来插入文本的文件,说到底它们并不是头文件,所以应以 .inc 结尾。不允许分离出 -inl.h 头文件的做法.

所有头文件要能够自给自足。换言之,用户和重构工具不需要为特别场合而包含额外的头文件。详言之,一个头文件要有 #define 保护,统统包含它所需要的其它头文件,也不要求定义任何特别 symbols.

不过有一个例外,即一个文件并不是 self-contained 的,而是作为文本插入到代码某处。或者,文件内容实际上是其它头文件的特定平台(platform-specific)扩展部分。这些文件就要用 .inc 文件扩展名。

如果 .h 文件声明了一个模板或内联函数,同时也在该文件加以定义。凡是有用到这些的 .cc 文件,就得统统包含该头文件,否则程序可能会在构建中链接失败。不要把这些定义放到分离的 -inl.h 文件里(译者注:过去该规范曾提倡把定义放到 -inl.h 里过)。

有个例外:如果某函数模板为所有相关模板参数显式实例化,或本身就是某类的一个私有成员,那么它就只能定义在实例化该模板的 .cc 文件里。

#define 保护

所有头文件都应该有 #define 保护来防止头文件被多重包含, 命名格式当是: <PROJECT>_<PATH>_<FILE>_H_ .

为保证唯一性, 头文件的命名应该基于所在项目源代码树的全路径. 例如, 项目 foo 中的头文件 foo/src/bar/baz.h 可按如下方式保护:

#ifndef FOO_BAR_BAZ_H_
#define FOO_BAR_BAZ_H_
...
#endif // FOO_BAR_BAZ_H_

前置声明

尽可能地避免使用前置声明。使用 #include 包含需要的头文件即可。

定义

所谓「前置声明」(forward declaration)是类、函数和模板的纯粹声明,没伴随着其定义.

优点
  • 前置声明能够节省编译时间,多余的 #include 会迫使编译器展开更多的文件,处理更多的输入。
  • 前置声明能够节省不必要的重新编译的时间。 #include 使代码因为头文件中无关的改动而被重新编译多次。
缺点
  • 前置声明隐藏了依赖关系,头文件改动时,用户的代码会跳过必要的重新编译过程。
  • 前置声明可能会被库的后续更改所破坏。前置声明函数或模板有时会妨碍头文件开发者变动其 API. 例如扩大形参类型,加个自带默认参数的模板形参等等。
  • 前置声明来自命名空间 std:: 的 symbol 时,其行为未定义。
  • 很难判断什么时候该用前置声明,什么时候该用 #include 。极端情况下,用前置声明代替 #include 甚至都会暗暗地改变代码的含义:
// b.h:
struct B {};
struct D : B {};

// good_user.cc:
#include "b.h"
void f(B*);
void f(void*);
void test(D* x) { f(x); } // calls f(B*)

如果 #includeBD 的前置声明替代, test() 就会调用 f(void*) .

  • 前置声明了不少来自头文件的 symbol 时,就会比单单一行的 include 冗长。
  • 仅仅为了能前置声明而重构代码(比如用指针成员代替对象成员)会使代码变得更慢更复杂.

内联函数

只有当函数只有 10 行甚至更少时才将其定义为内联函数.

定义

当函数被声明为内联函数之后, 编译器会将其内联展开, 而不是按通常的函数调用机制进行调用.

优点

只要内联的函数体较小, 内联该函数可以令目标代码更加高效. 对于存取函数以及其它函数体比较短, 性能关键的函数, 鼓励使用内联.

缺点

滥用内联将导致程序变得更慢. 内联可能使目标代码量或增或减, 这取决于内联函数的大小. 内联非常短小的存取函数通常会减少代码大小, 但内联一个相当大的函数将戏剧性的增加代码大小. 现代处理器由于更好的利用了指令缓存, 小巧的代码往往执行更快。

结论

一个较为合理的经验准则是, 不要内联超过 10 行的函数. 谨慎对待析构函数, 析构函数往往比其表面看起来要更长, 因为有隐含的成员和基类析构函数被调用!

另一个实用的经验准则: 内联那些包含循环或 switch 语句的函数常常是得不偿失 (除非在大多数情况下, 这些循环或 switch 语句从不被执行).

有些函数即使声明为内联的也不一定会被编译器内联, 这点很重要; 比如虚函数和递归函数就不会被正常内联. 通常, 递归函数不应该声明成内联函数.(YuleFox 注: 递归调用堆栈的展开并不像循环那么简单, 比如递归层数在编译时可能是未知的, 大多数编译器都不支持内联递归函数). 虚函数内联的主要原因则是想把它的函数体放在类定义内, 为了图个方便, 抑或是当作文档描述其行为, 比如精短的存取函数.

#include 的路径及顺序

使用标准的头文件包含顺序可增强可读性, 避免隐藏依赖: 相关头文件, C 库, C++ 库, 其他库的 .h, 本项目内的 .h.

项目内头文件应按照项目源代码目录树结构排列, 避免使用 UNIX 特殊的快捷目录 . (当前目录) 或 .. (上级目录). 例如, google-awesome-project/src/base/logging.h 应该按如下方式包含:

#include "base/logging.h"

又如, dir/foo.ccdir/foo_test.cc 的主要作用是实现或测试 dir2/foo2.h 的功能, foo.cc 中包含头文件的次序如下:

  1. dir2/foo2.h (优先位置, 详情如下)
  2. C 系统文件
  3. C++ 系统文件
  4. 其他库的 .h 文件
  5. 本项目内 .h 文件

这种优先的顺序排序保证当 dir2/foo2.h 遗漏某些必要的库时, dir/foo.ccdir/foo_test.cc 的构建会立刻中止。因此这一条规则保证维护这些文件的人们首先看到构建中止的消息而不是维护其他包的人们。

dir/foo.ccdir2/foo2.h 通常位于同一目录下 (如 base/basictypes_unittest.ccbase/basictypes.h), 但也可以放在不同目录下.

按字母顺序分别对每种类型的头文件进行二次排序是不错的主意。注意较老的代码可不符合这条规则,要在方便的时候改正它们。

您所依赖的符号 (symbols) 被哪些头文件所定义,您就应该包含(include)哪些头文件,前置声明 (forward declarations) 情况除外。比如您要用到 bar.h 中的某个符号, 哪怕您所包含的 foo.h 已经包含了 bar.h, 也照样得包含 bar.h, 除非 foo.h 有明确说明它会自动向您提供 bar.h 中的 symbol. 不过,凡是 cc 文件所对应的「相关头文件」已经包含的,就不用再重复包含进其 cc 文件里面了,就像 foo.cc 只包含 foo.h 就够了,不用再管后者所包含的其它内容。

举例来说, google-awesome-project/src/foo/internal/fooserver.cc 的包含次序如下:

#include "foo/public/fooserver.h" // 优先位置

#include <sys/types.h>
#include <unistd.h>

#include <hash_map>
#include <vector>

#include "base/basictypes.h"
#include "base/commandlineflags.h"
#include "foo/public/bar.h"

例外:

有时,平台特定(system-specific)代码需要条件编译(conditional includes),这些代码可以放到其它 includes 之后。当然,您的平台特定代码也要够简练且独立,比如:

#include "foo/public/fooserver.h"

#include "base/port.h" // For LANG_CXX11.

#ifdef LANG_CXX11
#include <initializer_list>
#endif // LANG_CXX11
译者 (YuleFox) 笔记
  1. 避免多重包含是学编程时最基本的要求;
  2. 前置声明是为了降低编译依赖,防止修改一个头文件引发多米诺效应;
  3. 内联函数的合理使用可提高代码执行效率;
  4. -inl.h 可提高代码可读性 (一般用不到吧:D);
  5. 标准化函数参数顺序可以提高可读性和易维护性 (对函数参数的堆栈空间有轻微影响, 我以前大多是相同类型放在一起);
  6. 包含文件的名称使用 ... 虽然方便却易混乱, 使用比较完整的项目路径看上去很清晰, 很条理, 包含文件的次序除了美观之外, 最重要的是可以减少隐藏依赖, 使每个头文件在 “最需要编译” (对应源文件处 :D) 的地方编译, 有人提出库文件放在最后, 这样出错先是项目内的文件, 头文件都放在对应源文件的最前面, 这一点足以保证内部错误的及时发现了.
译者(acgtyrant)笔记
  1. 原来还真有项目用 #includes 来插入文本,且其文件扩展名 .inc 看上去也很科学。
  2. Google 已经不再提倡 -inl.h 用法。
  3. 注意,前置声明的类是不完全类型(incomplete type),我们只能定义指向该类型的指针或引用,或者声明(但不能定义)以不完全类型作为参数或者返回类型的函数。毕竟编译器不知道不完全类型的定义,我们不能创建其类的任何对象,也不能声明成类内部的数据成员。
  4. 类内部的函数一般会自动内联。所以某函数一旦不需要内联,其定义就不要再放在头文件里,而是放到对应的 .cc 文件里。这样可以保持头文件的类相当精炼,也很好地贯彻了声明与定义分离的原则。
  5. #include 中插入空行以分割相关头文件, C 库, C++ 库, 其他库的 .h 和本项目内的 .h 是个好习惯。

作用域

命名空间

鼓励在 .cc 文件内使用匿名命名空间或 static 声明. 使用具名的命名空间时, 其名称可基于项目名或相对路径. 禁止使用 using 指示(using-directive)。禁止使用内联命名空间(inline namespace)。

定义

命名空间将全局作用域细分为独立的, 具名的作用域, 可有效防止全局作用域的命名冲突.

优点

虽然类已经提供了(可嵌套的)命名轴线 (YuleFox 注: 将命名分割在不同类的作用域内), 命名空间在这基础上又封装了一层.

举例来说, 两个不同项目的全局作用域都有一个类 Foo, 这样在编译或运行时造成冲突. 如果每个项目将代码置于不同命名空间中, project1::Fooproject2::Foo 作为不同符号自然不会冲突.

内联命名空间会自动把内部的标识符放到外层作用域,比如:

namespace X {
inline namespace Y {
void foo();
} // namespace Y
} // namespace X

X::Y::foo()X::foo() 彼此可代替。内联命名空间主要用来保持跨版本的 ABI 兼容性。

缺点

命名空间具有迷惑性, 因为它们使得区分两个相同命名所指代的定义更加困难。

内联命名空间很容易令人迷惑,毕竟其内部的成员不再受其声明所在命名空间的限制。内联命名空间只在大型版本控制里有用。

有时候不得不多次引用某个定义在许多嵌套命名空间里的实体,使用完整的命名空间会导致代码的冗长。

在头文件中使用匿名空间导致违背 C++ 的唯一定义原则 (One Definition Rule (ODR)).

结论

根据下文将要提到的策略合理使用命名空间.

  • 遵守命名空间命名中的规则。
  • 像之前的几个例子中一样,在命名空间的最后注释出命名空间的名字。
  • 用命名空间把文件包含, gflags 的声明/定义, 以及类的前置声明以外的整个源文件封装起来, 以区别于其它命名空间:
    // .h 文件
    namespace mynamespace {

    // 所有声明都置于命名空间中
    // 注意不要使用缩进
    class MyClass {
    public:
    ...
    void Foo();
    };

    } // namespace mynamespace
    // .cc 文件
    namespace mynamespace {

    // 函数定义都置于命名空间中
    void MyClass::Foo() {
    ...
    }

    } // namespace mynamespace

    更复杂的 .cc 文件包含更多, 更复杂的细节, 比如 gflags 或 using 声明。

    #include "a.h"

    DEFINE_FLAG(bool, someflag, false, "dummy flag");

    namespace a {

    ...code for a... // 左对齐

    } // namespace a
  • 不要在命名空间 std 内声明任何东西, 包括标准库的类前置声明. 在 std 命名空间声明实体是未定义的行为, 会导致如不可移植. 声明标准库下的实体, 需要包含对应的头文件.
  • 不应该使用 using 指示 引入整个命名空间的标识符号。
    // 禁止 —— 污染命名空间
    using namespace foo;
  • 不要在头文件中使用 命名空间别名 除非显式标记内部命名空间使用。因为任何在头文件中引入的命名空间都会成为公开API的一部分。
    // 在 .cc 中使用别名缩短常用的命名空间
    namespace baz = ::foo::bar::baz;
    // 在 .h 中使用别名缩短常用的命名空间
    namespace librarian {
    namespace impl { // 仅限内部使用
    namespace sidetable = ::pipeline_diagnostics::sidetable;
    } // namespace impl

    inline void my_inline_function() {
    // 限制在一个函数中的命名空间别名
    namespace baz = ::foo::bar::baz;
    ...
    }
    } // namespace librarian
  • 禁止用内联命名空间

匿名命名空间和静态变量

.cc 文件中定义一个不需要被外部引用的变量时,可以将它们放在匿名命名空间或声明为 static 。但是不要在 .h 文件中这么做。

定义

所有置于匿名命名空间的声明都具有内部链接性,函数和变量可以经由声明为 static 拥有内部链接性,这意味着你在这个文件中声明的这些标识符都不能在另一个文件中被访问。即使两个文件声明了完全一样名字的标识符,它们所指向的实体实际上是完全不同的。

结论

推荐、鼓励在 .cc 中对于不需要在其他地方引用的标识符使用内部链接性声明,但是不要在 .h 中使用。

匿名命名空间的声明和具名的格式相同,在最后注释上 namespace :

namespace {
...
} // namespace

非成员函数、静态成员函数和全局函数

使用静态成员函数或命名空间内的非成员函数, 尽量不要用裸的全局函数. 将一系列函数直接置于命名空间中,不要用类的静态方法模拟出命名空间的效果,类的静态方法应当和类的实例或静态数据紧密相关.

优点:

某些情况下, 非成员函数和静态成员函数是非常有用的, 将非成员函数放在命名空间内可避免污染全局作用域.

缺点

将非成员函数和静态成员函数作为新类的成员或许更有意义, 当它们需要访问外部资源或具有重要的依赖关系时更是如此.

结论

有时, 把函数的定义同类的实例脱钩是有益的, 甚至是必要的. 这样的函数可以被定义成静态成员, 或是非成员函数. 非成员函数不应依赖于外部变量, 应尽量置于某个命名空间内. 相比单纯为了封装若干不共享任何静态数据的静态成员函数而创建类, 不如使用 2.1. 命名空间。举例而言,对于头文件 myproject/foo_bar.h , 应当使用

namespace myproject {
namespace foo_bar {
void Function1();
void Function2();
} // namespace foo_bar
} // namespace myproject

而非

namespace myproject {
class FooBar {
public:
static void Function1();
static void Function2();
};
} // namespace myproject

定义在同一编译单元的函数, 被其他编译单元直接调用可能会引入不必要的耦合和链接时依赖; 静态成员函数对此尤其敏感. 可以考虑提取到新类中, 或者将函数置于独立库的命名空间内.

如果你必须定义非成员函数, 又只是在 .cc 文件中使用它, 可使用匿名 2.1. 命名空间 或 static 链接关键字 (如 static int Foo() {...}) 限定其作用域.

局部变量

将函数变量尽可能置于最小作用域内, 并在变量声明时进行初始化.

C++ 允许在函数的任何位置声明变量. 我们提倡在尽可能小的作用域中声明变量, 离第一次使用越近越好. 这使得代码浏览者更容易定位变量声明的位置, 了解变量的类型和初始值. 特别是,应使用初始化的方式替代声明再赋值, 比如:

int i;
i = f(); // 坏——初始化和声明分离
int j = g(); // 好——初始化时声明
vector<int> v;
v.push_back(1); // 用花括号初始化更好
v.push_back(2);
vector<int> v = {1, 2}; // 好——v 一开始就初始化

属于 if, whilefor 语句的变量应当在这些语句中正常地声明,这样子这些变量的作用域就被限制在这些语句中了,举例而言:

while (const char* p = strchr(str, '/')) str = p + 1;

有一个例外, 如果变量是一个对象, 每次进入作用域都要调用其构造函数, 每次退出作用域都要调用其析构函数. 这会导致效率降低.

// 低效的实现
for (int i = 0; i < 1000000; ++i) {
Foo f; // 构造函数和析构函数分别调用 1000000 次!
f.DoSomething(i);
}

在循环作用域外面声明这类变量要高效的多:

Foo f;                      // 构造函数和析构函数只调用 1 次
for (int i = 0; i < 1000000; ++i) {
f.DoSomething(i);
}

静态和全局变量

禁止定义静态储存周期非POD变量,禁止使用含有副作用的函数初始化POD全局变量,因为多编译单元中的静态变量执行时的构造和析构顺序是未明确的,这将导致代码的不可移植。

禁止使用类的静态储存周期变量:由于构造和析构函数调用顺序的不确定性,它们会导致难以发现的 bug 。不过 constexpr 变量除外,毕竟它们又不涉及动态初始化或析构。

静态生存周期的对象,即包括了全局变量,静态变量,静态类成员变量和函数静态变量,都必须是原生数据类型 (POD : Plain Old Data): 即 int, char 和 float, 以及 POD 类型的指针、数组和结构体。

静态变量的构造函数、析构函数和初始化的顺序在 C++ 中是只有部分明确的,甚至随着构建变化而变化,导致难以发现的 bug. 所以除了禁用类类型的全局变量,我们也不允许用函数返回值来初始化 POD 变量,除非该函数(比如 getenv()getpid() )不涉及任何全局变量。函数作用域里的静态变量除外,毕竟它的初始化顺序是有明确定义的,而且只会在指令执行到它的声明那里才会发生。

Xris 译注:

同一个编译单元内是明确的,静态初始化优先于动态初始化,初始化顺序按照声明顺序进行,销毁则逆序。不同的编译单元之间初始化和销毁顺序属于未明确行为 (unspecified behaviour)。

同理,全局和静态变量在程序中断时会被析构,无论所谓中断是从 main() 返回还是对 exit() 的调用。析构顺序正好与构造函数调用的顺序相反。但既然构造顺序未定义,那么析构顺序当然也就不定了。比如,在程序结束时某静态变量已经被析构了,但代码还在跑——比如其它线程——并试图访问它且失败;再比如,一个静态 string 变量也许会在一个引用了前者的其它变量析构之前被析构掉。

改善以上析构问题的办法之一是用 quick_exit() 来代替 exit() 并中断程序。它们的不同之处是前者不会执行任何析构,也不会执行 atexit() 所绑定的任何 handlers. 如果您想在执行 quick_exit() 来中断时执行某 handler(比如刷新 log),您可以把它绑定到 _at_quick_exit(). 如果您想在 exit()quick_exit() 都用上该 handler, 都绑定上去。

综上所述,我们只允许 POD 类型的静态变量,即完全禁用 vector (使用 C 数组替代) 和 string (使用 const char[])。

如果您确实需要一个 class 类型的静态或全局变量,可以考虑在 main() 函数或 pthread_once() 内初始化一个指针且永不回收。注意只能用 raw 指针,别用智能指针,毕竟后者的析构函数涉及到上文指出的不定顺序问题。

Yang.Y 译注:

上文提及的静态变量泛指静态生存周期的对象, 包括: 全局变量, 静态变量, 静态类成员变量, 以及函数静态变量.

译者 (YuleFox) 笔记

  1. cc中的匿名命名空间可避免命名冲突, 限定作用域, 避免直接使用using 关键字污染命名空间;
  2. 嵌套类符合局部使用原则, 只是不能在其他头文件中前置声明, 尽量不要 public;
  3. 尽量不用全局函数和全局变量, 考虑作用域和命名空间限制, 尽量单独形成编译单元;
  4. 多线程中的全局变量 (含静态成员变量) 不要使用 class 类型 (含 STL 容器), 避免不明确行为导致的 bug.
  5. 作用域的使用, 除了考虑名称污染, 可读性之外, 主要是为降低耦合, 提高编译/执行效率.

译者(acgtyrant)笔记

  1. 注意「using 指示(using-directive)」和「using 声明(using-declaration)」的区别。
  2. 匿名命名空间说白了就是文件作用域,就像 C static 声明的作用域一样,后者已经被 C++ 标准提倡弃用。
  3. 局部变量在声明的同时进行显式值初始化,比起隐式初始化再赋值的两步过程要高效,同时也贯彻了计算机体系结构重要的概念「局部性(locality)」。
  4. 注意别在循环犯大量构造和析构的低级错误。

函数

输入和输出

总述

我们倾向于按值返回, 否则按引用返回。 避免返回指针, 除非它可以为空.

说明

C++ 函数由返回值提供天然的输出, 有时也通过输出参数(或输入/输出参数)提供. 我们倾向于使用返回值而不是输出参数: 它们提高了可读性, 并且通常提供相同或更好的性能.

C/C++ 中的函数参数或者是函数的输入, 或者是函数的输出, 或兼而有之. 非可选输入参数通常是值参或 const 引用, 非可选输出参数或输入/输出参数通常应该是引用 (不能为空). 对于可选的参数, 通常使用 std::optional 来表示可选的按值输入, 使用 const 指针来表示可选的其他输入. 使用非常量指针来表示可选输出和可选输入/输出参数.

避免定义需要 const 引用参数去超出生命周期的函数, 因为 const 引用参数与临时变量绑定. 相反, 要找到某种方法来消除生命周期要求 (例如, 通过复制参数), 或者通过 const 指针传递它并记录生命周期和非空要求.

在排序函数参数时, 将所有输入参数放在所有输出参数之前. 特别要注意, 在加入新参数时不要因为它们是新参数就置于参数列表最后, 而是仍然要按照前述的规则, 即将新的输入参数也置于输出参数之前.

这并非一个硬性规定. 输入/输出参数 (通常是类或结构体) 让这个问题变得复杂. 并且, 有时候为了其他函数保持一致, 你可能不得不有所变通.

编写简短函数

总述

我们倾向于编写简短, 凝练的函数.

说明

我们承认长函数有时是合理的, 因此并不硬性限制函数的长度. 如果函数超过 40 行, 可以思索一下能不能在不影响程序结构的前提下对其进行分割.

即使一个长函数现在工作的非常好, 一旦有人对其修改, 有可能出现新的问题, 甚至导致难以发现的 bug. 使函数尽量简短, 以便于他人阅读和修改代码.

在处理代码时, 你可能会发现复杂的长函数. 不要害怕修改现有代码: 如果证实这些代码使用 / 调试起来很困难, 或者你只需要使用其中的一小段代码, 考虑将其分割为更加简短并易于管理的若干函数.

引用参数

总述

所有按引用传递的参数必须加上 const.

定义

在 C 语言中, 如果函数需要修改变量的值, 参数必须为指针, 如 int foo(int* pval). 在 C++ 中, 函数还可以声明为引用参数: int foo(int &val).

优点

定义引用参数可以防止出现 (*pval)++ 这样丑陋的代码. 引用参数对于拷贝构造函数这样的应用也是必需的. 同时也更明确地不接受空指针.

缺点

容易引起误解, 因为引用在语法上是值变量却拥有指针的语义.

结论

函数参数列表中, 所有引用参数都必须是 const:

void Foo(const string &in, string *out);

事实上这在 Google Code 是一个硬性约定: 输入参数是值参或 const 引用, 输出参数为指针. 输入参数可以是 const 指针, 但决不能是非 const 的引用参数, 除非特殊要求, 比如 swap().

有时候, 在输入形参中用 const T* 指针比 const T& 更明智. 比如:

  • 可能会传递空指针.
  • 函数要把指针或对地址的引用赋值给输入形参.

总而言之, 大多时候输入形参往往是 const T&. 若用 const T* 则说明输入另有处理. 所以若要使用 const T*, 则应给出相应的理由, 否则会使得读者感到迷惑.

函数重载

总述

若要使用函数重载, 则必须能让读者一看调用点就胸有成竹, 而不用花心思猜测调用的重载函数到底是哪一种. 这一规则也适用于构造函数.

定义

你可以编写一个参数类型为 const string& 的函数, 然后用另一个参数类型为 const char* 的函数对其进行重载:

class MyClass {
public:
void Analyze(const string &text);
void Analyze(const char *text, size_t textlen);
};
优点

通过重载参数不同的同名函数, 可以令代码更加直观. 模板化代码需要重载, 这同时也能为使用者带来便利.

缺点

如果函数单靠不同的参数类型而重载 (acgtyrant 注:这意味着参数数量不变), 读者就得十分熟悉 C++ 五花八门的匹配规则, 以了解匹配过程具体到底如何. 另外, 如果派生类只重载了某个函数的部分变体, 继承语义就容易令人困惑.

结论

如果打算重载一个函数, 可以试试改在函数名里加上参数信息. 例如, 用 AppendString()AppendInt() 等, 而不是一口气重载多个 Append(). 如果重载函数的目的是为了支持不同数量的同一类型参数, 则优先考虑使用 std::vector 以便使用者可以用列表初始化指定参数.

缺省参数

总述

只允许在非虚函数中使用缺省参数, 且必须保证缺省参数的值始终一致. 缺省参数与函数重载遵循同样的规则. 一般情况下建议使用函数重载, 尤其是在缺省函数带来的可读性提升不能弥补下文中所提到的缺点的情况下.

优点

有些函数一般情况下使用默认参数, 但有时需要又使用非默认的参数. 缺省参数为这样的情形提供了便利, 使程序员不需要为了极少的例外情况编写大量的函数. 和函数重载相比, 缺省参数的语法更简洁明了, 减少了大量的样板代码, 也更好地区别了 “必要参数” 和 “可选参数”.

缺点

缺省参数实际上是函数重载语义的另一种实现方式, 因此所有不应当使用函数重载的理由也都适用于缺省参数.

虚函数调用的缺省参数取决于目标对象的静态类型, 此时无法保证给定函数的所有重载声明的都是同样的缺省参数.

缺省参数是在每个调用点都要进行重新求值的, 这会造成生成的代码迅速膨胀. 作为读者, 一般来说也更希望缺省的参数在声明时就已经被固定了, 而不是在每次调用时都可能会有不同的取值.

缺省参数会干扰函数指针, 导致函数签名与调用点的签名不一致. 而函数重载不会导致这样的问题.

结论

对于虚函数, 不允许使用缺省参数, 因为在虚函数中缺省参数不一定能正常工作. 如果在每个调用点缺省参数的值都有可能不同, 在这种情况下缺省函数也不允许使用. (例如, 不要写像 void f(int n = counter++); 这样的代码.)

在其他情况下, 如果缺省参数对可读性的提升远远超过了以上提及的缺点的话, 可以使用缺省参数. 如果仍有疑惑, 就使用函数重载.

函数返回类型后置语法

总述

只有在常规写法 (返回类型前置) 不便于书写或不便于阅读时使用返回类型后置语法.

定义

C++ 现在允许两种不同的函数声明方式. 以往的写法是将返回类型置于函数名之前. 例如:

int foo(int x);

C++11 引入了这一新的形式. 现在可以在函数名前使用 auto 关键字, 在参数列表之后后置返回类型. 例如:

auto foo(int x) -> int;

后置返回类型为函数作用域. 对于像 int 这样简单的类型, 两种写法没有区别. 但对于复杂的情况, 例如类域中的类型声明或者以函数参数的形式书写的类型, 写法的不同会造成区别.

优点

后置返回类型是显式地指定Lambda 表达式的返回值的唯一方式. 某些情况下, 编译器可以自动推导出 Lambda 表达式的返回类型, 但并不是在所有的情况下都能实现. 即使编译器能够自动推导, 显式地指定返回类型也能让读者更明了.

有时在已经出现了的函数参数列表之后指定返回类型, 能够让书写更简单, 也更易读, 尤其是在返回类型依赖于模板参数时. 例如:

template <class T, class U> auto add(T t, U u) -> decltype(t + u);

对比下面的例子:

template <class T, class U> decltype(declval<T&>() + declval<U&>()) add(T t, U u);
缺点

后置返回类型相对来说是非常新的语法, 而且在 C 和 Java 中都没有相似的写法, 因此可能对读者来说比较陌生.

在已有的代码中有大量的函数声明, 你不可能把它们都用新的语法重写一遍. 因此实际的做法只能是使用旧的语法或者新旧混用. 在这种情况下, 只使用一种版本是相对来说更规整的形式.

结论

在大部分情况下, 应当继续使用以往的函数声明写法, 即将返回类型置于函数名前. 只有在必需的时候 (如 Lambda 表达式) 或者使用后置语法能够简化书写并且提高易读性的时候才使用新的返回类型后置语法. 但是后一种情况一般来说是很少见的, 大部分时候都出现在相当复杂的模板代码中, 而多数情况下不鼓励写这样复杂的模板代码.

来自Google的奇技

Google 用了很多自己实现的技巧 / 工具使 C++ 代码更加健壮, 我们使用 C++ 的方式可能和你在其它地方见到的有所不同.

所有权与智能指针

总述

动态分配出的对象最好有单一且固定的所有主, 并通过智能指针传递所有权.

定义

所有权是一种登记/管理动态内存和其它资源的技术. 动态分配对象的所有主是一个对象或函数, 后者负责确保当前者无用时就自动销毁前者. 所有权有时可以共享, 此时就由最后一个所有主来负责销毁它. 甚至也可以不用共享, 在代码中直接把所有权传递给其它对象.

智能指针是一个通过重载 *-> 运算符以表现得如指针一样的类. 智能指针类型被用来自动化所有权的登记工作, 来确保执行销毁义务到位. std::unique_ptr 是 C++11 新推出的一种智能指针类型, 用来表示动态分配出的对象的独一无二的所有权; 当 std::unique_ptr 离开作用域时, 对象就会被销毁. std::unique_ptr 不能被复制, 但可以把它移动(move)给新所有主. std::shared_ptr 同样表示动态分配对象的所有权, 但可以被共享, 也可以被复制; 对象的所有权由所有复制者共同拥有, 最后一个复制者被销毁时, 对象也会随着被销毁.

优点
  • 如果没有清晰、逻辑条理的所有权安排, 不可能管理好动态分配的内存.
  • 传递对象的所有权, 开销比复制来得小, 如果可以复制的话.
  • 传递所有权也比”借用”指针或引用来得简单, 毕竟它大大省去了两个用户一起协调对象生命周期的工作.
  • 如果所有权逻辑条理, 有文档且不紊乱的话, 可读性会有很大提升.
  • 可以不用手动完成所有权的登记工作, 大大简化了代码, 也免去了一大波错误之恼.
  • 对于 const 对象来说, 智能指针简单易用, 也比深度复制高效.
缺点
  • 不得不用指针(不管是智能的还是原生的)来表示和传递所有权. 指针语义可要比值语义复杂得许多了, 特别是在 API 里:这时不光要操心所有权, 还要顾及别名, 生命周期, 可变性以及其它大大小小的问题.
  • 其实值语义的开销经常被高估, 所以所有权传递带来的性能提升不一定能弥补可读性和复杂度的损失.
  • 如果 API 依赖所有权的传递, 就会害得客户端不得不用单一的内存管理模型.
  • 如果使用智能指针, 那么资源释放发生的位置就会变得不那么明显.
  • <span class="pre">std::unique_ptr</span> 的所有权传递原理是 C++11 的 move 语法, 后者毕竟是刚刚推出的, 容易迷惑程序员.
  • 如果原本的所有权设计已经够完善了, 那么若要引入所有权共享机制, 可能不得不重构整个系统.
  • 所有权共享机制的登记工作在运行时进行, 开销可能相当大.
  • 某些极端情况下 (例如循环引用), 所有权被共享的对象永远不会被销毁.
  • 智能指针并不能够完全代替原生指针.
结论

如果必须使用动态分配, 那么更倾向于将所有权保持在分配者手中. 如果其他地方要使用这个对象, 最好传递它的拷贝, 或者传递一个不用改变所有权的指针或引用. 倾向于使用 std::unique_ptr 来明确所有权传递, 例如:

std::unique_ptr<Foo> FooFactory();
void FooConsumer(std::unique_ptr<Foo> ptr);

如果没有很好的理由, 则不要使用共享所有权. 这里的理由可以是为了避免开销昂贵的拷贝操作, 但是只有当性能提升非常明显, 并且操作的对象是不可变的(比如说 std::shared_ptr<const Foo> )时候, 才能这么做. 如果确实要使用共享所有权, 建议于使用 std::shared_ptr .

不要使用 std::auto_ptr, 使用 std::unique_ptr 代替它.

Cpplint

总述

使用 cpplint.py 检查风格错误.

说明

cpplint.py 是一个用来分析源文件, 能检查出多种风格错误的工具. 它不并完美, 甚至还会漏报和误报, 但它仍然是一个非常有用的工具. 在行尾加 // NOLINT, 或在上一行加 // NOLINTNEXTLINE, 可以忽略报错.

某些项目会指导你如何使用他们的项目工具运行 cpplint.py. 如果你参与的项目没有提供, 你可以单独下载 cpplint.py.

译者(acgtyrant)笔记

  1. 把智能指针当成对象来看待的话, 就很好领会它与所指对象之间的关系了.
  2. 原来 Rust 的 Ownership 思想是受到了 C++ 智能指针的很大启发啊.
  3. scoped_ptrauto_ptr 已过时. 现在是 shared_ptruniqued_ptr 的天下了.
  4. 按本文来说, 似乎除了智能指针, 还有其它所有权机制, 值得留意.
  5. Arch Linux 用户注意了, AUR 有对 cpplint 打包.

其他C++特性

命名约定

最重要的一致性规则是命名管理. 命名的风格能让我们在不需要去查找类型声明的条件下快速地了解某个名字代表的含义: 类型, 变量, 函数, 常量, 宏, 等等, 甚至. 我们大脑中的模式匹配引擎非常依赖这些命名规则.

命名规则具有一定随意性, 但相比按个人喜好命名, 一致性更重要, 所以无论你认为它们是否重要, 规则总归是规则.

通用命名规则

总述

函数命名, 变量命名, 文件命名要有描述性; 少用缩写.

说明

尽可能使用描述性的命名, 别心疼空间, 毕竟相比之下让代码易于新读者理解更重要. 不要用只有项目开发者能理解的缩写, 也不要通过砍掉几个字母来缩写单词.

int price_count_reader;    // 无缩写
int num_errors; // "num" 是一个常见的写法
int num_dns_connections; // 人人都知道 "DNS" 是什么
int n;                     // 毫无意义.
int nerr; // 含糊不清的缩写.
int n_comp_conns; // 含糊不清的缩写.
int wgc_connections; // 只有贵团队知道是什么意思.
int pc_reader; // "pc" 有太多可能的解释了.
int cstmr_id; // 删减了若干字母.

注意, 一些特定的广为人知的缩写是允许的, 例如用 i 表示迭代变量和用 T 表示模板参数.

模板参数的命名应当遵循对应的分类: 类型模板参数应当遵循类型命名的规则, 而非类型模板应当遵循变量命名的规则.

文件命名

总述

文件名要全部小写, 可以包含下划线 (_) 或连字符 (-), 依照项目的约定. 如果没有约定, 那么 “_” 更好.

说明

可接受的文件命名示例:

  • my_useful_class.cc
  • my-useful-class.cc
  • myusefulclass.cc
  • myusefulclass_test.cc // _unittest_regtest 已弃用.

C++ 文件要以 .cc 结尾, 头文件以 .h 结尾. 专门插入文本的文件则以 .inc 结尾, 参见头文件自足.

不要使用已经存在于 /usr/include 下的文件名 (Yang.Y 注: 即编译器搜索系统头文件的路径), 如 db.h.

通常应尽量让文件名更加明确. http_server_logs.h 就比 logs.h 要好. 定义类时文件名一般成对出现, 如 foo_bar.hfoo_bar.cc, 对应于类 FooBar.

内联函数必须放在 .h 文件中. 如果内联函数比较短, 就直接放在 .h 中.

注释

格式

规则特例

前面说明的编程习惯基本都是强制性的. 但所有优秀的规则都允许例外, 这里就是探讨这些特例.

现有不合规范的代码

总述

对于现有不符合既定编程风格的代码可以网开一面.

说明

当你修改使用其他风格的代码时, 为了与代码原有风格保持一致可以不使用本指南约定. 如果不放心, 可以与代码原作者或现在的负责人员商讨. 记住, 一致性 也包括原有的一致性.

Windows 代码

总述

Windows 程序员有自己的编程习惯, 主要源于 Windows 头文件和其它 Microsoft 代码. 我们希望任何人都可以顺利读懂你的代码, 所以针对所有平台的 C++ 编程只给出一个单独的指南.

说明

如果你习惯使用 Windows 编码风格, 这儿有必要重申一下某些你可能会忘记的指南:

  • 不要使用匈牙利命名法 (比如把整型变量命名成 iNum). 使用 Google 命名约定, 包括对源文件使用 .cc 扩展名.
  • Windows 定义了很多原生类型的同义词 (YuleFox 注: 这一点, 我也很反感), 如 DWORD, HANDLE 等等. 在调用 Windows API 时这是完全可以接受甚至鼓励的. 即使如此, 还是尽量使用原有的 C++ 类型, 例如使用 const TCHAR* 而不是 LPCTSTR.
  • 使用 Microsoft Visual C++ 进行编译时, 将警告级别设置为 3 或更高, 并将所有警告(warnings)当作错误(errors)处理.
  • 不要使用 #pragma once; 而应该使用 Google 的头文件保护规则. 头文件保护的路径应该相对于项目根目录 (Yang.Y 注: 如 #ifndef SRC_DIR_BAR_H_, 参考#define 保护一节).
  • 除非万不得已, 不要使用任何非标准的扩展, 如 #pragma__declspec. 使用 __declspec(dllimport)__declspec(dllexport) 是允许的, 但必须通过宏来使用, 比如 DLLIMPORTDLLEXPORT, 这样其他人在分享使用这些代码时可以很容易地禁用这些扩展.

然而, 在 Windows 上仍然有一些我们偶尔需要违反的规则:

  • 通常我们禁止使用多重继承, 但在使用 COM 和 ATL/WTL 类时可以使用多重继承. 为了实现 COM 或 ATL/WTL 类/接口, 你可能不得不使用多重实现继承.
  • 虽然代码中不应该使用异常, 但是在 ATL 和部分 STL(包括 Visual C++ 的 STL) 中异常被广泛使用. 使用 ATL 时, 应定义 _ATL_NO_EXCEPTIONS 以禁用异常. 你需要研究一下是否能够禁用 STL 的异常, 如果无法禁用, 可以启用编译器异常. (注意这只是为了编译 STL, 自己的代码里仍然不应当包含异常处理).
  • 通常为了利用头文件预编译, 每个每个源文件的开头都会包含一个名为 StdAfx.hprecompile.h 的文件. 为了使代码方便与其他项目共享, 请避免显式包含此文件 (除了在 precompile.cc 中), 使用 /FI 编译器选项以自动包含该文件.
  • 资源头文件通常命名为 resource.h 且只包含宏, 这一文件不需要遵守本风格指南.

结束语

运用常识和判断力, 并且保持一致.

编辑代码时, 花点时间看看项目中的其它代码, 并熟悉其风格. 如果其它代码中 if 语句使用空格, 那么你也要使用. 如果其中的注释用星号 (*) 围成一个盒子状, 那么你同样要这么做.

风格指南的重点在于提供一个通用的编程规范, 这样大家可以把精力集中在实现内容而不是表现形式上. 我们展示的是一个总体的的风格规范, 但局部风格也很重要, 如果你在一个文件中新加的代码和原有代码风格相去甚远, 这就破坏了文件本身的整体美观, 也让打乱读者在阅读代码时的节奏, 所以要尽量避免.

好了, 关于编码风格写的够多了; 代码本身才更有趣. 尽情享受吧!

☑️ ⭐

向量

引言

本课程旨在围绕各类数据结构的设计与实现,揭示其中的规律原理与方法技巧;同时针对算法设计及其性能分析,使学生了解并掌握主要的套路与手段。本文将讲解数据结构向量及查找和排序。

抽象数据类型

接口与实现

向量属于最最基本的线性结构,我们笼统称之为线性序列。

本章我们将围绕这种数据结构展示和讨论两方面问题:

  1. 如何根据统一的接口规范来定制并实现一个数据结构
  2. 围绕这种数据结构展示如何通过更加有效的算法使得我们对外的接口能够更加高效率地工作:查找、排序

首先我们要辨析抽象数据类型和数据结构:

  • 抽象数据类型 = 数据模型 + 定义在该模型的一组操作
  • 数据结构 = 基于某种特定语言,实现 ADT 的一整套算法

更形象一点,我们可以将数据结构比喻成某种产品比如汽车。作为用户 Application 而言,他只关心这种产品的外在特性能够提供的功能;而实现者 Implementation 则需要对这些功能以及特性具体如何落实负责。

向量ADT

所谓向量,实际上是 C++ 等高级编程语言中数组这种数据组织形式的一个推广和泛化。

循秩访问

在这些高级程序设计语言中所谓的数组实际上就是一段连续的内存空间,它被均匀地划分为若干个单元,而每一个单元都会与一个编号彼此回应,并且可以直接访问。

而向量可以被认为是数组的抽象与泛化,它同样是由一组抽象的元素按照刚才的线性次序封装而成。不同的是原来通过下标 i 的访问方式变成了秩 rank。

另外向量中元素的类型得到了拓展,不限于是某一种特定的基本类型,它的所有操作、管理维护更加简化,可以通过统一的接口来完成。

向量ADT接口

可以通过这些操作接口对向量做各种操作,同时也只能通过这些操作接口对向量进行操作。

接口操作实例

构造与析构

#ifndef SRC_VECTOR_H
#define SRC_VECTOR_H

#define DEFAULT_CAPACITY 3 // 默认初始容量

namespace Vector {
using Rank = int; // 秩

template<typename T> class Vector {
protected:
T* _elem; // 数据
Rank _size; // 规模
Rank _capacity; // 容量

void expand(); // 空间不足扩容
void shrink(); // 装填过小压缩
void copyFrom(T const* A, Rank lo, Rank hi); // 复制数组区间

Rank maxItem(Rank lo, Rank hi); // 选取最大元素
Rank partition(Rank lo, Rank hi); // 轴点构造算法

void selectionSort(Rank lo, Rank hi); // 选择排序

bool bubble(Rank lo, Rank hi); // 扫描交换
void bubbleSort(Rank lo, Rank hi); // 起泡排序

void merge(Rank lo, Rank mid, Rank hi); // 归并算法
void mergeSort(Rank lo, Rank hi); // 归并排序

void heapSort(Rank lo, Rank hi); // 堆排序
void quickSort(Rank lo, Rank hi); // 快速排序
void shellSort(Rank lo, Rank hi); // 希尔排序

public:
/* 构造函数 */
Vector(int c = DEFAULT_CAPACITY, Rank s = 0, T v = 0) {
_elem = new T[_capacity = c];
for (_size = 0; _size < s; ++_size)
_elem[_size] = v;
}

Vector(T const* A, Rank n) { copyFrom(A, 0, n); }
Vector(T const* A, Rank lo, Rank hi) { copyFrom(A, lo, hi); }
Vector(Vector<T> const& V) { copyFrom(V._elem, 0, V._size); }
Vector(Vector<T> const& V, Rank lo, Rank hi) { copyFrom(V._elem, lo, hi); }

/* 析构函数 */
~Vector() { delete[] _elem; }

/* 只读接口 */
Rank size() const { return _size; } // 规模
bool empty() const { return !_size; } // 判空

Rank find(T const& e) const { return find(e, 0, _size); } // 无序向量整体查找
Rank find(T const& e, Rank lo, Rank hi); // 无序向量区间查找

Rank search(T const& e) const { // 有序向量整体查找
return (_size <= 0)? -1: search(e, 0, _size);
}
Rank search(T const& e, Rank lo, Rank hi) const; // 有序向量区间查找

/* 可写接口 */
T& operator[] (Rank r); // 重载下标操作符
const T& operator[] (Rank r) const;
Vector<T>& operator= (Vector<T> const&); // 重载赋值操作符

T remove(Rank r); // 删除单一元素
int remove(Rank lo, Rank hi); // 删除区间元素

Rank insert(Rank r, T const& e); // 插入元素
Rank insert(T const& e) { return insert(_size, e); } // 插入末元素

void sort(Rank lo, Rank hi); // 区间排序
void sort() { sort(0, _size); } // 整体排序

void unsort(Rank lo, Rank hi); // 区间置乱
void unsort() { unsort(0, _size); } // 整体置乱

/* 遍历接口 */
void traverse(void(*) (T&)); // 函数指针遍历
template<typename VST> void traverse(VST&); // 函数对象遍历
};
}

#endif //SRC_VECTOR_H

整个 Vector 被封装起来,来自各种用户 application 的操作接口 interface 提供在外面,相当于一个 Vector 结构的使用说明书。

/* 构造函数 */
Vector(int c = DEFAULT_CAPACITY, Rank s = 0, T v = 0) {
_elem = new T[_capacity = c];
for (_size = 0; _size < s; ++_size)
_elem[_size] = v;
}

Vector(T const* A, Rank n) { copyFrom(A, 0, n); }
Vector(T const* A, Rank lo, Rank hi) { copyFrom(A, lo, hi); }
Vector(Vector<T> const& V) { copyFrom(V._elem, 0, V._size); }
Vector(Vector<T> const& V, Rank lo, Rank hi) { copyFrom(V._elem, lo, hi); }

/* 析构函数 */
~Vector() { delete[] _elem; }

复制

template <typename T>
void Vector<T>::copyFrom(const T *A, Rank lo, Rank hi) {
_elem = new T[_capacity = 2*(hi - lo)];
_size = 0;

while (lo < hi)
_elem[_size++] = A[lo++];
}

复制操作将 _elem 空间扩展为原来的二倍,然后将区间元素依次复制。

可扩充向量

可扩充向量

现在我们用 _size 表示实际规模,_capacity 表示总容量。

T* _elem;           // 数据
Rank _size; // 规模
Rank _capacity; // 容量

这里的问题是 _capacity 一旦确定按照目前的方案它就将一成不变,而这样一种策略显然存在明显的不足。这种不足体现在两个方面:

  • 上溢(overflow):_elem[] 不足以存放所有元素,尽管此时系统仍有足够的空间
  • 下溢(underflow):_elem[] 中的元素寥寥无几,装填因子 = _size/_capacity << 50%

动态空间管理

我们需要从静态管理策略改编为动态管理策略,模仿蝉的做法在即将发生上溢时适当地扩大内部数组容量。

向量的生命周期:

  • (a) 最开始虽然元素很多但不至于出现上溢的情况
  • (b) 但剩余空间有可能会逐步地占用,在某一时刻内部数组饱和
  • (c) 模仿蝉退掉外壳,动态申请另一个外壳:另一段存放空间,它的大小应该比原来的有所增长
  • (d) 把原先存放好的有效元素逐一按次序复制过来,使得它们对外界而言依旧保持原貌
  • (e) 新多出的空间足以存放新需要插入的元素,原来占用的空间在此之后被释放并且归还给系统

template <typename T>
void Vector<T>::expand() {
if (_size < _capacity) return;
_capacity = std::max(_capacity, DEFAULT_CAPACITY);

T* oldElem = _elem;
_elem = new T[_capacity <<= 1];

for (int i = 0; i < _size; ++i)
_elem[i] = oldElem[i];
delete[] oldElem;
}

得益于向量的封装,尽管扩容之后数据区的物理地址有所改变,却不致出现野指针。

递增式扩容

每当发现当前的内部数组即将发生上溢,我们并不是对它进行容量的加倍而只是在原来的容量的基础上追加一个固定的数额:

T* oldElem = _elem;
_elem = new T[_capacity += INCREMENT];

对于这种策略而言,每经过 I 次插入操作它都需要进行一次扩容,每次分摊成本为 O(n)。

加倍式扩容

T* oldElem = _elem;
_elem = new T[_capacity <<= 1];

每次的分摊成本为 O(1) 常数时间。

倍增策略通过在空间的效率上做了一个适当的牺牲换取在时间方面的巨大收益。

无序向量

循秩访问

首先讨论向量元素的访问。表面上看这并不是什么问题,因为在向量 ADT 中已经定义了两个标准的接口 V.get(r)V.put(r, e)。通过它们我们已经可以自如地来写或者是读向量中特定的元素,但这两种接口在形式上还不是那么简洁直观。

我们期望数组那种直接地访问方式:A[r],为此需要重载下标操作符 []

template <typename T>
T& Vector<T>::operator[](Rank r) const { return _elem[r]; }

插入

再来考察向量的插入算法,如何讲某一个特定的元素插入到向量的特定位置。

因为原有向量所有元素都是紧邻排列的,所以为了能够插入新的元素我们需要将对应位置之后的所有元素称作它的后继,进行一个整体的右移操作。

template <typename T>
Rank Vector<T>::insert(Rank r, T const& e) {
expand();
for (int i = _size; i > r; --i)
_elem[i] = _elem[i - 1];

_elem[r] = e;
_size++;

return r;
}

区间删除

template <typename T>
int Vector<T>::remove(Rank lo, Rank hi) {
if (lo == hi) return 0;

while(hi < _size)
_elem[lo++] = _elem[hi++];

shrink();
return hi - lo;
}

单元素删除

template <typename T>
T Vector<T>::remove(Rank r) {
T e = _elem[r];
remove(r, r + 1);
return e;
}

查找

无序向量只支持判等操作,有序向量还需要支持其中的元素相互比较大小。

template <typename T>
Rank Vector<T>::find(T const& e, Rank lo, Rank hi) {
while ((lo < hi--) && (_elem[hi] != e));
return hi;
}

hi 出发逆向逐一取出向量中的各个元素,与目标元素进行比对。如果不相等,就忽略它并且考察它的前驱,整个工作会遍历向量中的所有元素。

去重/唯一化

向量的唯一化需要把其中重复的元素都剔除掉,只保留一个拷贝。

template <typename T>
int Vector<T>::deduplicate() {
int oldSize = _size;
Rank i = 1;
while (i < _size) {
(find(_elem[i], 0, i) < 0)?
i++:
remove(i);
}

return oldSize - _size;
}

遍历

template <typename T>
void Vector<T>::traverse(void (*visit) (T&)) {
for (int i = 0; i < _size; ++i)
visit(_elem[i]);
}

template <typename T> template <typename VST>
void Vector<T>::traverse(VST& visit) {
for (int i = 0; i < _size; ++i)
visit(_elem[i]);
}
  • 利用函数指针机制,只读或局部性修改
  • 利用函数对象机制,可全局性修改

template <typename T>
struct Increase {
virtual void operator()(T& e) { e++; }
}

......

template <typename T>
void increase(Vector<T>& V) {
v.traverse(Increase<T>());
}

有序向量

唯一化

与起泡排序算法的理解相同,有序/无序序列中,任意/总有一对相邻元素顺序/逆序

因此,相邻逆序对的数目,可用以度量向量的逆序程度。

template <typename T>
int Vector<T>::disordered() const {
int n = 0;
for (int i = 1; i < _size; i++)
n += (_elem[i - 1] > _e);
return n;
}

二分查找

Fib查找

插值查找

起泡排序

归并排序

位图

☑️ ☆

Convex Hull

引言

本节我们将探索计算几何的核心问题:凸包问题。计算几何领域几乎所有的问题都可以“归约”为凸包问题,因此学习凸包问题对整个计算几何体系至关重要。

Convexity

Why Convex Hull

我们计算几何的第一站就是凸包问题,它在计算几何中处于核心位置,这个核心体现在几乎所有的问题从理论上讲都可以归结为凸包问题。

Nails In The Table

接下来我们通过一个具体的动手实验领会一下凸包到底是什么。

为此你需要找到一张桌子或是屏幕,假想在这个桌子上钉上一系列的钉子,然后用皮筋将其撑到足够大以至于它能将桌面上的所有钉子都包含进去。

接下来的事情非常的轻松,你只要松手就行。那么随着啪的一声,你将会看到这幅图景:

刚才的皮筋就会变成这样一段一段蓝色的线段,它们首尾相连构成了一个紧绷的包围圈。这个蓝色的橡皮筋在在现在这样的一个图景状态就是我们所说的凸包,我们可以看到所谓的凸包是由这上面若干个钉子来决定的,虽然其中有一些钉子并不发挥作用,我们大致可以感觉到因为它们呆在内部。

那么,这之间的玄机又是什么呢?

Paint Blending

为了更好地理解什么是凸包,我们再来看一个应用的例子。

艺术家经常要通过混合得到某种他想要又不是从工厂直接生产出来的颜料。我们知道一般来说每种颜料都可以分成是红绿蓝三个分量的数值指标,每种组合对应的大致都是一种颜料。

我们不妨为了简便起见只考虑红的以及绿的两个分量,所以这样的话每一种颜料也就是它所对应的颜色都可以用红的和绿的这样两个数字,或者说它们在整体的成份中所占的百分比来对应。

C = (R, G)

比如说某种颜料 X 它所对应的红的分量可能是 10%,而绿的分量是 35%;另一种颜料比如叫 Y,那么它所对应的这两个分量一个是 16% 一个是 20%。 现在的问题来了,用这两种颜料能否兑出我们所希望的某些颜料呢?

X = (10%, 35%)  Y = (16%, 20%)

我们来看一下,当颜料混合在一块的时候它们的变化是多端的,有很多很多种组合,每几种颜料它们按照不同的分量、按照不同的比重勾兑在一块所得到的颜色其实都会不同。当然,艺术家有他的勾兑的方法,包括他的灵感,那么如果从数学的角度,从算法的角度来考虑,这其中应该用什么样的指导的方法呢?

那么从数学上来看我们一般来说都可以认为有一个目标的颜色,比如说这里的 U,这种颜色比如说特定的来说他希望红的占的比重是 12%,而绿的比重是 30%。

U = (12%, 30%)

对于这样的一种目标的颜料我们应该用刚才的 X、Y,这两种来自于工厂的原始颜料用什么样的比例来对它们进行混合和勾兑呢?

好,我想你已经知道这个答案了。没错 我们应该用两份的 X 和一份的 Y 勾兑起来,就可以得到 U 了。

你不妨去做个简单的验算,两份的 10% 再加上一份*的 16% 合在一块再除以 3,正好是 12%;而两份的 35%,再加上一份的 20% 也同样的除以 3 恰好也是 30%,所以用 2 比 1 的比例是这个问题的一个解。

好,如果说我们为此花费这些时间还是值得的话,我们还是希望得到一个方法,否则的话我们会很困惑,因为如果你没有掌握这背后的、统一的方法的话,那么如果下一次换一种颜色比如说这里的 V 它要求的是 13% 和 22%,那你可能又要花费一些时间了。

V = (13%, 22%)

那么首先一个问题是这种颜料能不能勾兑出来。并不是像我们这里所说的那样,每两种颜色给定了以后你都能勾兑出所有的颜色。其实在这个时候我们或许需要第三种颜色,比如这里我们也许从厂房里可以拿到第三种颜色 Z,它的对应的比重是 7% 和 15%。

Z = (07%, 15%)

好了,这个时候用这三种颜色是否能把它勾兑出来呢?

好,现在我来揭晓答案。正确的比例应该是一份的 X,三份的 Y 再加上刚才我们新添的第三种颜色 Z 一份 1 比 3 比 1。你可以按照刚才同样的方法去推算一下 验算一下,我想答案应该是它。

那么所有这里讨论的事情其实都是颜色,或者准确地讲是颜料之间的那种勾兑混合。这个东西和我们这里讨论的计算几何有什么关系呢?其实它们之间有着非常深刻的联系。

Color Space

既然谈到几何,那么少不了就要谈到它最最基础的一个概念叫做空间,欧氏空间。

在这里我们将欧氏空间对应于颜色,我们称之为颜色空间,具体来讲我们要将每一种颜色都对应成是这个空间中的一个点。无论这种颜色或者颜料是来自于生产厂家直接供应的那种基础性的颜料,还是艺术家为了创作的需要必须重新勾兑出来的新的颜色。总而言之每一种颜色都对应这个空间中的一个点。

当然这里因为我们讨论的都是正数,那可以认为它基本上都限于第一个象限,这不是主要的问题。那么现在的问题是在于我们固然可以按照这种方法将我们刚才的三种颜料也就是 X、Y、Z 按照横轴也就是刚才比如红色的分量数值以及纵轴,也就是刚才说的绿色的分量的数值对应地画出一个一个的点,三种颜料,分别是三种点。

我们刚才看到过,在我们只有 X 和 Y 两种颜料的时候如果我们要勾兑出 U,那个比重是 2 比 1。其实这件事情倒过来,我们在给出了固定的 X 和 Y 之后我可以将我们目标的那个 U 也在这个屏幕上画出来,如果你画出来的话你就会发现其实非常地巧,我们可以验证一下它们三者是所谓共线的。

如果是这种情况,那么我们认为 U 肯定是能被勾兑出来的,而且它的勾兑比例可以从几何上一目了然的能解释。

你可以再去计算一下,我会告诉你其实 U 到 X 的距离相对更短,U 到 Y 的距离相对更长,而二者的距离之比其实是 1 比 2,而我们刚才勾兑的比例是反过来的 2 比 1。

其实这就是一个规律,也就是说如果我要勾兑的一种颜色恰好是位于这两个顶点的那条连接的线段上,而且它们的距离存在一个比的话,那么这种颜色就必然能够被勾兑出来。而且勾兑的方法就蕴含在刚才的那个比例中,只要把刚才那个距离比 1 比 2 颠倒过来变成 2 比 1,它就必然能得到这种颜色。

你可以作为一个极端的例子去想一下,整个的是如果要勾兑 Y 和勾兑 X 本身的时候另一个分量是 0 是同样的道理。

好,那么刚才我们也可以解释为什么 V 这种颜色必须要借助第三种颜色才能够勾兑出来。因为你大致可以看出来因为 V 并没有位于 X 和 Y 所确定的这条线段上跑偏了,在这种情况下我们说必然要借助 Z,而之所以要借助 Z 或者说准确地讲按照我们刚才那个比例必须是 1 比 3 比 1 也蕴含在这个图中,原理是一样的。

如果在这种情况下我们要做的事情就是要首先确认 V 这个颜料所对应的那个点是不是落在 X、Y、Z 所定义的这个三角形的内部,如果是它就一定能勾兑出来;如果不是,至少它是不能勾兑出来的。

好,如果它能勾兑出来,具体的勾兑的比例是多少呢?在这个图中也给出来了,为此我们只需要去量一下 V 到这三个点的距离,然后找一下它们的比。我们在这里会发现它们的比恰好是 3 比 3 比 1,所以倒过来在这里我们勾兑的比例自然也就是这个最短的最近的这个点对应的那个颜色要取的更多,反其道而行之它要取三份;而到更远的那两个点所对应的颜色所取的比例要更少,完全可以用这个来度量

当然以上的这些结论你还需要在课后再做仔细的推导和严格的验证,在这里你不妨把这个结论记下来:也就是说如果有一种颜料能够被两种已知的颜料勾兑出来,它必然位于二者之间的那条连线上;如果是对于三种颜料的情况,那么某种目标的颜色能够被勾兑出来当且仅当在颜色空间中它位于这三个点所对应的那个三角形的内部,而勾兑的比例是与他们的距离成反比的。

Convex Hull

我们虽然不是很喜欢数学,但是不得不还要用一些简单的数学把刚才我们所看到的那个结论严格地表述出来。

也就是说我们如果给定的是平面二维空间中的一系列的点的话,那么这些点所对应的颜料能构造出哪些新的颜料出来呢?我们会发现其实每一种新的颜料从几何来讲,对应于原来那些颜料的某一个调和方案。

那么在这里有一些勾兑方案专门地称之为凸的勾兑方案,或者叫作凸组合 Convex Combination。具体而言,如果是一个凸组合需要有哪些条件呢?

我们说大致有两个主要的条件:

  1. 所有分量的总和必须是 100%
  2. 所有分量必须是非负的

Extreme Points

Extremity

在我们最开始给定的这些点中,哪些是最终对凸包有贡献的被皮筋绷住的,哪些是没有实质作用的,这种性质可以归纳为所谓的极性。

沿着刚才的那个思路,我们观察结论可以表述为这样的一幅图。我们看到在刚才的所有那些钉子中凡事被最终的皮筋绷住的钉子,暂时没有实质作用的这些钉子我们都用青色来表示,有什么本质不同呢?

if there exists a line L through p
such that
all points of S lie on the same side of L

数学上的观察告诉我们,所谓有用的点都有一个共同的特点:经过它们我们总能找到一条直线使得所有的点都落在这条直线的同一侧。

Strategy

在排序算法中有一个非常有意思的算法:起泡排序 Bubblesort。我们这里的算法设计和它是非常类似的:

如何甄别极点和非极点呢?

我们需要回忆颜料勾兑的例子,一种颜料能够被其他几种颜料勾兑出来当且仅当它落在某一个三角形的内部。反过来像极点这样不能被其他颜料勾兑出来的颜色它就不可能被包含于任何三角形的内部,这样的话我们又往前转化了一步,将我们的甄别任务转化为某一个点是否会被包含于另外的三个点所确定的三角形内部。

In-Triangle Test

根据刚才的分析,所谓凸包问题可以归结为一系列的判断:任何的一个点是否会落在其他的三个点所对应的三角形内部被它们包围,我们称这个为 In-Triangle Test。

基于 In-Triangle Test,我们就可以将非极点们一个一个地找出来并且将它们排除在我们的视野之外。

首先做初始化,要像无罪推论一样将所有的点都设定为极点。接着枚举出所有可能的三角形,对于每个三角形我们还要去考察除它们之外的每一个点 s;一旦我们发现 s 的确是落在当前这个三角形内部,我们就可以立即断定它不是一个极点,从而将它排除在外。

Make all points of S as EXTREME
For each triangle Δ(p, q, r)
For each s in S\{p, q, r}
If s in Δ(p, q, r)
mark s as NON_EXTREME

void extremePoint(Point S[], int n) {
for (int s = 0; s < n; s++)
S[s].extreme = TRUE;

// For each triangle
for (int p = 0; p < n; p++) {
for (int q = p + 1; q < n; q++) {
for (int r = q + 1; r < n; r++) {
// For each point
for (int s = 0; s < n; s++) {
if (s == p || s == q || s == r || !S[s].extreme)
continue;

if (InTriangle(S[p], S[q], S[r], S[s]))
S[s].extreme = FALSE;
}
}
}
}

}

To-Left Test

我们给出的第一个基于极点的凸包算法虽然效率低下,但是它的意义还是很重要的,它会引出 To-Left Test,后面这个测试几乎是贯穿于我们计算几何这个课程的始终。

每当我们给定了一个点以及一个三角形后,如何来判定这个点是否落在这个三角形的内部?

依然是大事化小小事化了,我们将刚才这个 In-Triangle Test 转化为三次 To-Left Test。也就是说一个点如果确实落在某一个三角形的内部的话,那么相对于这个三角形的三条边所做的 To-Left Test 都会统一的返回 true。

所谓 To-Left Test,就是说这个点相对于有向线段而言位于左侧还是右侧。这里的敏锐观察可以归结为一个点如果落在三角形内部,它的充要条件当且仅当它相对于这三条直线的 To-Left Test 都是 true,它同时位于这三条直线的左侧。

那么现在问题转变为如何判断一个点在线段的左侧/右侧?

Determinant

bool ToLeft(Point p, Point q, Point s)
return Area(p, q, s) > 0;

int Area2(Point p, Point q, Point s)
return p.x * q.y - p.y * q.x
+ q.x * s.y - q.y * s.x
+ s.x * p.y - s.y * p.x;

Extreme Edges

Definition

延续极点的思路推广到边,引入所谓的极边。

极边的候选者其实就是来自于任何两个相邻极点的连边,凡是对最终的凸包有贡献的那些边都称之为极边;凡是那些对凸包没有贡献的就不是极边,或者叫作非极边,non-extreme Edge。

就像我们定义极点一样,如果有一条这样的连边确实是极边的话,那么所有的点都会同时落在它的同侧,相应的另一侧就必然是空的。更具体来讲,以逆时针次序凸包边界每一条边都有这样一个特性:所有的点都恰好落在它的左侧,它们的右侧都是空的。

这样我们算法中的实质问题就自然地转化和具体化为如何来甄别任何两个点之间的那条连边是否为极边的问题。

Algorithm

Let EE = null
For each directed segment pq
If points in S\{p, q} lie to the same side of pq
Let {pq} = EE

按照极边的思路,我们可以将伪代码细化为这样一段真实的代码:

void markEE(Point S[], int n) {
for (int k = 0; k < n; k++)
S[k].extreme = FALSE;

for (int p = 0; p < n; p++)
for (int q = p + 1; q < n; q++)
checkEdge(S, n, p, q);
}

void checkEdge() {
bool LEmpty = TRUE, REmpty = TRUE;
for (int k = 0; k < n && (LEmpty || REmpty); k++) {
if (k != p && k != q) {
ToLeft(S[p], S[q], S[k])? LEmpty = FALSE: REmpty = FALSE;
}
}

if (LEmpty || REmpty)
S[p].extreme = S[q].extreme = TRUE;
}

Incremental Construction

Decrease and Conquer

接下来我们将从一个典型的算法思想减而治之 Decrease and Conquer 进一步改进。

一个经典的应该能回忆起来的算法就是插入排序 Insertionsort。插入排序整个思路可以归纳为将整个待排序序列存成线性结构,接下来在任何时候都将它分为排序和未排序两部分,在未排序部分随机找出一个(一般是两者分界的那个元素),通过一次查找在 sorted 子序列中找到这个元素对应的恰当插入位置。

同理,我们也可以应用于极边算法。

In-Convex-Polygon Test

递进式的核心技术是 In-Convex-Polygon Test,也就是判别多边形内部或者外部的问题。

我们要判断一个新引入的点是否是当前的极点,其实本质上就是判断当前这个点是否落在此前的凸包的外面或者是里面的位置关系。

要将刚才那种直觉转化成数学上的判断:每次我们递增式新引入的这个点如果是当前的 extreme point 的话,那么充要条件其实就是看它是否落在当前这个凸包的外面:如果落在外面那它就是下一个 extreme point;否则不是。

如果凸多边形确实是给定的,而且在此后要反复多次地做这类的查询的话,你是可以对这个多边形做一个预处理(本质上是排序)。

我们可以大致以一个点作为基础,在其余的 n - 1 个点中可以找到一个居中的连接起来确定一条有向线段。接下来又是我们刚才的惯用的 To-Left Test,经过这样一次常数成本的操作,我们确实可以判断出来这个未知的点到底是落在左边或者是右边,无论是哪边我们都可以将搜索的范围有效地收缩为原先的一半。

如此往复,我们每一次经过常数时间的成本都可以将这个问题的范围有效地降解为此前的一半,如此下去最终总会到达平凡的情况–trivial case:In-Triangle Test。

但是这个算法却不可行,最重要的是凸包并不是一成不变的,这种情况下我们的预处理是没有效力的。

Why Not Binary Search

与插入排序类似,sorted 部分本身就是动态的,即便可以使用二分查找,线性存储所带来的插入成本在最坏情况也会将这种优化无效化。

回到凸包,对于这种情况朴素的方法反而是最好的。我们可以沿着给定的凸多边形边界做习惯性的 CCW 逆时针旋转遍历,可以发现内部的点一定是在左手一侧的;反之如果我们在任何一段发现某一个点在右侧,那么可以立即断定它并非落在内部。

Support-Lines

其实我们还有一个任务要完成,解决如何将新引入的这个点附着或者是增加到原先的凸包上去,要使之成为一个完整的可以继续使用的结构。

凸包切线又被称为 Support Line。

Pattern Of Turns

只需要花费两次 To-Left Test,就可以明确确定一个顶点到底是来自 ts(L + R) 还是 st(R + L)。

Exterior/Interior

Jarvis March

Selectionsort

在介绍 GW 算法之前为了更好地理解它的算法思路,不妨温习一下之前我们很熟悉的选择排序。

与刚才的插入排序非常对称,在这里我们的 sorted 和 unsorted 部分是前后颠倒了,这个颠倒实际上是有本质区别的。

我们需要从 unsorted 部分中去找出一个最大的元素,接着将它进行一次交换挪到刚才 sorted 那个部分的首部。悄然之间,sorted 部分就向前迈进了一步。

那么这样一个算法思路从宏观的策略来讲我们可以概括为:每次我们都是维护一个局部的解,然后在尚未处理的部分中要去找到一个与当前的这个局部解紧密相关联的一个元素。没错,凸包就可以这么来做。

Strategy

我们如果反思一下在 Extreme Edge 那个算法中为什么会需要多达 n^3 的时间,就会发现根本的原因在于我们实际上考察的对象是遍布所有可能的那些边,这些边的总数会多达 n^2,每个又需要 n 时间鉴别。那么有什么改进的诀窍呢?

刚才的 selectionsort 就给了我们提示,也就是说我们或许能够将下一个的查找范围缩小到一个足够小的范围。

Jarvis 观察注意到一些结论:

  1. 所有构成凸包的那些边其实在拓扑上讲都是首尾相连构成一个环状结构的
  2. 如果构造过程确实是一条一条边构造,那么如果我在某一个时刻构造出一条边,那么接下来我必然可以沿着它的某一个端点向后继续去找到下一条 extreme edge

Coherence

该图可以说明如何在当前已有的这些极边基础上沿着下一个端点拓展出新的极边:

当前节点称作 k,它的前驱我们称之为 i,下一个极边则是 s。根据刚才 Jarvis 的判断,这个 s 必然来自于其他尚未处理的那些点中的一员。

s 之所以可以脱颖而出,其资本在于它是所有这些拐角中的最小者。也许有同学已经跃跃欲试准备用三角函数和反三角函数操作了,但其实有一种基本的技术就可以解决我们的问题。

To-Left Test

Lowest-Then-Leftmost

一个技术细节问题,也就是我们刚才说到的起点和第一条极边应该如何来找呢?

作为第一个点,它至少是极点。在这里针对于我们目前的算法需求,可以对问题进一步简化,也就是找到沿着 y 轴负方向最低的位置。这个点也就是所谓的 Lowest Point,在没有退化的情况下必然是 extreme point,所以我们可以以它为起点。

如果出现多个最低点的退化情况,则优先选择最左侧的点,也称为 Lowest-Then-Leftmost point。

Implementation

void Jarvis(Point S[], int n) {
for (int k = 0; k < n; k++)
S[k].extreme = FALSE

int ltl = LTL(S, n);
int k = ltl;

// start with LTL
do {
P[k].extreme = TRUE;
int s = -1;

for (int t = 0; t < n; t++)
if (t != k && t != s && (s == -1 || !ToLeft(P[k], P[s], P[t])))
s = t;
P[k].succ = s;
k = s;
} while(ltl != k)
}

初始化所有点都被视为非极点,接下来找到刚才所说的 Lowest-Then-Leftmost point 并且把它作为我们的第一个点 k 进入下面一个迭代循环。

每一个点当它进入这个循环的时候必为极点,第一个点如此,后面的点也一样。接下来我们则要找 s 是逐渐优化最终找到的极点,任何时候我们都未必知道它就是,需要遍历所有候选 t

t 通过 To-Left 测试时什么都不处理,s 依然为候选者;反过来 To-Left 测试失败意味着出现在右侧,需要更迭 st

int LTL(Point S[], int n) {
int ltl = 0;
for (int k = 1; k < n; k++)
if (P[k].y < P[ltl].y || (P[k].y == P[ltl].y && P[k].x < P[ltl].x))
ltl = k;
return ltl;
}

Output Sensitivity

Lower Bound

Reduction

在前面几节里我们围绕凸包的计算问题给了一系列的算法,从最开始的 n^4 极点算法一直到后面 n^3 极边的算法,再到 Jarvis march 以及 Incremental n^2,我们在沿着一条不断递减的路线在降低这个算法的复杂度。

但是如果计算模型是固定的话,必然有一个我们所说的 Low Bound 的概念:下界,也就是复杂度再低也不会低于某一个极限。

CAO Chong’s Methodology

三国中曹操的儿子曹冲有个很著名的故事:曹冲称象。

我们需要度量一个东西的难度,曹冲是要称出一头象的重量,他去找中间参照物石头,通过石头的重量估算出象的重量,而 Reduction 关系就是曹冲的船和水。

Transitivity

那么为什么这个问题可以像曹冲称象一样能够间接通过 A 问题的难度就得到 B 问题的难度呢?

对于 A 问题的任何一个输入,我们都可以曲径通幽式的先把它转化为 B 问题的输入,接下来调用 B 问题的任意算法得到输出,再转化为 A 的输出。

如果 A 问题确实存在某一个下界,而且这个下界是严格大于 n 的,那么我们说 B 问题的所有算法都不可能低于这个复杂度下界。

Reduction: Input

首先要把我们未知的那个问题(也就是那头象)摆在右边,这里我们考虑二维的凸包 2-dimensional convex hull 这个问题。

而石头则是 Sorting。也许初看这个问题可能会很迷茫,排序这个问题和凸包这个问题一个是纯粹的抽象计算问题,一个是具体的几何计算问题,二者之间怎么会有联系呢?

  1. 证明可以在线性时间内将排序问题的任何一个输入转化为凸包问题的输入
  2. 证明凸包问题的结果线性时间内转换回到排序问题

排序问题的输入可以理解为在数轴或者平面上 x 轴一系列的点,在图中我们只取了四个点。为了转换为凸包问题我们需要辅助线,以抛物线作为标尺将每一个点做提升变换,将 n 个数字转化为平面上的 n 个点。

Reduction: Output

来自抛物线上有线个点的凸包都具有这样的一个特性:最左侧的那个点和最右侧的那个点会在上面连上一条纵跨的一条单调直线。

这样我们就完成了 Reduction 的第二步:将凸包问题转化为排序问题。输入是无序的,输出是有序的,这正是排序算法的要求。

(注:这里有一个疑惑就是如果是正五边形,那么这个左右边界又该如何去界定呢?边界的连线并不单调。)

Sorting <=N 2d-CH

所以排序算法的下界是 nlogn,那么凸包问题也是如此,成为 Convex Hull 的下界。

Graham Scan: Algorithm

Preprocessing

那么我们来看一个下界意义上讲最优的算法:Graham Scan。

Graham Scan 首先要做的一件事情是一个预处理,一个排序。这个 presorting 其实就是要找到某一个特定的点,并且将其余所有的点按照这个点所对应的极坐标按极角来做一个排序。

那么具体的这样第一个点应该找谁呢?

其实任何一个极点理论上都是可以的,同样为了简化算法的解释和实现,我们不妨依然采用前面所讲过的 Lowest-then-Leftmost point 为 1 号点。

接下来会有与 1 号成角度最小的 2 号点,这里不妨假设 1、2 号点为同一高度,并且没有三点共线的情况,接着按照 (1, 2) 极轴的夹角从小到大命名其他点。

Graham Scan 算法的数据结构也很简单,只需要两个栈 T 和 S。初始化时依次将 1、2 入栈 S 中,其他 n-2 个点自顶到底存入 T 栈。

而排序可以选用任意排序,只是对象变成了点,而比较器变为 To-Left Test。

Scan

这个扫描过程中要关注三个东西:S 栈栈顶以及次栈顶、T 栈栈顶,我们可以用 S[0]S[1]T[0] 表示。

while(!T.empty()) {
// test type of current turn
toLeft(S[0], S[1], T[0])?
// step forward at a left turn
S.push(T.pop()):
// or, backtrack
S.pop();
}

Graham Scan: Correctness

Left Turn

Right Turn

9 号点被包含在了某一个三角形(1-8-10)的内部,它应该被排除掉。

Graham Scan: Analysis

Backtracks

Planarity

根据欧拉公式,平面图中所有边的数量包括面数加在一起依然和顶点数目保持同阶,边数不会超过顶点数的三倍。

Amortization

  if: S.size()++; T.size()--;   //  1 - 2
else: S.size()++; // -1 + 0

Divide-And-Conquer (1)

Merge

归并排序作为引子引出我们的算法。

Divide-And-Conquer 要求我们接近均匀切分 divide,接着我们把这些结果合并起来成为有序序列,变成最终结果。

凸包问题也是如此,把输入的点集分成大小规模接近的子集分别求出它们的凸包。问题实质就变成了我有两个凸包子集之后如何将它们合并得到更大的凸包。

Common Kernel

找到一个公共核使得这两个待合并的子凸包能够同时关于这个点是角度有序的。

Interior

二路归并采用环形次序,然后 Graham Scan 即可。

Exterior

我们预选的那个来自第一个子凸包的 centroid point 不幸落在第二个子凸包的外面,在这种情况下我们应当如何完成二者的归并呢?

Divide-And-Conquer (2)

Preprocessing

不妨做一个假设,待合并的两个子凸包或者说它们对应的点集是沿着某个方向是可分割的,彼此独立。如果这样我们的合并任务就会变得更加简明、简单。

为了保证这一点,我们引入一个预处理:按 x 轴排序。

Common Tangents

Topmost + Bottommost?

Stitch

我们可以在最初构造一个子凸包的时候记下 leftmost 和 rightmost 各是哪两个顶点,剩下几乎不用花时间:把此前计算结果延续下来即可,而分摊到每一次合并常数时间就够了。

Zig-Zag

☑️ ☆

Introduction

引言

计算几何的重要之处在于它是多门技术与学科的基础,例如图形学、CAD、GIS、路径规划等。这些技术的背后原理往往是基于计算几何的本质上。所以该门课程的学习对养成计算几何理论的总体认识很有帮助,这种认识将为学习者日后的研究工作提供几何的视角。

What can we learn from this course?

  • Awareness of Computational Geometry theory that will help students incorporate Computational Geometry into their future research
  • Comprehensive understanding on fundamental paradigms/strategies for solving geometric problems, incremental construction, plane sweeping
  • Essential geometric structures and algorithms such as polygon decompositions, Voronoi diagrams, Delaunay triangulations

本课程的教学目标有三:

  • 对计算几何理论的总体认识,在日后的研究工作中,这种认识为你提供几何的视角
  • 对几何问题求解范式及策略的全面领会,包括递增式构造、平面扫描、分而治之、分层化、近似以及随机化等
  • 对基本几何结构及其算法的透彻掌握,包括凸包、多边形细分、Voronoi图、Delaunay三角剖分,以及几何求交、点定位、范围查找、截窗查询等

Are you qualified for learning Computational Geometry?

Computational Geometry requires some skills of algorithm design and analysis as well as programming, but you don’t need to be an expert before learning this course. Actually, C/C++ programming experience and some basic knowledge of common data structures will be enough. To make sure whether you are qualified for learning this course, check the list below:

  • C/C++ programming: variable, function, struct, class;
  • Algorithm design and analysis: complexity, amortized analysis, recursion, divide and conquer, linked list, binary search tree, priority queue.

计算几何这门课对数据结构和算法基础和编程基础有一定的要求,但这并不意味着你需要精通所有相关课程。实际上,你只需掌握一些常见数据结构,拥有一定的算法分析能力,以及C/C++语言编程的基本技巧。为确认自己是否适宜选修这门课程,不妨对照以下清单做一清点:

  • C/C++语言程序设计基础:变量,函数,结构体,类
  • 数据结构与算法分析:复杂度、摊还分析、递归、分治法、链表、栈、二叉搜索树、优先队列

History of This Course

这门课已经开设 18 年之久,虽然国外诸多著名高校都开设了这门课程,但国内做计算几何方面的学校和机构屈指可数。

What’s Computational Geometry

说到计算几何,我们要做一个名词辨析。

如果你第一次听到 Computational Geometry,首先注意到的肯定是几何,脑海中浮现的是曲线、曲面诸如此类。事实上我国数学家苏步青八十年代就曾出版过一本《计算几何》的书。 此计算几何非彼计算几何,这门课更加强调的是计算。现代计算几何人们公认诞生于 1978 年 Shamos 那篇著名的博士论文,所以这门学科到现在也不过区区四十年的发展历史。

当然计算几何之所以很重要,就是因为它是很多学科尤其是技术学科的基础,包括典型的图形学、CAD、GIS、路径规划等等……最后都会回到计算几何这些基本的问题。

在学习之前如果一言以蔽之概括一下的话,计算几何就是就是”算法设计与分析”的几何版,它所讨论的对象、问题的表面形式都是几何的,它求解这些问题的方法、策略高到上面的方法论其实也都是几何的。尽管从这个方面讲计算几何只是算法设计与分析的一个分支,但是正因为它融入了很多古典的一些离散几何学、组合几何学等等精华的结论和方法,所以它不仅仅是一个几何和计算两个问题的物理反应,而是很深入的化学反应。

How to Learn CG Better

计算几何强调本质的东西就是要形象。

没有人喜欢复杂深奥的东西,所以这门课如果在学习过程中没办法很好理解推导和公式,不必拘泥于复杂深奥的泥潭,暂时放下它,将注意力放在图形和具体表现上。

❌