Tagged Questions
53
votes
5answers
10k views
Why is std::map implemented as red-black tree?
WHY is std::map implemented as a red-black tree?
There are several balanced BST out there, what were design trade-offs in choosing red-black tree?
40
votes
12answers
58k views
Which data structure would you use: TreeMap or HashMap? (Java)
Description | A Java program to read a text file and print each of the unique words in alphabetical order together with the number of times the word occurs in the text.
The program should declare a ...
14
votes
8answers
8k views
C++ map insertion and lookup performance and storage overhead
I would like to store a mapping of an integer key to a float value in-memory.
I have roughly 130 million keys (and, accordingly, 130 million values).
My focus is on lookup performance -- I have to ...
12
votes
6answers
3k views
What is the difference between a Map and a Dictionary?
What is the difference between a Map and a Dictionary? I am not asking for how they are defined in language X or Y (which seems to be what generally people are asking here on SO), I want to know what ...
11
votes
2answers
6k views
Fastest C++ map?
Correct me I'm wrong but std::map is an ordered map, thus each time I insert a value the map uses an algorithm to sort its items internally, which takes some time.
My application gets information ...
9
votes
3answers
190 views
c++ efficient data structure for bidirectional random access
I have elements a and b of two sets A and B. Now these are related to each other (0..1:n cardinality) so each a has at most one partner in B and each b can have several (at least one) associations to ...
9
votes
2answers
306 views
What are the strengths and weaknesses of PHP's array type as a data structure?
As a PHP programmer, I use arrays for pretty much everything. I know SPLFixedArray can be useful in certain cases, and I know PHP arrays aren't very memory efficient, but I have rarely run into ...
8
votes
3answers
14k views
Howto Create Map of Vector From Sorted Data
I have the following data as input (sorted by first column):
foo 1 2
foo 3 3
bar 10 11
I want to create a Map of Vector with first column as key of the map
such that we have:
foo = {1,2,3,3}
bar = ...
7
votes
6answers
8k views
What's the difference between set<pair> and map in C++?
There are two ways in which I can easily make a key,value attribution in C++ STL: maps and sets of pairs. For instance, I might have
map<key_class,value_class>
or
...
7
votes
7answers
300 views
Map with two Key for a value?
I want to create a map that has two key :
map.put (key1,key2,value1);// Insert into map
map.get(key1,key2); // return value1
i have looking into multikeyMap but i don't know how i will do it
7
votes
3answers
587 views
Haskell Range Map library
Is there a Haskell library that allows me to have a Map from ranges to values? (Preferable somewhat efficient.)
let myRangeMap = RangeMap [(range 1 3, "foo"),(range 2 7, "bar"),(range 9 12, "baz")]
...
7
votes
3answers
9k views
What's the difference between the data structure Tree and Graph?
Academically speaking, what's the essential difference between the data structure Tree and Graph? And how about the tree based search and Graph based search?
7
votes
1answer
2k views
6
votes
5answers
455 views
C++ priority dictionary
I need a container to store pairs, I have two operations:
update value by key
get the key with maximum value.
For the first operation, map is a good structure. For the second operation, seems ...
6
votes
3answers
315 views
Idea for keep information about visited states
I making now 15-puzzle solver (in c++), but instead of only 15-puzzle, my program must to solve also 3x4 puzzles, 8x8 puzzles, etc... - > X x Y puzzles. I must somehow keep information about visited ...
