Using an array as key in map C ++

Question

Basically, I need to find all matching anagrams to a word. What I was doing was using an array of size 26 to represent the letters in a word. Ex:

abcdefg={1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
aaaaaaa={7,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

This is how I'm creating the array.

//stringtemp is a C++ string representing the word.
//letters is a size 26 int array representing all the letters in the string.
for(int i=0;i<stringtemp.length();i++)
{
    letters[stringtemp[i]-65]+=1;
}

And this is how I'm storing the array in the map.

dictionary[letters].push_back(stringtemp);

So, am I doing something wrong or is this impossible in C++. In all the other answers I found, they suggested to use a vector as the key, but that won't work in my case(I think.)

As the answers below reflect, a C style array will not copy as you're expecting it to. — Drew Dormann
– Drew Dormann, Commented Sep 15, 2012 at 15:32
Including the definitions of dictionary and letters would help. — Gabriel
– Gabriel, Commented Sep 15, 2012 at 21:57

Luc Danton · Accepted Answer · 2012-09-15 15:37:29Z

12

All of std::array<T, 26>, std::string and std::vector<T> are perfectly valid key types for a std::map, since they all define less-than comparison operators. Note that std::array<T, 26> is similar to std::tuple<T, T, ..., T>, and comparison is defined lexicographically, very similar to string comparison.

#include <array>
#include <map>

typedef std::array<unsigned int, 26> alphabet;

std::map<alphabet, std::string> dictionary;

dictionary[{{1, 0, ..., 8}}] = "hello";

With a bit more work, you can also make all of those types keys for an std::unordered_map, though you'll have to add a bit of boilerplate code from Boost (using hash_combine).

edited Sep 15, 2012 at 15:37

Luc Danton

35.6k8 gold badges73 silver badges117 bronze badges

answered Sep 15, 2012 at 15:29

Kerrek SB

480k96 gold badges904 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Luc Danton Over a year ago

std::string isn't really in contention of being a key type.

Kerrek SB Over a year ago

@LucDanton: string will do in a crunch, and it's the only type which has a ready-made hash function defined for it. So if a hash table turns out to be computationally indispensable, then it'd be easier to use a string than define your own hash operations on a vector. Otherwise you have a valid point of course.

user1525047 Over a year ago

When I try that, I get an "expected initializer before '<' token" error. Also, when I try to import array, it returns an array file not found error. Any idea what the cause is?

Kerrek SB Over a year ago

@user1525047: You'll need C++11 support for std::array. In GCC, add -std=c++0x to your compiler command. Alternatively, use <tr1/include> and std::tr1::array.

Jonathan Seng · Accepted Answer · 2012-09-15 15:29:49Z

2

std::map allows you to provide a Compare operator in the constructor. You may need to provide such a Comparator in order for two arrays {1,....} and {1,....} to match since they may be different actual objects.

answered Sep 15, 2012 at 15:29

Jonathan Seng

1,2197 silver badges20 bronze badges

Comments

Pete Becker · Accepted Answer · 2012-09-15 15:29:03Z

1

The key type in a map must have an operator< defined for it. You could define operator< for your array type, but there's a much simpler approach: sort the letters in each word into alphabetical order, and use that sorted string as the key.

answered Sep 15, 2012 at 15:29

Pete Becker

77.1k8 gold badges82 silver badges171 bronze badges

1 Comment

Kerrek SB Over a year ago

A string consisting of 12000 'a's would be fairly inefficient that way, though.

Collectives™ on Stack Overflow

Using an array as key in map C ++

3 Answers 3

4 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related