TimothyQiu's Blog

keep it simple stupid

使用 Conan 管理 C++ 依赖

分类:技术

现代 CMake 使用 C++ 依赖项时已经相对方便了。比如 find_package(OpenSSL 1.0 REQUIRED) 就可以自动在本地机器上查找已安装的与 OpenSSL 1.0 兼容的包,然后就可以直接 target_link_libraries(targetName PRIVATE OpenSSL::SSL) 使用,不必再手动写头文件和库文件配置。

要做到「本地机器上已安装」,macOS 和 Linux 系统都非常方便,大多数库都可以直接通过系统级包管理工具安装,而 Windows 上就稍显麻烦。我之前比较喜欢的是,比较复杂的库还是留着在各平台手动安装,简单的则使用 CMake 的 FetchContent 模块下载使用。但这样的缺点是每次重新生成工程时,都需要下载一遍依赖并编译。尤其最近国内的网络状态,HTTPS 连接 GitHub 经常超慢。所以想想还是用现成的包管理工具吧。

目前市面上流行的包管理工具中:vcpkg 虽然很多人用,但是微软那套逻辑我始终表示审美不能;Hunter 虽然是纯 CMake 解决方案,但是官方涵盖的库偶有不足;而 Conan 我一开始是不喜欢的,不但需要使用 Python 安装,而且它的前世 biicode 当年也风光过现在已经挂了。不过现在看来,Conan 似乎是这几个之中比较成熟好用的解决方案,至少,符合我的审美就是了。

安装

官方推荐用 Python 在虚拟环境里用 pip install conan 安装,可以随时保持最新。

我在 macOS 上使用 Homebrew 安装,可以少管理一个虚拟环境。感觉 Arch Linux 这样滚动更新的系统也可以直接使用系统包管理工具安装。

找到想要的库

想要使用 spdlog 时,首先搜索:

$ conan search spdlog -r conan-center
Existing package recipes:

spdlog/0.14.0@bincrafters/stable
spdlog/0.16.3@bincrafters/stable
spdlog/0.17.0@bincrafters/stable
spdlog/1.0.0@bincrafters/stable
spdlog/1.1.0@bincrafters/stable
spdlog/1.2.1@bincrafters/stable
spdlog/1.3.0@bincrafters/stable
spdlog/1.3.1@bincrafters/stable
spdlog/1.4.1@bincrafters/stable
spdlog/1.4.2
spdlog/1.4.2@bincrafters/stable
spdlog/1.5.0

命令行中的 -r conan-center 表示所要搜索的仓库,conan-center 是官方自带的默认仓库,如果你本地添加了多个仓库的话,也可以用 all 表示搜索所有仓库。不带这个选项时则是在本地的缓存中查找。

搜索结果中每一行都是一个可用的包的名称,使用 @user/channel 后缀的是完整的包命名方式。官方 conan-center 仓库中,最近的包都是通过 CI 自动构建二进制文件的,这些包使用name/version 的命名方式。

想要知道某个版本/包的详情,可以使用这样的命令查看:

$ conan inspect spdlog/1.5.0

会列出一些信息和安装时的可选参数。

当然,你也可以直接在网站 https://conan.io/center/ 查找 conan-center 仓库中的包。

依赖的指定、安装、使用

一般使用名为 conanfile.txt 的纯文本文件指定依赖,格式类似 INI 文件。

[requires]
spdlog/1.5.0

[generators]
cmake_find_package

[requires] 部分很简单,列出你所需要依赖的包的名称即可。[generators] 部分指定所需要的「生成器」,可以生成与 CMake、SCons 等工具的对接文件。

使用 conan install /path/to/source-dir 可以安装依赖并生成对接文件,参数为包含 conanfile.txt 的目录。当然,这样做会把「对接文件」生成在当前目录,可以使用 -if 参数指定输出目录,推荐放在 CMake 的构建目录。

这样,Conan 就会把 1.5.0 版本的 spdlog 安装到自己管理的目录(一般是 ~/.conan),然后在输出目录输出一个 Findspdlog.cmake 文件。

CMakeLists.txt 中,要让 find_package 使用 Findspdlog.cmake 文件,把它所在的目录加入到 CMAKE_MODULE_PATH 中即可:

# 因为我们把 Findspdlog.cmake 输出到了构建目录
list(APPEND CMAKE_MODULE_PATH "${CMAKE_BINARY_DIR}")

# 按照正常方式搜索
find_package(spdlog REQUIRED)

# ...

# 这个生成器导出的目标是 package::package
target_link_libraries(targetName PRIVATE spdlog::spdlog)

当然,官方教程中使用的是 cmake 生成器,它不会生成 FindXXX.cmake,而是生成一个 conanbuildinfo.cmake,你需要在 CMakeLists.txt 中手动初始化:

include(${CMAKE_BINARY_DIR}/conanbuildinfo.cmake)
conan_basic_setup(TARGETS)

# ...

# 这个生成器导出的目标是 CONAN_PKG::package
target_link_libraries(targetName PRIVATE CONAN_PKG::spdlog)

这种方法把 Conan 显式写入了 CMake 配置里,我个人不是很喜欢。(但是 CONAN_PKG::package 的表述确实比 package::package 好一些,因为一些库官方提供的目标并不都是 package::package。)

其它零碎

构建版本

Conan 默认安装/构建的二进制是 Release 版本的。而 CMake 的默认构建方式则是 Debug。

所以,尤其在使用类似 MSVC 的编译器时,你可能需要手动指定安装 Debug 版:

$ conan install . -s build_type=Debug

当然你也可以试试 cmake_multi 或者 cmake_find_package_multi 生成器,可以同时安装 Debug 和 Release 版本。抑或是使用官方提供的CMake 集成,自己写脚本把 CMake 和 Conan 的构建类型同步起来。

包的参数

在使用 conanfile.txt 指定依赖时,还可以同时指定一些可选参数。比如指定使用 spdlog 的动态链接版本:

[options]
spdlog:shared=True

好了,这就是大致的 Conan 使用介绍。

真正上手,还请参阅官方文档 https://docs.conan.io/

我所知道的 constexpr

分类:技术

在知乎上看到《constexpr 究竟有什么用?》的问题,正巧前段时间趁着了解 constexpr if 的时候刚做过相关资料的搜集,拼凑了一下搞了一个回答。篇幅所限,完整版放在这里,主要是追加一些例子并补完一些周边内容 😄

constexpr 关键词是 C++11 引入的;C++14 中放宽了对 constexpr 函数的语法要求;而 C++17 则复用了该关键字,引入了 constexpr if。

constexpr 主要为 C++03 引入了以下变动:

拓展常量表达式的概念

之所以要拓展常量表达式的概念,是因为 C++03 中的一些尴尬,这从原本的标准库中就能看出来。

比如我们都知道 INT_MAX 是 C 语言的遗产,C++ 则更希望大家使用 std::numeric_limits<int>::max() 来拿 int 型的上限。然而不幸的是,后者是个函数调用而不是整型常量,使用起来可能需要花更多心思在性能或者别的东西上,没有前者那么自由。

int foo[std::numeric_limits<char>::max()];  // error: 不是常量表达式

又比如标准文件流,它的构造函数可以带上这样的第二个参数:

std::fstream foo("foo.txt", std::ios::in | std::ios::out);

这个参数是 openmode 类型的,是由实现具体定义的一种 Bitmask 类型。出于类型安全的考虑,通常用枚举值实现而不是整型。但是这样一来就有个问题,同样是写 std::ios::in | std::ios::out,如果用整型的话可以作为常量表达式使用,而为了类型安全考虑换用枚举实现(尤其是重载 operator|)后,就再也不可能是常量表达式了。

inline openmode operator|(openmode lhs, openmode rhs)
{
    return openmode(int_type(lhs) | int_type(rhs));
}

明明是这样简单的函数,对它的调用却不是常量表达式,就更别提编译时求值了。这就让委员会陷入了必须在「类型安全」和「效率」里二选一的尴尬境地。

标准库里会遇到这样的问题,大家日常使用也会遇到。加之标准委员会很想借此机会把原本标准中对于「常量表达式」(尤其是整型常量表达式)复杂的定义重构简化,引入 constexpr 来标记一些简单的函数,让对它们的调用能够作为常量表达式存在就很合情合理了。

而 constexpr 成员函数也可以类推,比独立的 constexpr 函数多一些对于类本身的限制便是了。

至于 constexpr 函数「到底应该多简单」,其实并没有必要刻意去记那些限制。如果你标记了 constexpr 的函数不够简单,编译器会提醒你哪里有问题的。

强制要求表达式编译时求值

说到这里,「constexpr 函数」并不能和「编译时求值」划等号,它只表达了「这个函数具备这样的能力」。

如果需要强制要求表达式在编译时求值,那么我们需要在变量定义前添加 constexpr,这样,用来初始化这个变量的表达式就「必须」是常量表达式,否则会报错。

#include <fstream>

// 该函数不是 constexpr 函数
int identity(std::ios::openmode mode)
{
    return mode;
}

constexpr auto out = std::ios::out;  // 此处为 constexpr

int main()
{
    constexpr int modeFail = std::ios::in | identity(out);  // 出错
              int modePass = std::ios::in | identity(out);  // 正常
}

constexpr 函数只有同时满足

  1. 所有参数都是常量表达式
  2. 返回的结果被用于常量表达式(比如用于初始化 constexpr 数据)

才会触发编译时求值。如果只有参数是常量表达式而结果不是,那么是否触发编译时求值取决于具体实现。

constexpr if

C++17 的 constexpr if 严格意义上不是 constexpr 而是 if 的一部分。

constexpr if 的主要用途是简化模板代码(这也意味着除非你是「库作者」或者「模版狂魔」,很少会用到)。很多原本需要绕弯借助类型 Tag 或者 SFINAE 来实现,需要拆成 N 个函数的功能,可以借助 constexpr if 写到一个函数里。

以下面的 get_value 函数为例。这个函数正常情况下会把参数原样返回,但如果传入指针,则返回被指针指向的内容。

如果用简单的类型 Tag 来实现,需要拆成三个模板:

template <typename T>
auto get_value(T t, std::true_type) {
    return *t;
}

template <typename T>
auto get_value(T t, std::false_type) {
    return t;
}

template <typename T>
auto get_value(T t) {
    return get_value(t, std::is_pointer<T>{}); 
}

如果用 SFINAE 来实现,需要拆成两个模板:

template <typename T, std::enable_if_t<std::is_pointer_v<T>, int> = 0>
auto get_value(T t) {
    return *t;
}

template <typename T, typename std::enable_if_t<!std::is_pointer_v<T>, int> = 0>
auto get_value(T t) {
    return t;
}

而如果用 constexpr if 来实现,可以简化为一个:

template <typename T>
auto get_value(T t)
{
    if constexpr (std::is_pointer_v<T>) {
        return *t;
    } else {
        return t;
    }
}

也有人把 constexpr if 拿来代替当作 #if 用,相信你可以想象得出具体的用法。但……我觉得那是邪道,所以不写了 😛

constexprconst

最初接触到 C++11 时,constexprconst 的关系让我很是害怕,因为排列组合似乎很多。不过这回终于下了决心,整理了下,没有初见时想象的那么复杂,总共似乎也有两个情况。

在修饰数据(变量)时,constexpr 是隐含 const 语义的。同时,constexpr 只和变量本身有关,遇到类似 const int *pint *const p 的破事时,建议还是写明:

constexpr int const foo = 42;
constexpr int       foo = 42;    // 和上面等价
constexpr int const *pb = &bar;  // 此处 &bar 必须是常量表达式

在涉及 constexpr 成员函数时,成员函数可能会有 const 修饰的情况。C++11 中,constexpr 成员函数是隐含 const 的;C++14 以来则没有这个限制。这里似乎可以借用 Python 的哲学「Better explicit than implicit」来表达一下,总共就几个字母的事情,就别偷懒了,你没法保证别人和你一样清楚这些「不那么直观」的东西。


以上就是所有内容了,感觉还是有些流水账的样子。

顺便小小吐槽一下「模板」,macOS 自带的拼音输入法只能通过 mú bǎn 打出来,所以我老是打成「版」……

std::error_code 和它的朋友们

分类:技术

前几天看 API 文档时候遇到了 std::error_code 这个东西,当时以为是 errno 的 Alias,后续查阅文档才发现并没有那么简单。

system_error

std::error_code 包含在 <system_error> 头文件中,相关的共有四个组件:

std::system_error 是一个继承自 std::runtime_error 的异常类,用以表示与 OS 交互时得到的以错误码形式返回的错误。因此除了提供标准的 what() 函数外,它还额外暴露了一个返回 std::error_codecode() 函数。同时,因为必须提供错误码,它既不提供空构造、也不提供接受字符串的构造函数。

从名字上就可以看出来(同时也是当时的提案 N2241 中指出的),整个 <system_error> 头文件都是为实现这个异常而生的。STL 有意将 std::error_code 作为 std::system_error 的附属品,而非单独的错误处理机制。

std::error_code

STL 中早期类似的错误码实现需求来自(C++17 才正式进入标准的)文件系统 API,当时的实现认为错误分类应在 errno 和操作系统原生错误码上二选一。但由于 STL 中网络、各种奇形怪状的 Boost 库的陆续加入,大家急需一个可扩展的错误码表示方案,才演变成现在的 std::error_code

std::error_code 顾名思义表示错误码,是由一个 int 型的 value 和一个 std::error_category * 型的 category 组成的值类型类。

之所以在 value 外还需要保存一个 category,是因为即使是同样的错误码,在不同的库或者场景下表示的意义可能不同。同样是 42,在一个库的错误码中可能表示「文件不存在」,在另一个库中可能就表示「DNS 解析失败」。如果你熟悉 Cocoa 的那一套,那么这就类似 NSErrordomain 属性。

此外,虽然没有明说 value 在等于 0 时表示无错误,但整个系统就是建立在这样的假设上的,例如:

构造 std::error_code

std::error_code 的构造函数共有三种重载:

前两种没啥好说的,第三种却值得推敲。

template<class ErrorCodeEnum>
error_code(ErrorCodeEnum e) noexcept;

此处的 ErrorCodeEnum 只是名字上说是枚举,但其实只要是用户定义类型就行(比如 enum class / enum / class),所以理论上可以从异常直接构造 std::error_code

通常,如果构造函数只接受一个参数,那么我们推荐将它标记为 explicit 以免发生不必要的隐式转换。但这个函数不然,它要的就是让原始的 ErrorCodeEnum 可以隐式转换为 std::error_code,从而实现这两者的直接比较。

catch (std::system_error const& e) {
    if (e.code() == std::errc::invalid_argument) {
        // blah blah blah...
    }
}

当然,为了避免从任意类型的值都能搞个 std::error_code 出来,此重载只有当 std::is_error_code_enum<ErrorCodeEnum>::valuetrue 时才会有效。所以你自定义错误码枚举时,需要在 std 命名空间中特化此模版。

#include <iostream>
#include <system_error>

enum class YourErrorCode {
    kSuccess = 0,  // 别忘了 0 应该表示无错误
    kNetworkError,
    kBadRequest,
    kServerError,
};

// 特化模版,启用对应的重载
namespace std {
template<>
struct is_error_code_enum<YourErrorCode>: true_type {};
}

// 提供工厂函数
// 工厂函数不必要写在 std 中
std::error_code make_error_code(YourErrorCode code)
{
    return {
        static_cast<int>(code),
        std::generic_category(),  // 这里暂时用自带的 category
    };
}

int main()
{
    std::error_code e = YourErrorCode::kBadRequest;
    std::cout << e << '\n';  // 自带一个输出流的重载
}

当然,如果后续 C++ 中终于引入 Concept 的话,这个重载应该就没有这么复杂了吧。

std::error_category

前面说到 std::error_code 里保存的其实是指向 std::error_category 的指针,而非对象。这是因为这个类就是应该被当作单例来用的,实际也只能这么用才对,因为它的 operator=() 是通过直接比较 this 指针来实现的。

此外,std::error_category 还是个纯虚类,你必须实现的纯虚函数有:

STL 自带 std::error_category 的几个子类,很好地示范了「如何正确使用纯虚类」:不暴露具体的子类,而是暴露工厂函数,只通过接口(纯虚类)访问子类。

// 得到的都是 std::error_category const&
auto const& gec = std::generic_category();
auto const& sec = std::system_category();

std::error_condition

2007 年,<system_error> 正式进入标准前夕,委员会对 N2241 提案给出了一些意见,其中包括一条

Obscure the distinction between system-specific errors and the general and portable notion of an error condition.

于是,为了区分「系统相关的错误」和「平台无关的错误」,std::error_condition 诞生了。

因此你可以看到,std::error_condition 是一个与 std::error_code 除了语义几乎没有差别的东西。从库作者的角度,你可以理解为封装底层细节时用 std::error_code,而对外暴露接口时推荐使用 std::error_condition

一起玩

std::error_conditionstd::error_code 虽然是两个独立的类,但它们可以通过 std::error_category 连接在一起。

这两个类的对象互相比较时,STL 提供了对应的 operator=() 等函数的重载,通过调用双方的 category().equivalent(other) 来比较。只要任何一方的 category 认为对方与自己等价,两者就会被判为相等。

// 卖个萌 :-P
enum class MyErrorCondition {
    kChenggong,
    kWangluoCuowu,
    kQingqiuCuowu,
    kFuwuqiCuowu,
};

class MyErrorCategory: public std::error_category
{
public:
    // 还记得 std::error_cateory 是个单例么?
    static MyErrorCategory const& instance() {
        static MyErrorCategory instance;
        return instance;
    }

    char const *name() const noexcept override {
        return "MyErrorCategory";
    }

    std::string message(int code) const override {
        return "Message";  // 偷个懒
    }

    bool equivalent(std::error_code const& code, int condition) const noexcept override {
        // 理论上你用不着在这里处理 code.category() == this->instance 的情况

        // 因为是个单例,所以某些情况下不得不用这么绕的办法来拿
        auto const& yourErrorCodeCategory = std::error_code(YourErrorCode{}).category();

        if (code.category() == yourErrorCodeCategory) {
            switch (static_cast<MyErrorCondition>(condition)) {
            case MyErrorCondition::kChenggong:
                return code == YourErrorCode::kSuccess;
            case MyErrorCondition::kWangluoCuowu:
                return code == YourErrorCode::kNetworkError;
            case MyErrorCondition::kQingqiuCuowu:
                return code == YourErrorCode::kBadRequest;
            case MyErrorCondition::kFuwuqiCuowu:
                return code == YourErrorCode::kServerError;
            }
        }
        return false;
    }
};

// error_condition 同样需要特化模版启动重载
namespace std {
    template<>
    struct is_error_condition_enum<MyErrorCondition>: true_type {};
}

// error_condition 同样可以通过工厂函数构造
std::error_condition make_error_condition(MyErrorCondition code)
{
    return {static_cast<int>(code), MyErrorCategory::instance()};
}


int main()
{
    std::error_code code = YourErrorCode::kNetworkError;
    std::error_condition condition = MyErrorCondition::kWangluoCuowu;
    std::cout << (code == condition) << '\n';
}

看上去有点绕,但由于通常 std::error_code 是底层接口定死的,而你所做的只能是用 std::error_condition 来适配的情况来说,还是很合理的。

还是 STL 轻松,直接抛 std::system_error 给你。std::error_code 甩脸,要抽象你自己去用 std::error_condition 搞,哈哈。

顺带一提

上面已经提到此处的 std::system_error 异常与 std::error_code 的关系。事实上,至少在提出引入 std::error_code 提案的作者看来,STL 乃至 C++ 中推荐的错误汇报方法还是异常。由于存在与操作系统等底层 API 的交互,才引入了「从 API 返回的错误码构建异常」以及「将异常转换为错误码传给 API」这样的需求。

当然,为了方便统一范式,便于不支持异常的系统使用文件系统 API。C++17 才正式进入标准的文件系统 API 也添加了「默认抛异常,但额外传一个 std::error_code 就不抛异常」的机制。

以上。

《C++ 并发编程实战》读书笔记: 管理线程

分类:技术

最近终于找到本有兴趣的书啦,就是这本《C++ 并发编程实战》。我会找一些自己觉得没想到、好玩、或者有自己想法的地方整理下。

顺带吐个槽:In Action 系列的封面人物真心诡异,还是 O'reilly 萌萌哒的奇怪可爱小动物看着顺心。

join() 的异常安全

std::thread 要求在析构函数被调用时,该对象必须没有与之相关联的线程,否系统分分钟自尽给你看(调用 std::terminate())。

一般情况下,我们主要需要注意的地方是析构前对 join() 或者 detach() 的调用。如果要分离线程,线程启动后就可以立即调用 detach(),基本不会带来什么问题。而 join() 则没法立即调用,这样就会带来可能会被忽视的异常安全问题:线程启动后,如果某处抛出异常,可能把本应执行的 join() 跳过,导致程序自行退出。

void foo()
{
    std::thread t(thread_func);
    do_something();  // 如果抛出异常,就可能把下面的 join() 跳过
    t.join();
}

do_something();try / catch 包裹起来,并在 catch 里调 t.join() 最后把异常重新 throw 出去的方案固然可行,但对于 C++ 而言,更好的方案是 RAII:

class thread_guard
{
public:
    explicit thread_guard(std::thread& t)
        : thread_(t)
    {
    }

    ~thread_guard()
    {
        if (thread_.joinable()) {  // join() 前对象必须满足 joinable
            thread_.join();
        }
    }

    thread_guard(thread_guard const&) = delete;
    thread_guard& operator=(thread_guard const&) = delete;

private:
    std::thread& thread_;
};

void foo()
{
    std::thread t(thread_func);
    thread_guard g(t);

    do_something();
}

当然你也可以考虑把 std::thread 移动进去而不是传引用,书里管那种东西叫 scoped_thread,调用时不必为 std::thread 对象单独开一个名字。

线程传参二三事

给线程函数传参是通过 std::thread 的构造函数完成的,其原理与 std::bind 类似。所有参数先在当前线程被复制 / 移动到对象内部,然后在新线程中完成对线程函数的调用。

这两步的划分会导致会被一些人说「坑」(虽然实际上是他们自己没注意)。

比如从「被复制」到「实际调用线程函数」之间可能并不连续,那么被复制的参数届时是否还有效就可能成为问题,例如:

void thread_func(std::string const& s);

void foo(int bar)
{
    char buffer[1024];
    sprintf(buffer, "%d", bar);
    std::thread t(thread_func, buffer);
    t.detach();
}

前面说过构造函数仅负责原样复制 / 移动参数,所以 char *std::string 的转换是在新线程中的第二步时做的,于是例子中 t 对象构造函数暂存的其实是指向栈上的 buffer 的指针。而由于 detach()foo 返回后可能新线程还未正式启动。如果 thread_func 真正被调用时 foo 已经返回,那么这个指针参数就无效了。

一个解法是把代码改成 std::thread t(thread_func, std::string(buffer));这样构造函数就会把实参 std::string 移动进去(即便在 std::string 无法移动只能复制的平行宇宙,这样做也是安全的)。

用 STL 寻找前 K 个最大的数

分类:技术

前几天找资料,顺手看到了这篇博文,讲了博主如何优化自己以前的算法的过程。于是立马想起了 GoingNative 2013 上的演讲 C++ Seasoning 以及前不久看到的这篇 From goto to std::transform。于是不禁想,「寻找前 K 大数」这样的任务,能不能直接用 C++ 标准库来完成?如果能的话,性能又如何呢?于是我重新登录了那个以前做了两道题就尘封多年的 OJ 帐号……

凭着最直观最 naïve 想法,第一个版本我用了 std::sort 来代替手工排序。不出所料,这样的做法跑了 562 ms,要排到 700 名开外的样子。

#include <stdio.h>
#include <algorithm>
#include <functional>
#include <vector>

int main()
{
    int numVillagers;
    int topCount;

    while (scanf("%d %d\n", &numVillagers, &topCount) == 2) {
        if (numVillagers == 0 && topCount == 0) {
            break;
        }

        std::vector<int> wealth(numVillagers);
        for (int i = 0; i < numVillagers; i++) {
            scanf("%d", &(wealth[i]));
        }
        std::sort(wealth.begin(), wealth.end(), std::greater<int>());

        if (topCount > numVillagers) {
            topCount = numVillagers;
        }

        for (int i = 0; i < topCount - 1; i++) {
            printf("%d ", wealth[i]);
        }
        printf("%d\n", wealth[topCount - 1]);
    }
}

于是优化:考虑到每次新建 std::vector 的开销,把 wealth 拎出来放到循环外,reserve() 题目中的最大值,每次在循环里重新 resize() 后,时间顿时缩短到了 296 ms,可以排到 180+ 的样子。

std::vector<int> wealth;
wealth.reserve(100000);

而在前面说过的演讲中,我还听到了一个之前从未留意的函数 std::nth_element。其作用是确保调用后第 N 个元素是范围内第 N 大的元素。调用后,[begin, N) 内的任意元素都小于 (N, end) 内的任意元素。

std::nth_element(wealth.begin(), wealth.begin() + topCount, wealth.end(), std::greater<int>());
std::sort(wealth.begin(), wealth.begin() + topCount, std::greater<int>());

尝试修改成以上的略显罗嗦的代码后,程序运行时间缩短到了 171 ms,可以排到 70+ 的样子。时间上和博文中给出的最小堆实现相同,但是内存占用要比它大很多。

既然上面是先用 std::nth_element 大致排序了一下,而后再用 std::sort 排序前半部分,那么,STL 里是否存在一次性只排 [begin, N] 范围内的数,而无视 (N, end) 内的顺序的函数呢?答案是存在,可以直接使用 std::partial_sort 解决。

#include <stdio.h>
#include <algorithm>
#include <functional>
#include <vector>

int main()
{
    int numVillagers;
    int topCount;

    std::vector<int> wealth;
    wealth.reserve(100000);

    while (scanf("%d %d\n", &numVillagers, &topCount) == 2) {
        if (numVillagers == 0 && topCount == 0) {
            break;
        }

        wealth.resize(numVillagers);
        for (int i = 0; i < numVillagers; i++) {
            scanf("%d", &(wealth[i]));
        }

        if (topCount > numVillagers) {
            topCount = numVillagers;
        }

        std::partial_sort(wealth.begin(), wealth.begin() + topCount, wealth.end(), std::greater<int>());

        for (int i = 0; i < topCount - 1; i++) {
            printf("%d ", wealth[i]);
        }
        printf("%d\n", wealth[topCount - 1]);
    }
}

此时的程序执行时间 156 ms,排名第 25 位。而截止到此时,我个人其实什么都没有干,实际任务都交给了 STL。

如同各种 MyStringMyVector 一样,一般情况下自己去实现这些通用算法在 STL 面前几乎没有任何优势。尤其是 C++11 带来 lambda 表达式以来,大大方便了 <algorithm> 中各种算法的使用,我觉得不去用 STL 的理由越发稀少了。

以上。