Why accessing map values by using at in C++ is so slow when key values are std vectors?

c++ map get value by key
map c++
map<string, string c++
c++ map example
c++ map get value by index
map::find
map::insert
map iterator c

I'm using std::map defined as std::map<std::vector<int>, double> and you see the key values are vector of integers. The number of members in my map is 24600. Here is the minimum working example:

InOutLetFileVelocityWeights.h:

#include <iostream>
#include <string>
#include <vector>
#include <map>

class InOutLetFileVelocityWeights
{
        public:
          InOutLetFileVelocityWeights();

          const std::string& GetWeightsFilePath()
          {
            return velocityWeightsFilePath;
          }
          void SetWeightsFilePath(const std::string& path)
          {
            velocityWeightsFilePath = path;
          }

          double GetValue(std::vector<int>& xyz);

          void Initialise();

        private:
          std::string velocityWeightsFilePath;

          std::map<std::vector<int>, double> weights_table;
};

InOutLetFileVelocityWeights.cc:

#include "InOutLetFileVelocityWeights.h"
#include <algorithm>
#include <fstream>
#include <cmath>

InOutLetFileVelocityWeights::InOutLetFileVelocityWeights()
{
}

double InOutLetFileVelocityWeights::GetValue(std::vector<int>& xyz)
{

      double value;

      value = weights_table.at(xyz);

      return value;

}

void InOutLetFileVelocityWeights::Initialise()
{
/* Load and read file. */
const std::string in_name = velocityWeightsFilePath;

std::fstream myfile;
myfile.open(in_name.c_str(), std::ios_base::in);

std::string input_line;
/* input files are in ASCII, in format:
 *  *
 *   * coord_x coord_y coord_z weights_value
 *    *
 *     * */
while (myfile.good())
{
            double x, y, z;
            double v;
            myfile >> x >> y >> z >> v;

            std::vector<int> xyz;
            xyz.push_back(x);
            xyz.push_back(y);
            xyz.push_back(z);

            weights_table[xyz] = v;

        //std::cout << x << y << z << v << std::endl;
}
myfile.close();
}

main.cc:

#include "InOutLetFileVelocityWeights.h"

int main(int argc, char *argv[])
{

const std::string in_name = "Flow-Weights.txt";

std::vector<int> xyz;

xyz.push_back(760);
xyz.push_back(189);
xyz.push_back(368);

InOutLetFileVelocityWeights* Iolet = new InOutLetFileVelocityWeights();

Iolet->SetWeightsFilePath(in_name);

Iolet->Initialise();

double value = Iolet->GetValue(xyz);

std::cout << value << std::endl;

return 0;

}

Any idea why it takes that long to get the value from GetValue function? The input file is here: https://drive.google.com/file/d/1Bvv4JfdjJjCo-GKnduBdqabDJHo3UxbV/view?usp=sharing .

You have some other problem, like trying to access keys that aren't there and expanding the size of the map, or it's not hung where you think it is, or there's a compiler bug or something like that. This self-contained example reading from a file "x" containing 25000 4-tuples of ints is basically instant on my laptop with g++ and no optimization.

#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <fstream>

std::map<std::vector<int>, double> weights_table;
std::vector<std::vector<int> > allkeys;

void
loadit(char const *name)
{
  /* Load and read file. */
  std::fstream myfile;
  myfile.open(name, std::ios_base::in);

  std::string input_line;
  /* input files are in ASCII, in format:
   *
   * coord_x coord_y coord_z weights_value
   *
   * */
  while (myfile.good())
    {
      int x, y, z;
      double v;
      myfile >> x >> y >> z >> v;

      std::vector<int> xyz;
      xyz.push_back(x);
      xyz.push_back(y);
      xyz.push_back(z);
      allkeys.push_back(xyz);

      weights_table[xyz] = v;
    }
  myfile.close();
}

double GetValue(std::vector<int> xyz)
{
      double value;

      value = weights_table.at(xyz);

      return value;
}

int
main()
{
  loadit("x");
  double res=0;
  for (size_t i=0; i < allkeys.size(); ++i)
    res+=GetValue(allkeys[i]);
  std::cout << res << std::endl;
  return (0);
}

map::operator[] - C++ Reference, A reference to the mapped value of the element with a key value equivalent to k. accessing mapped values #include <iostream> #include <map> #include mymap['a'] is an element mymap['b'] is another element mymap['c'] is another� Why accessing map values by using at in C++ is so slow when key values are std vectors? I'm using std::map defined as std::map<std::vector<int>, double> and you see the key values are vector of integers.

You may like to use std::tuple<int, int, int> instead of std::vector<int> for your keys, as the former is much cheaper to create and copy.

And std::unordered_map instead of std::map. The former can give you close to O(1) lookup complexity (depending on your hash function) and it is more CPU cache friendly than std::map.

map::at - C++ Reference, Access element. Returns a reference to the mapped value of the element identified with key k. If k does not match the key of any element in the container, the� map count() function in C++ STL– Returns the number of matches to element with key value ‘g’ in the map. map equal_range() in C++ STL – Returns an iterator of pairs. The pair refers to the bounds of a range that includes all the elements in the container which have a key equivalent to k.

A std::map sorts by keys. When you insert an element, it must compare the key of the new element with many other keys (logarithmic in size). Since your keys are of type std::vector, imagine the work needed to insert an element, or 24600!

Also access becomes quite expensive. The complexity of std::map::at() is logarithmic in size, but again, you need to compare your keys which are of type std::vector (I'm not sure how keys of type std::vector are sorted, but it guess this is linear in size).

Furthermore, each time you create your std::vector, you are allocating dynamically, which is very expensive (you could just use a std::array for this job). You even create a copy when calling GetValue(std::vector<int> xyz) (the argument xyz should be passed as a const reference.

As an alternative, you could store your variables x, y and z in a std::array<int, 3> and use a std::map<std::array<int,3>, double>. This would solve your time issue.

Anyways, a std::map with keys of type std::array is as ugly as a map with keys of type std::vector. You should not use those kind of maps.

I don't know what the exact goal of your program is, but consider the following. When you try to get your double given a triplet, how did you decide which triplet you need? I guess you need to do this for each triplet, or for some random triplet. In both cases, you actually don't need a std::map. You can just store both triplets and values in std::vector:

// size
const size_t N = 24600;

// reserve space for vector of triplets (x, y, z) and vector of doubles (v)
std::vector<std::array<int, 3>> vec_triplets;
std::vector<double vec_values;
vec_triplets.reserve(N);
vec_values.reserve(N);

// for each triplet and double, store it in the vector
for ( ... )
{
    vec_triplets.emplace_back(std::array<int, 3>{x, y, z});
    vec_values.emplace_back(v);
}

// now I need to compute something using a triplet and the associated double
for (size_t idx = 0; idx < N; ++idx)
{
    const auto& triplet = vec_triplets[idx];
    const associated_double = vec_values[idx];
    /* do whatever you need */
}

map::at() in C++ STL, No two mapped values can have same key values. map::at() and throws an exception when we try to access an element not in the range, while Get hold of all the important DSA concepts with the DSA Self Paced Course at a Difference between Static and Dynamic Memory Allocation in C � Const vs� In this article we see how & why to use std::map in c++. std::map Introduction. std::map is an associative container that store elements in key-value pair. Benefits of using std::map : It stores only unique keys and that too in sorted order based on its assigned sorting criteria.

Why is it so slow?

Because you do much more than you need to here:

weights_table[xyz] = v;

map::operator[] searches the entry for the given key, inserts a key-value pair when no entry for given key exist, and then returns you a reference to the value.

If you just want to insert an element in a map you should use map::insert.

Then in your GetValue you are passing the vectors by value. This might take a while when the vectors are big.

Also make sure to enable compiler optimizations!

Searching in a map using std::map functions in C++, Searching in a map using std::map functions in C++ As map stores key-value pair, all the search operations take “O(log(n))” time (n is size of� Key value of the element whose mapped value is accessed. Member type key_type is the type of the keys for the elements stored in the container, defined in map as an alias of its first template parameter (Key). If an rvalue (second version), the key is moved instead of copied when a new element is inserted. Return value

C++ Maps Explained, What is a map in C++? A C++ map is a way to store a key-value pair. � C++ map use cases There are two main reasons why the map type can be� Copy all values from a map to vector using transform() & function pointer. We can also call the std::transform() with a function pointer i.e. let’s create a template function that returns second value from a given pair i.e.

STL Tutorial - Map Class, Learn to use the Standard Template Library map class as an associative array and How would you go about storing this in C++? One option would be to write your value pair stored in the map, you can retrieve them in the order of the keys . at () function is used reference the element mapped to the key value given as the parameter to the function. For example, if we have a string “hi” mapped to an integer 1, then passing the integer 1 as the parameter of at () function will return the string “hi”. How is at () function different from operator []

How to sort a map by value in C++, Using std::vector. This method entails copying the map into a vector of key-value pairs, and sorting the vector according to the increasing order of its pair's� map containers are generally slower than unordered_map containers to access individual elements by their key, but they allow the direct iteration on subsets based on their order. The mapped values in a map can be accessed directly by their corresponding key using the bracket operator (. Maps are typically implemented as binary search trees.

Comments
  • If you can avoid it, I recommend not using containers as keys anywhere.
  • Are all your vectors size three? I have a feeling std::array<int, 3> might yield much faster comparisons than the generic vector code. Or possibly using simd instructions on a struct containing 3 ints (you could even put 4 and leave the last one to 0 since most instructions i know of operate on 128 bits)
  • Vectors always need to allocate dynamic memory once there are elements in them. If you know your vectors have exactly 3 elements, switch to arrays or tuples.
  • You are all missing the point. This is not very efficient code. It still shouldn't take 5 hours for one lookup.
  • if it takes 5 hours for that line, then maybe the problem is not really performance but a bug in your code. Can you provide a minimal reproducible example ?
  • Yes, I just tried your code and my code in my laptop and it just gives me the result instantly, but in our cluster, it just hangs... It's gonna drive me crazy I believe to find out what's going on here...
  • @AloneProgrammer Did you run the program on your cluster in a debugger? How do you know that the program hangs on the line you referred to? Couldn't there be some problem with a (parallel) file system, network, etc.?
  • Initialization part is not slow, it just takes a couple of seconds. The part that is really slow is: value = weights_table.at(xyz);.
  • @AloneProgrammer depends on what you call slow, a couple of seconds can be a very long time ;)
  • Yes, I compare it to couple of hours that my code stuck at this line value = weights_table.at(xyz);.
  • @AloneProgrammer Inserting elements as you do with keys of type std::vector and allocating the std::vector every time is extreeeemely slow!