C言語にC＋＋のmapを作成するには何が必要でしょうか？

Question

前提・実現したいこと

Paizaの「レベルアップ問題集」の「Bランクレベルアップメニュー」での解答にC++のmapを使った解答が乗っていたのですが、C言語でmapを作成することは可能でしょうか？また作成するにはどんな知識が必要でしょうか？
C言語で私が解いた回答は60点で100点には届きませんでした。
https://paiza.jp/works/mondai/prob60/sort_add_9

発生している問題・エラーメッセージ

エラーメッセージはございません。

該当のソースコード

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<string, int> SD;
    for (int i = 0; i < n; ++i) {
        string s;
        int d;
        cin >> s >> d;
        SD[s] += d;
    }
vector<pair<int, string>> DS;
    for (auto iter = SD.begin(); iter != SD.end(); ++iter) {
        DS.push_back(make_pair(iter->second, iter->first));
    }
    sort(DS.begin(), DS.end(), greater<pair<int,string>>());
    for (int i = 0; i < DS.size(); ++i) {
        cout << DS[i].second << ' ' << DS[i].first << endl;
    }
}

#include <stdio.h>
#include <string.h>

#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)

int main(void)
{
    int n;
    scanf("%d", &n);
    
    
    char s[20][n];
    int d[n];
    for (int i = 0; i < n; i++) {
        scanf("%s%d", s[i], &d[i]);
        //printf("%s %d\n", s[i], d[i]);
    }
    //printf("\n");
    
    int d_ans[n];
    char s_ans[20][n];
    int now = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && strcmp(s[i], s[j]) == 0) {
                d_ans[j] = d[i] + d[j];
                strcpy(s_ans[j], s[j]);
                now++;
            } else if (j && strcmp(s[i], s[j]) != 0) {
                d_ans[j] = d[j];
                strcpy(s_ans[j], s[j]);
            } else {
                d_ans[i] = d[i];
                strcpy(s_ans[i], s[i]);
            }
        }
    }
    
   for (int i = 0; i < n - now/2; i++) {
       for (int j = n - now/2 - 1; j > i; j--) {
           if (d_ans[j - 1] < d_ans[j]) {
               swap(int, d_ans[j - 1], d_ans[j]);
               char t[20];
               strcpy(t, s_ans[j - 1]);
               strcpy(s_ans[j - 1], s_ans[j]);
               strcpy(s_ans[j], t);
           } 
       }
   }
    
    //printf("%d\n", n - now/2);
    for (int i = 0; i < n - now/2; i++) {
        printf("%s %d\n", s_ans[i], d_ans[i]);
    }
    
    return 0;
    
}

試したこと

C言語の初心者なのでhash法をどのように改造したらよいか分かりませんでした。

補足情報（FW/ツールのバージョンなど）

piaza.ioを使用。

Comments

[BeatStar]

できなくはないと思いますが、リスト構造とかみたいに大掛かりになると思いますよ。

単に似たような実装であれば『構造体』にするだけです。

[dodox86]

C++のstd::mapの性能にどこまで迫るかで難易度が全然違うのではないでしょうか。
単に(キー/値)のペア、それも最大件数がそれほど多くなく、決まっているなら簡単でしょうけど、ちゃんとやろうとすると様々な背景知識が必要なはずです。単なる（キー/値）のペアだと検索の速度がO(N)になりますが、ちゃんと実装するとO(log N)に迫るはずです。

https://atcoder.jp/contests/apg4b/tasks/APG4b_aa?lang=ja

[whitehorse85921]

BeatStar様、ありがとうございます。
私のようなC言語初心者にはまだ実装できないと思いました。私の実力で構造体で実装できるか分かりませんが試してみたいと思います。

[whitehorse85921]

dodox86様、ありがとうございます。
様々な背景知識が必要とあったので、今の私には到底できそうにないなと思いました。もう少し修行を積んでからチャレンジしたいと思います。

[actorbug]

質問とは関係ありませんが、C言語の回答で正常動作しない入力例を挙げておきます。
3
A 1
A 2
B 4
また、入力が20行を超えた際にも正常動作しなくなると思われます。

[whitehorse85921]

actorbug様、ありがとうございます。
実は入力が8行を超えるのも正常に動作しませんでした。

[kazuma-s]

その Paiza の問題の解答を C で書きたいのなら、C独自のコードを
書くことで質問にある C++ のコードと同程度の行数で書けます。
map を使わなくてもよいから、Cでどう書けばよいのか知りたければ
そのことを質問に追記してください。

[dodox86]

質問の主旨はもともと「C++のstd::mapをC言語で作るには？」ですし、そのことについて既に複数の回答もいただいているので、自分なりの結論を得られたらBAを挙げていったんは質問をクローズすべきかと思います。テーマが変わるなら新規に別の質問で。

[whitehorse85921]

kazuma-s様、ありがとうございます。
「C独自のコードを書くことで質問にある C++ のコードと同程度の行数で書けます。」と教えて頂きありがとうございます。テーマが変わりますので新規の質問でやりたいと思います。

[whitehorse85921]

dodox86様、ありがとうございます。
BAを挙げて質問をクローズいたします。mapをＣ言語では今の私に出来そうにないので、別の質問を立てたいと思います。

Answer 1

まず、2次元配列の使い方が奇妙なので復習したほうがよいでしょう。

次に、この問題はS_iが1つの半角英文字なので26種だか52種だかは知りませんが256種は超えません
よって最初に256個のint配列を2個用意しカウントおよび出現したかを計測してやるだけです。

最後にどうしてもmapがほしければ赤黒木もしくはハッシュテーブルを実装する事になり
アルゴリズムとデータ構造について勉強する必要があります。

正直ファイル分割ができない競プロでやりたくないですし
勉強した結果uthashなどのヘッダライブラリを使う事になる気もします

---

よく考えるとソートの際に面倒くさいので構造体の方が楽でしたが
入力は以下のような感じ

struct {
    char ch;
    int count;
} data[255] = {};

for(int i = 0; i < n; i++){
    char ch;
    int d;
    scanf("%c %d", &ch, &d);
    data[ch].ch = ch;
    data[ch].count += d;
}

Comments

[whitehorse85921]

asm様、ありがとうございます。
「最初に256個のint配列を2個用意しカウントおよび出現したかを計測してやるだけです。」と折角おっしゃって下さったのに理解が出来ずすみません。
どんな実装になるのか今の私には想像がつきません。
アルゴリズムとデータ構造も少しずつ勉強したいと思います。

[whitehorse85921]

asm様、ありがとうございます。
コードのご提示ありがとうございます。ご提示いただいたコードを基に解いてみたいと思います。

Answer 2

C言語でmapを作成することは可能でしょうか？また作成するにはどんな知識が必要でしょうか？

Mapって、ぶっちゃけ対応表/辞書もっと言えば電話帳です、名前から電話番号を引き当てるってゆー。
だからたとえば「名前から電話番号を引き当てる」のを目的とするなら:

struct record {
  char name[32];
  char phone[15];
};

struct record Phonebook[100]; // 100人分の電話帳

とかやっといて、電話帳に挿入/削除/検索の機能を実装すればいい。

※ もちろん 登録数を(100じゃなく)可変にしたいとか、高速に検索したいとか、要件に応じて
もっと凝ったつくりにする必要があるでしょうよ(ハッシュ表による電話帳とかね)。

Comments

[whitehorse85921]

episteme様、ありがとうございます。
構造体で電話帳を作る場合登録数を可変に出来るの知りませんでした。ハッシュ表による電話帳は実装が難しそうです。

Answer 3

作成しようとする C++ の Map の知識と、 C の知識だと思います。

Comments

[whitehorse85921]

jimbe様、ありがとうございます。
C++のmapの知識とCの知識両方必要なのですね。今はCだけでいっぱいいっぱいですが、いずれ積み上げたいと思います。