Order in std::set and difference to std::unordered_set

Question

I expected the order of std::set to be consistent like std::list or std::vector, only that a value will not be appended a second time. MSVC 110 prooved me wrong. I expected the following code the yield the result shown below, which is the case when running the code on ideone (http://ideone.com/e47GwQ) (not sure which compiler and version they use, though).

#include <iostream>
#include <set>

template <typename C>
int insert_get_index(C& container, typename C::value_type value)
{
    typename C::iterator it = container.insert(value).first;
    return std::distance(container.begin(), it);
}

int main()
{
    int a = 3, b = 1, c = 9;
    std::set<int*> set;

    std::cout << insert_get_index(set, &a) << "\n";
    std::cout << insert_get_index(set, &b) << "\n";
    std::cout << insert_get_index(set, &c) << "\n";
    std::cout << insert_get_index(set, &a) << "\n";
    std::cout << insert_get_index(set, &b) << "\n";
    std::cout << insert_get_index(set, &c) << "\n";

    return 0;
}

0
1
2
0
1
2

Running the code in Visual Studio 2012 yields what you can see below.

0
0
2
1
0
2

Now, why did I thin that std::set behaves like described above? Because cplusplus.com states

Sets are containers that store unique elements following a specific order.

and additionally, there is std::unordered_set.

1. Did I understand the documentation incorrectly and std::set is instead value ordered?
2. And what's std::unordered_set for then?
3. Is there a different standard library container that fulfils my requirements?

Answer 1

Did I understand the documentation incorrectly and std::set is instead value ordered?

It is indeed ordered by value. Unless you provide your own comparator, they are ordered by comparing them using std::less. For most types, this uses <. For pointers (which can't generally be compared with < in a well-defined way), it defines an unspecified but consistent ordering. (On common platforms with a linear address space, this would probably simply compare address values; but you can't rely on that).

So in this case, storing pointers to local variables, it depends on where the compiler chooses to allocate storage for each variable, which could vary from compiler to compiler.

And what's std::unordered_set for then?

When you don't care about the order, this can give better performance. It uses a hash table to give constant-time lookup, while set uses a search tree (or something similar) to give logarithmic-time lookup.

Is there a different standard library container that fulfils my requirements?

No, there's no container that both maintains insertion order, and provides fast value-based lookup. Depending on your exact requirements, you might use vector to maintain the order, and put up with a linear-time lookup using std::find; or you might use two containers, one to maintain the order and one to provide fast lookup, with careful logic to keep them consistent.