Quel est le moyen idéal pour faire une liste unique de valeurs en C?

Question

Disons que nous avons

typedef struct { 
    int value1; 
    int value2; 
} values_t; 

et

values_t* values; 

est rempli de valeurs [i] .value1 et valeurs [i] .value2 paires qui peuvent ou peuvent ne pas être unique.

et nous voulons remplir

values_t* values_unique; 

uniquement avec uniques paires de valeurs , dans l'ordre où ils apparaissent d'abord dans valeurs.

Quelle est la façon idéale de faire cela en C?

EDIT: Supposons qu'ils sont des pointeurs correctement mallocés; ci-dessus est juste un pseudo code.

Answer 1

Vous utilisez probablement un hachage des valeurs, le maintien d'une liste des hash et les valeurs correspondantes, et seulement ajouter une nouvelle paire au tableau values_unique (dont la question ne à l'origine n'a pas déclaré comme un tableau) si il n'est pas trouvé via le hachage. Si la liste est volumineuse, l'accélération du hachage au lieu d'une recherche séquentielle dans toute la liste peut être très significative.

Answer 2

Je sais qu'il est assez ennuyeux de suggérer une langue différente, mais l'utilisation de C++ stl serait triviale.

set<values_t> mySet(); 

for(int i=0; i < number_of_values; i++) 
{ 
    mySet.insert(values[i]); 
} 

values_t * values_unique = new values_t[mySet.size()]; 

int j=0; 

for(set<values_t>::iterator i = mySet.begin(); mySet.end() != i; i++) 
{ 
    values_unique[j] = *i; 
    j++ 
} 

Answer 3

Ce sera quelque chose comme ça (Ne pas avoir été le codage en C pour longtemps, et le code n'a pas été testé):

#include<stdlib.h> 
#include<stdio.h> 

typedef struct { 
    int value1; 
    int value2; 
} values_t; 
values_t* values; 
size_t values_size = 100; 
values_t* values_unique; 
size_t values_unique_size; 
int valcmp(const values_t* a, const values_t* b) 
{ 
    //a < b -> -1 
    //a == b -> 0 
    //a > b -> 1 
    return (a->value1 == b->value1) ? ((a->value2 == b->value2) ? 0 : ((a->value2 < b->value2) ? -1 : 1)) : ((a->value1 < b->value1) ? -1 : 1); 
} 
int main(void) 
{ 
    values = malloc(values_size * sizeof(values_t)); 
    values_unique = malloc(values_size * sizeof(values_t)); 
    //fill the values table 
    memcpy(values_unique, values, values_size * sizeof(values_t)); 
    qsort(values_unique, values_size, sizeof(values_t), valcmp); 
    int i; 
    //hopefully values_size > 0 
    for(i = 1, values_unique_size = 1; i < values_size; ++i) 
     if(valcmp(&values_unique[i], &values_unique[values_unique_size - 1]) != 0) 
      values_unique[values_unique_size] = values_unique[i]; 
} 

même en C++:

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

vector<pair<int,int> > V, V_unique; 

int main() 
{ 
    V_unique = V; 
    sort(V_unique.begin(), V_unique.end()); 
    V_unique.resize(unique(V_unique.begin(), V_unique.end()) - V_unique.begin()); 
}