в итоге порядок хранение элементов в контейнере map меняется, они хранятся в порядке:
[0] "Запись 1", new MyObj( 0 )
[1] "Запись 16", new MyObj( 2 )
[2] "Запись 2", new MyObj( 1 )
а как сделать чтобы порядок был по мере поступления а не по алфавиту? чтобы порядок хранения был:
[0] "Запись 1", new MyObj( 0 )
[1] "Запись 2", new MyObj( 1 )
[2] "Запись 16", new MyObj( 2 )
Re: std::map изменение порядка добавление элементов
Здравствуйте, emergen, Вы писали:
E>[0] "Запись 1", new MyObj( 0 ) E>[1] "Запись 16", new MyObj( 2 ) E>[2] "Запись 2", new MyObj( 1 )
E>а как сделать чтобы порядок был по мере поступления а не по алфавиту? чтобы порядок хранения был: E>[0] "Запись 1", new MyObj( 0 ) E>[1] "Запись 2", new MyObj( 1 ) E>[2] "Запись 16", new MyObj( 2 )
map — это ассоциативный контейнер, элементы которого упорядочены по возрастанию значений ключа. Порядок вставки элементов неважен.
Если все, что тебе нужно, это сохранение порядка добавления элементов в конец, то тебе нужен list. Можно, конечно, применить и вектор, но зачем?
Впрочем, предполагаю, что в какой-то момент тебе понадобится, чтобы выпонлялось условие "Запись 16" > "Запись 2".
Тут понадобится собственный предикат сортировки.
Здравствуйте, emergen, Вы писали:
E>добавляю в std::map поэлементно: E>... E>в итоге порядок хранение элементов в контейнере map меняется, они хранятся в порядке: E>... E>а как сделать чтобы порядок был по мере поступления а не по алфавиту? чтобы порядок хранения был:
Если нужен и быстрый доступ по ключу и доступ в порядке поступления и ещё какой-нибудь индекс — тогда смотри Boost.MultiIndex.
Re[2]: std::map изменение порядка добавление элементов
Здравствуйте, landerhigh, Вы писали:
L>map — это ассоциативный контейнер, элементы которого упорядочены по возрастанию значений ключа. Порядок вставки элементов неважен. L>Если все, что тебе нужно, это сохранение порядка добавления элементов в конец, то тебе нужен list. Можно, конечно, применить и вектор, но зачем?
Как зачем? Произвольный доступ, дружественность к кэшу и т.п. Хотя, учитывая характер вопроса, топик-стартеру это ещё фиолетово.
Re: std::map изменение порядка добавление элементов
Здравствуйте, emergen, Вы писали:
E>а как сделать чтобы порядок был по мере поступления а не по алфавиту? чтобы порядок хранения был: E>[0] "Запись 1", new MyObj( 0 ) E>[1] "Запись 2", new MyObj( 1 ) E>[2] "Запись 16", new MyObj( 2 )
Навскидку:
1) Отказаться от ключей-строк в пользу ключей-чисел; например, парсить "Запись ([0-9]+)" и приводить к числу (если строки единообразны). Заодно, сильно выиграешь и в производительности, и в нагрузке на память. А возможно, что ещё и сможешь использовать вектор вместо мапа. (Рекомендую boost::ptr_vector)
namespace naturalsort {
template<class I, class J>
int sign_compare(I i, I iend, J j, J jend)
{
while(i != iend && j != jend)
{
if(isdigit(*i) && isdigit(*j)) // если встретились числа с обеих сторон
{
// в надежде на то, что long long будет достаточно для сопоставления серий цифр
// и наплевав на проблемы с не-европейскими десятичными цифрами (арабскими и китайскими)long long x = 0, m = 0; while(i != iend && isdigit(*i)) { ++m; x = x*10 + (*i++) - '0'; }
long long y = 0, n = 0; while(j != jend && isdigit(*j)) { ++n; y = y*10 + (*j++) - '0'; }
if(x != y) return x<y ? -1 : 1; // сперва смотрим на неравенство чисел ( '789' < '1234' )if(m != n) return m<n ? -1 : 1; // если числа равны, смотрим на неравенство длин ( '123' < '0000123' )
}
else
{
if(*i != *j) return *i < *j ? -1 : 1;
i++; j++;
}
}
// общие части строк равны, смотрим на оставшийся хвост - у кого он есть, та строка длиннее, а значит, "больше"return (i != iend) ? 1 : (j != jend) ? -1 : 0;
}
template<class I, class J>
bool less_compare(I i, I iend, J j, J jend) { return sign_compare(i,iend,j,jend) < 0; }
struct comparator
{
template<class Container>
bool operator()(Container const& lhs, Container const& rhs) const {
return less_compare(std::begin(lhs), std::end(lhs), std::begin(rhs), std::end(rhs));
}
};
}//namespace naturalsort
..... std::map<std::string, std::shared_ptr<MyObj>, naturalsort::comparator> buf .....
Перекуём баги на фичи!
Re[2]: std::map изменение порядка добавление элементов
Чтобы действовать аккуратнее, и не париться о сверхдлинных числах, — нужно предположить, что итераторы там — честные Forward, а не просто Input.
template<class I, class J>
int compare_numbers(I i, I iend, J j, J jend) // в предположении, что оба диапазона содержат только цифры
{
ptrdiff_t m = std::distance(i,iend);
ptrdiff_t n = std::distance(j,jend);
int const mn = m>n ? 1 : m<n ? -1 : 0; // запомним на будущее, кто был длиннее
// если m != n, то нужно смотреть на содержимое старших разрядов; должны быть нулиfor( ; m > n; ++i, --m ) if(*i != '0') return 1; // длиннее был первый, и там оказался ненулевой разрядfor( ; n > m; ++j, --n ) if(*j != '0') return -1; // ненулевой разряд оказался во втором диапазоне
// теперь длины диапазонов равны, и мы можем сравнить лексикографическиfor( ; m > 0; ++i, ++j, --m, --n )
{
if(*i > *j) return 1;
if(*i < *j) return -1;
}
// оказалось, что числа равны, возвращаем более слабый признак - длины чисел с ведущими нулямиreturn mn;
}
template<class I, class J>
int compare_strings(I i, I iend, J j, J jend)
{
while(i != iend && j != jend)
{
if(isdigit(*i) && isdigit(*j))
{
I inext = find_if(i, iend, is_not_digit);
J jnext = find_if(j, jend, is_not_digit);
int c = compare_numbers(i, inext, j, jnext);
if(c) return c;
i = inext; j = jnext;
}
else
{
if(*i > *j) return 1;
if(*i < *j) return -1;
++i; ++j;
}
}
}