２次元以上の配列をstd::sortを使って並べ替えする技

課題

２次元以上のデータを並べ替えするにはループ処理を書くなど意外と面倒です。
SQLならばORDER BY句で並べ替えができます。けれどもDBを使うほどのものでないデータであればもっと簡易に並べ替えしたいところです。

• ２次元以上の配列は次元ごとにループや関数を準備する必要がある面倒

解決方法

CやC++のunionやcastを使ってデータ側を変更することstd::sortで並べ替えをします。

• unionを使って２次元以上のデータを１次元のデータにパック
• castを使って１次元データとしてstd::sortに渡す

unionやcastを使うことに躊躇いがあるかもしれません。けれども、コード上から明確に利用方法が分かるのであれば、そうそう問題にはならないと思います。この例では以下になります。

• unionをメモリを１次元と２次元以上の切り替えのために利用
• castをstd::sortにunionを渡すために利用

（また、unionを任意のメモリを異る型でアクセスするためのビューだと視点を持つと、他にもいろいろ応用できそうです。）

ソースコード

最初にstd::sortで並べ替えをしたあと、std::mapを使って並べ替えをします。キーが重複していないデータであればstd::mapでも並べ替えをすることができます。

main.cxx

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <map>

using target_t =  union {
    u_int8_t b[8];
    u_int64_t lldata;
};
void print_array(target_t * targets, size_t size)
{
    for (int i = 0; i < size; ++i) {
        std::cout << std::hex << std::setfill('0') << &(targets[i].lldata) << ":" << std::setw(16) << std::setfill('0') << targets[i].lldata << std::endl;
        for (auto & b: targets[i].b) {
            std::cout << std::hex << reinterpret_cast<void*>(&b) << ":" <<  static_cast<u_int16_t>(b) << std::endl;
        }
    }
}
int main(int argc, char ** argv)
{
    //--------------------------------------------------
    //  並べ替えしたい2次元以上のデータ
    //--------------------------------------------------
#define TEST_DATA { \
          {0x17, 0x16, 0x15, 0x14, 0x13, 0x07, 0x07, 0x07} \
        , {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x07, 0x07} \
        , {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07} \
        , {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x06} \
        }

    //--------------------------------------------------
    //  ２次元以上のデータを１次にパックして並べ替えます
    //--------------------------------------------------
    target_t targets[] = TEST_DATA;
#define SIZE_TEST_DATA (sizeof(targets)/sizeof(target_t))
    std::cout << "-----ソート前" << std::endl;
    print_array(targets, SIZE_TEST_DATA);
    std::sort(reinterpret_cast<u_int64_t*>(targets), reinterpret_cast<u_int64_t*>(targets) + SIZE_TEST_DATA);
    std::cout << "-----ソート後" << std::endl;
    print_array(targets, SIZE_TEST_DATA);

    //--------------------------------------------------
    //  対象のデータに重複がなければstd::mapでも並べ替え
    //  できます。
    //--------------------------------------------------
    target_t targets2[] = TEST_DATA;
#define SIZE_TEST_DATA2 (sizeof(targets2)/sizeof(target_t))
    std::map<u_int64_t, int> v;
    for (int idx = 0; idx < SIZE_TEST_DATA2; ++idx) {
        v.insert(std::make_pair(targets2[idx].lldata, idx));
    }
    for (auto & item : v) {
        std::cout << std::hex << std::setw(16) << std::setfill('0') << item.first << ":" << item.second << std::endl;
    }
    return 0;
}

Makefile

Makefile

TARG += sort_sample
SRCS += main.cxx
LIBS += -lLLVM
LIBS += -lclangFrontend -lclangSerialization -lclangDriver
LIBS += -lclangTooling -lclangParse -lclangSema
LIBS += -lclangAnalysis -lclangRewriteFrontend -lclangRewrite
LIBS += -lclangEdit -lclangAST -lclangLex -lclangBasic -lclangASTMatchers
OPTS += -g
#OPTS += -static -static-libgcc -static-libstdc++
FLAGS += -std=c++11 -Wno-unused-parameter -fno-strict-aliasing -fsanitize=address -fno-omit-frame-pointer
INCS += -I/usr/lib/llvm-10/include
LIBDS += -L/usr/lib/llvm-10/lib

$(TARG): main.cxx
	clang++ $(SRCS) $(OPTS) $(FLAGS) $(INCS) $(LIBDS) $(LIBS) -o $(TARG)

実行結果

std::sortを使った並べ替え

$ ./sort_sample
-----ソート前
0x7ffec815efe0:0707071314151617
0x7ffec815efe0:17
0x7ffec815efe1:16
0x7ffec815efe2:15
0x7ffec815efe3:14
0x7ffec815efe4:13
0x7ffec815efe5:7
0x7ffec815efe6:7
0x7ffec815efe7:7
0x7ffec815efe8:0707050403020100
0x7ffec815efe8:0
0x7ffec815efe9:1
0x7ffec815efea:2
0x7ffec815efeb:3
0x7ffec815efec:4
0x7ffec815efed:5
0x7ffec815efee:7
0x7ffec815efef:7
0x7ffec815eff0:0706050403020100
0x7ffec815eff0:0
0x7ffec815eff1:1
0x7ffec815eff2:2
0x7ffec815eff3:3
0x7ffec815eff4:4
0x7ffec815eff5:5
0x7ffec815eff6:6
0x7ffec815eff7:7
0x7ffec815eff8:0606050403020100
0x7ffec815eff8:0
0x7ffec815eff9:1
0x7ffec815effa:2
0x7ffec815effb:3
0x7ffec815effc:4
0x7ffec815effd:5
0x7ffec815effe:6
0x7ffec815efff:6
-----ソート後
0x7ffec815efe0:0606050403020100
0x7ffec815efe0:0
0x7ffec815efe1:1
0x7ffec815efe2:2
0x7ffec815efe3:3
0x7ffec815efe4:4
0x7ffec815efe5:5
0x7ffec815efe6:6
0x7ffec815efe7:6
0x7ffec815efe8:0706050403020100
0x7ffec815efe8:0
0x7ffec815efe9:1
0x7ffec815efea:2
0x7ffec815efeb:3
0x7ffec815efec:4
0x7ffec815efed:5
0x7ffec815efee:6
0x7ffec815efef:7
0x7ffec815eff0:0707050403020100
0x7ffec815eff0:0
0x7ffec815eff1:1
0x7ffec815eff2:2
0x7ffec815eff3:3
0x7ffec815eff4:4
0x7ffec815eff5:5
0x7ffec815eff6:7
0x7ffec815eff7:7
0x7ffec815eff8:0707071314151617
0x7ffec815eff8:17
0x7ffec815eff9:16
0x7ffec815effa:15
0x7ffec815effb:14
0x7ffec815effc:13
0x7ffec815effd:7
0x7ffec815effe:7
0x7ffec815efff:7

std::mapを使った並べ替え

0606050403020100:3
0706050403020100:2
0707050403020100:1
0707071314151617:0

環境

$ clang++ --version
clang version 10.0.0-4ubuntu1
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin