В моей следующей программе я сейчас использую unordered_map
только потому, что мне нужно время поиска / вставки O (1). Но теперь хотелось, чтобы все было заказано. Сортировка каждый раз очень неэффективна. Какие у меня есть альтернативы? Я читал, что hash_map
выполняет свою работу, но статьи, которые я читаю, очень сбивают с толку или довольно сложны для понимания. В чем сложность вставки / поиска hash_map
и действительно ли она упорядочена? Если да, то определено ли это в C ++ 0x и как его реализовать? Если нет, то что еще я могу использовать? Спасибо.
include <iostream>
#include <iterator>
#include <set>
#include <vector>
#include <unordered_map>
using namespace std;
template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
std::hash<T> hasher;
seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
template <typename C> struct ContainerHasher
{
typedef typename C::value_type value_type;
inline size_t operator()(const C & c) const
{
size_t seed = 0;
for (typename C::const_iterator it = c.begin(), end = c.end(); it != end; ++it)
{
hash_combine<value_type>(seed, *it);
}
return seed;
}
};
typedef std::set<int> my_set;
typedef std::vector<int> my_vector;
typedef std::unordered_map<my_set, my_vector, ContainerHasher<std::set<int>>> my_map;
typedef my_map::iterator m_it;
void print(my_map& data)
{
for( m_it it(data.begin()) ; it!=data.end(); ++it)
{
cout << "Key : ";
copy(it->first.begin(), it->first.end(), ostream_iterator<int>(cout, " "));
cout << " => Value: ";
copy (it->second.begin(),it->second.end(),ostream_iterator<int>(cout," "));
cout << endl;
}
cout << "---------------------------------------------------------------\n";
}
int main()
{
my_vector v1,v2,v3;
for(int i = 1; i<=10; ++i)
{
v1.push_back(i);
v2.push_back(i+10);
v3.push_back(i+20);
}
my_set s1(v3.begin(),v3.begin()+3);
my_set s2(v1.begin(),v1.begin()+3);
my_set s3(v2.begin(),v2.begin()+3);
my_map m1;
m1.insert(make_pair(s1,v1));
m1.insert(make_pair(s2,v2));
m1.insert(make_pair(s3,v3));
print(m1);
my_set s4(v3.begin(),v3.begin()+3);
m_it it = m1.find(s4);
if(it != m1.end())
{
cout << endl << "found" << endl;
}
else
{
cout << endl << "Not found" << endl;
}
}
РЕДАКТИРОВАТЬ:
Раньше я использовал std :: map
, но у меня большое количество элементов (в миллионах). Так что, даже если количество элементов настолько велико, все ли вы рекомендуете карту
, если я хочу ее заказать?