Which map structure should I use?

This is a discussion on Which map structure should I use? within the C++ Programming forums, part of the General Programming Boards category; I'm going to map chunks of string to chars. There's going to be 256 <key - element> links. The map ...

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    110

    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.
    Last edited by überfuzz; 11-24-2012 at 08:52 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,448
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    I don't know what ..a perfect hash function is. Do you have any example or link I can look up?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,448
    Searching the Web could help.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    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.
    Last edited by überfuzz; 11-24-2012 at 10:24 AM. Reason: Forgot to mention

  6. #6
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,452
    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
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Thanks Elysia ... Thanks for bearing with me!

  8. #8
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    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?..

  9. #9
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,452
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #10
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Thanks you very much!

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

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,448
    You will have to do a linear search, unless you create another map.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,452
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  13. #13
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Ok thanks for your time!

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

  14. #14
    Registered User
    Join Date
    Dec 2005
    Posts
    134
    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;
    S_ccess is waiting for u. Go Ahead, put u there.

  15. #15
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to find number of structure members in a given structure?
    By bhaskarReddy in forum C Programming
    Replies: 4
    Last Post: 01-16-2012, 04:37 AM
  2. Replies: 4
    Last Post: 04-25-2010, 10:57 AM
  3. Replies: 1
    Last Post: 04-02-2009, 06:51 AM
  4. Replies: 9
    Last Post: 05-21-2007, 12:10 AM
  5. Replies: 4
    Last Post: 11-22-2006, 11:20 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21