CODEWITHSUNDEEP
c++c++11boostvectorstl
c.bear
c.bear

Reputation: 1445

std::vector as key in std::set and std::unordered_set

I'm writing a program that evaluates tons of positions in a board game (i.e. othello). My board representation is an std::vector. Since the same position can occure more times in processing, I use an std::set<std::vector> to store examined positions.

In term of performances I don't know if it is preferable to use std::set (that works natively because std::vector implements all the operators required) or std::unordered_set with a good hashing function (i.e. boost::hash_range(...)).

In alternative are there other good solutions to achieve the same goal? (Maybe different board representations [bitboards for sure when available] or different data structures?)

EDIT ************************************** EDIT

This is the pseudo code to fetch boards:

enqueue initial board
while queue not empty:
    dequeue a board
    if board is already examined: //std::set search
        continue
    put board in examined boards
    if board is solved:
        print solution
    else:
        for each possible board that can arise out of this one:
            add board to end of queue

Upvotes: 1

Views: 281

Answers (1)

Daniel
Daniel

Reputation: 1051

see

Why on earth would anyone use set instead of unordered_set?

what is the difference between set and unordered_set in C++?

Basically: unless you're concerned about the order of the values you should probably go with unordered_set.

But as for all other performance problems: When in doubt --> start measuring. Implement both "less" and "hash", then try it with both classes and check which is performing better (Note: in this case you don't have almost the same API anyway. So it shouldn't take you long to switch classes for a test)

Upvotes: 1

Related Questions