Optimaler container für viele inserts + find_if?

happystudent

Hallo,

ich habe eine Funktion in meinem Code, welche laut Profiler weit über 90% der gesamten Laufzeit beansprucht. Die Funktion sieht so aus:

struct data
{
    double error;
    std::vector<int> values;
};

std::vector<data> data_container;

bool contains_data(data const &dat, std::vector<data>::iterator &it)
{
    // Das hier ist langsam
    it = std::find_if(data_container.begin(), data_container.end(), [&dat](data const &d)
    {
        return dat.values == d.values;
    });
    return it != data_container.end();
}

Also ich habe ein struct data , welches einen vector<int> und ein double beinhaltet. Der vector kann dabei beliebig lang sein (üblicherweise zwischen 10 - 100 Elementen).

Dann hab ich einen vector<data> , der hier mit data_container bezeichnet ist. Dieser wird während der Laufzeit des Programs sehr schnell befüllt und hat nach wenigen Minuten bereits mehrere 100000 Elemente (oder noch mehr).

Das Suchen in diesem (rasant wachsenden) vector stellt sich jetzt als Performance-Problem heraus... Welche Datenstruktur würdet ihr für so eine Anwendung empfehlen?

std::set bzw. std::unordered_set?

happystudent

sat schrieb:

std::set bzw. std::unordered_set?

Ja also an unordered_set hab ich auch schon gedacht (die Reihenfolge ist egal, deswegen ist unordered_set wahrscheinlich besser als set ), aber wie kann ich einen vector<int> als key in einem unordered_set benutzen?

Dafür braucht man ja wahrscheinlich eine eigene hash Funktion, aber wie soll die bei einem vector aussehen?

unskilled

http://stackoverflow.com/questions/20511347/a-good-hash-function-for-a-vector

ganz unten

std::size_t operator()(std::vector<uint32_t> const& vec) const {
  std::size_t seed = 0;
  for(auto& i : vec) {
    seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
  }
  return seed;
}

happystudent

Ok danke, werd ich mal ausprobieren

TyRoXx

boost::hash kann auch vector . Aber das wäre natürlich zu einfach.