-1

I know that the basic Map of C++ basically a Red Balck tree and therefore insertion and deletions takes O(log N). I intend to better performance with a Hash Table however I could not find bulit-in structure in C++ STD or even C++11 (rectify me if I am wrong). Now the question is how to acquire a way of Hash Table in C++11?

erogol
  • 13,156
  • 33
  • 101
  • 155

2 Answers2

3

What you are looking for is an std::unordered_map, which was introduced in C++11. The complexity of accessing an element is average constant time.

Joseph Mansfield
  • 108,238
  • 20
  • 242
  • 324
  • `s/amortized/average/g`. Big subtle difference. –  Feb 01 '14 at 18:32
  • @delnan Is amortized not appropriate here? Is it just insertion and deletion that are amortized constant time? – Joseph Mansfield Feb 01 '14 at 18:34
  • 1
    Roughly speaking: [Amortized](http://stackoverflow.com/q/200384/395760) refers to the total cost of n operations, while average-case complexity refers to a single operation on an "average" data set. Two orthogonal things. To speak of amortized constant time would be to imply (1) *some* lookups in a *sequence* of operations take worse-than-constant time, and (2) the bound is unconditional/worst-case rather than requiring a "nice" data set. –  Feb 01 '14 at 18:41
2

you can use std::unordered_map or boost::unordered_map.

example:

#include <iostream>
#include <string>
#include <boost/unordered_map.hpp>
#include <boost/foreach.hpp>
using namespace std;

int main(int argc, char** argv) {

    typedef boost::unordered_map<std::string, int> NumbersMap;
    NumbersMap numbers;
    numbers["1"]=1;
    numbers["2"]=2;
    numbers["13"]=13;
    numbers["100"]=100;

    BOOST_FOREACH( NumbersMap::value_type i, numbers) {
      std::cout << i.first << "," << i.second << "\n";
    }
    return 0;
}
4pie0
  • 29,204
  • 9
  • 82
  • 118