gsamaras gsamaras - 9 days ago 7
C++ Question

How to avoid constructing a new string?

I have a 1D char vector emulating a 2D vector (this is a requirement). This vector is 000111 and it's equivalent to vector[0] = 000 and vector[1] = 111 of a 2D. So it has two strings, all of same length (3 in this case). I want to set every string as a key in a

std::unordered_map
, so I am doing:

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>

int main ()
{
std::unordered_map<std::string, int> mymap;
std::vector<char> keys(2 * 3); // 2 keys, each one of length 3
for(int i = 0; i < 2; ++i)
{
for(int j = 0; j < 3; ++j)
{
keys[j + i * 3] = (i) ? '1' : '0';
}
}
// keys = 000111

for(int i = 0; i < 2; ++i)
{
mymap[std::string(keys.begin() + i * 3, keys.begin() + (i + 1) * 3)] = i;
}

for (auto& x: mymap) {
std::cout << x.first << ": " << x.second << std::endl;
}

/*
Output:
111: 1
000: 0
*/

return 0;
}


which makes me unhappy because I have to construct a new string and then insert that to the map. It would be nice if I could just emplace it or something in one step. Can I?

Answer

I think this is a drop-in replacement for a c++17 string_view. A string_view doesn't own any of the strings, so const-ness can be a problem (see the const-cast when inserting into the map)

The only changes that nedded to be made was

  1. const-cast, you'll have to solve this.
  2. the type of the multimap.
  3. Note the using statement just at the #endif

I just bolted a class, a hash-struct(in std::!) and a few overloads onto your code.

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
#ifdef HAS_STRING_VIEW
#include <string_view>
#else

class lps_noz_view{
public:
    lps_noz_view() = delete;
    lps_noz_view(const char* start, size_t size):start(start), stop(start + size){}
    lps_noz_view(const lps_noz_view& ) = default;
    lps_noz_view(lps_noz_view&& ) = default;
    const char* begin(){  return start;}
    const char* end(){  return stop;}
    const char* begin() const{  return start;}
    const char* end() const{  return stop;}
    std::string to_string() const{  return std::string(start, stop);}
private:
    const char* start;
    const char* stop;
};

bool operator < (const lps_noz_view& lhs, const lps_noz_view& rhs){
    return lhs.to_string() < rhs.to_string();  
    // or use strncmp to avoid creating strings =)
}

bool operator == (const lps_noz_view& lhs, const lps_noz_view& rhs){
    return lhs.to_string() == rhs.to_string();  
    // strncmp
}
std::ostream& operator << (std::ostream& os, const lps_noz_view& rhs){
    return os << rhs.to_string();
}

namespace std{
template<>
struct hash<lps_noz_view>
{
    using argument_type = lps_noz_view;
    using result_type = size_t;
    size_t operator()(const lps_noz_view& arg) const{
        return std::hash<std::string>()(std::string(arg.begin(), arg.end()));
    }
};
};

using string_view = lps_noz_view;
#endif
// 
int main ()
{
  std::unordered_map<string_view, int> mymap;
  std::vector<char> keys(2 * 3); // 2 keys, each one of length 3
  for(int i = 0; i < 2; ++i)
  {
    for(int j = 0; j < 3; ++j)
    {
      keys[j + i * 3] = (i) ? '1' : '0';
    }
  }
  // keys = 000111

  for(int i = 0; i < 2; ++i)
  {
    mymap[string_view(const_cast<const char*>(&(*keys.begin()) + i * 3), 
            (i + 1) * 3)] = i;
  }

  for (auto& x: mymap) {
    std::cout << x.first << ": " << x.second << std::endl;
  }

  /*
  Output:
  111: 1
  000: 0
  */

  return 0;
}