Problems with C++ Set Container

problems with c++ set container

std::set stores its values in a sorted binary tree, so it needs to know how to compare the values it holds. By default it uses std::less as a comparison function, which for un-specialized user defined types tries to call operator<. So, the easiest way to tell the set how to compare your objects is to define an operator< for your class:

template <class T, class S> 
class Property
{
public:
    pair<T,S> p;

    Property(T t, S s) { p = make_pair(t,s);}

    bool operator<(const Property<T,S>& rhs) const
    {
        return p < rhs.p;
    }
};

However, there are also other ways of telling std::set how to compare your type. One is to specialize the std::less template for your class:

namespace std {
template<typename T,typename S>
struct less<Property<T, S> >
{
    bool operator()(const Property<T, S>& lhs, const Property<T,S>& rhs) const
    {
        return lhs.p < rhs.p;
    }
};
}

Another is to replace the default comparison type with a function with the correct signature, or a class that has an operator() defined with the correct signature. This is where things start to get ugly.

// Comparison function
template<typename T, typename S>
bool property_less_function(const Property<T,S>& lhs, const Property<T,S>& rhs)
{
    return lhs.p < rhs.p;
}

// Comparison functor
template<typename T, typename S>
struct PropertyLess
{
    bool operator()(const Property<T,S>& lhs, const Property<T,S>& rhs) const
    {
        return lhs.p < rhs.p;
    }
};

int main()
{
    // Set using comparison function. 
    // Have to pass the function pointer in the constructor so it knows
    // which function to call. The syntax could be cleaned up with some
    // typedefs.
    std::set<Property<std::string, std::string>, 
        bool(*)(const Property<std::string, std::string>&, 
                const Property<std::string, std::string>&)> 
            set1(&property_less_function<std::string, std::string>);

    // Set using comparison functor. Don't have to pass a value for the functor
    // because it will be default constructed.
    std::set<Property<std::string, std::string>, PropertyLess<std::string, std::string> > set2;
}

Keep in mind that whatever less-than function you use, that function must define a strict weak ordering for your type.

Problem with C++ standard container not inserting new values

In this loop:

for(auto it : map)

the variable it is a copy of every element in map, so modifying it doesn't modify map.

If you want to modify the elements, you need to do:

for(auto &it : map)

so that it is a reference to every element in map.

Why not implement contains function in c++ Containers?

There is a good reason that containers do not share a "common (inherited) interface" (like in Java) and it is what makes the C++ generics so powerful. Why write code for every container when you can write it only once for all containers? This is one of the main principles the STL was built on.

If using containers relied on member functions from a common inherited interface you would have to write a find function for every container. That is wasteful and poor engineering. Good design says if you can write code in only one place you should because you only have to remove the bugs from that one place, and fixing a bug in one place fixes the bug everywhere.

So the philosophy behind the STL is to separate the algorithms from the containers so that you only have to write the algorithm once and it works for all containers. Once the algorithm is debugged, it is debugged for all containers.

A fly in that ointment is that some containers can make more efficient decisions due to their internal structure. For those containers a type specific function has been added which will take advantage of that efficiency.

But most functions should be separate from the containers. It is called decoupling and it reduces bugs while promoting code reuse, often much more so than polymorphism which is what libraries like Java containers use (a common inherited interface).

Why is the C++ STL set container's count() method thus named?

It's to make it consistent with other container classes, given that one of the great aspects of polymorphism is to be able to treat different classes with the same API.

It does actually return the count. The fact that the count can only be zero or one for a set does not change that aspect.

It's not fundamentally different to a collection object that only allows two things of each "value" at the same time. In that case, it would return the count of zero, one or two, but it's still a count, the same as with a set.

The relevant part of the standard that requires this is C++11 23.2.4 which talks about the associative containers set, multiset, map and multimap. Table 102 contains the requirements for these associative containers over and above the requirements for "regular" containers, and the bit for count is paraphrased below:

size_type a.count(k) - returns the number of elements with key equivalent to k. Complexity is log(a.size()) + a.count(k).

is_container trait fails on std::set SFINAE issue

Since std::set<T> only has one set of immutable iterators, there is only one version of begin() and end() which is declared to be const. That is, the definition of std::set<T> looks something like this (assuming it was declared in namespace std before):

template <typename T>
class std::set
{
public:
    class            iterator;
    typedef iterator const_iterator;
    ...
    const_iterator begin() const;
    const_iterator end() const;
    ...
};

The other containers have both a const and a non-const version of begin() and end() matching the signature you ask for. std::set doesn't have this. I'm not sure what the easiest work-around for this would be though.

That said, sizeof(char) is allowed to be sizeof(long). The easiest way to guarantee that the yes and no types have different size is to use references to arrays of different sizes for the same type, e.g.:

typedef char (&yes)[1];
typedef char (&no)[2];
...
enum { value = sizeof(some_expression) == sizeof(yes) };

value of set::find() if not found in container

auto a2 = s1.find(100);
cout << "find(100) : " << *a2 << endl;

Here you dereference (*a2) the end iterator. That is undefined behaviour - remember that s1.end() points to one past the last element and must not be dereferenced.

You're unlucky that you got a value from that dereference - it would be more convenient if your program crashed or otherwise reported the problem. But UB doesn't have to be diagnosed in any way.

You might have spotted the problem if you had run your program using Valgrind's memory checker (or your preferred equivalent). But there's a good chance that's unable to detect it (if the set has over-allocated, which is likely).

Set operation in c++(update existing value)

Key values of elements in a std::set are const for a good reason. Modifying them may destroy the order which is essential for a std::set.

Hence, the solution is to erase the iterator and insert a new one with key *it - sub. Please, note that std::set::erase() returns a new iterator which has to be used in your case to keep the while loop working properly.

#include<iostream>
#include<set>

template <typename T>
std::ostream& operator<<(std::ostream &out, const std::set<T> &values)
{
  const char *sep = "{ ";
  for (const T &value : values) { out << sep << value; sep = ", "; }
  return out << " }";
}

int main()
{
  std::set<int> test{ 11, 12, 13, 14, 15 };
  std::cout << "test: " << test << '\n';
  const int sub = 10;
  std::set<int>::iterator iter = test.begin();
  while (iter != test.end()) {
    const int value = *iter;
    iter = test.erase(iter);
    test.insert(value - sub);
  }
  std::cout << "test: " << test << '\n';
}

Output:

test: { 11, 12, 13, 14, 15 }
test: { 1, 2, 3, 4, 5 }

Live Demo on coliru

---

Changes on the std::set while iterating over it are not a problem in general but can cause subtle issues.

The most important fact is that all used iterators have to be kept intact or may not be used anymore. (That's why the current iterator of the erase element is assigned with the return value of std::set::erase() which is either an intact iterator or the end of set.)

Of course, elements can be inserted as well behind the current iterator. While this is not a problem concerning the std::set it may break the loop of my above example.

To demonstrate it, I changed the above sample a bit. Please, note that I added an additional counter to grant the termination of loop:

#include<iostream>
#include<set>

template <typename T>
std::ostream& operator<<(std::ostream &out, const std::set<T> &values)
{
  const char *sep = "{ ";
  for (const T &value : values) { out << sep << value; sep = ", "; }
  return out << " }";
}

int main()
{
  std::set<int> test{ 11, 12, 13, 14, 15 };
  std::cout << "test: " << test << '\n';
  const int add = 10;
  std::set<int>::iterator iter = test.begin();
  int n = 7;
  while (iter != test.end()) {
    if (n-- > 0) {
      const int value = *iter;
      iter = test.erase(iter);
      test.insert(value + add);
    } else ++iter;
  }
  std::cout << "test: " << test << '\n';
}

Output:

test: { 11, 12, 13, 14, 15 }
test: { 23, 24, 25, 31, 32 }

Live Demo on coliru

compiling error when erasing a STL std::set element by key

The problem is caused by the fact list::iterator does not have a comparison defined. The value type of an std::set requires a strict weak ordering.

A vector supports random access iterators, which have an ordering. A list is only required to support bidirectional iterators, which do not have an ordering (of course, an implementation is free to support random access iterators for lists as well, so on some compilers it might work).

In order to fix it, you would have to write a comparison function yourself. The problem is that the only way to detect the order of two iterators in a list would be to walk from one to the other, which requires linear time.

---

Related Topics