Как получить точное положение элемента в наборе?

Question

У меня есть std::set<std::string>, и я хочу узнать точное положение элемента в наборе после вставки.

Я пробовал с std::distance, но безуспешно:

#include <iostream>
#include <string>
#include <set>
#include <iterator>

using namespace std;

int main (int argc, char const *argv[])
{

    string array[] = { "zero", "one", "one", "zero", "two", "three", "zero" };
    set<string> numbers;
    for(size_t i = 0; i < 7; ++i)
    {
        int dist = distance(numbers.begin(), numbers.insert(array[i]).first);
        cout << array[i] << "\t" << dist << endl;
    }
    return 0;
}

выводов:

zero    0
one     0
one     0
zero    1
two     1
three   1
zero    3

Вместо этого я ожидал этого:

zero    0
one     1
one     1
zero    0
two     2
three   3
zero    0

Есть идеи?

Answer 1

Они сортируются лексикографически (в основном по алфавиту). Сравнением по умолчанию для std::set<T> является std::less<T>, что в свою очередь вызывает operator<.

Answer 2

Как уже говорилось, набор обычно реализуется с помощью своего рода дерева, которое, в свою очередь, хранит отсортированные данные, а не в том порядке, в котором вы их вставили (что позволяет вставлять и т. Д. В O (logN)).Если вы хотите получить желаемый эффект, вы можете использовать любой последовательный контейнер - vector, deque или list

Answer 3

Во-первых, строки сортируются лексикографически, а не по тем цифрам, которые они обозначают на английском языке. Во-вторых, для каждого элемента код проверяет текущее размещение в наборе до того, как набор будет полностью обновлен всеми элементами.

Приветствия и hth.,