Это мой код
map<string,int> persons;
persons["B"] = 123;
persons["A"] = 321;
for(map<string,int>::iterator i = persons.begin();
i!=persons.end();
++i)
{
cout<< (*i).first << ":"<<(*i).second<<endl;
}
Ожидаемый результат:
B:123
A:321
Но вывод, который он дает:
A:321
B:123
Я хочу, чтобы он поддерживал порядок, в котором ключи и значения были вставлены в map<string,int>.
Возможно ли это? Или я должен использовать другую структуру данных STL? Какой?
Нет стандартного контейнера, который делает то, что вы хотите. Очевидным контейнером для использования, если вы хотите сохранить порядок вставки, является вектор. Если вам также нужно искать строку, используйте вектор AND map. В общем случае карта будет иметь строку с векторным индексом, но поскольку ваши данные уже являются целыми числами, вы можете просто их дублировать, в зависимости от вашего варианта использования.
Как сказал Маттие в другом ответе, библиотека Boost.MultiIndex кажется правильным выбором для того, что вы хотите. Тем не менее, эта библиотека может быть немного сложной для использования в начале, особенно если у вас нет большого опыта работы с С++. Вот как вы могли бы использовать библиотеку для решения точной проблемы в коде вашего вопроса:
struct person {
std::string name;
int id;
person(std::string const & name, int id)
: name(name), id(id) {
}
};
int main() {
using namespace::boost::multi_index;
using namespace std;
// define a multi_index_container with a list-like index and an ordered index
typedef multi_index_container<
person, // The type of the elements stored
indexed_by< // The indices that our container will support
sequenced<>, // list-like index
ordered_unique<member<person, string,
&person::name> > // map-like index (sorted by name)
>
> person_container;
// Create our container and add some people
person_container persons;
persons.push_back(person("B", 123));
persons.push_back(person("C", 224));
persons.push_back(person("A", 321));
// Typedefs for the sequence index and the ordered index
enum { Seq, Ord };
typedef person_container::nth_index<Seq>::type persons_seq_index;
typedef person_container::nth_index<Ord>::type persons_ord_index;
// Let test the sequence index
persons_seq_index & seq_index = persons.get<Seq>();
for(persons_seq_index::iterator it = seq_index.begin(),
e = seq_index.end(); it != e; ++it)
cout << it->name << ":"<< it->id << endl;
cout << "\n";
// And now the ordered index
persons_ord_index & ord_index = persons.get<Ord>();
for(persons_ord_index::iterator it = ord_index.begin(),
e = ord_index.end(); it != e; ++it)
cout << it->name << ":"<< it->id << endl;
cout << "\n";
// Thanks to the ordered index we have fast lookup by name:
std::cout << "The id of B is: " << ord_index.find("B")->id << "\n";
}
Что производит следующий вывод:
B:123
C:224
A:321
A:321
B:123
C:224
The id of B is: 123
Карта определенно не подходит для вас:
"Внутренне элементы на карте сортируются от нижнего к более высокому значению ключа после определенного строгого критерия слабого порядка, установленного при построении".
Цитата взята из здесь.
К сожалению, в STL нет неупорядоченного ассоциативного контейнера, поэтому либо используйте неассоциативный, например vector, либо напишите свой собственный: - (
карты и наборы должны налагать строгие слабые порядки на данные. Strick слабое упорядочение утверждает, что никакие записи equavalent (отличается от того, что они равны).
Вам необходимо предоставить функтор, который может использовать карта/набор для выполнения a<b. С помощью этого функтора map/set сортирует свои элементы (в STL из GCC используется красно-черное дерево). Он определяет погоду, два предмета равны, если !a<b && !b<a - испытание на равнозначность.
Функтор выглядит следующим образом:
template <class T>
struct less : binary_function<T,T,bool> {
bool operator() (const T& a, const T& b) const {
return a < b;
}
};
Если вы можете предоставить функцию, которая сообщает STL, как заказывать вещи, карта и набор могут делать то, что вы хотите. Например
template<typename T>
struct ItemHolder
{
int insertCount;
T item;
};
Затем вы можете легко написать функтор для заказа с помощью insertCount. Если ваша реализация использует красно-черные деревья, ваши базовые данные останутся сбалансированными - однако вы получите много перебалансировки, поскольку ваши данные будут создаваться на основе инкрементного упорядочения (против Random) - и в этом случае a list с push_back будет лучше. Однако вы не можете получить доступ к данным по ключу так же быстро, как с помощью карты/набора.
Если вы хотите сортировать по строке - предоставить функтору поиск по строке, используя insertCount, вы можете работать в обратном порядке. Если вы хотите выполнить поиск, вы можете иметь две карты.
map<insertcount, string> x; // auxhilary key
map<string, item> y; //primary key
Я часто использую эту стратегию, но я никогда не помещал ее в код, который выполняется часто. Я рассматриваю boost:: bimap.
Помимо рекомендации Neil для комбинированной карты + +, если вам нужно как сохранить порядок вставки, так и возможность поиска по ключу, вы также можете рассмотреть возможность использования дополнительных библиотек с несколькими индексами, которые предоставляют контейнеры, адресуемые более чем одним способом.
Ну, нет контейнера STL, который действительно делает то, что вы пожелаете, но есть возможности.
1. STL
По умолчанию используйте vector. Здесь это означало бы:
struct Entry { std::string name; int it; };
typedef std::vector<Entry> container_type;
Если вы хотите искать по строке, у вас всегда есть алгоритм find.
class ByName: std::unary_function<Entry,bool>
{
public:
ByName(const std::string& name): m_name(name) {}
bool operator()(const Entry& entry) const { return entry.name == m_name; }
private:
std::string m_name;
};
// Use like this:
container_type myContainer;
container_type::iterator it =
std::find(myContainer.begin(), myContainer.end(), ByName("A"));
2. Boost.MultiIndex
Это кажется излишним, но вы всегда можете проверить его здесь.
Он позволяет создавать ОДИН контейнер для хранения, доступный через различные индексы различных стилей, которые поддерживаются для вас (почти) магически.
Вместо того, чтобы использовать один контейнер (std::map) для ссылки на контейнер хранения (std::vector) со всеми проблемами синхронизации, которые он вызывает... вам лучше использовать Boost.
Используйте вектор. Это дает вам полный контроль над заказом.
Для сохранения всех ограничений временной сложности вам нужен map + list:
struct Entry
{
string key;
int val;
};
typedef list<Entry> MyList;
typedef MyList::iterator Iter;
typedef map<string, Iter> MyMap;
MyList l;
MyMap m;
int find(string key)
{
Iter it = m[key]; // O(log n)
Entry e = *it;
return e.val;
}
void put(string key, int val)
{
Entry e;
e.key = key;
e.val = val;
Iter it = l.insert(l.end(), e); // O(1)
m[key] = it; // O(log n)
}
void erase(string key)
{
Iter it = m[key]; // O(log n)
l.erase(it); // O(1)
m.erase(key); // O(log n)
}
void printAll()
{
for (Iter it = l.begin(); it != l.end(); it++)
{
cout<< it->key << ":"<< it->val << endl;
}
}
Enjoy
У меня была такая же проблема каждый раз в то время, и вот мое решение: https://github.com/nlohmann/fifo_map. Это решение только для заголовков С++ 11 и может использоваться как замена для std::map.
В вашем примере его можно использовать следующим образом:
#include "fifo_map.hpp"
#include <string>
#include <iostream>
using nlohmann::fifo_map;
int main()
{
fifo_map<std::string,int> persons;
persons["B"] = 123;
persons["A"] = 321;
for(fifo_map<std::string,int>::iterator i = persons.begin();
i!=persons.end();
++i)
{
std::cout<< (*i).first << ":"<<(*i).second << std::endl;
}
}
Вывод затем
B:123
A:321
Существует std:: unordered_map, который вы можете проверить. С первого взгляда похоже, что это может решить вашу проблему.
Я также думаю, что карта - это не путь. Клавиши на карте образуют набор; один ключ может появиться только один раз. Во время вставки на карте карта должна искать ключ, чтобы убедиться, что он не существует или обновить значение этого ключа. Для этого важно (с точки зрения производительности), чтобы ключи и, следовательно, записи, имели какой-то порядок. Поскольку такая карта с упорядочением вставки будет крайне неэффективной при вставках и извлечении записей.
Еще одна проблема заключается в том, что вы используете один и тот же ключ дважды; должна ли быть сохранена первая или последняя запись и должна ли она обновлять порядок вставки или нет?
Поэтому я предлагаю вам пойти с предложением Neils, вектором для вставки-времени и Map для поиска по ключевым словам.
Да, контейнер карты не для вас.
Как вы просили, вместо этого вам нужен следующий код:
struct myClass {
std::string stringValue;
int intValue;
myClass( const std::string& sVal, const int& iVal ):
stringValue( sVal ),
intValue( iVal) {}
};
std::vector<myClass> persons;
persons.push_back( myClass( "B", 123 ));
persons.push_back( myClass( "A", 321 ));
for(std::vector<myClass>::iterator i = persons.begin();
i!=persons.end();
++i)
{
std::cout << (*i).stringValue << ":" << (*i).intValue << std::endl;
}
Здесь вывод не сортируется, как ожидалось.
Я проголосовал бы за typedef std::vector< std::pair< std::string, int > > UnsortedMap;
Назначение выглядит несколько иначе, но ваш цикл остается таким же, как сейчас.
Карта упорядоченная коллекция (второй параметр в шаблоне является функтором порядка), как установлено. Если вы хотите постить элементы в этих секвенциях в качестве pushd, вы должны использовать deque или list или vector.
Чтобы делать то, что они делают, и быть эффективными на нем, карты используют хэш-таблицы и сортировку. Таким образом, вы бы использовали карту, если вы готовы отказаться от памяти о порядке вставки, чтобы получить удобство и производительность при поиске по клавишам.
Если вам нужен заказ на вставку, одним из способов было бы создать новый тип, который связывает значение, которое вы храните, с порядком, в котором вы его храните (вам нужно будет написать код для отслеживания заказа), Затем вы использовали бы карту строки для этого нового типа для хранения. Когда вы выполняете поиск с помощью ключа, вы также можете получить порядок вставки, а затем отсортировать свои значения на основе порядка вставки.
Еще одна вещь: если вы используете карту, помните о том, что тестирование, если люди [ "C" ] существуют (после того, как вы только вставили A и B), фактически введет пару значений ключа в ваш карта.
Используйте карту вместе с вектором итераторов при вставке в Map. (Итераторы карт гарантированно не признаются недействительными)
В приведенном ниже коде я использую Set установить myset; vector:: iterator > vec;
void printNonDuplicates() { vector:: iterator > :: iterator vecIter; for (vecIter = vec.begin(); vecIter!= vec.end(); vecIter ++) { соиЬ < < (* vecIter) → c_str() <
void insertSet (строка str) { Пара:: итератор, bool > ret; ret = myset.insert(str); если (ret.second) vec.push_back (ret.first); }
`` struct Compare: public binary_function { bool operator() (int a, int b) {return true;} };
используйте это, чтобы получить все элементы карты в обратном порядке, в которые вы ввели (т.е. первый введенный элемент будет последним, а последний введенный элемент будет первым). Не так хорошо, как тот же порядок, но он может служить вашей цели с небольшим неудобством.
Вместо карты вы можете использовать парную функцию с вектором! например:
vector<::pair<unsigned,string>> myvec;
myvec.push_back(::pair<unsigned,string>(1,"a"));
myvec.push_back(::pair<unsigned,string>(5,"b"));
myvec.push_back(::pair<unsigned,string>(3,"aa"));`
Вывод:
myvec[0]=(1,"a"); myvec[1]=(5,"b"); myvec[2]=(3,"aa");
или другой ex:
vector<::pair<string,unsigned>> myvec2;
myvec2.push_back(::pair<string,unsigned>("aa",1));
myvec2.push_back(::pair<string,unsigned>("a",3));
myvec2.push_back(::pair<string,unsigned>("ab",2));
Выход: myvec2[0]=("aa",1); myvec2[1]=("a",3); myvec2[2]=("ab",2);
Надеюсь, это поможет кому-то еще в будущем, кто искал не отсортированные карты, такие как я!