Быстрое и изящное одностороннее отображение известных целочисленных значений

Сортируйте массив ключом и сделайте двоичный поиск.

Как дополнительно, если вам нужна бинарная поисковая реализация, не пропустите обзор стандартной библиотеки C ++. Следующее делает один на массиве вашего типа структуры с использованием алгоритма COVAL_RANGE (извинения за несколько хаки качества кода)

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

struct S {
    int k, v;
};

bool operator <( const S & a, const S & b ) {
    return a.k < b.k;
};

// must be sorted in key order
S values[] = {{42,123},{666,27}};

int main() {

    S t;
    cin >> t.k;

    S * valend = &values[0] + sizeof(values) / sizeof(S);
    pair <S*,S*> pos = equal_range( &values[0], valend , t);

    if ( pos.first != pos.second ) {
        cout << pos.first->v << endl;
    }
    else {
        cout << "no" << endl;
    }
}

Почему не хешированная карта? Это даст вам более или менее постоянные времена для поиска для любого ключа.

Вы можете использовать Boost :: uss.

#include <iostream>
#include <boost/assign.hpp>

int main()
{
    typedef std::map< int, int > int2int_t;
    typedef int2int_t::const_iterator int2int_cit;

    const int2int_t theMap
        = boost::assign::map_list_of
            ( 2, 5 )
            ( 79, 12958 )
            ;

    int2int_cit it = theMap.find( 2 );
    if ( it != theMap.end() )
    {
        const int result = it->second;
        std::cout << result << std::endl;
    }
}

Если вы не хотите использовать карту по любой причине, (например, вы просто хотите использовать массив, который вы установлены В процессе компиляции) вы также можете использовать функтор в сочетании с <алгоритм> :

#include <windows.h>
#include <cstdlib>
#include <functional>
#include <algorithm>
#include <iostream>
using namespace std;

struct s { int a; int b; };

s theMap[] = { {2, 5}, {79, 12958 } };

struct match_key : public unary_function<s, bool>
{
    match_key(int key) : key_(key) {};
    bool operator()(const s& rhs) const
    {
        return rhs.a == key_;
    }
private:
    int key_;
};

int main()
{
    size_t mapSize = sizeof(theMap)/sizeof(theMap[0]);
    s* it = find_if(&theMap[0], &theMap[mapSize], match_key(79));
    cout << it->b;

    return 0;
}

Существует также техника, известная как «XMacros», который является хорошим способом сделать именно то, о чем вы тоже говорите. Тем не менее, легко злоупотреблять технику, поэтому я всегда рекомендую использовать его с осторожностью. Ознакомьтесь с: http://en.wikipedia.org/wiki/c_preprocessor#x-macros

Основной сигнал, у вас есть файл, где вы прочитаете свои сопоставления, скажем, Foo.txt, который выглядит так: Карта (2,5)
Карта (79,12958)
...

Затем вы определяете карту макроса (A, B), которая принимает эти два аргумента и делает вашу инициализацию для вас. Затем # Включите файл (foo.txt). Вы можете даже сделать это в нескольких пропусках, если хотите, переопределить макрос между каждым #include файла. Затем добавить больше отображений, которые вы просто добавляете их в Foo.txt и перекомпилируйте. Это очень мощно и может быть использовано для многих разных вещей.

Если вы на 100% определенные Themap не будет расти до более 1000 записей (профиль!), Возможно, быстрее сделать двоичный поиск.

Если значение A имеет разумную границу (например, ниже 1000), вы можете просто сделать простой массив с A в качестве индекса для гарантированного сложности O (1) Отказ Если вы используете GCC, вы можете использовать этот синтаксис ( http://gcc.gnu.org/onlinedocs/gccteSignaved-inits.html#designation-inits ):

int theMap[256] = { [2] = 5, [79] = 12958 };

(это не К сожалению, поддерживается G ++, к сожалению)

в любых других случаях, используйте std :: unordered_map , как показано в других ответах.

Если вам нужно сопоставление времени компиляции, вы можете использовать следующий шаблон:

// template to specialize
template<int T> struct int2int {};    

// macro for simplifying declaration of specializations
#define I2I_DEF(x, v) template<> struct int2int<x> { static const int value = v; };

// definitions
I2I_DEF(2, 5) I2I_DEF(79, 12958) I2I_DEF(55, 100) // etc.

// use
#include <iostream>    
int main()
{
  std::cout << int2int<2>::value << " " << int2int<79>::value << std::endl;

  return 0;
}

Таблица прыжка. Выключатель, вероятно, будет настроить это, если вы сможете использовать это, в противном случае вам может понадобиться некоторая сборка, но это, вероятно, самый быстрый путь.

У вас была правильная идея, это карта. Используйте STD :: Map .

std::map<int, int> theMap;
theMap[2] = 5;
std::map<int, int>::const_iterator iter = theMap.find(2);
if (iter != theMap.end())
   iter->second; // found it

Вставляем пары ints, извлекаем значение по клавишам, логарифмическая сложность. Если у вас действительно большой набор данных и вам требуется более быстрое извлечение, используйте std::tr1::unordered_map или boost::unordered_map (в случае, если ваша стандартная библиотека не имеет реализации TR1).

std::map или std::unordered_map, вероятно, самый чистый. К сожалению, в С++ нет встроенных ассоциативных массивов.

std::map<int,int> mymap; // the same with unordered map

// one way of inserting
mymap.insert ( std::make_pair(2,5) );
mymap.insert ( std::make_pair(79,12958) );

// another
mymap[2] = 5;
mymap[79] = 12958;

Для проверки

std::map<int,int>::const_iterator iter = mymap.find(2);
if ( iter != mymap.end() )
{
   // found
   int value = iter->second;
}

unordered_map имеет преимущество амортизированного времени поиска O(1) по сравнению с O(log n) из map.

Кластеризация первичного ключа сохраняет его вместе со строками; это означает, что он занимает меньше места (так как нет отдельных блоков индекса). Однако, как правило, его основное преимущество заключается в том, что сканирование диапазона может, как правило, обращаться к строкам, которые находятся в одном блоке, уменьшая операции ввода-вывода, что становится довольно важным, когда у вас есть большой набор данных (не 50 кбит/с).

Я думаю, что 50k int является довольно искусственным эталоном, и не тот, о котором вы заботитесь в реальном мире.

Если число исходных целых чисел i относительно велико (так что прямой поиск становится неэффективным), но все еще управляемым, можно относительно легко построить идеальную хеш-функцию хеш(i) для входных целых чисел (например, с помощью хэширования Пирсона ), а затем использовать хэшированное значение в качестве записи в таблице вывода map

output = map[hash(i)];

Конечно, если диапазон входных значений относительно мал, можно использовать функцию идентификации вместо хэша и просто превратить всю вещь в straghforward переназначать

output = map[i];

(хотя если бы это было так, вы бы, вероятно, даже не спросили.)

Псевдокод является почти допустимым кодом C++ 0x - но C++ 0x требует меньше!

map<int, int> theMap = { {2, 5}, {79, 12958 } };
assert ( theMap[ 2 ] == 5 );

В «нормальном» C++, вы должны инициализировать карту так, все еще довольно элегантно:

pair< int, int > map_array[2] = { make_pair(2, 5), make_pair(79, 12958) };
map< int, int > theMap( &map_array[0], &map_array[2] ); // sorts the array
assert ( theMap[ 2 ] == 5 );

Это быстро писать и быстро бежать!

Изменить: Не делайте карту глобальной переменной. (Хотя это безопасно в C++ 0x.) В этом случае он будет инициализирован правильно только в том случае, если компилятор выберет его инициализацию после map_array, что ОЧЕНЬ не гарантировано. Если вы хотите быть глобальным, инициализируйте его с помощью (& map _ array [0], & map _ array [2]); .

Если количество исходных целых чисел i относительно велико (так что прямой поиск становится неэффективным), но все же управляемо, вы можете относительно легко построить идеальную хеш-функцию hash (i) для ваших входных целых чисел (например, с использованием хеширования Пирсона ), а затем используйте хешированное значение в качестве записи в выходной таблице map

output = map[hash(i)];

Конечно, если диапазон входных значений относительно невелик, вы можете использовать функцию идентификации вместо хэша и просто превратить все это в прямое переназначение

output = map[i];

(хотя, если бы это было так, вы, вероятно, даже не спросили бы.)