在编译时计算和排序C++向量

Question

在编译时计算和排序C++向量

c++c++11metaprogramming

11

我有一个名为A的类，它有一个std::vector<int>作为成员变量。

当创建A的实例时，需要填充这个向量。

计算可能需要一些时间，我想知道：

它是否可以在编译时完成？
这个向量是否可以在编译时排序？

我对元编程不熟悉，目前还没有找到实现方法。这不是一个特定于操作系统的问题。

下面是A.cpp文件内容：

#include "A.h"
#define SIZEV 100

A::A()
{
    fillVector();
}

void A::fillVector()
{
    // m_vector is an attribute of class "A"
    // EXPECTATION 1 : fill the vector with the following calculation at compile time

    const int a=5;
    const int b=7;
    const int c=9;

    for(int i=0;i<SIZEV;i++){
        for(int j=0;j<SIZEV;j++){
            for(int k=0;k<SIZEV;k++){
                this->m_vector.push_back(a*i+b*j+c*k);
            }
        }
    }

    // EXPECTATION 2 : sort the vector as compile time 
}

std::vector<int> A::getVector() const
{
    return m_vector;
}

void A::setVector(const std::vector<int> &vector)
{
    m_vector = vector;
}

和 main.cpp（Qt 应用程序但不重要）：

#include <QCoreApplication>
#include "A.h"

int main(int argc, char *argv[])
{
    QCoreApplication app(argc, argv);

    A a;
    auto vec = a.getVector();

    // use vec, etc ...

    return app.exec();
}

- BlackPopa

3

我指的是在编译时。 - BlackPopa

1

你有考虑过代码生成吗？ - Karoly Horvath

2

你确定计算是最耗时的吗？对我来说，更耗时的是调用push_back。你尝试过在定义m_vector时设置初始大小，然后在循环中设置值吗？或者甚至使用数组？ - Estiny

1

@BlackPopa：谁说过“复制粘贴”了？ - Karoly Horvath

你的数据高度冗余。你可以用给定值的元素计数和/或前缀和的形式表示相同的信息，这样可以得到一个小而快速访问的形式。无论是否使用它来完全消除m_vector，在启动时使用该想法进行CountingSort将会更快。请参见我的答案。（很抱歉在各个地方留下评论，但是人们（如@TemplateRex）在我编辑答案时不会收到通知，我认为这是一个有价值的新想法，没有人提出过。） - Peter Cordes

显示剩余9条评论

7个回答

10

这是一个简单的整数编译时排序方法。它通过为每个元素计算其在列表中的位置，从而确定每个位置应该放什么元素，并在适当的位置插入新的列表。虽然复杂度方面可能不如先前的解决方案高效（是O（n^2）），但更易于理解并且不使用递归。

#include <initializer_list>
#include <array>
#include <tuple>

template<int... members>
struct IntList
{
    constexpr bool operator==(IntList) const { return true; }

    template<int... others>
    constexpr bool operator==(IntList<others...>) const { return false; }

    template<int idx>
    static constexpr auto at() 
    {
        return std::get<idx>(std::make_tuple(members...));
    }

    template<int x>
    static constexpr auto indexOf()
    {
        int sum {};
        auto _ = { 0, (x > members ? ++sum : 0)... };
        return sum;
    }

    template<int x>
    static constexpr auto count()
    {
        int sum {};
        auto _ = { 0, (x == members ? ++sum : 0)... };
        return sum;
    }

    template<int i>
    static constexpr auto ith()
    {
        int result{};
        auto _ = {
            ( i >= indexOf<members>() && i < indexOf<members>() + count<members>() ? 
              result = members : 0 )...
        };
        return result;
    }

    template<std::size_t... i>
    static constexpr auto sortImpl(std::index_sequence<i...>)
    {
        return IntList< ith<i>()... >();
    }

    static constexpr auto sort() 
    {
        return sortImpl(std::make_index_sequence<sizeof...(members)>());
    }
};

static_assert(IntList<1, 2, 3>().at<1>() == 2, "");

static_assert(IntList<>().indexOf<1>()           == 0, "");
static_assert(IntList<1>().indexOf<1>()          == 0, "");
static_assert(IntList<1, 2, 3, 4>().indexOf<3>() == 2, "");

static_assert(IntList<>().count<1>()        == 0, "");
static_assert(IntList<1>().count<1>()       == 1, "");
static_assert(IntList<1, 1>().count<1>()    == 2, "");
static_assert(IntList<2, 2, 1>().count<1>() == 1, "");
static_assert(IntList<1, 2, 1>().count<1>() == 2, "");

static_assert(IntList<>().sort()        == IntList<>(),        "");
static_assert(IntList<1>().sort()       == IntList<1>(),       "");
static_assert(IntList<1, 2>().sort()    == IntList<1, 2>(),    "");
static_assert(IntList<2, 1>().sort()    == IntList<1, 2>(),    "");
static_assert(IntList<3, 2, 1>().sort() == IntList<1, 2, 3>(), "");
static_assert(IntList<2, 2, 1>().sort() == IntList<1, 2, 2>(), "");
static_assert(IntList<4, 7, 2, 5, 1>().sort() == IntList<1, 2, 4, 5, 7>(), "");
static_assert(IntList<4, 7, 7, 5, 1, 1>().sort() == IntList<1, 1, 4, 5, 7, 7>(), "");

- Ab Wilson

2

这是优美的代码。所有代码都应该是优美的。 - Generic Name

谢谢，非常感谢。 - Ab Wilson

5

传统的处理在预计算可以完成的漫长计算方面是将结果作为构建过程的一部分进行计算，生成一个硬编码了结果的.cpp文件（在拥有嵌入式资源的平台上也可以使用这些资源）。

然而，在这里，计算非常简单，慢的部分可能只是分配，如果你想保留数据在std::vector中，则必须在运行时进行分配。如果你可以使用C风格数组，就可以像上面描述的那样将所有内容放入可执行文件中，但这会使可执行文件增加4MB，并且从磁盘加载其所造成的减速会抵消任何预计算带来的速度优势。

换句话说，当计算昂贵且输出较小时，构建时预先计算是有意义的。你的情况恰好相反，因此我建议避免这种方法。

- Matteo Italia

3

@BlackPopa，你在问题中提到的计算是你正在进行的实际计算吗？如果是的话，最好事先使用reserve()函数来保留所需的空间（即SIZEV*SIZEV*SIZEV），这样可能会更快。 - mattnewport

3

一般而言，要牢记的是，如果您的代码具有良好的渐进复杂度（O(n)、O(n log n)），并且是内存受限的（与 CPU 受限相反），通常从磁盘读取数据无法打败从头开始计算的方法，因为它的时间复杂度是O(n)，而传输速率更高约两个数量级的RAM会产生更大的常数。 - Matteo Italia

2

@BlackPopa，我不知道你做了什么，但reserve()并不是push_back()的替代品 - 你需要在循环中调用m_vector.reserve(SIZEV*SIZEV*SIZEV)，然后再使用push_back()。其他什么都不需要改变，你仍然要使用push_back()。这样会更快，如果不是的话，那就是你的测量有误。 - mattnewport

2

@BlackPopa 不要这样做，那是未定义的行为。vector::reserve()只是预先分配了足够的空间来存储请求的元素数量，它并不会改变向量的大小。如果您使用operator[]来访问这些元素，您的向量的size()仍将为0。 - mattnewport

3

在我对标量类型的std::vector进行的所有测试中，使用resize而不是reserve，然后使用operator[]存储元素更快，因为元素的零初始化非常便宜且避免了push_back执行的所有大小/容量检查。 - Matteo Italia

显示剩余7条评论

5

数据是从0到SIZEV * (a+b+c)的整数，但整数数量是SIZEV³。这是一组密集的整数，范围很小，因此使用计数排序是完美的选择（而且你永远不需要构建未排序的数组，只需在生成时增加计数）。

无论保留计数/前缀和，计数排序在启动时间上对于对比其他排序方式来说都是绝对优势，同时保持其他所有内容不变。

你可以将数据保存为紧凑形式（O(cuberoot(n))大小）的前缀和向量，以便在O(log (cuberoot(n)))时间内（二分搜索前缀和）从m_vector进行查找，其中n是m_vector的长度。请参见以下说明。

根据缓存/内存延迟，实际上不扩展m_vector可能会或可能不会提高性能。如果需要一系列值，则可以非常快速地从前缀和中即时生成m_vector的连续元素。

class A {
    // vector<uint16_t> m_counts;  // needs to be 32b for SIZEV>=794 (found experimentally).

    vector<uint32_t> m_pos;     // values are huge: indices into m_vector, up to SIZEV**3 - 1
    vector<uint16_t> m_vector;  // can be 16b until SIZEV>3121: max val is only (a+b+c) * (SIZEV-1)
}
void A::fillVector()
{
    const int a=5;
    const int b=7;
    const int c=9;

    const auto max_val = (SIZEV-1) * (a+b+c);

    m_vector.reserve(SIZEV*SIZEV*SIZEV);
    m_vector.resize(0);
    // or clear it, but that writes tons of mem, unless you use a custom Allocator::construct to leave it uninit
    // http://en.cppreference.com/w/cpp/container/vector/resize

    m_pos.resize(max_val + 1);  // again, ideally avoid zeroing
                  // but if not, do it before m_counts

    m_counts.clear();  // do this one last, so it's hot in cache even if others wasted time writing zeros.
    m_counts.resize(max_val + 1); // vector is now zeroed
    // Optimization: don't have a separate m_counts.
    // zero and count into m_pos, then do prefix summing in-place


    // manually strength-reduce the multiplication to addition
    // in case the compiler decides it won't, or can't prove it won't overflow the same way
    // Not necessary with gcc or clang: they both do this already
    for(int kc=c*(SIZEV-1) ; kc >= 0 ; kc-=c) {
      for(int jb=b*(SIZEV-1) ; jb >= 0 ; jb-=b) {
        for(int ia=a*(SIZEV-1) ; ia >= 0 ; ia-=a) {
          m_counts[kc + jb + ia]++;
          // do the smallest stride in the inner-most loop, for better cache locality
        }
      }
    }
// write the early elements last, so they'll be hot in the cache when we're done


    int val = 0;
    uint32_t sum = 0;
    for ( auto &count : m_counts ) {
       m_vector.insert(m_vector.end(), count, val++);
       // count is allowed to be zero for vector::insert(pos, count, value)
       m_pos[val] = sum;   // build our vector of prefix sums
       sum += count;

       //count = (sum+=count);  // in-place conversion to prefix sums
    }
    assert(m_vector.size() == SIZEV*SIZEV*SIZEV);
}

或者，不是实际扩展1.6GB的数组，而是对计数进行前缀和，给出一个向量作为m_vector中索引运行的起始位置的元素。即idx = m_pos[val]; m_vector[idx] == val。（当val <= 13时，这会崩溃，因为有些值不能表示为a、b和c的和，所以在m_count中有零，在m_pos中有重复项）

无论如何，你可以用二分查找代替对m_vector[i]的读取来查找i在m_pos中的位置。你要找的是m_pos中具有值<= i的最高索引。那个索引就是你在m_vector[i]中找到的。（或者类似于这样；我可能有一个偏移错误。）

哈希表行不通，因为你需要将多个i的值映射到0..(750*(a+b+c))中的每个数字。（所有m_vector[i]具有相同值的i）

如果你需要一系列连续的元素，可以将它们动态生成到一个tmp缓冲区中。查看m_pos[i+1]，以查看下一个具有不同值的元素何时到来。（查看m_counts可能会节省一些减法，但你最好只在m_pos中进行差异计算，以避免从触摸第二个数组引起的缓存未命中/缓存污染。）

实际上，m_counts可能根本不需要作为类成员保留，只需要在FillVector中作为临时变量。或者FillVector可以计入m_pos，并在原地将其转换为前缀和。

理想情况下，你可以使用模板来聪明地选择足够宽但不超过所需的m_counts和m_vector类型。IDK数论，所以我不知道是否有一个m_counts的桶会溢出uint16_t。平均计数将是750**3 / (750*(5+7+9)) = 26786，并且它们肯定聚集在m_counts的高端。实际上，SIZEV=793可以使用uint16_t计数器，而SIZEV=794产生了几个计数>65536（感谢Chris提供的工作示例，我可以很容易地测试这个）。

m_vector可以是uint16_t，直到(SIZEV-1)*(a+b+c) > MAX_UINT16（65535）。也就是说，在SIZEV >= 3122时，m_vector占用28.3 GiB的RAM。

在SIZEV = 750时，m_pos大约是L1缓存大小的2倍（Intel CPU）（750*(5+7+9) * 4B per short = 63000B）。如果编译器做得好，并使用有条件移动而不是不可预测的分支指令进行二进制搜索，则速度可能相当快。这肯定会节省大量主内存流量，如果您有多个线程，则这很有价值。

另外，从不触及m_vector意味着您可以处理需要比您拥有的更多内存来存储列表的问题大小。

如果您想在创建m_counts时真正创造性地优化缓存（通过三重嵌套循环），请使最内层循环向前和向后移动，而不是同一方向两次。这只对极大的SIZEV或者如果其他超线程对缓存施加了很大的压力才会有影响。

  for(int kc=c*(SIZEV-1) ; kc >= 0 ; kc-=c) {
    for(int jb=b*(SIZEV-1) ; jb >= 0 ; jb-=b) {

      for(int ia=0 ; ia<SIZEV*a ; ia+=a)
        counts[kc + jb + ia]++;
      if (! (jb-=b )) break;
      for(int ia=a*(SIZEV-1) ; ia >= 0 ; ia-=a)
        counts[kc + jb + ia]++;

    }
  }

倒计数到零（带或不带双向内部循环）很可能是下一次循环开始时的小胜利，在计数变高时进行大型memsets之前，这也有助于在前向扫描中就地执行前缀和。

我的先前回答，可能是死路一条：

有没有找到排序向量中第i个元素的闭式公式的希望？甚至有O(log i)算法可以即时生成它吗？

除非您在访问它时需要从此向量获取大量连续元素，否则计算它可能会更快。内存很慢，CPU很快，因此如果您可以在大约150个时钟周期内计算a [i]，则可以获得优势。（假设每次访问都是缓存未命中，或者不触及所有向量内存会减少程序其余部分的缓存未命中）。

如果我们能够做到这一点，理论上我们可以首先按顺序编写排序后的数组。

要做到这一点：洗牌常数，使a <= b <= c。

0、a、[a * 2..a * int（b / a）]、b、[b + a..b + a * int（（c-b）/ a）与b * 2..b * int（c / b）]、c、[一些数量的bx + ay]、c + a、[更多的bx + ay]，...

好的，这变成了一个组合混乱，这个想法可能不可行。至少，对于任何a，b和c的一般情况来说是这样。

使用a = 5，b = 7，c = 9：

0、5 = a、7 = b、9 = c、10 = 2a、12 = b + a、14 = 2b、14 = c + a、15 = 3a、16 = c + b、18 = 2c

我太困了，看不出模式，但这是一个更长的列表

# bash
limit=5; for ((i=0 ; i<limit ; i++)); do
             for ((j=0 ; j<limit ; j++)); do 
               for ((k=0 ; k<limit ; k++)); do 
                 printf "%2d: %d %d %d\n" $((5*i + 7*j + 9*k)) $i $j $k; 
           done; done; done | sort -n | cat -n
     1   0: 0 0 0
     2   5: 1 0 0
     3   7: 0 1 0
     4   9: 0 0 1
     5  10: 2 0 0
     6  12: 1 1 0
     7  14: 0 2 0
     8  14: 1 0 1
     9  15: 3 0 0
    10  16: 0 1 1
    11  17: 2 1 0
    12  18: 0 0 2
    13  19: 1 2 0
    14  19: 2 0 1
    15  20: 4 0 0
    16  21: 0 3 0
    17  21: 1 1 1
    18  22: 3 1 0
    19  23: 0 2 1
    20  23: 1 0 2
    21  24: 2 2 0
    22  24: 3 0 1
    23  25: 0 1 2
    24  26: 1 3 0
    25  26: 2 1 1
    26  27: 0 0 3
    27  27: 4 1 0
    28  28: 0 4 0
    29  28: 1 2 1
    30  28: 2 0 2
    31  29: 3 2 0
    32  29: 4 0 1
    33  30: 0 3 1
    34  30: 1 1 2
    35  31: 2 3 0
    36  31: 3 1 1
    37  32: 0 2 2
    38  32: 1 0 3
    39  33: 1 4 0
    40  33: 2 2 1
    41  33: 3 0 2
    42  34: 0 1 3
    43  34: 4 2 0
    44  35: 1 3 1
    45  35: 2 1 2
    46  36: 0 0 4
    47  36: 3 3 0
    48  36: 4 1 1
    49  37: 0 4 1
    50  37: 1 2 2
    51  37: 2 0 3
    52  38: 2 4 0
    53  38: 3 2 1
    54  38: 4 0 2
    55  39: 0 3 2
    56  39: 1 1 3
    57  40: 2 3 1
    58  40: 3 1 2
    59  41: 0 2 3
    60  41: 1 0 4
    61  41: 4 3 0
    62  42: 1 4 1
    63  42: 2 2 2
    64  42: 3 0 3
    65  43: 0 1 4
    66  43: 3 4 0
    67  43: 4 2 1
    68  44: 1 3 2
    69  44: 2 1 3
    70  45: 3 3 1
    71  45: 4 1 2
    72  46: 0 4 2
    73  46: 1 2 3
    74  46: 2 0 4
    75  47: 2 4 1
    76  47: 3 2 2
    77  47: 4 0 3
    78  48: 0 3 3
    79  48: 1 1 4
    80  48: 4 4 0
    81  49: 2 3 2
    82  49: 3 1 3
    83  50: 0 2 4
    84  50: 4 3 1
    85  51: 1 4 2
    86  51: 2 2 3
    87  51: 3 0 4
    88  52: 3 4 1
    89  52: 4 2 2
    90  53: 1 3 3
    91  53: 2 1 4
    92  54: 3 3 2
    93  54: 4 1 3
    94  55: 0 4 3
    95  55: 1 2 4
    96  56: 2 4 2
    97  56: 3 2 3
    98  56: 4 0 4
    99  57: 0 3 4
   100  57: 4 4 1
   101  58: 2 3 3
   102  58: 3 1 4
   103  59: 4 3 2
   104  60: 1 4 3
   105  60: 2 2 4
   106  61: 3 4 2
   107  61: 4 2 3
   108  62: 1 3 4
   109  63: 3 3 3
   110  63: 4 1 4
   111  64: 0 4 4
   112  65: 2 4 3
   113  65: 3 2 4
   114  66: 4 4 2
   115  67: 2 3 4
   116  68: 4 3 3
   117  69: 1 4 4
   118  70: 3 4 3
   119  70: 4 2 4
   120  72: 3 3 4
   121  74: 2 4 4
   122  75: 4 4 3
   123  77: 4 3 4
   124  79: 3 4 4
   125  84: 4 4 4

- Peter Cordes

我没有收到你的新回答通知，我会仔细阅读的，这种方法看起来非常有趣。 :) - BlackPopa

2

@BlackPopa 我正在准备使用计数排序的答案，但是 Peter 先我一步了。我可以确认这样做更快。如果你感兴趣，这里是我的基准测试。 - Chris Drew

@Chris Drew：我看了一下，非常感谢，差别确实很大！ - BlackPopa

@ChrisDrew：感谢提供代码链接。当uint16_t溢出时，有可用的工作代码进行检查非常方便。我在我的答案中链接了该代码的修改版本。我们都在计算最大值和所需数组大小时存在一个偏差。我现在认为我已经正确了。我注意到您没有反转循环，在内部循环中执行较小的步幅以获得更好的缓存局部性。此外，自从我最初的回答以来，我又有了另一个想法：使用三重循环计数到零，这样当您计算前缀和（或将其扩展为“m_vector”）时，“counts”的前面就会在缓存中热起来。 - Peter Cordes

4

虽然这是可以做到的（实例），但你不应该这样做。这将会花费太多的编译时间。

编译器并没有被设计用于快速、高效的数值大规模处理。现在，限制你的编译时工作只做相对简单的事情，而不是对1000万个元素进行排序。

即使你写了"合规"代码，今天大多数的编译器也会崩溃。我写的代码很早以前就出问题了，尽管我试图小心地控制递归深度限制。

无论如何，为了后代：

template<class T>struct tag{using type=T;};
template<class Tag>using type_t=typename Tag::type;

template<int...Xs> struct values { constexpr values() {}; };

template<int...Xs> constexpr values<Xs...> values_v = {};

template<class...Vs> struct append;
template<class...Vs> using append_t=type_t<append<Vs...>>;
template<class...Vs> constexpr append_t<Vs...> append_v = {};

template<> struct append<>:tag<values<>>{};
template<int...Xs>struct append<values<Xs...>>:tag<values<Xs...>>{};
template<int...Lhs, int...Rhs, class...Vs>
struct append<values<Lhs...>,values<Rhs...>,Vs...>:
    tag<append_t<values<Lhs...,Rhs...>,Vs...>>
{};

template<int...Lhs>
constexpr values<Lhs...> simple_merge( values<Lhs...>, values<> ) { return {}; }
template<int...Rhs>
constexpr values<Rhs...> simple_merge( values<>, values<Rhs...> ) { return {}; }
constexpr values<> simple_merge( values<>, values<> ) { return {}; }

template<int L0, int...Lhs, int R0, int...Rhs>
constexpr auto simple_merge( values<L0, Lhs...>, values<R0, Rhs...> )
-> std::conditional_t<
    (R0 < L0),
    append_t< values<R0>, decltype( simple_merge( values<L0,Lhs...>{}, values<Rhs...>{} ) ) >,
    append_t< values<L0>, decltype( simple_merge( values<Lhs...>{}, values<R0, Rhs...>{} ) ) >
> {
    return {};
}

template<class Lhs, class Rhs>
using simple_merge_t = decltype( simple_merge( Lhs{}, Rhs{} ) );
template<class Lhs, class Rhs>
constexpr simple_merge_t<Lhs, Rhs> simple_merge_v = {};

template<class Values, size_t I> struct split
{
private:
    using one = split<Values, I/2>;
    using two = split<typename one::rhs, I-I/2>;
public:
    using lhs = append_t< typename one::lhs, typename two::lhs >;
    using rhs = typename two::rhs;
};
template<class Values, size_t I> using split_t=type_t<split<Values, I>>;

template<class Values> struct split<Values, 0>{
    using lhs = values<>;
    using rhs = Values;
};
template<int X0, int...Xs> struct split<values<X0, Xs...>, 1> {
    using lhs = values<X0>;
    using rhs = values<Xs...>;
};
template<class Values, size_t I> using before_t = typename split<Values, I>::lhs;
template<class Values, size_t I> using after_t = typename split<Values, I>::rhs;

template<size_t I>using index_t=std::integral_constant<size_t, I>;
template<int I>using int_t=std::integral_constant<int, I>;
template<int I>constexpr int_t<I> int_v={};

template<class Values> struct front;
template<int X0, int...Xs> struct front<values<X0, Xs...>>:tag<int_t<X0>>{};
template<class Values> using front_t=type_t<front<Values>>;
template<class Values> constexpr front_t<Values> front_v = {};

template<class Values, size_t I>
struct get:tag<front_t< after_t<Values, I> >> {};
template<class Values, size_t I> using get_t = type_t<get<Values, I>>;
template<class Values, size_t I> constexpr get_t<Values, I> get_v = {};

template<class Values>
struct length;
template<int...Xs>
struct length<values<Xs...>>:tag<index_t<sizeof...(Xs)>> {};
template<class Values> using length_t = type_t<length<Values>>;
template<class Values> constexpr length_t<Values> length_v = {};

template<class Values> using front_half_t = before_t< Values, length_v<Values>/2 >;
template<class Values> constexpr front_half_t<Values> front_half_v = {};
template<class Values> using back_half_t = after_t< Values, length_v<Values>/2 >;
template<class Values> constexpr back_half_t<Values> back_half_v = {};

template<class Lhs, class Rhs>
struct least : tag< std::conditional_t< (Lhs{}<Rhs{}), Lhs, Rhs > > {};
template<class Lhs, class Rhs> using least_t = type_t<least<Lhs, Rhs>>;
template<class Lhs, class Rhs>
struct most : tag< std::conditional_t< (Lhs{}>Rhs{}), Lhs, Rhs > > {};
template<class Lhs, class Rhs> using most_t = type_t<most<Lhs, Rhs>>;

template<class Values>
struct pivot {
private:
    using a = get_t<Values, 0>;
    using b = get_t<Values, length_v<Values>/2>;
    using c = get_t<Values, length_v<Values>-1>;
    using d = most_t< least_t<a,b>, most_t< least_t<b,c>, least_t<a,c> > >;
public:
    using type = d;
};
template<int X0, int X1>
struct pivot<values<X0, X1>>: tag< most_t< int_t<X0>, int_t<X1> > > {};

template<class Values> using pivot_t = type_t<pivot<Values>>;
template<class Values> constexpr pivot_t<Values> pivot_v = {};

template<int P>
constexpr values<> lower_split( int_t<P>, values<> ) { return {}; }
template<int P, int X0>
constexpr std::conditional_t< (X0<P), values<X0>, values<> > lower_split( int_t<P>, values<X0> ) { return {}; }

template<int P, int X0, int X1, int...Xs >
constexpr auto lower_split( int_t<P>, values<X0, X1, Xs...> )
-> append_t<
    decltype(lower_split( int_v<P>, front_half_v<values<X0, X1, Xs...>> )),
    decltype(lower_split( int_v<P>, back_half_v<values<X0, X1, Xs...>> ))
>{ return {}; }
template<int P>
constexpr values<> upper_split( int_t<P>, values<> ) { return {}; }
template<int P, int X0>
constexpr std::conditional_t< (X0>P), values<X0>, values<> > upper_split( int_t<P>, values<X0> ) { return {}; }
template<int P, int X0, int X1, int...Xs>
constexpr auto upper_split( int_t<P>, values<X0, X1, Xs...> )
-> append_t<
    decltype(upper_split( int_v<P>, front_half_v<values<X0, X1, Xs...>> )),
    decltype(upper_split( int_v<P>, back_half_v<values<X0, X1, Xs...>> ))
>{ return {}; }

template<int P>
constexpr values<> middle_split( int_t<P>, values<> ) { return {}; }
template<int P, int X0>
constexpr std::conditional_t< (X0==P), values<X0>, values<> > middle_split( int_t<P>, values<X0> ) { return {}; }
template<int P, int X0, int X1, int...Xs>
constexpr auto middle_split( int_t<P>, values<X0, X1, Xs...> )
-> append_t<
    decltype(middle_split( int_v<P>, front_half_v<values<X0, X1, Xs...>> )),
    decltype(middle_split( int_v<P>, back_half_v<values<X0, X1, Xs...>> ))
>{ return {}; }

template<class Values>
using lower_split_t = decltype(lower_split( pivot_v<Values>, Values{} ) );
template<class Values> constexpr lower_split_t<Values> lower_split_v = {};
template<class Values>
using upper_split_t = decltype(upper_split( pivot_v<Values>, Values{} ) );
template<class Values> constexpr upper_split_t<Values> upper_split_v = {};
template<class Values>
using middle_split_t = decltype(middle_split( pivot_v<Values>, Values{} ) );
template<class Values> constexpr middle_split_t<Values> middle_split_v = {};

constexpr values<> simple_merge_sort( values<> ) { return {}; }
template<int X>
constexpr values<X> simple_merge_sort( values<X> ) { return {}; }

template<class Values>
using simple_merge_sort_t = decltype( simple_merge_sort( Values{} ) );
template<class Values>
constexpr simple_merge_sort_t<Values> simple_merge_sort_v = {};

template<int X0, int X1, int...Xs>
constexpr auto simple_merge_sort( values<X0, X1, Xs...> )
-> 
simple_merge_t<
    simple_merge_t<
        simple_merge_sort_t<lower_split_t<values<X0, X1, Xs...>>>, simple_merge_sort_t<upper_split_t<values<X0, X1, Xs...>>>
    >,
    middle_split_t<values<X0, X1, Xs...>>
>
{ return {}; }


template<class Values>constexpr Values cross_add( Values ) { return {}; }
template<class Values>constexpr values<> cross_add( values<>, Values ) { return {}; }
template<int A0, int...B>constexpr values<(B+A0)...> cross_add( values<A0>, values<B...> ) { return {}; }

template<int A0, int A1, int...A, int...B>
constexpr auto cross_add( values<A0, A1, A...>, values<B...>)
-> append_t<
    decltype(cross_add( front_half_v<values<A0, A1, A...>>, values_v<B...> ) ),
    decltype(cross_add( back_half_v<values<A0, A1, A...>>, values_v<B...> ) )
> { return {}; }

template<class V0, class V1, class V2, class... Vs>
constexpr auto cross_add( V0, V1, V2, Vs... )
-> decltype(
    cross_add( cross_add( V0{}, V1{} ), V2{}, Vs{}... )
) { return {}; }

template<class...Vs>
using cross_add_t = decltype( cross_add(Vs{}...) );
template<class...Vs>
constexpr cross_add_t<Vs...> cross_add_v = {};

template<int X, int...Xs>
constexpr values<(X*Xs)...> scale( int_t<X>, values<Xs...> ) { return {}; }
template<class X, class Xs>
using scale_t = decltype( scale(X{}, Xs{}) );
template<class X, class Xs> constexpr scale_t<X,Xs> scale_v = {};

template<int X0, int...Xs> struct generate_values : generate_values<X0-1, X0-1, Xs...> {};
template<int...Xs> struct generate_values<0,Xs...>:tag<values<Xs...>>{};
template<int X0> using generate_values_t = type_t<generate_values<X0>>;

一个三数中值编译时归并排序和叉积生成器。我可以通过努力大幅减少行数。

使用constexpr std::array可能比上述纯类型解决方案更快。

- Yakk - Adam Nevraumont

我在模板元编程方面没有太多经验。使用 https://zh.wikipedia.org/wiki/%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F，模板是否能更好地处理问题？关于运行时 CountingSort，请看我的回答（这将比 std::sort 对于这种密集高度重复的数据快得多）。 - Peter Cordes

2

也许不完全符合您的要求，但您可以编写一个单独的程序来计算向量、对其进行排序，然后将其输出到列表中。然后您只需读取该文件即可。

如果从磁盘读取速度太慢，您还可以将输出调整为合法的C++文件，该文件初始化具有硬编码值满足您要求的类实例。然后将其链接回您的主项目并编译，从而实现与您在此处概述的更复杂的元编程任务相同的功能。

- AGML

3

即使将预先计算好的数组嵌入可执行文件中，仍需从磁盘中读取，因此性能方面的考虑不受此选择的影响。 - Matteo Italia

没错，我想是这样的。不过，这与通过模板元编程将数组嵌入可执行文件有什么不同吗？ - AGML

1

@AGML：不，完全不是。你的方法还有一个巨大的好处，就是只需要在所需数据更改时重新构建庞大的对象文件，而不是在每次编译时使编译器对1.6GB的数据进行排序。然而，普遍共识（我也同意）是，在运行时让应用程序执行此操作将更有利于应用程序的性能，甚至不考虑分发1.6GB的可执行文件的问题。CountingSort很快。 - Peter Cordes

1

你可以使用斜堆在编译时对整数进行排序。以下示例适用于c++17。

#include <type_traits>
#include <utility>

template <class T, T... s>
using iseq = std::integer_sequence<T, s...>;

template <class T, T v>
using ic = std::integral_constant<T, v>;

template <class T, T v1, T v2>
constexpr auto ic_less_impl(ic<T, v1>, ic<T, v2>) -> ic<bool, v1 < v2>;
template <class ic1, class ic2>
using ic_less = decltype(ic_less_impl(ic1(), ic2()));

template <bool b>
using bool_cond_t = std::conditional_t<b, std::true_type, std::false_type>;

struct nil {};

template <class T, T v, T... s>
constexpr auto iseq_front_impl(iseq<T, v, s...>) -> ic<T, v>;
template <class T>
constexpr auto iseq_front_impl(iseq<T>) -> nil;
template <class seq>
using iseq_front = decltype(iseq_front_impl(seq()));

template <class T, T v, T... s>
constexpr auto iseq_pop_front_impl(iseq<T, v, s...>) -> iseq<T, s...>;
template <class seq>
using iseq_pop_front = decltype(iseq_pop_front_impl(seq()));

template <class T, T v, T... s>
constexpr auto iseq_append_impl(iseq<T, s...>, ic<T, v>) -> iseq<T, s..., v>;
template <class T, T v>
constexpr auto iseq_append_impl(nil, ic<T, v>) -> iseq<T, v>;
template <class seq, class c>
using iseq_append = decltype(iseq_append_impl(seq(), c()));

template <class seq>
using iseq_is_empty = bool_cond_t<std::is_same<iseq_front<seq>, nil>::value>;

template <class X, class L, class R>
struct skew_heap {};

template <class X, class L, class R>
constexpr auto skh_get_top_impl(skew_heap<X, L, R>) -> X;
template <class H>
using skh_get_top = decltype(skh_get_top_impl(H()));

template <class X, class L, class R>
constexpr auto skh_get_left_impl(skew_heap<X, L, R>) -> L;
template <class H>
using skh_get_left = decltype(skh_get_left_impl(H()));

template <class X, class L, class R>
constexpr auto skh_get_right_impl(skew_heap<X, L, R>) -> R;
template <class H>
using skh_get_right = decltype(skh_get_right_impl(H()));

template <class H>
using skh_is_empty = bool_cond_t<std::is_same<H, nil>::value>;

template <class H1, class H2>
constexpr auto skh_merge_impl(H1, H2) -> decltype(auto) {
    if constexpr (skh_is_empty<H1>::value) {
        return H2{};
    } else if constexpr (skh_is_empty<H2>::value) {
        return H1{};
    } else {
        using x1 = skh_get_top<H1>;
        using l1 = skh_get_left<H1>;
        using r1 = skh_get_right<H1>;

        using x2 = skh_get_top<H2>;
        using l2 = skh_get_left<H2>;
        using r2 = skh_get_right<H2>;

        if constexpr (ic_less<x2, x1>::value) {
            using new_r2 = decltype(skh_merge_impl(H1(), r2()));
            return skew_heap<x2, new_r2, l2> {};
        } else {
            using new_r1 = decltype(skh_merge_impl(r1(), H2()));
            return skew_heap<x1, new_r1, l1>{};
        }
    }
}
template <class H1, class H2>
using skh_merge = decltype(skh_merge_impl(H1(), H2()));

template <class H1, class IC1>
using skh_push = skh_merge<H1, skew_heap<IC1, nil, nil>>;

template <class H>
using skh_pop = skh_merge<skh_get_left<H>, skh_get_right<H>>;

template <class H, class seq>
constexpr auto skh_heapify_impl(H, seq) -> decltype(auto) {
    if constexpr (iseq_is_empty<seq>::value) {
        return H{};
    } else {
        using val = iseq_front<seq>;
        return skh_heapify_impl(skh_push<H, val>{}, iseq_pop_front<seq>{});
    }
}
template <class seq>
using skh_heapify = decltype(skh_heapify_impl(nil(), seq()));

template <class H, class seq>
constexpr auto skh_to_sortseq_impl(H, seq) -> decltype(auto) {
    if constexpr (skh_is_empty<H>::value) {
        return seq{};
    } else {
        using val = skh_get_top<H>;
        return skh_to_sortseq_impl(skh_pop<H>{}, iseq_append<seq, val>{});
    }
}
template <class H>
using skh_to_sortseq = decltype(skh_to_sortseq_impl(H(), nil()));

template <class seq>
using sort_seq = skh_to_sortseq<skh_heapify<seq>>;

static_assert(std::is_same<iseq<int, 1, 2, 3, 4, 5, 6, 7, 8, 9>, sort_seq<iseq<int, 2, 3, 5, 8, 9, 6, 7, 1, 4>>>::value);

- firejox

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- TemplateRex · Accepted Answer

std::vector<int>没有任何constexpr构造函数（因为不允许constexpr进行动态内存分配）。所以你无法在编译时对std::vector<int>进行排序。

你可以在编译时创建一个带有常量N的std::array<int, N>，但是由于std::sort也不是constexpr，你必须编写自己的排序程序。

你也可以编写Boost.MPL编译时向量或列表，并使用其中的sort例程。但这不会像std::array那样扩展得好。

另一个解决方法可能是将向量存储到static变量中，并在程序初始化时进行排序。你的程序启动时间稍微长一些，但不会影响其主要功能。

由于排序的复杂度是O(N log N)，你甚至可以进行两个步骤的构建，并将排序后的向量写入文件，然后将其编译链接到主程序，或者在程序启动时以O(N)的时间将其加载到static变量中。