Use existing object in vector or create new if not exists in C++

Question

Let's assume that I have a class named Store which contains products. Functions are inlined for simplicity.

class Store
{
public:
    Store(string name)
        : _name(name)
    {}

    string getName() const
    { return _name; };

    const std::vector<string> getProducts()
    { return _products; };

    void addProduct(const string& product)
    { _products.push_back(product); }

private:
    const string _name;
    std::vector<string> _products;
};

Then I have a two dimensional string array which contains store-product -pairs. Same store can be multiple times in array.

string storeListing[4][2] = {{"Lidl", "Meat"},
                             {"Walmart", "Milk"},
                             {"Lidl", "Milk"},
                             {"Walmart", "Biscuits"}};

Now I want to iterate through array, create Store-object for each store in array and add products of it to object. So I need to use existing Store-object or create a new if there is no any with correct name yet. What is a way to implement this? Currently I'm trying to use pointer and set it to relevant object, but I'm getting sometimes segmentation faults and sometimes other nasty problems when I modify code slightly. I guess I'm calling some undefined behavior here.

std::vector<Store> stores;
for (int i = 0; i < 4; ++i) {
    string storeName = storeListing[i][0];
    string productName = storeListing[i][1];

    Store* storePtr = nullptr;
    for (Store& store : stores) {
        if (store.getName() == storeName) {
            storePtr = &store;
        }
    }

    if (storePtr == nullptr) {
        Store newStore(storeName);
        stores.push_back(newStore);
        storePtr = &newStore;
    }

    storePtr->addProduct(productName);
}

Perhaps [`std::map`](http://en.cppreference.com/w/cpp/container/map) (or [`std::unordered_map`](http://en.cppreference.com/w/cpp/container/unordered_map)) would be more useful here? — Some programmer dude, Oct 23 '17 at 06:30

Jodocus · Answer 1 · 2017-10-23T06:46:39.367

Use a std::unordered_set<Store>, where the hash type is the string name of the store. Using a map-like type would lead to duplicated storage of the store name (one time as a key to the map and one time inside the Store object itself).

template <>
struct std::hash<Store> {
    using Store = argument_type;
    using result_type = std::size_t;
    result_type operator()(const argument_type& s) const noexcept {
       return result_type{ std::hash<std::string>{}(s._name) }();
    }
};

std::unordered_set<Store> stores;
for (int i = 0; i < 4; ++i) {
   string storeName = storeListing[i][0];
   string productName = storeListing[i][1];

   auto iter = stores.find(storeName);
   if(iter == stores.end()) iter = stores.emplace(storeName);
   iter->addProduct(productName);
}

Hafnernuss · Accepted Answer · 2017-10-23T08:26:28.483

Most likely, because you insert "Store" copies into your vector:

if (storePtr == nullptr) {
    Store newStore(storeName);   //create Store on stack
    stores.push_back(newStore);  //Make a COPY that is inserted into the vec
    storePtr = &newStore;       // And this is where it all goes wrong.
}

newStore goes out of scope at the end of the if and StorePtr is lost.

Try it with:

storePtr = stores.back();

Or make your vector a std::vector<Store*>.

And then:

if (storePtr == nullptr) {
Store * newStore = new Store(storeName);   //create Store on stack
stores.push_back(newStore);  //Make a COPY that is inserted into the vec
storePtr = newStore;       // And this is where it all goes wrong.
}

And of course, as the comments suggest, a std::map would be better suited here.

In short, std::map stores key-value pairs. The key would most likely be your store name, and the value the product.

Quick example:

std::map<std::string, std::string> myMap;
myMap["Lidl"] = "Milk";
myMap["Billa"] = "Butter";
//check if store is in map:
if(myMap.find("Billa") != myMap.end())
  ....

Note, you can of course use your Store object as value. To use it as key, you have to take care of a few things:

std::maps with user-defined types as key

For your specific example i would suggest you use a std::string as key, and a vector of Products as value.

score 0 · Answer 3 · answered Oct 23 '17 at 06:52

There are a few problems in your approach.

Problem 1:

Store has a const data member. This will make it impossible to reorder the vector of stores. That needs to be corrected.

Problem 2:

You need to point at the right Store after insertion. Here's one approach:

// decompose the problem:
// first step - get a pointer (iterator) to a mutable store *in the vector*
auto locate_or_new(std::vector<Store>& stores, std::string const& storeName)
-> std::vector<Store>::iterator
{
    auto iter = std::find_if(begin(stores), end(stores),
                             [&](Store& store)
                             {
                                 return store.getName() == storeName;
                             });
    if (iter == end(stores))
    {
        iter = stores.emplace(end(stores), storeName);
    }
    return iter;
}

//
// 2 - insert the product in terms of the above function.    
auto addProduct(std::vector<Store>& stores, std::string const& storeName, std::string const& productName)
-> std::vector<Store>::iterator
{
    auto istore = locate_or_new(stores, storeName);
    istore->addProduct(productName);
    return istore;
}

Note:

Since inserting objects into a vector can cause iterator invalidation, you will need to be careful to not hold references to objects inside the vector across sections of code that could create new stores.

Could you please elaborate the problem with const data member and vector? Do you mean that I should never use const data members if I plan to store objects of class in vector? — Paulus Limma, Oct 23 '17 at 08:16
@PaulusLimma yes - because when you extend the vector it is possible that objects will need to be moved. They can't be moved if they are immutable. — Richard Hodges, Oct 23 '17 at 08:24

score 0 · Answer 4 · answered Oct 23 '17 at 06:53

if (storePtr == nullptr) {
        Store newStore(storeName);
        stores.push_back(newStore);
        storePtr = &newStore;
    }

Once the if ends newStore is gone and you are left with dangling pointer storePtr. You could use an std::set<Store *> here

std::set<Store *> myset;
Store *c = new Store("store3");
std::set<Store *>::iterator iter = myset.find(c);
if(iter!=myset.end())
{
   (*iter)->addProduct("Product1");
}
else
{
   c->addProduct("Product1");
   myset.insert(c);
}

Nandee · Answer 5 · 2017-10-23T08:00:04.950

There is a solution using vectors and iterators. Dont forget to include the "algorithm" header!

std::vector<Store> stores;
for (int i = 0; i < 4; ++i) {
    string storeName = storeListing[i][0];
    string productName = storeListing[i][1];

    auto storeIter = std::find_if(stores.begin(), stores.end(), [storeName](Store store) -> bool {
        return store.getName() == storeName;
    }); //Find the store in the vector

    if (storeIter == stores.end()) //If the store doesn't exists
    {
        stores.push_back(Store(storeName)); //Add the store to the vector
        storeIter = prev(stores.end()); //Get the last element from the vector
    }
    Store* storePtr = &(*storeIter); //You can convert the iterator into a pointer if you really need it
    storeIter->addProduct(productName);
    //storePtr->addProduct(productName);
}

Use existing object in vector or create new if not exists in C++

5 Answers5