Which map structure should I use?

I'm going to map chunks of string to chars. There's going to be 256 <key - element> links. The map is going to be used like this.

string str = "ABCDABCDABCD"; //A string that's going to be mapped.
string copm_str ; .. .. .. .. .. ..// Mapped string, compressed.

str [function that uses map to compress data] -> comp_str; ..//Sorry if I'm vague, I haven't looked at members of the map classes in C++.

The map is going to look something like this.
a = "AAAA";
b = "AAAB";
etc..
t = "ABCD";
etc..

So in this example the string str would be mapped to, comp_str = "ttt". If I got this right I only need to find elements and keys in the map. So my question is, which C++ map should I use? (It's been a while since I tinkered in C++)

Edit, I'm looking for the structure with the lowest complexity while finding elements or keys.

Quote:

---

Originally Posted by überfuzz

I'm looking for the structure with the lowest complexity while finding elements or keys.

---

Then std::unordered_map is likely to be what you want: it is intended to be implemented by a hash table, and thus has O(1) complexity for key lookup in the average case. The alternative would be to use std::map which is intended to be implemented by a balanced binary tree, having an average and worst case complexity of O(log n) for key lookup.

That said, if you know the 256 possible string keys in advance, then it may be feasible to derive and use a perfect hash function and just use an array to map.

I don't know what ..a perfect hash function is. Do you have any example or link I can look up?

Searching the Web could help.

I can't set up the map properly... I get errors I don't really understand.

Code:

---

Aligner.cpp: In function 'int main()':
Aligner.cpp:264:48: warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x
Aligner.cpp:264:48: warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x
Aligner.cpp:264:48: error: deducing from brace-enclosed initializer list requires #include <initializer_list>
Aligner.cpp:264:48: error: deducing from brace-enclosed initializer list requires #include <initializer_list>
Aligner.cpp:264:48: error: deducing from brace-enclosed initializer list requires #include <initializer_list>
Aligner.cpp:264:48: error: deducing from brace-enclosed initializer list requires #include <initializer_list>
Aligner.cpp:264:48: error: no match for 'operator=' in 'map = {{"AAAA", "a"}, {"AAAB", "b"}, {"AAAC", "b"}}'
/it/sw/gcc/4.5.3/lib/gcc/i386-pc-solaris2.10/4.5.3/../../../../include/c++/4.5.3/tr1/unordered_map.h:180:5: note: candidate is: std::tr1::unordered_map<std::basic_string<char>, char>& std::tr1::unordered_map<std::basic_string<char>, char>::operator=(const std::tr1::unordered_map<std::basic_string<char>, char>&)

---

If someone could explain what I'm doing wrong or how I should do it instead...

Code:

---

std::tr1::unordered_map<std::string,int> map;
....map = {{"AAAA","1"},{"AAAB","2"},{"AAAC","3"}};

---

Thanks!

Edit, I forgot to mention that I tried to include the..<initializer_list> and got the same result.

There is no operator = that adds elements to a map, nor is there such a constructor to my knowledge.
You'll have to use a loop and use the insert method or index operator.
map["AAAA"] = "1";
map["ABAB"] = "N";
//etc

Thanks Elysia ... Thanks for bearing with me!

I can't access the instances in the map. This is how I've set it up.

Code:

---

std::tr1::unordered_map<std::string,int> map;
        map["AAAA"]=0;
        map["AAAB"]=1;
        map["AAAC"]=2;
//        int test = map.find("AAAB");
//        cout << test << endl;

---

when I try to use find() and at() etc I'm sprayed with error messages. How do I access a element using a key and vis-versa?..

This works for me using a C+11 compiler:

Code:

---

#include <unordered_map>
#include <string>
#include <iostream>

int main()
{
        std::unordered_map<std::string,int> map;
        map["AAAA"]=0;
        map["AAAB"]=1;
        map["AAAC"]=2;
        int test = map.find("AAAB")->second;
        std::cout << test << std::endl;
}

---

std::unordered_map returns a pair from find, where the first member is the key and the second member the value.

Thanks you very much!

And the other way around? Getting the string if the int is known?

You will have to do a linear search, unless you create another map.

There is no standard container for that that I know of.
But there is Boost.Bimap which would do what you want. It should be enough to just download it (no compilation requires) for bimap AFAIK.
Or, if you don't want to use external libraries, you can use two maps. One for mapping X -> Y and one for Y -> X.

Ok thanks for your time!

I don't need to map both ways, I'm just curious...:)

I would like to add here, If you have insert new items in the map then prefer insert() method over index overloaded operator insertion mechanism. insert() is more efficient in this case. And when you have update existing map then use index overloaded operator insertion mechanism.

Code:

---

insert method:
map.insert(pair<std::string, int>("AAAA", 0));

index overloaded operator insertion mechanism:
map["AAAA"]=0;

---

Maybe I should ask about the function using the map, or show it to get more input. The only way the map is used is to find mappings. A string is chopped into lengths of 4, the chunks are then compressed into 1 byte chars. The new string is smaller and possibly faster to work with.

Code:

---

string compress(string str, int offset = 0){
.. buildmap();
.. string compstr;
.. ..for(int i = offset; i < str.length()/4; i = i+4){
.. .. compstr += (char)map.find(str.substr(i,4))->second;
.. ..}
.. return compstr;
}

---

..I'm tinkering with an algorithm and I'm in the process of searching for possible refinements. This one being for sizing down the data (ÜBERBIG DATA is handled) in the algorithm. Feel free to comment my compress function. Is it gnarly?

..Edit, maven - I don't need to insert stuff in my application, once it's done it's done so to speak. Thanks!