標籤:

C++ 怎麼生成 4096 個函數?

前幾天去面試,遇到一個道題,原題忘了,大概意思就是生成 4096 個函數,並且保存在一個函數指針數組裡面,函數無參返回 int,要求通過函數指針數組調用能返回函數在數組中的位置,如 fun[50]() 就返回 50,於是我的代碼只有下面一部分:

typedef int(*fun)();

int main()
{
const short num = 4096;
fun f[num];

return 0;
}

我只做到聲明函數指針數組。

後面該怎麼去生成 4096 個函數我就不知道了。

有人說通過宏,但是我也沒頭緒。

求大神指教。

好吧,也可能存在我誤解的情況,不過那個要求還有函數指針數組我是確定的。


給一個C++11編譯期生成數組的版本。

#include &
#include &
using namespace std;

constexpr int N = 256;

typedef int (*func)();
typedef array& A;

template& int f() {
return x;
}

template& struct S;

template& struct S&<0, i...&> {
static constexpr A gs() {
return A{{ f&<0&>, f&... }};
}
};

template& struct S& {
static constexpr A gs() {
return S&::gs();
}
};

constexpr A a = S&::gs();

int main() {
for (int i = 0; i &< N; i++) cout &<&< a[i]() &<&< endl; }

這是參考 c++ - C++11: Compile Time Calculation of Array 的,不過 N=4096 很可能編譯不過。

如果是工程上用的,我會使用宏生成

constexpr A a = { f&<0&>, f&<1&>, ... f& };


//按慣例來個模板元的.....

#include &

typedef int(*fun)();
//跟題主保持一致

template& struct A {
static int func() { return counter; };
static void funSet4096(fun* f) {
A&::funSet4096(f); //靜態迭代
f[counter]=A&::func; //每個特化的A&都有不同的函數,符合要求
std::cout &<&< f[counter] &<&< std::endl; std::cout &<&< counter &<&< std::endl; }; }; template&<&> struct A &<-1&> { //此乃靜態迭代終止條件
static void funSet4096(fun*) {};
};

int main() {
fun f[4096];
A&<4095&>::funSet4096(f); //給f賦值
return 0;
}

本想再來個宏的,看到有大神已經貼上啦,那我來個文件自我包含的,比邪惡更邪惡,

以下代碼的實現前提是你放這段代碼進去的文件必須名為"main.cpp":

#ifndef FIRST_START
#define FIRST_START
#include &
typedef int( *fun )( ); //跟題主保持一致

template& struct A { static int fun() { return 1; }; };

int main()
{
fun f[4096];
int i = 0;
#include "main.cpp" //帶我裝逼帶我飛...
return 0;
}

#else
f[i++] = A&<__COUNTER__&>::fun; std::cout &<&< i++ &<&< std::endl; #if __COUNTER__ &< 1024 //不好意思題主,編譯器不讓我嵌套4096層... #include "main.cpp" #endif #endif

* 必須說明__COUNTER__宏是編譯器擴展並非C++標準,但VC,GCC均有支持


如果用lambda表達式的話這題真的不算題...

int main(void)
{
std::function& f[4096];
int count = 0;

for (int i = 0; i &< 4096; i++) { f[i] = [=](){return i;}; } for (int i = 0; i &< 4096; i++) { std::cout &<&< f[i]() &<&< " "; } return 0; }

模版版本

#include &

template &
int T_F()
{
return i;
}

typedef int (*func)();

template &
struct set_functions {
static void set(func *funcs)
{
funcs[count-1] = T_F&;
set_functions&::set(funcs);
}
};

template &<&>
struct set_functions&<0&> {
static void set(func *funcs)
{
funcs[0] = T_F&<0&>;
}
};

int main(void)
{
func f[4096];

set_functions&<4096&>::set(f);

for (int i = 0; i &< 4096; i++) { std::cout &<&< f[i]() &<&< " "; } return 0; }


我來個邪惡的版本。。

#define EMPTY()
#define DEFER(id) id EMPTY()
#define OBSTRUCT(...) __VA_ARGS__ DEFER(EMPTY)()
#define EXPAND(...) __VA_ARGS__

#define EVAL(...) EVAL1(EVAL1(EVAL1(EVAL1(__VA_ARGS__))))
#define EVAL1(...) EVAL2(EVAL2(EVAL2(EVAL2(__VA_ARGS__))))
#define EVAL2(...) EVAL3(EVAL3(EVAL3(EVAL3(__VA_ARGS__))))
#define EVAL3(...) EVAL4(EVAL4(EVAL4(EVAL4(__VA_ARGS__))))
#define EVAL4(...) EVAL5(EVAL5(EVAL5(EVAL5(__VA_ARGS__))))
#define EVAL5(...) EVAL6(EVAL6(EVAL6(EVAL6(__VA_ARGS__))))
#define EVAL6(...) __VA_ARGS__

#define CAT(a, ...) PRIMITIVE_CAT(a, __VA_ARGS__)
#define PRIMITIVE_CAT(a, ...) a ## __VA_ARGS__

#define INC(x) PRIMITIVE_CAT(INC_, x)
#define INC_0 1
#define INC_1 2
#define INC_2 3
#define INC_3 4
#define INC_4 5
#define INC_5 6
#define INC_6 7
#define INC_7 8
#define INC_8 9
#define INC_9 9

#define DEC(x) PRIMITIVE_CAT(DEC_, x)
#define DEC_0 0
#define DEC_1 0
#define DEC_2 1
#define DEC_3 2
#define DEC_4 3
#define DEC_5 4
#define DEC_6 5
#define DEC_7 6
#define DEC_8 7
#define DEC_9 8

#define CHECK_N(x, n, ...) n
#define CHECK(...) CHECK_N(__VA_ARGS__, 0,)

#define NOT(x) CHECK(PRIMITIVE_CAT(NOT_, x))
#define NOT_0 ~,1,

#define COMPL(b) PRIMITIVE_CAT(COMPL_, b)
#define COMPL_0 1
#define COMPL_1 0

#define BOOL(x) COMPL(NOT(x))

#define IIF(c) PRIMITIVE_CAT(IIF_, c)
#define IIF_0(t, ...) __VA_ARGS__
#define IIF_1(t, ...) t

#define IF(c) IIF(BOOL(c))

#define EAT(...)
#define EXPAND(...) __VA_ARGS__
#define WHEN(c) IF(c)(EXPAND, EAT)

#define REPEAT(count, macro, ...)
WHEN(count)
(
OBSTRUCT(REPEAT_INDIRECT) ()
(
DEC(count), macro, __VA_ARGS__
)
OBSTRUCT(macro)
(
DEC(count), __VA_ARGS__
)
)

#define REPEAT_INDIRECT() REPEAT

#define NUMBER 3

#define M(i, _) int f_##i() { return i; }
EVAL(REPEAT(NUMBER, M, ~))

#include &

int main() {
typedef int (*fun)();

fun f[NUMBER];

#undef M
#define M(i, _) f[i] = f_##i;
EVAL(REPEAT(NUMBER, M, ~))

for (int i = 0; i &< NUMBER; ++i) { printf("%d ", f[i]()); } return 0; }

想驗證4096時是否正確請把NUMBER 定義成4096。(CPU 100%不要怪我!

大部分宏的代碼來自 http://stackoverflow.com/questions/3136686/is-the-c99-preprocessor-turing-complete


來一個純C版的,純正的函數指針,沒有lambda什麼的

#include &

#define _F0 __asm mov eax, __COUNTER__ __asm ret
#define _F1 _F0 _F0 _F0 _F0 _F0 _F0 _F0 _F0
#define _F2 _F1 _F1 _F1 _F1 _F1 _F1 _F1 _F1
#define _F3 _F2 _F2 _F2 _F2 _F2 _F2 _F2 _F2
#define _F4 _F3 _F3 _F3 _F3 _F3 _F3 _F3 _F3

#define MAX (1&<&<12) //4096 typedef int(*funcType)(void); void getFuncArry(funcType* list,int buffer_size) { funcType func; __asm call __continue _F4 __continue : __asm pop eax __asm mov func, eax int i; for (i = 0; i &< (MAX &< buffer_size ? MAX : buffer_size); i++) list[i] = (funcType)((int)func + 6 * i); } int main() { int (*list[4096])(void); getFuncArry(list, sizeof(list)); printf("%d", list[3000]()); //Output: 3000 }

在VS下編譯


直擼版

#include &
typedef int (*F) ();

template &
int foo() { return I; }

template &
void gao(F* f) {
f[S] = foo&;
gao&(f);
}

template &<&>
void gao&<0&>(F* f) {
f[0] = foo&<0&>;
};

int main() {
using namespace std;
F f[4096];
gao&<4095&>(f);

for (int i = 0; i&<4096; ++i) cout &<&< f[i]() &<&< endl; }

防爆編譯器二分版

#include &
typedef int (*F) ();

template &
int foo() { return I; }

template &
struct enable_if {
typedef void type;
};

template &<&> struct enable_if& {};

template &
typename enable_if&::type gao(F* f) {
f[S] = foo&;
}

template &
typename enable_if&::type gao(F* f) {
f[S] = foo&;
f[E] = foo&;
}

template &
typename enable_if&::type gao(F* f) {
gao&(f);
gao&<(S+E)/2, E&>(f);
}

int main() {
using namespace std;
F f[4096];
gao&<0, 4095&>(f);

for (int i = 0; i&<4096; ++i) cout &<&< f[i]() &<&< endl; }

其實我覺得 lambda 不算作弊且最方便了


完了完了,完全看不懂你們寫的c++啊

10年來的c++功夫好像白練了。。哈哈


這個方法本質上和 @wcy123 的一樣,只是稍微提升了一點可移植性。
這裡用 C 語言實現。如果換成 C++ 風格可以用 constexpr 定義常量,再把頭文件名改一下。
要求是函數編譯後機器碼長度不長於 CODE_LENGTH ,且 MAGIC_NUM 首次在機器碼中匹配到的就是立即數。還有一個就是寄存器能容納 int 。

#include &
#include &

enum {
CODE_LENGTH = 16,
REQ_NUM = 4096,
MAGIC_NUM = 0x43C2,
};

typedef struct {
char bitcodes[CODE_LENGTH];
} func_mem_t;

typedef int (*func_ptr_t)(void);

int base_func(void){
return MAGIC_NUM;
}

func_mem_t func_mem_arr[REQ_NUM];
func_ptr_t func_arr[REQ_NUM];

size_t search_number_offset(void){
func_mem_t mem_buf;
memcpy(mem_buf, base_func, CODE_LENGTH);

size_t start_place;
int magic_key=MAGIC_NUM;
for (start_place = 0; start_place+sizeof(int) &<= CODE_LENGTH; ++start_place) if (memcmp(mem_buf.bitcodes+start_place, magic_key, sizeof(int))==0) return start_place; return CODE_LENGTH; } size_t number_offset; void generate_funcs(void){ int i; for (i = 0; i &< REQ_NUM; ++i){ memcpy(func_mem_arr+i, base_func, CODE_LENGTH); memcpy(func_mem_arr[i].bitcodes+number_offset, i, sizeof(int)); func_arr[i]=(func_ptr_t)func_mem_arr[i]; } } int main(int argc, char **argv){ number_offset=search_number_offset(); if (number_offset == CODE_LENGTH){ fprintf(stderr, "The method used in this program fails. "); return 0; } generate_funcs(); int input_num; scanf("%d", input_num); while (input_num&>=0input_num&

更新:上面那個別看了,雖然勉強可移植但用了擴展語法。

#include &
#include &

template &
int generation() noexcept { return i; }

template &
class foo;
template &
struct foo&&> {
using fptr_t = int(*)();
fptr_t array[sizeof...(Ints)]=
{ generation&... };
};

foo&&> bar;

int main(int, char**){
for (auto fptr : bar.array)
std::cout&<&< fptr() &<&< " "; std::cout&<&

C++14 下的,這個題目提出來時已經有了。

C++11 可以手動實現 integer_sequence ,大概 50~70 行, make_integer_sequence 用二分法生成數列以免遞歸過深。


我的思路是用 JIT ,首先我們看一下這種函數的機器指令是啥

int f()
{
return 0x12345678;
}
/*
gcc -c -O3 -o a.o a.c objdump -d a.o

a.o: file format elf64-x86-64

Disassembly of section .text:

0000000000000000 &:
0: b8 78 56 34 12 mov $0x12345678,%eax
5: c3 retq
*/

很好,這個函數的內容就是二進位數字 b8 78 56 34 12 c3

其中 b8 是機器指令,4 位元組就是常量操作符,c3 就是 ret。

我們生成一大堆這樣的機器指令就好了。

#include &
#include &
#include &
#define _GNU_SOURCE
#include &
#define N 4096
// 生成機器指令
void jit(char * buffer)
{
int c = 0;
for(int i = 0 ; i &< N; ++i){ buffer[c++] = 0xb8; //mov ax *((long long *) buffer[c]) = (long long) i; // mov what? c+=4; buffer[c++] = 0xc3; // ret }; } // 申請內存 void* alloc() { // 6 bytes for the machine code void * ret = mmap(NULL, 6*N, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0); assert(ret); return ret; } // 提交可執行代碼 void submit(void *addr) { int i = mprotect(addr, 6*N,PROT_EXEC|PROT_READ); assert(i == 0); } void release(void *addr) { int r = munmap(addr,6*N); assert(r == 0); } int main(int argc, char *argv[]) { typedef int (*fun)(); void * addr = alloc(); jit(addr); submit(addr); fun fun_array[N]; for(int i = 0; i &< N; ++i){ fun_array[i] = (fun)(((char*)addr) + i * 6); } // invoke them for(int i = 0; i &< 10; ++i){ printf("%d ",fun_array[i]()); } release(addr); return 0; }

這個程序就是寫著鬧著玩的,嚴重不可移植,不可擴展。但是如果你對 JIT 感興趣。這就是最簡單的例子了。也可以考慮使用 llvm 動態生成代碼,效果要好得多。

注意

gcc -std=c99 -o a.out a.c # 編譯出錯,MAP_ANONYMOUS 沒有定義
gcc -std=gnu99 -o a.out a.c # 編譯 OK

參考這個答案 c - MAP_ANONYMOUS with C99 standard


模板嵌套層次太深。。

boost.preprocessor的迭代次數也不夠(只有256)。

換成std::function,用lambda那叫作弊。

最後發現還是第一種比較容易:

#include &

using std::size_t;

typedef int (*fun) ();

constexpr size_t $$ = 256;

template&

struct _ {

static int __() { return I; }

static void $(fun* f) {

f[I] = __; _&::$(f);

}

};

template& struct _& {

static int __() { return I; }

static void $(fun* f) {

f[I] = __; _&::$(f); _&::$(f);

}

};

template& struct _& {

static int __() { return I; }

static void $(fun* f) { f[I] = __; }

};

template&<&> struct _&<0, 0&> {

static int __() { return 0; }

public:

static void $(fun* f) { f[0] = __; }

};

template& struct $ {

static void __(fun* f) {

_&::$(f); _&::$(f);

}

};

int main() {

const short num = 4096;

fun f[num];

$&::__(f);

return 0;

}


PS:我的確實不符合要求 大家去看 @Milo Yip 他們的代碼的

#include &
#include &
#include &
using namespace std;
int main(){
vector&&> fun;
for (int i = 0; i != 4096; ++i){
fun.push_back([=]{
return i;
});
}
//test
}


我有個想法,先用手機寫點偽代碼填坑

struct f
{
int n;
f operator[](int i) { return f{i}; }
int operator()(void) { return n; }
}


#include &

template&
class Func {
public:
int (*operator[](int i))()
{
if(i == I)
return f;
else {
Func& func;
return func[i];
}
}
static int f() { return I; }
};

template&<&>
class Func&<0&> {
public:
int (*operator[](int i))() { return f; };
static int f() { return 0; }
};

int main()
{
Func&<4095&> func;
for (int i = 0; i &< 4096; i++) std::cout &<&< func[i]() &<&< std::endl; } // Output: // 0 // 1 // ... // 4095

Complie the code with "g++ -ftemplate-depth=4097"

用 clang 編譯好像會導致 clang Segmetation fault……(畢竟遞歸層數太多,試了下 1024 的話 clang 還是可以編譯過的。Pia!&<(=o ‵-′)ノ☆ clang++

// 其實我也就剛學 C++ 兩月,求各位菊苣輕嘲。
// 答完發現上面各位菊苣的版本都比我的強,忽略我吧


template & struct f { static void apply(int (**ret)()) {

ret[FROM] = []() {return FROM;}; f&::apply(ret);

} };

template & struct f& { static void apply(int (**)()) {} };

...

int (*fps[4096])();

f&<&>::apply(fps);

...


用模版的話,還是比較簡單的

using FunType = int(*)();

template &
struct make_fun
{
static void make_fun_i(FunType* f)
{
f[i] = f_i;
make_fun&::make_fun_i(f);
}

static int f_i()
{
return i;
}
};

template &<&>
struct make_fun&<0&>
{
static void make_fun_i(FunType* f)
{
f[0] = f_i;
}

static int f_i()
{
return 0;
}
};

int _tmain(int argc, _TCHAR* argv[])
{
FunType f[4096] = { 0 };
make_fun&<4095&>::make_fun_i(f);

cout &<&< f[4095]() &<&< endl; return 0; }


用C++解釋器 例如CInt或者Ch或輪子哥的那個,

動態生成代碼,想多少就多少.


推薦閱讀:

C 與 C++ 的真正區別在哪裡?
如何評價 Visual C++ 將整合 Clang 用於開發 Windows 程序?
編譯 C++ 項目時模板引發的「undefined reference to」問題?
在哪些領域,C++ 還有著不可替代的優勢?為什麼?
C 語言局部變數,堆與棧的問題?

TAG:C | CC | C11 |