C++ STL映射,我不希望它排序!

正如Matthieu在另一个回答中所说的 Boost.MultiIndex library

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's 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

引自 here .

vector ,或自己写:-(

我偶尔也会遇到同样的问题,以下是我的解决方案: https://github.com/nlohmann/fifo_map . 这是一个仅限页眉的C++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

除了尼尔的一个组合向量+映射的建议,如果你需要保持插入顺序和按关键字搜索的能力,你也可以考虑使用Boost多索引库,它提供了多个方法可寻址的容器。

地图和集合旨在对数据施加严格的弱排序。Strick弱排序坚持认为没有条目是 equavalent (不同于平等)。

您需要提供映射/集合可用于执行的函子 a<b . 使用此函子,映射/集合对其项进行排序(在GCC的STL中,它使用红黑树)。它决定两个项目是否相等,如果 !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;
};

red-black trees 您的底层数据将保持平衡——然而,您将得到大量的重新平衡,因为您的数据将基于增量排序(与随机排序相比)生成——在本例中 list push_back 那就更好了。但是,您不能像使用地图/集合那样快速地通过键访问数据。

map<insertcount, string> x; // auxhilary key
map<string, item> y; //primary key

我经常使用这个策略——但是我从来没有将它放在经常运行的代码中。我在考虑 boost::bimap .

嗯,没有一个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

here

它允许您创建一个存储容器,可通过各种样式的各种索引访问,所有这些都(几乎)神奇地为您维护。

而不是使用一个容器( std::map )引用存储容器的步骤( std::vector

使用向量。它可以让您完全控制订购。

要保留所有时间复杂性约束,您需要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;
   }
}

享受

std::vector<std::pair<T, U> > unsorted_map;

我也认为地图不是一条好路。地图中的键形成一组;单个键只能出现一次。在地图中插入期间,地图必须搜索该键,以确保该键不存在或更新该键的值。对于这一点,重要的是(性能方面的)键以及条目具有某种排序。因此,具有插入顺序的映射在插入和检索条目时效率极低。

另一个问题是,如果使用同一个键两次;是否应保留第一个或最后一个条目,是否应更新插入顺序?

因此,我建议您使用Neils建议,一个用于插入时间排序的向量和一个用于基于键的搜索的映射。

如您所问,您需要以下代码:

   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;

分配看起来有点不同,但您的循环仍与现在完全相同。

为了做他们所做的事情并在这方面高效,地图使用哈希表和排序。因此,如果您愿意放弃插入顺序的内存,以获得按键查找的便利性和性能,则可以使用映射。

如果需要存储插入顺序,一种方法是创建一个新类型,将存储的值与存储顺序配对(需要编写代码来跟踪顺序)。然后,您将使用字符串映射到此新类型进行存储。使用键执行查找时,还可以检索插入顺序,然后根据插入顺序对值进行排序。

还有一件事:如果您正在使用一个映射,请注意这样一个事实:测试persons[“C”]是否存在(在您只插入了a和B之后),实际上会在映射中插入一个键值对。

在地图中插入时,使用地图和迭代器向量(保证映射迭代器不会失效)

在下面的代码中,我使用Set 向量::迭代器>vec;

无效打印非重复(){ 向量::迭代器>::迭代器向量器; for(vecIter=vec.begin();维克特=vec.end();vecIter++){ 库特<<(*vecIter)——>c_str()<

void insertSet(字符串str){ ret=myset.insert(str); 向量向后推(返回第一);

``结构比较:公共二进制函数{ 布尔运算符()(int a,int b){返回真;} };

使用此选项可按与输入相反的顺序获取地图的所有元素(即:第一个输入的元素将是最后一个,最后一个输入的元素将是第一个)。虽然不如同一订单好,但可能会给您带来一些不便。

您可以使用带有向量的pair函数来代替map! 前任:

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");

或另一个例子:

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);

希望这可以帮助其他人在未来谁是寻找非排序的地图像我一样!

有 std::unordered_map 你可以去看看。从第一个角度看,它似乎可以解决您的问题。

如果您不想使用Boost::multi_index,我在这里提供了一个概念验证类模板供您查看:

https://codereview.stackexchange.com/questions/233157/wrapper-class-template-for-stdmap-stdlist-to-provide-a-sequencedmap-which

使用std::map和std::list,后者使用指针来维护顺序。