Is the Std::Set Iteration Order Always Ascending According to the C++ Specification

Is the std::set iteration order always ascending according to the C++ specification?

Per the C++ standard, iteration over the elements in an std::set proceeds in sorted order as determined by std::less or by the optional comparison predicate template argument.

(Also per the C++ standard, insertion, lookup and deletion take at most O(lg n) time, so balanced search trees are currently the only viable implementation choice for std::set, even though the use of red-black trees is not mandated by the standard.)

Does `std::set` sort elements in every case?

By its definition std::set is a sorted container. Its part of the standard. Having it sorted helps maintain that its a set rather than just an arbitrary collection.

Source: http://www.sgi.com/tech/stl/set.html

Is the order of iterating through std::map known (and guaranteed by the standard)?

Yes, that's guaranteed. Moreover, *begin() gives you the smallest and *rbegin() the largest element, as determined by the comparison operator, and two key values a and b for which the expression !compare(a,b) && !compare(b,a) is true are considered equal. The default comparison function is std::less<K>.

The ordering is not a lucky bonus feature, but rather, it is a fundamental aspect of the data structure, as the ordering is used to determine when two keys are the same (by the above rule) and to perform efficient lookup (essentially a binary search, which has logarithmic complexity in the number of elements).

Change the order of a std::set as a member attribute

Something like that?

class CustomObject{
public:
    CustomObject(int _x) : x(_x) {};
    int x;
};

struct cmpStruct {
    bool operator() (const CustomObject*  lhs, const CustomObject*  rhs) const
    {
        return lhs->x > rhs->x;
    }
};

int main(int argc, char* argv[])
{
    std::set<CustomObject*, cmpStruct> container;

    CustomObject a(10);
    CustomObject b(20);
    CustomObject c(5);

    container.insert(&a);
    container.insert(&b);
    container.insert(&c);

    for(auto co : container) {
        std::cout << co->x << std::endl;
    }
    return 0;
}

Output:

20
10
5

Vector of set insert elements

teams being a std::vector<...> supports random access via an index.

auto & team_i = teams[i]; (0 <= i < teams.size()), will give you an element of the vector. team_i is a reference to type std::set<std::list<std::string>>.

As a std::set<...> does not support random access via an index, you will need to access the elements via iterators (begin(), end() etc.), e.g.: auto set_it = team_i.begin();. *set_it will be of type std::list<std::string>.

Since std::list<...> also does not support random access via an index, again you will need to access it via iterators, e.g.: auto list_it = set_it->begin();. *list_it will be of type std::string.

This way it is possible to access every set in the vector, every list in each set, and every string in each list (after you have added them to the data structure).

However - using iterators with std::set and std::list is not as convenient as using indexed random access with std::vector. std::vector has additional benefits (simple and efficient implementation, continous memory block).

If you use std::vectors instead of std::set and std::list, vek will be defined as:

typedef std::vector<std::vector<std::vector<std::string>>> vek;

std::list being a linked list offers some benefits (like being able to add an element in O(1)). std::set guarentees that each value is present once.
But if you don't really need these features, you could make you code simpler (and often more efficient) if you use only std::vectors as your containers.

Note: if every set will ever contain only 1 list (of strings) you can consider to get rid of 1 level of the hirarchy, I.e. store the lists (or vectors as I suggested) directly as elements of the top-level vector.

---

UPDATE:

Since the question was changed, here's a short update:

1. In my answer above, ignore all the mentions of the std::list. So when you iterate on the set::set the elements are already std::strings.
2. The reason the names are not in the order you expect:
   std::set keeps the elements sorted, and when you iterate it you will get the elements by that sorting order. See the answer here: Is the std::set iteration order always ascending according to the C++ specification?. Your set contains std::strings and the default sort order for them is alphabetically.
   
   Using std::vector instead of std::set like I proposed above, will get you the result you wanted (std::vector is not sorted automatically).

If you want to try using only std::vector:

Change vek to:

typedef std::vector<std::vector<std::string>>vek;

And replace the usage of insert (to add an element to the set) with push_back to do the same for a vector.

Why would anyone use set instead of unordered_set?

When, for someone who wants to iterate over the items of the set, the order matters.

What is the underlying data structure of a STL set in C++?

You could implement a binary search tree by first defining a Node struct:

struct Node
{
  void *nodeData;
  Node *leftChild;
  Node *rightChild;
}

Then, you could define a root of the tree with another Node *rootNode;

The Wikipedia entry on Binary Search Tree has a pretty good example of how to implement an insert method, so I would also recommend checking that out.

In terms of duplicates, they are generally not allowed in sets, so you could either just discard that input, throw an exception, etc, depending on your specification.

How to ensure that a std::map is ordered?

You don't have to do anything. The map will be in ascending order according to the values of the key.

Internally, the map performs a comparison between keys to order its elements. By default, it uses std::less<KEY>, which is equivalent to bool operator<(int, int) for integers. For user defined types, you have to options:

1. Implement a bool operator<(const MyType&, const MyType&) implementing a strict weak ordering comparison between your user defined types. Use this if your type has a natural ordering

2. Provide a binary functor that implements strict weak ordering, which you can pass as the 3rd template parameter to the map. Use this if your type does not have a natural ordering, or if you want to build the map with an ordering different to that used by std::less<Key> via the bool operator<(...) from point 1.

What typically happens behind the scenes is that the map is implemented as a self-balancing binary tree, and the strict weak ordering is used to place new elements in the map, and to determine whether two elements are equal. As an aside, the same logic applies to std::set, where the key and value are one and the same.

How to sort set of coordinates in ascending order by distance from point ( x1,y1)?

std::set is an ordered container, and ordering happens upon insertion, depending on a sorting criteria which can be specified with a second template argument. So use a set with a predicate which returns true or false based on the distance to the reference point.

struct DistanceCompare
{
  DistanceCompare(const std::pair<float,float>& point) : point_(point) {} 
  bool operator()(const std::pair<float,float>& lhs, 
                  const std::pair<float,float>& rhs) const
  {
    return distance2(lhs) < distance2(rhs);
  };

 private:
  float distance2(const std::pair<float,float>& point) const
  {
    // calculate distance squared between point and point_
    const float x = point.first  - point_.first;
    const float y = point.second - point_.second;
    return x*x + y*y;

  }
  std::pair<float, float> point_;
};

....
std::pair<float,float> refPoint = ....;
DistanceCompare comp(refPoint);
std::set<std::pair<float, float>, DistanceCompare> pointSet(comp);

It is enough to compare the distance squared, thus avoiding calls to std::sqrt.

---

Related Topics